PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
tidbitmap.c File Reference
#include "postgres.h"
#include <limits.h>
#include "access/htup_details.h"
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "lib/simplehash.h"
Include dependency graph for tidbitmap.c:

Go to the source code of this file.

Data Structures

struct  PagetableEntry
 
struct  TIDBitmap
 
struct  TBMIterator
 

Macros

#define MAX_TUPLES_PER_PAGE   MaxHeapTuplesPerPage
 
#define PAGES_PER_CHUNK   (BLCKSZ / 32)
 
#define WORDNUM(x)   ((x) / BITS_PER_BITMAPWORD)
 
#define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
 
#define WORDS_PER_PAGE   ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)
 
#define WORDS_PER_CHUNK   ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
 
#define SH_PREFIX   pagetable
 
#define SH_ELEMENT_TYPE   PagetableEntry
 
#define SH_KEY_TYPE   BlockNumber
 
#define SH_KEY   blockno
 
#define SH_HASH_KEY(tb, key)   hash_blockno(key)
 
#define SH_EQUAL(tb, a, b)   a == b
 
#define SH_SCOPE   static inline
 
#define SH_DEFINE
 
#define SH_DECLARE
 

Typedefs

typedef struct PagetableEntry PagetableEntry
 

Enumerations

enum  TBMStatus { TBM_EMPTY, TBM_ONE_PAGE, TBM_HASH }
 

Functions

static void tbm_union_page (TIDBitmap *a, const PagetableEntry *bpage)
 
static bool tbm_intersect_page (TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
 
static const PagetableEntrytbm_find_pageentry (const TIDBitmap *tbm, BlockNumber pageno)
 
static PagetableEntrytbm_get_pageentry (TIDBitmap *tbm, BlockNumber pageno)
 
static bool tbm_page_is_lossy (const TIDBitmap *tbm, BlockNumber pageno)
 
static void tbm_mark_page_lossy (TIDBitmap *tbm, BlockNumber pageno)
 
static void tbm_lossify (TIDBitmap *tbm)
 
static int tbm_comparator (const void *left, const void *right)
 
static uint32 hash_blockno (BlockNumber b)
 
TIDBitmaptbm_create (long maxbytes)
 
static void tbm_create_pagetable (TIDBitmap *tbm)
 
void tbm_free (TIDBitmap *tbm)
 
void tbm_add_tuples (TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
 
void tbm_add_page (TIDBitmap *tbm, BlockNumber pageno)
 
void tbm_union (TIDBitmap *a, const TIDBitmap *b)
 
void tbm_intersect (TIDBitmap *a, const TIDBitmap *b)
 
bool tbm_is_empty (const TIDBitmap *tbm)
 
TBMIteratortbm_begin_iterate (TIDBitmap *tbm)
 
TBMIterateResulttbm_iterate (TBMIterator *iterator)
 
void tbm_end_iterate (TBMIterator *iterator)
 

Macro Definition Documentation

#define BITNUM (   x)    ((x) % BITS_PER_BITMAPWORD)

Definition at line 75 of file tidbitmap.c.

Referenced by tbm_add_tuples(), tbm_iterate(), tbm_mark_page_lossy(), and tbm_page_is_lossy().

#define MAX_TUPLES_PER_PAGE   MaxHeapTuplesPerPage

Definition at line 53 of file tidbitmap.c.

Referenced by tbm_add_tuples(), and tbm_begin_iterate().

#define PAGES_PER_CHUNK   (BLCKSZ / 32)

Definition at line 70 of file tidbitmap.c.

Referenced by tbm_iterate(), tbm_lossify(), tbm_mark_page_lossy(), and tbm_page_is_lossy().

#define SH_DECLARE

Definition at line 198 of file tidbitmap.c.

#define SH_DEFINE

Definition at line 197 of file tidbitmap.c.

#define SH_ELEMENT_TYPE   PagetableEntry

Definition at line 191 of file tidbitmap.c.

#define SH_EQUAL (   tb,
  a,
 
)    a == b

Definition at line 195 of file tidbitmap.c.

#define SH_HASH_KEY (   tb,
  key 
)    hash_blockno(key)

Definition at line 194 of file tidbitmap.c.

#define SH_KEY   blockno

Definition at line 193 of file tidbitmap.c.

#define SH_KEY_TYPE   BlockNumber

Definition at line 192 of file tidbitmap.c.

#define SH_PREFIX   pagetable

Definition at line 190 of file tidbitmap.c.

#define SH_SCOPE   static inline

Definition at line 196 of file tidbitmap.c.

#define WORDNUM (   x)    ((x) / BITS_PER_BITMAPWORD)

Definition at line 74 of file tidbitmap.c.

Referenced by tbm_add_tuples(), tbm_iterate(), tbm_mark_page_lossy(), and tbm_page_is_lossy().

#define WORDS_PER_CHUNK   ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 80 of file tidbitmap.c.

Referenced by tbm_intersect_page(), and tbm_union_page().

#define WORDS_PER_PAGE   ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 78 of file tidbitmap.c.

Referenced by tbm_intersect_page(), tbm_iterate(), and tbm_union_page().

Typedef Documentation

Enumeration Type Documentation

enum TBMStatus
Enumerator
TBM_EMPTY 
TBM_ONE_PAGE 
TBM_HASH 

Definition at line 116 of file tidbitmap.c.

117 {
118  TBM_EMPTY, /* no hashtable, nentries == 0 */
119  TBM_ONE_PAGE, /* entry1 contains the single entry */
120  TBM_HASH /* pagetable is valid, entry1 is not */
121 } TBMStatus;
TBMStatus
Definition: tidbitmap.c:116

Function Documentation

static uint32 hash_blockno ( BlockNumber  b)
inlinestatic

Definition at line 177 of file tidbitmap.c.

178 {
179  uint32 h = b;
180 
181  h ^= h >> 16;
182  h *= 0x85ebca6b;
183  h ^= h >> 13;
184  h *= 0xc2b2ae35;
185  h ^= h >> 16;
186  return h;
187 }
unsigned int uint32
Definition: c.h:265
void tbm_add_page ( TIDBitmap tbm,
BlockNumber  pageno 
)

Definition at line 356 of file tidbitmap.c.

References TIDBitmap::maxentries, TIDBitmap::nentries, tbm_lossify(), and tbm_mark_page_lossy().

Referenced by bringetbitmap(), and gingetbitmap().

357 {
358  /* Enter the page in the bitmap, or mark it lossy if already present */
359  tbm_mark_page_lossy(tbm, pageno);
360  /* If we went over the memory limit, lossify some more pages */
361  if (tbm->nentries > tbm->maxentries)
362  tbm_lossify(tbm);
363 }
int maxentries
Definition: tidbitmap.c:133
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:984
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:912
int nentries
Definition: tidbitmap.c:132
void tbm_add_tuples ( TIDBitmap tbm,
const ItemPointer  tids,
int  ntids,
bool  recheck 
)

Definition at line 290 of file tidbitmap.c.

References Assert, BITNUM, elog, ERROR, i, InvalidBlockNumber, PagetableEntry::ischunk, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::maxentries, TIDBitmap::nentries, NULL, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), tbm_page_is_lossy(), WORDNUM, and PagetableEntry::words.

Referenced by blgetbitmap(), btgetbitmap(), collectMatchBitmap(), GinDataLeafPageGetItemsToTbm(), gingetbitmap(), ginPostingListDecodeAllSegmentsToTbm(), gistScanPage(), hashgetbitmap(), scanPendingInsert(), and storeBitmap().

292 {
294  PagetableEntry *page = NULL; /* only valid when currblk is valid */
295  int i;
296 
297  Assert(!tbm->iterating);
298  for (i = 0; i < ntids; i++)
299  {
300  BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
302  int wordnum,
303  bitnum;
304 
305  /* safety check to ensure we don't overrun bit array bounds */
306  if (off < 1 || off > MAX_TUPLES_PER_PAGE)
307  elog(ERROR, "tuple offset out of range: %u", off);
308 
309  /*
310  * Look up target page unless we already did. This saves cycles when
311  * the input includes consecutive tuples on the same page, which is
312  * common enough to justify an extra test here.
313  */
314  if (blk != currblk)
315  {
316  if (tbm_page_is_lossy(tbm, blk))
317  page = NULL; /* remember page is lossy */
318  else
319  page = tbm_get_pageentry(tbm, blk);
320  currblk = blk;
321  }
322 
323  if (page == NULL)
324  continue; /* whole page is already marked */
325 
326  if (page->ischunk)
327  {
328  /* The page is a lossy chunk header, set bit for itself */
329  wordnum = bitnum = 0;
330  }
331  else
332  {
333  /* Page is exact, so set bit for individual tuple */
334  wordnum = WORDNUM(off - 1);
335  bitnum = BITNUM(off - 1);
336  }
337  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
338  page->recheck |= recheck;
339 
340  if (tbm->nentries > tbm->maxentries)
341  {
342  tbm_lossify(tbm);
343  /* Page could have been converted to lossy, so force new lookup */
344  currblk = InvalidBlockNumber;
345  }
346  }
347 }
#define BITNUM(x)
Definition: tidbitmap.c:75
uint32 BlockNumber
Definition: block.h:31
uint32 bitmapword
Definition: bitmapset.h:29
uint16 OffsetNumber
Definition: off.h:24
#define ERROR
Definition: elog.h:43
int maxentries
Definition: tidbitmap.c:133
#define WORDNUM(x)
Definition: tidbitmap.c:74
bool iterating
Definition: tidbitmap.c:136
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define InvalidBlockNumber
Definition: block.h:33
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:53
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:878
int i
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:984
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:831
#define elog
Definition: elog.h:219
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:66
int nentries
Definition: tidbitmap.c:132
TBMIterator* tbm_begin_iterate ( TIDBitmap tbm)

Definition at line 602 of file tidbitmap.c.

References Assert, i, PagetableEntry::ischunk, TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::mcxt, MemoryContextAlloc(), TIDBitmap::nchunks, TIDBitmap::npages, NULL, TIDBitmap::pagetable, palloc(), qsort, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, tbm_comparator(), and TBM_HASH.

Referenced by BitmapHeapNext(), and startScanEntry().

603 {
604  TBMIterator *iterator;
605 
606  /*
607  * Create the TBMIterator struct, with enough trailing space to serve the
608  * needs of the TBMIterateResult sub-struct.
609  */
610  iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
612  iterator->tbm = tbm;
613 
614  /*
615  * Initialize iteration pointers.
616  */
617  iterator->spageptr = 0;
618  iterator->schunkptr = 0;
619  iterator->schunkbit = 0;
620 
621  /*
622  * If we have a hashtable, create and fill the sorted page lists, unless
623  * we already did that for a previous iterator. Note that the lists are
624  * attached to the bitmap not the iterator, so they can be used by more
625  * than one iterator.
626  */
627  if (tbm->status == TBM_HASH && !tbm->iterating)
628  {
629  pagetable_iterator i;
630  PagetableEntry *page;
631  int npages;
632  int nchunks;
633 
634  if (!tbm->spages && tbm->npages > 0)
635  tbm->spages = (PagetableEntry **)
637  tbm->npages * sizeof(PagetableEntry *));
638  if (!tbm->schunks && tbm->nchunks > 0)
639  tbm->schunks = (PagetableEntry **)
641  tbm->nchunks * sizeof(PagetableEntry *));
642 
643  npages = nchunks = 0;
644  pagetable_start_iterate(tbm->pagetable, &i);
645  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
646  {
647  if (page->ischunk)
648  tbm->schunks[nchunks++] = page;
649  else
650  tbm->spages[npages++] = page;
651  }
652  Assert(npages == tbm->npages);
653  Assert(nchunks == tbm->nchunks);
654  if (npages > 1)
655  qsort(tbm->spages, npages, sizeof(PagetableEntry *),
657  if (nchunks > 1)
658  qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
660  }
661 
662  tbm->iterating = true;
663 
664  return iterator;
665 }
static int tbm_comparator(const void *left, const void *right)
Definition: tidbitmap.c:1053
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
uint16 OffsetNumber
Definition: off.h:24
MemoryContext mcxt
Definition: tidbitmap.c:129
int schunkptr
Definition: tidbitmap.c:154
int spageptr
Definition: tidbitmap.c:153
TIDBitmap * tbm
Definition: tidbitmap.c:152
int nchunks
Definition: tidbitmap.c:135
PagetableEntry ** spages
Definition: tidbitmap.c:140
bool iterating
Definition: tidbitmap.c:136
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
PagetableEntry ** schunks
Definition: tidbitmap.c:141
TBMStatus status
Definition: tidbitmap.c:130
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:53
void * palloc(Size size)
Definition: mcxt.c:891
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:749
int i
int schunkbit
Definition: tidbitmap.c:155
#define qsort(a, b, c, d)
Definition: port.h:440
static int tbm_comparator ( const void *  left,
const void *  right 
)
static

Definition at line 1053 of file tidbitmap.c.

Referenced by tbm_begin_iterate().

1054 {
1055  BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
1056  BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
1057 
1058  if (l < r)
1059  return -1;
1060  else if (l > r)
1061  return 1;
1062  return 0;
1063 }
uint32 BlockNumber
Definition: block.h:31
TIDBitmap* tbm_create ( long  maxbytes)

Definition at line 210 of file tidbitmap.c.

References CurrentMemoryContext, TIDBitmap::lossify_start, makeNode, Max, TIDBitmap::maxentries, TIDBitmap::mcxt, Min, TIDBitmap::status, and TBM_EMPTY.

Referenced by collectMatchBitmap(), MultiExecBitmapIndexScan(), and MultiExecBitmapOr().

211 {
212  TIDBitmap *tbm;
213  long nbuckets;
214 
215  /* Create the TIDBitmap struct and zero all its fields */
216  tbm = makeNode(TIDBitmap);
217 
218  tbm->mcxt = CurrentMemoryContext;
219  tbm->status = TBM_EMPTY;
220 
221  /*
222  * Estimate number of hashtable entries we can have within maxbytes. This
223  * estimates the hash cost as sizeof(PagetableEntry), which is good enough
224  * for our purpose. Also count an extra Pointer per entry for the arrays
225  * created during iteration readout.
226  */
227  nbuckets = maxbytes /
228  (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
229  nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
230  nbuckets = Max(nbuckets, 16); /* sanity limit */
231  tbm->maxentries = (int) nbuckets;
232  tbm->lossify_start = 0;
233 
234  return tbm;
235 }
#define Min(x, y)
Definition: c.h:802
uint32 lossify_start
Definition: tidbitmap.c:137
MemoryContext mcxt
Definition: tidbitmap.c:129
char * Pointer
Definition: c.h:242
int maxentries
Definition: tidbitmap.c:133
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define Max(x, y)
Definition: c.h:796
#define makeNode(_type_)
Definition: nodes.h:556
TBMStatus status
Definition: tidbitmap.c:130
struct PagetableEntry PagetableEntry
static void tbm_create_pagetable ( TIDBitmap tbm)
static

Definition at line 242 of file tidbitmap.c.

References Assert, PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::mcxt, NULL, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, TBM_HASH, and TBM_ONE_PAGE.

Referenced by tbm_get_pageentry(), and tbm_mark_page_lossy().

243 {
244  Assert(tbm->status != TBM_HASH);
245  Assert(tbm->pagetable == NULL);
246 
247  tbm->pagetable = pagetable_create(tbm->mcxt, 128, NULL);
248 
249  /* If entry1 is valid, push it into the hashtable */
250  if (tbm->status == TBM_ONE_PAGE)
251  {
252  PagetableEntry *page;
253  bool found;
254  char oldstatus;
255 
256  page = pagetable_insert(tbm->pagetable,
257  tbm->entry1.blockno,
258  &found);
259  Assert(!found);
260  oldstatus = page->status;
261  memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
262  page->status = oldstatus;
263  }
264 
265  tbm->status = TBM_HASH;
266 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
MemoryContext mcxt
Definition: tidbitmap.c:129
PagetableEntry entry1
Definition: tidbitmap.c:138
BlockNumber blockno
Definition: tidbitmap.c:98
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
void tbm_end_iterate ( TBMIterator iterator)

Definition at line 787 of file tidbitmap.c.

References pfree().

Referenced by BitmapHeapNext(), entryGetItem(), ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), and startScanEntry().

788 {
789  pfree(iterator);
790 }
void pfree(void *pointer)
Definition: mcxt.c:992
static const PagetableEntry * tbm_find_pageentry ( const TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 798 of file tidbitmap.c.

References Assert, PagetableEntry::blockno, TIDBitmap::entry1, PagetableEntry::ischunk, TIDBitmap::nentries, NULL, TIDBitmap::pagetable, TIDBitmap::status, and TBM_ONE_PAGE.

Referenced by tbm_intersect_page().

799 {
800  const PagetableEntry *page;
801 
802  if (tbm->nentries == 0) /* in case pagetable doesn't exist */
803  return NULL;
804 
805  if (tbm->status == TBM_ONE_PAGE)
806  {
807  page = &tbm->entry1;
808  if (page->blockno != pageno)
809  return NULL;
810  Assert(!page->ischunk);
811  return page;
812  }
813 
814  page = pagetable_lookup(tbm->pagetable, pageno);
815  if (page == NULL)
816  return NULL;
817  if (page->ischunk)
818  return NULL; /* don't want a lossy chunk header */
819  return page;
820 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
PagetableEntry entry1
Definition: tidbitmap.c:138
BlockNumber blockno
Definition: tidbitmap.c:98
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int nentries
Definition: tidbitmap.c:132
void tbm_free ( TIDBitmap tbm)

Definition at line 272 of file tidbitmap.c.

References TIDBitmap::pagetable, pfree(), TIDBitmap::schunks, and TIDBitmap::spages.

Referenced by ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), MultiExecBitmapAnd(), MultiExecBitmapOr(), and startScanEntry().

273 {
274  if (tbm->pagetable)
275  pagetable_destroy(tbm->pagetable);
276  if (tbm->spages)
277  pfree(tbm->spages);
278  if (tbm->schunks)
279  pfree(tbm->schunks);
280  pfree(tbm);
281 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
void pfree(void *pointer)
Definition: mcxt.c:992
PagetableEntry ** spages
Definition: tidbitmap.c:140
PagetableEntry ** schunks
Definition: tidbitmap.c:141
static PagetableEntry * tbm_get_pageentry ( TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 831 of file tidbitmap.c.

References PagetableEntry::blockno, TIDBitmap::entry1, MemSet, TIDBitmap::nentries, TIDBitmap::npages, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, tbm_create_pagetable(), TBM_EMPTY, and TBM_ONE_PAGE.

Referenced by tbm_add_tuples(), and tbm_union_page().

832 {
833  PagetableEntry *page;
834  bool found;
835 
836  if (tbm->status == TBM_EMPTY)
837  {
838  /* Use the fixed slot */
839  page = &tbm->entry1;
840  found = false;
841  tbm->status = TBM_ONE_PAGE;
842  }
843  else
844  {
845  if (tbm->status == TBM_ONE_PAGE)
846  {
847  page = &tbm->entry1;
848  if (page->blockno == pageno)
849  return page;
850  /* Time to switch from one page to a hashtable */
852  }
853 
854  /* Look up or create an entry */
855  page = pagetable_insert(tbm->pagetable, pageno, &found);
856  }
857 
858  /* Initialize it if not present before */
859  if (!found)
860  {
861  char oldstatus = page->status;
862 
863  MemSet(page, 0, sizeof(PagetableEntry));
864  page->status = oldstatus;
865  page->blockno = pageno;
866  /* must count it too */
867  tbm->nentries++;
868  tbm->npages++;
869  }
870 
871  return page;
872 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
#define MemSet(start, val, len)
Definition: c.h:853
PagetableEntry entry1
Definition: tidbitmap.c:138
BlockNumber blockno
Definition: tidbitmap.c:98
int npages
Definition: tidbitmap.c:134
TBMStatus status
Definition: tidbitmap.c:130
int nentries
Definition: tidbitmap.c:132
static void tbm_create_pagetable(TIDBitmap *tbm)
Definition: tidbitmap.c:242
void tbm_intersect ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 453 of file tidbitmap.c.

References Assert, PagetableEntry::blockno, elog, TIDBitmap::entry1, ERROR, i, PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

454 {
455  Assert(!a->iterating);
456  /* Nothing to do if a is empty */
457  if (a->nentries == 0)
458  return;
459  /* Scan through chunks and pages in a, try to match to b */
460  if (a->status == TBM_ONE_PAGE)
461  {
462  if (tbm_intersect_page(a, &a->entry1, b))
463  {
464  /* Page is now empty, remove it from a */
465  Assert(!a->entry1.ischunk);
466  a->npages--;
467  a->nentries--;
468  Assert(a->nentries == 0);
469  a->status = TBM_EMPTY;
470  }
471  }
472  else
473  {
474  pagetable_iterator i;
475  PagetableEntry *apage;
476 
477  Assert(a->status == TBM_HASH);
478  pagetable_start_iterate(a->pagetable, &i);
479  while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
480  {
481  if (tbm_intersect_page(a, apage, b))
482  {
483  /* Page or chunk is now empty, remove it from a */
484  if (apage->ischunk)
485  a->nchunks--;
486  else
487  a->npages--;
488  a->nentries--;
489  if (!pagetable_delete(a->pagetable, apage->blockno))
490  elog(ERROR, "hash table corrupted");
491  }
492  }
493  }
494 }
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
Definition: tidbitmap.c:502
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
PagetableEntry entry1
Definition: tidbitmap.c:138
#define ERROR
Definition: elog.h:43
BlockNumber blockno
Definition: tidbitmap.c:98
int nchunks
Definition: tidbitmap.c:135
bool iterating
Definition: tidbitmap.c:136
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int i
#define elog
Definition: elog.h:219
int nentries
Definition: tidbitmap.c:132
static bool tbm_intersect_page ( TIDBitmap a,
PagetableEntry apage,
const TIDBitmap b 
)
static

Definition at line 502 of file tidbitmap.c.

References Assert, BITS_PER_BITMAPWORD, PagetableEntry::blockno, PagetableEntry::ischunk, NULL, PagetableEntry::recheck, tbm_find_pageentry(), tbm_page_is_lossy(), PagetableEntry::words, WORDS_PER_CHUNK, and WORDS_PER_PAGE.

Referenced by tbm_intersect().

503 {
504  const PagetableEntry *bpage;
505  int wordnum;
506 
507  if (apage->ischunk)
508  {
509  /* Scan each bit in chunk, try to clear */
510  bool candelete = true;
511 
512  for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
513  {
514  bitmapword w = apage->words[wordnum];
515 
516  if (w != 0)
517  {
518  bitmapword neww = w;
519  BlockNumber pg;
520  int bitnum;
521 
522  pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
523  bitnum = 0;
524  while (w != 0)
525  {
526  if (w & 1)
527  {
528  if (!tbm_page_is_lossy(b, pg) &&
529  tbm_find_pageentry(b, pg) == NULL)
530  {
531  /* Page is not in b at all, lose lossy bit */
532  neww &= ~((bitmapword) 1 << bitnum);
533  }
534  }
535  pg++;
536  bitnum++;
537  w >>= 1;
538  }
539  apage->words[wordnum] = neww;
540  if (neww != 0)
541  candelete = false;
542  }
543  }
544  return candelete;
545  }
546  else if (tbm_page_is_lossy(b, apage->blockno))
547  {
548  /*
549  * Some of the tuples in 'a' might not satisfy the quals for 'b', but
550  * because the page 'b' is lossy, we don't know which ones. Therefore
551  * we mark 'a' as requiring rechecks, to indicate that at most those
552  * tuples set in 'a' are matches.
553  */
554  apage->recheck = true;
555  return false;
556  }
557  else
558  {
559  bool candelete = true;
560 
561  bpage = tbm_find_pageentry(b, apage->blockno);
562  if (bpage != NULL)
563  {
564  /* Both pages are exact, merge at the bit level */
565  Assert(!bpage->ischunk);
566  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
567  {
568  apage->words[wordnum] &= bpage->words[wordnum];
569  if (apage->words[wordnum] != 0)
570  candelete = false;
571  }
572  apage->recheck |= bpage->recheck;
573  }
574  /* If there is no matching b page, we can just delete the a page */
575  return candelete;
576  }
577 }
uint32 BlockNumber
Definition: block.h:31
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
#define WORDS_PER_CHUNK
Definition: tidbitmap.c:80
uint32 bitmapword
Definition: bitmapset.h:29
#define WORDS_PER_PAGE
Definition: tidbitmap.c:78
BlockNumber blockno
Definition: tidbitmap.c:98
static const PagetableEntry * tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:798
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:878
bool tbm_is_empty ( const TIDBitmap tbm)

Definition at line 583 of file tidbitmap.c.

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

584 {
585  return (tbm->nentries == 0);
586 }
int nentries
Definition: tidbitmap.c:132
TBMIterateResult* tbm_iterate ( TBMIterator iterator)

Definition at line 680 of file tidbitmap.c.

References Assert, BITNUM, BITS_PER_BITMAPWORD, TBMIterateResult::blockno, PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, TBMIterateResult::ntuples, NULL, TBMIterateResult::offsets, output(), TBMIterator::output, PAGES_PER_CHUNK, TBMIterateResult::recheck, PagetableEntry::recheck, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, TBM_ONE_PAGE, WORDNUM, PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by BitmapHeapNext(), and entryGetItem().

681 {
682  TIDBitmap *tbm = iterator->tbm;
683  TBMIterateResult *output = &(iterator->output);
684 
685  Assert(tbm->iterating);
686 
687  /*
688  * If lossy chunk pages remain, make sure we've advanced schunkptr/
689  * schunkbit to the next set bit.
690  */
691  while (iterator->schunkptr < tbm->nchunks)
692  {
693  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
694  int schunkbit = iterator->schunkbit;
695 
696  while (schunkbit < PAGES_PER_CHUNK)
697  {
698  int wordnum = WORDNUM(schunkbit);
699  int bitnum = BITNUM(schunkbit);
700 
701  if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
702  break;
703  schunkbit++;
704  }
705  if (schunkbit < PAGES_PER_CHUNK)
706  {
707  iterator->schunkbit = schunkbit;
708  break;
709  }
710  /* advance to next chunk */
711  iterator->schunkptr++;
712  iterator->schunkbit = 0;
713  }
714 
715  /*
716  * If both chunk and per-page data remain, must output the numerically
717  * earlier page.
718  */
719  if (iterator->schunkptr < tbm->nchunks)
720  {
721  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
722  BlockNumber chunk_blockno;
723 
724  chunk_blockno = chunk->blockno + iterator->schunkbit;
725  if (iterator->spageptr >= tbm->npages ||
726  chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
727  {
728  /* Return a lossy page indicator from the chunk */
729  output->blockno = chunk_blockno;
730  output->ntuples = -1;
731  output->recheck = true;
732  iterator->schunkbit++;
733  return output;
734  }
735  }
736 
737  if (iterator->spageptr < tbm->npages)
738  {
739  PagetableEntry *page;
740  int ntuples;
741  int wordnum;
742 
743  /* In ONE_PAGE state, we don't allocate an spages[] array */
744  if (tbm->status == TBM_ONE_PAGE)
745  page = &tbm->entry1;
746  else
747  page = tbm->spages[iterator->spageptr];
748 
749  /* scan bitmap to extract individual offset numbers */
750  ntuples = 0;
751  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
752  {
753  bitmapword w = page->words[wordnum];
754 
755  if (w != 0)
756  {
757  int off = wordnum * BITS_PER_BITMAPWORD + 1;
758 
759  while (w != 0)
760  {
761  if (w & 1)
762  output->offsets[ntuples++] = (OffsetNumber) off;
763  off++;
764  w >>= 1;
765  }
766  }
767  }
768  output->blockno = page->blockno;
769  output->ntuples = ntuples;
770  output->recheck = page->recheck;
771  iterator->spageptr++;
772  return output;
773  }
774 
775  /* Nothing more in the bitmap */
776  return NULL;
777 }
static void output(uint64 loop_count)
#define BITNUM(x)
Definition: tidbitmap.c:75
uint32 BlockNumber
Definition: block.h:31
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
uint32 bitmapword
Definition: bitmapset.h:29
#define WORDS_PER_PAGE
Definition: tidbitmap.c:78
uint16 OffsetNumber
Definition: off.h:24
PagetableEntry entry1
Definition: tidbitmap.c:138
BlockNumber blockno
Definition: tidbitmap.h:40
int schunkptr
Definition: tidbitmap.c:154
BlockNumber blockno
Definition: tidbitmap.c:98
int spageptr
Definition: tidbitmap.c:153
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:44
#define WORDNUM(x)
Definition: tidbitmap.c:74
TIDBitmap * tbm
Definition: tidbitmap.c:152
int nchunks
Definition: tidbitmap.c:135
PagetableEntry ** spages
Definition: tidbitmap.c:140
bool iterating
Definition: tidbitmap.c:136
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:70
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
PagetableEntry ** schunks
Definition: tidbitmap.c:141
TBMIterateResult output
Definition: tidbitmap.c:156
TBMStatus status
Definition: tidbitmap.c:130
int schunkbit
Definition: tidbitmap.c:155
static void tbm_lossify ( TIDBitmap tbm)
static

Definition at line 984 of file tidbitmap.c.

References Assert, PagetableEntry::blockno, i, PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::lossify_start, TIDBitmap::maxentries, Min, TIDBitmap::nentries, NULL, PAGES_PER_CHUNK, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, and tbm_mark_page_lossy().

Referenced by tbm_add_page(), tbm_add_tuples(), and tbm_union_page().

985 {
986  pagetable_iterator i;
987  PagetableEntry *page;
988 
989  /*
990  * XXX Really stupid implementation: this just lossifies pages in
991  * essentially random order. We should be paying some attention to the
992  * number of bits set in each page, instead.
993  *
994  * Since we are called as soon as nentries exceeds maxentries, we should
995  * push nentries down to significantly less than maxentries, or else we'll
996  * just end up doing this again very soon. We shoot for maxentries/2.
997  */
998  Assert(!tbm->iterating);
999  Assert(tbm->status == TBM_HASH);
1000 
1001  pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
1002  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
1003  {
1004  if (page->ischunk)
1005  continue; /* already a chunk header */
1006 
1007  /*
1008  * If the page would become a chunk header, we won't save anything by
1009  * converting it to lossy, so skip it.
1010  */
1011  if ((page->blockno % PAGES_PER_CHUNK) == 0)
1012  continue;
1013 
1014  /* This does the dirty work ... */
1015  tbm_mark_page_lossy(tbm, page->blockno);
1016 
1017  if (tbm->nentries <= tbm->maxentries / 2)
1018  {
1019  /*
1020  * We have made enough room. Remember where to start lossifying
1021  * next round, so we evenly iterate over the hashtable.
1022  */
1023  tbm->lossify_start = i.cur;
1024  break;
1025  }
1026 
1027  /*
1028  * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
1029  * hashtable and may have deleted the non-lossy chunk. We can
1030  * continue the same hash table scan, since failure to visit one
1031  * element or visiting the newly inserted element, isn't fatal.
1032  */
1033  }
1034 
1035  /*
1036  * With a big bitmap and small work_mem, it's possible that we cannot get
1037  * under maxentries. Again, if that happens, we'd end up uselessly
1038  * calling tbm_lossify over and over. To prevent this from becoming a
1039  * performance sink, force maxentries up to at least double the current
1040  * number of entries. (In essence, we're admitting inability to fit
1041  * within work_mem when we do this.) Note that this test will not fire if
1042  * we broke out of the loop early; and if we didn't, the current number of
1043  * entries is simply not reducible any further.
1044  */
1045  if (tbm->nentries > tbm->maxentries / 2)
1046  tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
1047 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
#define Min(x, y)
Definition: c.h:802
uint32 lossify_start
Definition: tidbitmap.c:137
BlockNumber blockno
Definition: tidbitmap.c:98
int maxentries
Definition: tidbitmap.c:133
bool iterating
Definition: tidbitmap.c:136
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:70
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int i
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:912
int nentries
Definition: tidbitmap.c:132
static void tbm_mark_page_lossy ( TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 912 of file tidbitmap.c.

References BITNUM, PagetableEntry::blockno, PagetableEntry::ischunk, MemSet, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, PAGES_PER_CHUNK, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, tbm_create_pagetable(), TBM_HASH, WORDNUM, and PagetableEntry::words.

Referenced by tbm_add_page(), tbm_lossify(), and tbm_union_page().

913 {
914  PagetableEntry *page;
915  bool found;
916  BlockNumber chunk_pageno;
917  int bitno;
918  int wordnum;
919  int bitnum;
920 
921  /* We force the bitmap into hashtable mode whenever it's lossy */
922  if (tbm->status != TBM_HASH)
924 
925  bitno = pageno % PAGES_PER_CHUNK;
926  chunk_pageno = pageno - bitno;
927 
928  /*
929  * Remove any extant non-lossy entry for the page. If the page is its own
930  * chunk header, however, we skip this and handle the case below.
931  */
932  if (bitno != 0)
933  {
934  if (pagetable_delete(tbm->pagetable, pageno))
935  {
936  /* It was present, so adjust counts */
937  tbm->nentries--;
938  tbm->npages--; /* assume it must have been non-lossy */
939  }
940  }
941 
942  /* Look up or create entry for chunk-header page */
943  page = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
944 
945  /* Initialize it if not present before */
946  if (!found)
947  {
948  char oldstatus = page->status;
949 
950  MemSet(page, 0, sizeof(PagetableEntry));
951  page->status = oldstatus;
952  page->blockno = chunk_pageno;
953  page->ischunk = true;
954  /* must count it too */
955  tbm->nentries++;
956  tbm->nchunks++;
957  }
958  else if (!page->ischunk)
959  {
960  char oldstatus = page->status;
961 
962  /* chunk header page was formerly non-lossy, make it lossy */
963  MemSet(page, 0, sizeof(PagetableEntry));
964  page->status = oldstatus;
965  page->blockno = chunk_pageno;
966  page->ischunk = true;
967  /* we assume it had some tuple bit(s) set, so mark it lossy */
968  page->words[0] = ((bitmapword) 1 << 0);
969  /* adjust counts */
970  tbm->nchunks++;
971  tbm->npages--;
972  }
973 
974  /* Now set the original target page's bit */
975  wordnum = WORDNUM(bitno);
976  bitnum = BITNUM(bitno);
977  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
978 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
#define BITNUM(x)
Definition: tidbitmap.c:75
#define MemSet(start, val, len)
Definition: c.h:853
uint32 BlockNumber
Definition: block.h:31
uint32 bitmapword
Definition: bitmapset.h:29
BlockNumber blockno
Definition: tidbitmap.c:98
#define WORDNUM(x)
Definition: tidbitmap.c:74
int nchunks
Definition: tidbitmap.c:135
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:70
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
int npages
Definition: tidbitmap.c:134
TBMStatus status
Definition: tidbitmap.c:130
int nentries
Definition: tidbitmap.c:132
static void tbm_create_pagetable(TIDBitmap *tbm)
Definition: tidbitmap.c:242
static bool tbm_page_is_lossy ( const TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 878 of file tidbitmap.c.

References Assert, BITNUM, PagetableEntry::ischunk, TIDBitmap::nchunks, NULL, PAGES_PER_CHUNK, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, WORDNUM, and PagetableEntry::words.

Referenced by tbm_add_tuples(), tbm_intersect_page(), and tbm_union_page().

879 {
880  PagetableEntry *page;
881  BlockNumber chunk_pageno;
882  int bitno;
883 
884  /* we can skip the lookup if there are no lossy chunks */
885  if (tbm->nchunks == 0)
886  return false;
887  Assert(tbm->status == TBM_HASH);
888 
889  bitno = pageno % PAGES_PER_CHUNK;
890  chunk_pageno = pageno - bitno;
891 
892  page = pagetable_lookup(tbm->pagetable, chunk_pageno);
893 
894  if (page != NULL && page->ischunk)
895  {
896  int wordnum = WORDNUM(bitno);
897  int bitnum = BITNUM(bitno);
898 
899  if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
900  return true;
901  }
902  return false;
903 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
#define BITNUM(x)
Definition: tidbitmap.c:75
uint32 BlockNumber
Definition: block.h:31
uint32 bitmapword
Definition: bitmapset.h:29
#define WORDNUM(x)
Definition: tidbitmap.c:74
int nchunks
Definition: tidbitmap.c:135
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:70
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
void tbm_union ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 371 of file tidbitmap.c.

References Assert, TIDBitmap::entry1, i, TIDBitmap::iterating, TIDBitmap::nentries, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().

372 {
373  Assert(!a->iterating);
374  /* Nothing to do if b is empty */
375  if (b->nentries == 0)
376  return;
377  /* Scan through chunks and pages in b, merge into a */
378  if (b->status == TBM_ONE_PAGE)
379  tbm_union_page(a, &b->entry1);
380  else
381  {
382  pagetable_iterator i;
383  PagetableEntry *bpage;
384 
385  Assert(b->status == TBM_HASH);
386  pagetable_start_iterate(b->pagetable, &i);
387  while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
388  tbm_union_page(a, bpage);
389  }
390 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
Definition: tidbitmap.c:394
PagetableEntry entry1
Definition: tidbitmap.c:138
bool iterating
Definition: tidbitmap.c:136
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int i
int nentries
Definition: tidbitmap.c:132
static void tbm_union_page ( TIDBitmap a,
const PagetableEntry bpage 
)
static

Definition at line 394 of file tidbitmap.c.

References BITS_PER_BITMAPWORD, PagetableEntry::blockno, PagetableEntry::ischunk, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), tbm_mark_page_lossy(), tbm_page_is_lossy(), PagetableEntry::words, WORDS_PER_CHUNK, and WORDS_PER_PAGE.

Referenced by tbm_union().

395 {
396  PagetableEntry *apage;
397  int wordnum;
398 
399  if (bpage->ischunk)
400  {
401  /* Scan b's chunk, mark each indicated page lossy in a */
402  for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
403  {
404  bitmapword w = bpage->words[wordnum];
405 
406  if (w != 0)
407  {
408  BlockNumber pg;
409 
410  pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
411  while (w != 0)
412  {
413  if (w & 1)
414  tbm_mark_page_lossy(a, pg);
415  pg++;
416  w >>= 1;
417  }
418  }
419  }
420  }
421  else if (tbm_page_is_lossy(a, bpage->blockno))
422  {
423  /* page is already lossy in a, nothing to do */
424  return;
425  }
426  else
427  {
428  apage = tbm_get_pageentry(a, bpage->blockno);
429  if (apage->ischunk)
430  {
431  /* The page is a lossy chunk header, set bit for itself */
432  apage->words[0] |= ((bitmapword) 1 << 0);
433  }
434  else
435  {
436  /* Both pages are exact, merge at the bit level */
437  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
438  apage->words[wordnum] |= bpage->words[wordnum];
439  apage->recheck |= bpage->recheck;
440  }
441  }
442 
443  if (a->nentries > a->maxentries)
444  tbm_lossify(a);
445 }
uint32 BlockNumber
Definition: block.h:31
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
#define WORDS_PER_CHUNK
Definition: tidbitmap.c:80
uint32 bitmapword
Definition: bitmapset.h:29
#define WORDS_PER_PAGE
Definition: tidbitmap.c:78
BlockNumber blockno
Definition: tidbitmap.c:98
int maxentries
Definition: tidbitmap.c:133
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:878
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:984
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:912
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:831
int nentries
Definition: tidbitmap.c:132