#include "storage/itemptr.h"
#include "utils/dsa.h"

Include dependency graph for tidbitmap.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	TBMIterator

struct	TBMIterateResult

Macros
#define	TBM_MAX_TUPLES_PER_PAGE MaxHeapTuplesPerPage

Typedefs
typedef struct TIDBitmap	TIDBitmap

typedef struct TBMPrivateIterator	TBMPrivateIterator

typedef struct TBMSharedIterator	TBMSharedIterator

typedef struct TBMIterator	TBMIterator

typedef struct TBMIterateResult	TBMIterateResult

Functions
TIDBitmap *	tbm_create (Size maxbytes, dsa_area *dsa)

void	tbm_free (TIDBitmap *tbm)

void	tbm_free_shared_area (dsa_area *dsa, dsa_pointer dp)

void	tbm_add_tuples (TIDBitmap tbm, const ItemPointerData 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)

int	tbm_extract_page_tuple (TBMIterateResult iteritem, OffsetNumber offsets, uint32 max_offsets)

bool	tbm_is_empty (const TIDBitmap *tbm)

TBMPrivateIterator *	tbm_begin_private_iterate (TIDBitmap *tbm)

dsa_pointer	tbm_prepare_shared_iterate (TIDBitmap *tbm)

bool	tbm_private_iterate (TBMPrivateIterator iterator, TBMIterateResult tbmres)

bool	tbm_shared_iterate (TBMSharedIterator iterator, TBMIterateResult tbmres)

void	tbm_end_private_iterate (TBMPrivateIterator *iterator)

void	tbm_end_shared_iterate (TBMSharedIterator *iterator)

TBMSharedIterator *	tbm_attach_shared_iterate (dsa_area *dsa, dsa_pointer dp)

int	tbm_calculate_entries (Size maxbytes)

TBMIterator	tbm_begin_iterate (TIDBitmap tbm, dsa_area dsa, dsa_pointer dsp)

void	tbm_end_iterate (TBMIterator *iterator)

bool	tbm_iterate (TBMIterator iterator, TBMIterateResult tbmres)

static bool	tbm_exhausted (TBMIterator *iterator)

Macro Definition Documentation

◆ TBM_MAX_TUPLES_PER_PAGE

#define TBM_MAX_TUPLES_PER_PAGE MaxHeapTuplesPerPage

Definition at line 34 of file tidbitmap.h.

Typedef Documentation

◆ TBMIterateResult

typedef struct TBMIterateResult TBMIterateResult

◆ TBMIterator

typedef struct TBMIterator TBMIterator

◆ TBMPrivateIterator

typedef struct TBMPrivateIterator TBMPrivateIterator

Definition at line 43 of file tidbitmap.h.

◆ TBMSharedIterator

typedef struct TBMSharedIterator TBMSharedIterator

Definition at line 44 of file tidbitmap.h.

◆ TIDBitmap

typedef struct TIDBitmap TIDBitmap

Definition at line 40 of file tidbitmap.h.

Function Documentation

◆ tbm_add_page()

void tbm_add_page	(	TIDBitmap *	tbm,
		BlockNumber	pageno
	)

Definition at line 433 of file tidbitmap.c.

{
    /* Enter the page in the bitmap, or mark it lossy if already present */
    tbm_mark_page_lossy(tbm, pageno);
    /* If we went over the memory limit, lossify some more pages */
    if (tbm->nentries > tbm->maxentries)
        tbm_lossify(tbm);
}

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

Referenced by bringetbitmap(), and gingetbitmap().

◆ tbm_add_tuples()

void tbm_add_tuples	(	TIDBitmap *	tbm,
		const ItemPointerData *	tids,
		int	ntids,
		bool	recheck
	)

Definition at line 367 of file tidbitmap.c.

{
    BlockNumber currblk = InvalidBlockNumber;
    PagetableEntry *page = NULL;    /* only valid when currblk is valid */
    int         i;
 
    Assert(tbm->iterating == TBM_NOT_ITERATING);
    for (i = 0; i < ntids; i++)
    {
        BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
        OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
        int         wordnum,
                    bitnum;
 
        /* safety check to ensure we don't overrun bit array bounds */
        if (off < 1 || off > TBM_MAX_TUPLES_PER_PAGE)
            elog(ERROR, "tuple offset out of range: %u", off);
 
        /*
         * Look up target page unless we already did.  This saves cycles when
         * the input includes consecutive tuples on the same page, which is
         * common enough to justify an extra test here.
         */
        if (blk != currblk)
        {
            if (tbm_page_is_lossy(tbm, blk))
                page = NULL;    /* remember page is lossy */
            else
                page = tbm_get_pageentry(tbm, blk);
            currblk = blk;
        }
 
        if (page == NULL)
            continue;           /* whole page is already marked */
 
        if (page->ischunk)
        {
            /* The page is a lossy chunk header, set bit for itself */
            wordnum = bitnum = 0;
        }
        else
        {
            /* Page is exact, so set bit for individual tuple */
            wordnum = WORDNUM(off - 1);
            bitnum = BITNUM(off - 1);
        }
        page->words[wordnum] |= ((bitmapword) 1 << bitnum);
        page->recheck |= recheck;
 
        if (tbm->nentries > tbm->maxentries)
        {
            tbm_lossify(tbm);
            /* Page could have been converted to lossy, so force new lookup */
            currblk = InvalidBlockNumber;
        }
    }
}

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

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

◆ tbm_attach_shared_iterate()

TBMSharedIterator * tbm_attach_shared_iterate	(	dsa_area *	dsa,
		dsa_pointer	dp
	)

Definition at line 1466 of file tidbitmap.c.

{
    TBMSharedIterator *iterator;
    TBMSharedIteratorState *istate;
 
    /*
     * Create the TBMSharedIterator struct, with enough trailing space to
     * serve the needs of the TBMIterateResult sub-struct.
     */
    iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator));
 
    istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
 
    iterator->state = istate;
 
    iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
 
    if (istate->npages)
        iterator->ptpages = dsa_get_address(dsa, istate->spages);
    if (istate->nchunks)
        iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
 
    return iterator;
}

References dsa_get_address(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIteratorState::pagetable, palloc0(), TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, TBMSharedIterator::ptpages, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spages, and TBMSharedIterator::state.

Referenced by tbm_begin_iterate().

◆ tbm_begin_iterate()

TBMIterator tbm_begin_iterate	(	TIDBitmap *	tbm,
		dsa_area *	dsa,
		dsa_pointer	dsp
	)

Definition at line 1575 of file tidbitmap.c.

{
    TBMIterator iterator = {0};
 
    /* Allocate a private iterator and attach the shared state to it */
    if (DsaPointerIsValid(dsp))
    {
        iterator.shared = true;
        iterator.i.shared_iterator = tbm_attach_shared_iterate(dsa, dsp);
    }
    else
    {
        iterator.shared = false;
        iterator.i.private_iterator = tbm_begin_private_iterate(tbm);
    }
 
    return iterator;
}

References DsaPointerIsValid, TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_attach_shared_iterate(), and tbm_begin_private_iterate().

Referenced by BitmapTableScanSetup().

◆ tbm_begin_private_iterate()

TBMPrivateIterator * tbm_begin_private_iterate ( TIDBitmap * tbm )

Definition at line 679 of file tidbitmap.c.

{
    TBMPrivateIterator *iterator;
 
    Assert(tbm->iterating != TBM_ITERATING_SHARED);
 
    /*
     * Create the TBMPrivateIterator struct, with enough trailing space to
     * serve the needs of the TBMIterateResult sub-struct.
     */
    iterator = (TBMPrivateIterator *) palloc(sizeof(TBMPrivateIterator));
    iterator->tbm = tbm;
 
    /*
     * Initialize iteration pointers.
     */
    iterator->spageptr = 0;
    iterator->schunkptr = 0;
    iterator->schunkbit = 0;
 
    /*
     * If we have a hashtable, create and fill the sorted page lists, unless
     * we already did that for a previous iterator.  Note that the lists are
     * attached to the bitmap not the iterator, so they can be used by more
     * than one iterator.
     */
    if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
    {
        pagetable_iterator i;
        PagetableEntry *page;
        int         npages;
        int         nchunks;
 
        if (!tbm->spages && tbm->npages > 0)
            tbm->spages = (PagetableEntry **)
                MemoryContextAlloc(tbm->mcxt,
                                   tbm->npages * sizeof(PagetableEntry *));
        if (!tbm->schunks && tbm->nchunks > 0)
            tbm->schunks = (PagetableEntry **)
                MemoryContextAlloc(tbm->mcxt,
                                   tbm->nchunks * sizeof(PagetableEntry *));
 
        npages = nchunks = 0;
        pagetable_start_iterate(tbm->pagetable, &i);
        while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
        {
            if (page->ischunk)
                tbm->schunks[nchunks++] = page;
            else
                tbm->spages[npages++] = page;
        }
        Assert(npages == tbm->npages);
        Assert(nchunks == tbm->nchunks);
        if (npages > 1)
            qsort(tbm->spages, npages, sizeof(PagetableEntry *),
                  tbm_comparator);
        if (nchunks > 1)
            qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
                  tbm_comparator);
    }
 
    tbm->iterating = TBM_ITERATING_PRIVATE;
 
    return iterator;
}

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

Referenced by startScanEntry(), and tbm_begin_iterate().

◆ tbm_calculate_entries()

int tbm_calculate_entries ( Size maxbytes )

Definition at line 1546 of file tidbitmap.c.

{
    Size        nbuckets;
 
    /*
     * Estimate number of hashtable entries we can have within maxbytes. This
     * estimates the hash cost as sizeof(PagetableEntry), which is good enough
     * for our purpose.  Also count an extra Pointer per entry for the arrays
     * created during iteration readout.
     */
    nbuckets = maxbytes /
        (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
    nbuckets = Min(nbuckets, INT_MAX - 1);  /* safety limit */
    nbuckets = Max(nbuckets, 16);   /* sanity limit */
 
    return (int) nbuckets;
}

References Max, and Min.

Referenced by compute_bitmap_pages(), and tbm_create().

◆ tbm_create()

TIDBitmap * tbm_create	(	Size	maxbytes,
		dsa_area *	dsa
	)

Definition at line 256 of file tidbitmap.c.

{
    TIDBitmap  *tbm;
 
    /* Create the TIDBitmap struct and zero all its fields */
    tbm = makeNode(TIDBitmap);
 
    tbm->mcxt = CurrentMemoryContext;
    tbm->status = TBM_EMPTY;
 
    tbm->maxentries = tbm_calculate_entries(maxbytes);
    tbm->lossify_start = 0;
    tbm->dsa = dsa;
    tbm->dsapagetable = InvalidDsaPointer;
    tbm->dsapagetableold = InvalidDsaPointer;
    tbm->ptpages = InvalidDsaPointer;
    tbm->ptchunks = InvalidDsaPointer;
 
    return tbm;
}

References CurrentMemoryContext, TIDBitmap::dsa, TIDBitmap::dsapagetable, TIDBitmap::dsapagetableold, InvalidDsaPointer, TIDBitmap::lossify_start, makeNode, TIDBitmap::maxentries, TIDBitmap::mcxt, TIDBitmap::ptchunks, TIDBitmap::ptpages, TIDBitmap::status, tbm_calculate_entries(), and TBM_EMPTY.

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

◆ tbm_end_iterate()

void tbm_end_iterate ( TBMIterator * iterator )

Definition at line 1598 of file tidbitmap.c.

{
    Assert(iterator && !tbm_exhausted(iterator));
 
    if (iterator->shared)
        tbm_end_shared_iterate(iterator->i.shared_iterator);
    else
        tbm_end_private_iterate(iterator->i.private_iterator);
 
    *iterator = (TBMIterator)
    {
        0
    };
}

References Assert(), TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_end_private_iterate(), tbm_end_shared_iterate(), and tbm_exhausted().

Referenced by ExecEndBitmapHeapScan(), and ExecReScanBitmapHeapScan().

◆ tbm_end_private_iterate()

void tbm_end_private_iterate ( TBMPrivateIterator * iterator )

Definition at line 1151 of file tidbitmap.c.

{
    pfree(iterator);
}

References pfree().

Referenced by entryGetItem(), ginFreeScanKeys(), startScanEntry(), and tbm_end_iterate().

◆ tbm_end_shared_iterate()

void tbm_end_shared_iterate ( TBMSharedIterator * iterator )

Definition at line 1163 of file tidbitmap.c.

{
    pfree(iterator);
}

References pfree().

Referenced by tbm_end_iterate().

◆ tbm_exhausted()

static bool tbm_exhausted ( TBMIterator * iterator )

inlinestatic

Definition at line 118 of file tidbitmap.h.

{
    /*
     * It doesn't matter if we check the private or shared iterator here. If
     * tbm_end_iterate() was called, they will be NULL
     */
    return !iterator->i.private_iterator;
}

References TBMIterator::i, and TBMIterator::private_iterator.

Referenced by ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), and tbm_end_iterate().

◆ tbm_extract_page_tuple()

int tbm_extract_page_tuple	(	TBMIterateResult *	iteritem,
		OffsetNumber *	offsets,
		uint32	max_offsets
	)

Definition at line 902 of file tidbitmap.c.

{
    PagetableEntry *page = iteritem->internal_page;
    int         wordnum;
    int         ntuples = 0;
 
    for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
    {
        bitmapword  w = page->words[wordnum];
 
        if (w != 0)
        {
            int         off = wordnum * BITS_PER_BITMAPWORD + 1;
 
            while (w != 0)
            {
                if (w & 1)
                {
                    if (ntuples < max_offsets)
                        offsets[ntuples] = (OffsetNumber) off;
                    ntuples++;
                }
                off++;
                w >>= 1;
            }
        }
    }
 
    return ntuples;
}

References BITS_PER_BITMAPWORD, TBMIterateResult::internal_page, PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by BitmapHeapScanNextBlock(), and entryGetItem().

◆ tbm_free()

void tbm_free ( TIDBitmap * tbm )

Definition at line 312 of file tidbitmap.c.

{
    if (tbm->pagetable)
        pagetable_destroy(tbm->pagetable);
    if (tbm->spages)
        pfree(tbm->spages);
    if (tbm->schunks)
        pfree(tbm->schunks);
    pfree(tbm);
}

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

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

◆ tbm_free_shared_area()

void tbm_free_shared_area	(	dsa_area *	dsa,
		dsa_pointer	dp
	)

Definition at line 331 of file tidbitmap.c.

{
    TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
    PTEntryArray *ptbase;
    PTIterationArray *ptpages;
    PTIterationArray *ptchunks;
 
    if (DsaPointerIsValid(istate->pagetable))
    {
        ptbase = dsa_get_address(dsa, istate->pagetable);
        if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
            dsa_free(dsa, istate->pagetable);
    }
    if (DsaPointerIsValid(istate->spages))
    {
        ptpages = dsa_get_address(dsa, istate->spages);
        if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
            dsa_free(dsa, istate->spages);
    }
    if (DsaPointerIsValid(istate->schunks))
    {
        ptchunks = dsa_get_address(dsa, istate->schunks);
        if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
            dsa_free(dsa, istate->schunks);
    }
 
    dsa_free(dsa, dp);
}

References dsa_free(), dsa_get_address(), DsaPointerIsValid, TBMSharedIteratorState::pagetable, pg_atomic_sub_fetch_u32(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunks, and TBMSharedIteratorState::spages.

Referenced by ExecBitmapHeapReInitializeDSM().

◆ tbm_intersect()

void tbm_intersect	(	TIDBitmap *	a,
		const TIDBitmap *	b
	)

Definition at line 530 of file tidbitmap.c.

{
    Assert(!a->iterating);
    /* Nothing to do if a is empty */
    if (a->nentries == 0)
        return;
    /* Scan through chunks and pages in a, try to match to b */
    if (a->status == TBM_ONE_PAGE)
    {
        if (tbm_intersect_page(a, &a->entry1, b))
        {
            /* Page is now empty, remove it from a */
            Assert(!a->entry1.ischunk);
            a->npages--;
            a->nentries--;
            Assert(a->nentries == 0);
            a->status = TBM_EMPTY;
        }
    }
    else
    {
        pagetable_iterator i;
        PagetableEntry *apage;
 
        Assert(a->status == TBM_HASH);
        pagetable_start_iterate(a->pagetable, &i);
        while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
        {
            if (tbm_intersect_page(a, apage, b))
            {
                /* Page or chunk is now empty, remove it from a */
                if (apage->ischunk)
                    a->nchunks--;
                else
                    a->npages--;
                a->nentries--;
                if (!pagetable_delete(a->pagetable, apage->blockno))
                    elog(ERROR, "hash table corrupted");
            }
        }
    }
}

References a, Assert(), b, PagetableEntry::blockno, elog, ERROR, i, PagetableEntry::ischunk, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

◆ tbm_is_empty()

bool tbm_is_empty ( const TIDBitmap * tbm )

Definition at line 660 of file tidbitmap.c.

{
    return (tbm->nentries == 0);
}

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

◆ tbm_iterate()

bool tbm_iterate	(	TBMIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 1618 of file tidbitmap.c.

{
    Assert(iterator);
    Assert(tbmres);
 
    if (iterator->shared)
        return tbm_shared_iterate(iterator->i.shared_iterator, tbmres);
    else
        return tbm_private_iterate(iterator->i.private_iterator, tbmres);
}

References Assert(), TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_private_iterate(), and tbm_shared_iterate().

Referenced by bitmapheap_stream_read_next().

◆ tbm_prepare_shared_iterate()

dsa_pointer tbm_prepare_shared_iterate ( TIDBitmap * tbm )

Definition at line 755 of file tidbitmap.c.

{
    dsa_pointer dp;
    TBMSharedIteratorState *istate;
    PTEntryArray *ptbase = NULL;
    PTIterationArray *ptpages = NULL;
    PTIterationArray *ptchunks = NULL;
 
    Assert(tbm->dsa != NULL);
    Assert(tbm->iterating != TBM_ITERATING_PRIVATE);
 
    /*
     * Allocate TBMSharedIteratorState from DSA to hold the shared members and
     * lock, this will also be used by multiple worker for shared iterate.
     */
    dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
    istate = dsa_get_address(tbm->dsa, dp);
 
    /*
     * If we're not already iterating, create and fill the sorted page lists.
     * (If we are, the sorted page lists are already stored in the TIDBitmap,
     * and we can just reuse them.)
     */
    if (tbm->iterating == TBM_NOT_ITERATING)
    {
        pagetable_iterator i;
        PagetableEntry *page;
        int         idx;
        int         npages;
        int         nchunks;
 
        /*
         * Allocate the page and chunk array memory from the DSA to share
         * across multiple processes.
         */
        if (tbm->npages)
        {
            tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
                                        tbm->npages * sizeof(int));
            ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
            pg_atomic_init_u32(&ptpages->refcount, 0);
        }
        if (tbm->nchunks)
        {
            tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
                                         tbm->nchunks * sizeof(int));
            ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
            pg_atomic_init_u32(&ptchunks->refcount, 0);
        }
 
        /*
         * If TBM status is TBM_HASH then iterate over the pagetable and
         * convert it to page and chunk arrays.  But if it's in the
         * TBM_ONE_PAGE mode then directly allocate the space for one entry
         * from the DSA.
         */
        npages = nchunks = 0;
        if (tbm->status == TBM_HASH)
        {
            ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
 
            pagetable_start_iterate(tbm->pagetable, &i);
            while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
            {
                idx = page - ptbase->ptentry;
                if (page->ischunk)
                    ptchunks->index[nchunks++] = idx;
                else
                    ptpages->index[npages++] = idx;
            }
 
            Assert(npages == tbm->npages);
            Assert(nchunks == tbm->nchunks);
        }
        else if (tbm->status == TBM_ONE_PAGE)
        {
            /*
             * In one page mode allocate the space for one pagetable entry,
             * initialize it, and directly store its index (i.e. 0) in the
             * page array.
             */
            tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
                                             sizeof(PagetableEntry));
            ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
            memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
            ptpages->index[0] = 0;
        }
 
        if (ptbase != NULL)
            pg_atomic_init_u32(&ptbase->refcount, 0);
        if (npages > 1)
            qsort_arg(ptpages->index, npages, sizeof(int),
                      tbm_shared_comparator, ptbase->ptentry);
        if (nchunks > 1)
            qsort_arg(ptchunks->index, nchunks, sizeof(int),
                      tbm_shared_comparator, ptbase->ptentry);
    }
 
    /*
     * Store the TBM members in the shared state so that we can share them
     * across multiple processes.
     */
    istate->nentries = tbm->nentries;
    istate->maxentries = tbm->maxentries;
    istate->npages = tbm->npages;
    istate->nchunks = tbm->nchunks;
    istate->pagetable = tbm->dsapagetable;
    istate->spages = tbm->ptpages;
    istate->schunks = tbm->ptchunks;
 
    ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
    ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
    ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
 
    /*
     * For every shared iterator referring to pagetable and iterator array,
     * increase the refcount by 1 so that while freeing the shared iterator we
     * don't free pagetable and iterator array until its refcount becomes 0.
     */
    if (ptbase != NULL)
        pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
    if (ptpages != NULL)
        pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
    if (ptchunks != NULL)
        pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
 
    /* Initialize the iterator lock */
    LWLockInitialize(&istate->lock, LWTRANCHE_SHARED_TIDBITMAP);
 
    /* Initialize the shared iterator state */
    istate->schunkbit = 0;
    istate->schunkptr = 0;
    istate->spageptr = 0;
 
    tbm->iterating = TBM_ITERATING_SHARED;
 
    return dp;
}

Referenced by BitmapTableScanSetup().

◆ tbm_private_iterate()

bool tbm_private_iterate	(	TBMPrivateIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 978 of file tidbitmap.c.

{
    TIDBitmap  *tbm = iterator->tbm;
 
    Assert(tbm->iterating == TBM_ITERATING_PRIVATE);
 
    /*
     * If lossy chunk pages remain, make sure we've advanced schunkptr/
     * schunkbit to the next set bit.
     */
    while (iterator->schunkptr < tbm->nchunks)
    {
        PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
        int         schunkbit = iterator->schunkbit;
 
        tbm_advance_schunkbit(chunk, &schunkbit);
        if (schunkbit < PAGES_PER_CHUNK)
        {
            iterator->schunkbit = schunkbit;
            break;
        }
        /* advance to next chunk */
        iterator->schunkptr++;
        iterator->schunkbit = 0;
    }
 
    /*
     * If both chunk and per-page data remain, must output the numerically
     * earlier page.
     */
    if (iterator->schunkptr < tbm->nchunks)
    {
        PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
        BlockNumber chunk_blockno;
 
        chunk_blockno = chunk->blockno + iterator->schunkbit;
        if (iterator->spageptr >= tbm->npages ||
            chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
        {
            /* Return a lossy page indicator from the chunk */
            tbmres->blockno = chunk_blockno;
            tbmres->lossy = true;
            tbmres->recheck = true;
            tbmres->internal_page = NULL;
            iterator->schunkbit++;
            return true;
        }
    }
 
    if (iterator->spageptr < tbm->npages)
    {
        PagetableEntry *page;
 
        /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
        if (tbm->status == TBM_ONE_PAGE)
            page = &tbm->entry1;
        else
            page = tbm->spages[iterator->spageptr];
 
        tbmres->internal_page = page;
        tbmres->blockno = page->blockno;
        tbmres->lossy = false;
        tbmres->recheck = page->recheck;
        iterator->spageptr++;
        return true;
    }
 
    /* Nothing more in the bitmap */
    tbmres->blockno = InvalidBlockNumber;
    return false;
}

References Assert(), PagetableEntry::blockno, TBMIterateResult::blockno, TIDBitmap::entry1, TBMIterateResult::internal_page, InvalidBlockNumber, TIDBitmap::iterating, TBMIterateResult::lossy, TIDBitmap::nchunks, TIDBitmap::npages, PAGES_PER_CHUNK, PagetableEntry::recheck, TBMIterateResult::recheck, TBMPrivateIterator::schunkbit, TBMPrivateIterator::schunkptr, TIDBitmap::schunks, TBMPrivateIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMPrivateIterator::tbm, tbm_advance_schunkbit(), TBM_ITERATING_PRIVATE, and TBM_ONE_PAGE.

Referenced by entryGetItem(), and tbm_iterate().

◆ tbm_shared_iterate()

bool tbm_shared_iterate	(	TBMSharedIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 1058 of file tidbitmap.c.

{
    TBMSharedIteratorState *istate = iterator->state;
    PagetableEntry *ptbase = NULL;
    int        *idxpages = NULL;
    int        *idxchunks = NULL;
 
    if (iterator->ptbase != NULL)
        ptbase = iterator->ptbase->ptentry;
    if (iterator->ptpages != NULL)
        idxpages = iterator->ptpages->index;
    if (iterator->ptchunks != NULL)
        idxchunks = iterator->ptchunks->index;
 
    /* Acquire the LWLock before accessing the shared members */
    LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
 
    /*
     * If lossy chunk pages remain, make sure we've advanced schunkptr/
     * schunkbit to the next set bit.
     */
    while (istate->schunkptr < istate->nchunks)
    {
        PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
        int         schunkbit = istate->schunkbit;
 
        tbm_advance_schunkbit(chunk, &schunkbit);
        if (schunkbit < PAGES_PER_CHUNK)
        {
            istate->schunkbit = schunkbit;
            break;
        }
        /* advance to next chunk */
        istate->schunkptr++;
        istate->schunkbit = 0;
    }
 
    /*
     * If both chunk and per-page data remain, must output the numerically
     * earlier page.
     */
    if (istate->schunkptr < istate->nchunks)
    {
        PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
        BlockNumber chunk_blockno;
 
        chunk_blockno = chunk->blockno + istate->schunkbit;
 
        if (istate->spageptr >= istate->npages ||
            chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
        {
            /* Return a lossy page indicator from the chunk */
            tbmres->blockno = chunk_blockno;
            tbmres->lossy = true;
            tbmres->recheck = true;
            tbmres->internal_page = NULL;
            istate->schunkbit++;
 
            LWLockRelease(&istate->lock);
            return true;
        }
    }
 
    if (istate->spageptr < istate->npages)
    {
        PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
 
        tbmres->internal_page = page;
        tbmres->blockno = page->blockno;
        tbmres->lossy = false;
        tbmres->recheck = page->recheck;
        istate->spageptr++;
 
        LWLockRelease(&istate->lock);
 
        return true;
    }
 
    LWLockRelease(&istate->lock);
 
    /* Nothing more in the bitmap */
    tbmres->blockno = InvalidBlockNumber;
    return false;
}

References PagetableEntry::blockno, TBMIterateResult::blockno, PTIterationArray::index, TBMIterateResult::internal_page, InvalidBlockNumber, TBMSharedIteratorState::lock, TBMIterateResult::lossy, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, PAGES_PER_CHUNK, TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, PTEntryArray::ptentry, TBMSharedIterator::ptpages, PagetableEntry::recheck, TBMIterateResult::recheck, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::spageptr, TBMSharedIterator::state, and tbm_advance_schunkbit().

Referenced by tbm_iterate().

◆ tbm_union()

void tbm_union	(	TIDBitmap *	a,
		const TIDBitmap *	b
	)

Definition at line 448 of file tidbitmap.c.

{
    Assert(!a->iterating);
    /* Nothing to do if b is empty */
    if (b->nentries == 0)
        return;
    /* Scan through chunks and pages in b, merge into a */
    if (b->status == TBM_ONE_PAGE)
        tbm_union_page(a, &b->entry1);
    else
    {
        pagetable_iterator i;
        PagetableEntry *bpage;
 
        Assert(b->status == TBM_HASH);
        pagetable_start_iterate(b->pagetable, &i);
        while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
            tbm_union_page(a, bpage);
    }
}

References a, Assert(), b, i, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().

Data Structures

Macros

Typedefs

Functions