56 #define MAX_TUPLES_PER_PAGE MaxHeapTuplesPerPage 73 #define PAGES_PER_CHUNK (BLCKSZ / 32) 77 #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) 78 #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) 81 #define WORDS_PER_PAGE ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1) 83 #define WORDS_PER_CHUNK ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1) 242 #define SH_USE_NONDEFAULT_ALLOCATOR 243 #define SH_PREFIX pagetable 244 #define SH_ELEMENT_TYPE PagetableEntry 245 #define SH_KEY_TYPE BlockNumber 246 #define SH_KEY blockno 247 #define SH_HASH_KEY(tb, key) murmurhash32(key) 248 #define SH_EQUAL(tb, a, b) a == b 249 #define SH_SCOPE static inline 384 for (i = 0; i < ntids; i++)
393 elog(
ERROR,
"tuple offset out of range: %u", off);
415 wordnum = bitnum = 0;
468 pagetable_iterator
i;
472 pagetable_start_iterate(b->
pagetable, &i);
473 while ((bpage = pagetable_iterate(b->
pagetable, &i)) != NULL)
524 apage->
words[wordnum] |= bpage->
words[wordnum];
560 pagetable_iterator
i;
564 pagetable_start_iterate(a->
pagetable, &i);
565 while ((apage = pagetable_iterate(a->
pagetable, &i)) != NULL)
596 bool candelete =
true;
625 apage->
words[wordnum] = neww;
645 bool candelete =
true;
654 apage->
words[wordnum] &= bpage->
words[wordnum];
655 if (apage->
words[wordnum] != 0)
717 pagetable_iterator
i;
731 npages = nchunks = 0;
732 pagetable_start_iterate(tbm->
pagetable, &i);
733 while ((page = pagetable_iterate(tbm->
pagetable, &i)) != NULL)
736 tbm->
schunks[nchunks++] = page;
738 tbm->
spages[npages++] = page;
790 pagetable_iterator
i;
803 tbm->
npages *
sizeof(
int));
821 npages = nchunks = 0;
826 pagetable_start_iterate(tbm->
pagetable, &i);
827 while ((page = pagetable_iterate(tbm->
pagetable, &i)) != NULL)
850 ptpages->
index[0] = 0;
888 if (ptchunks != NULL)
942 int schunkbit = *schunkbitp;
946 int wordnum =
WORDNUM(schunkbit);
947 int bitnum =
BITNUM(schunkbit);
954 *schunkbitp = schunkbit;
1008 chunk_blockno < tbm->spages[iterator->
spageptr]->blockno)
1011 output->
blockno = chunk_blockno;
1056 int *idxpages = NULL;
1057 int *idxchunks = NULL;
1059 if (iterator->
ptbase != NULL)
1061 if (iterator->
ptpages != NULL)
1104 output->
blockno = chunk_blockno;
1184 page = pagetable_lookup(tbm->
pagetable, pageno);
1225 page = pagetable_insert(tbm->
pagetable, pageno, &found);
1231 char oldstatus = page->
status;
1234 page->
status = oldstatus;
1260 chunk_pageno = pageno - bitno;
1262 page = pagetable_lookup(tbm->
pagetable, chunk_pageno);
1264 if (page != NULL && page->
ischunk)
1267 int bitnum =
BITNUM(bitno);
1296 chunk_pageno = pageno - bitno;
1304 if (pagetable_delete(tbm->
pagetable, pageno))
1313 page = pagetable_insert(tbm->
pagetable, chunk_pageno, &found);
1318 char oldstatus = page->
status;
1321 page->
status = oldstatus;
1330 char oldstatus = page->
status;
1334 page->
status = oldstatus;
1356 pagetable_iterator
i;
1372 while ((page = pagetable_iterate(tbm->
pagetable, &i)) != NULL)
1447 if (lpage->
blockno < rpage->blockno)
1449 else if (lpage->
blockno > rpage->blockno)
1478 iterator->
state = istate;
1496 static inline void *
1502 if (tbm->
dsa == NULL)
1516 return ptbase->ptentry;
1530 if (tbm->
dsa == NULL)
1555 nbuckets = maxbytes /
1557 nbuckets =
Min(nbuckets, INT_MAX - 1);
1558 nbuckets =
Max(nbuckets, 16);
static int tbm_comparator(const void *left, const void *right)
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
void tbm_end_iterate(TBMIterator *iterator)
void tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
struct PTIterationArray PTIterationArray
#define InvalidDsaPointer
dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm)
void tbm_union(TIDBitmap *a, const TIDBitmap *b)
struct pagetable_hash * pagetable
static void output(uint64 loop_count)
TBMSharedIteratorState * state
void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)
TIDBitmap * tbm_create(long maxbytes, dsa_area *dsa)
static uint32 pg_atomic_sub_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 sub_)
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
static int tbm_shared_comparator(const void *left, const void *right, void *arg)
#define FLEXIBLE_ARRAY_MEMBER
#define MemSet(start, val, len)
static uint32 pg_atomic_add_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 add_)
Datum idx(PG_FUNCTION_ARGS)
#define BITS_PER_BITMAPWORD
PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER]
static void tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
void LWLockRelease(LWLock *lock)
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
void pfree(void *pointer)
struct TBMSharedIteratorState TBMSharedIteratorState
static int tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
#define dsa_allocate0(area, size)
void tbm_free(TIDBitmap *tbm)
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
static const PagetableEntry * tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
MemoryContext CurrentMemoryContext
void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp)
static void pagetable_free(pagetable_hash *pagetable, void *pointer)
void LWLockInitialize(LWLock *lock, int tranche_id)
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
void * palloc0(Size size)
PTIterationArray * ptpages
bool tbm_is_empty(const TIDBitmap *tbm)
pg_atomic_uint32 refcount
TBMIterateResult * tbm_iterate(TBMIterator *iterator)
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
#define Assert(condition)
PagetableEntry ** schunks
TBMIterator * tbm_begin_iterate(TIDBitmap *tbm)
TBMIterateResult * tbm_shared_iterate(TBMSharedIterator *iterator)
#define InvalidBlockNumber
#define MAX_TUPLES_PER_PAGE
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
#define ItemPointerGetOffsetNumber(pointer)
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
dsa_pointer dsapagetableold
struct PagetableEntry PagetableEntry
#define DsaPointerIsValid(x)
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
void dsa_free(dsa_area *area, dsa_pointer dp)
void * MemoryContextAlloc(MemoryContext context, Size size)
pg_atomic_uint32 refcount
static void tbm_lossify(TIDBitmap *tbm)
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
TBMIteratingState iterating
static void pg_atomic_init_u32(volatile pg_atomic_uint32 *ptr, uint32 val)
#define ItemPointerGetBlockNumber(pointer)
long tbm_calculate_entries(double maxbytes)
#define qsort(a, b, c, d)
static void * pagetable_allocate(pagetable_hash *pagetable, Size size)
struct PTEntryArray PTEntryArray
TBMSharedIterator * tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
dsa_pointer dsa_allocate_extended(dsa_area *area, size_t size, int flags)
int index[FLEXIBLE_ARRAY_MEMBER]
static void tbm_create_pagetable(TIDBitmap *tbm)
PTIterationArray * ptchunks
#define dsa_allocate(area, size)
void tbm_end_shared_iterate(TBMSharedIterator *iterator)