tidbitmap.h File Reference

#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:

Go to the source code of this file.

Data Structures
struct	TBMIterator
struct	TBMIterateResult

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 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)
TBMPrivateIterator *	tbm_begin_private_iterate (TIDBitmap *tbm)
dsa_pointer	tbm_prepare_shared_iterate (TIDBitmap *tbm)
TBMIterateResult *	tbm_private_iterate (TBMPrivateIterator *iterator)
TBMIterateResult *	tbm_shared_iterate (TBMSharedIterator *iterator)
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)
TBMIterateResult *	tbm_iterate (TBMIterator *iterator)
static bool	tbm_exhausted (TBMIterator *iterator)

Typedef Documentation

TBMIterateResult

typedef struct TBMIterateResult TBMIterateResult

TBMIterator

typedef struct TBMIterator TBMIterator

TBMPrivateIterator

typedef struct TBMPrivateIterator TBMPrivateIterator

Definition at line 36 of file tidbitmap.h.

TBMSharedIterator

typedef struct TBMSharedIterator TBMSharedIterator

Definition at line 37 of file tidbitmap.h.

TIDBitmap

typedef struct TIDBitmap TIDBitmap

Definition at line 33 of file tidbitmap.h.

Function Documentation

tbm_add_page()

void tbm_add_page	(	TIDBitmap *	tbm,
		BlockNumber	pageno
	)

Definition at line 443 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 ItemPointer	tids,
		int	ntids,
		bool	recheck
	)

Definition at line 377 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 > 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, MAX_TUPLES_PER_PAGE, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), 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 1462 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) +
                                             MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
 
    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(), MAX_TUPLES_PER_PAGE, 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 1572 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 689 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) +
                                             MAX_TUPLES_PER_PAGE *
                                             sizeof(OffsetNumber));
    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, MAX_TUPLES_PER_PAGE, 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 1543 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 266 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 1595 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 BitmapPrefetch(), ExecEndBitmapHeapScan(), and ExecReScanBitmapHeapScan().

tbm_end_private_iterate()

void tbm_end_private_iterate

(

TBMPrivateIterator *

iterator

)

Definition at line 1147 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 1159 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 96 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 BitmapAdjustPrefetchIterator(), BitmapHeapNext(), BitmapPrefetch(), ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), and tbm_end_iterate().

tbm_free()

void tbm_free

(

TIDBitmap *

tbm

)

Definition at line 322 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 341 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 540 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 670 of file tidbitmap.c.

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

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

tbm_iterate()

TBMIterateResult * tbm_iterate

(

TBMIterator *

iterator

)

Definition at line 1614 of file tidbitmap.c.

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

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

Referenced by BitmapAdjustPrefetchIterator(), BitmapPrefetch(), and heapam_scan_bitmap_next_block().

tbm_prepare_shared_iterate()

dsa_pointer tbm_prepare_shared_iterate

(

TIDBitmap *

tbm

)

Definition at line 767 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;
}

References Assert, TIDBitmap::dsa, dsa_allocate, dsa_allocate0, dsa_get_address(), TIDBitmap::dsapagetable, TIDBitmap::entry1, i, idx(), PTIterationArray::index, PagetableEntry::ischunk, TIDBitmap::iterating, TBMSharedIteratorState::lock, LWLockInitialize(), LWTRANCHE_SHARED_TIDBITMAP, TIDBitmap::maxentries, TBMSharedIteratorState::maxentries, TIDBitmap::nchunks, TBMSharedIteratorState::nchunks, TIDBitmap::nentries, TBMSharedIteratorState::nentries, TIDBitmap::npages, TBMSharedIteratorState::npages, TIDBitmap::pagetable, TBMSharedIteratorState::pagetable, pg_atomic_add_fetch_u32(), pg_atomic_init_u32(), TIDBitmap::ptchunks, PTEntryArray::ptentry, TIDBitmap::ptpages, qsort_arg(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spageptr, TBMSharedIteratorState::spages, TIDBitmap::status, TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, TBM_NOT_ITERATING, TBM_ONE_PAGE, and tbm_shared_comparator().

Referenced by BitmapTableScanSetup().

tbm_private_iterate()

TBMIterateResult * tbm_private_iterate

(

TBMPrivateIterator *

iterator

)

Definition at line 972 of file tidbitmap.c.

{
    TIDBitmap  *tbm = iterator->tbm;
    TBMIterateResult *output = &(iterator->output);
 
    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 */
            output->blockno = chunk_blockno;
            output->ntuples = -1;
            output->recheck = true;
            iterator->schunkbit++;
            return output;
        }
    }
 
    if (iterator->spageptr < tbm->npages)
    {
        PagetableEntry *page;
        int         ntuples;
 
        /* 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];
 
        /* scan bitmap to extract individual offset numbers */
        ntuples = tbm_extract_page_tuple(page, output);
        output->blockno = page->blockno;
        output->ntuples = ntuples;
        output->recheck = page->recheck;
        iterator->spageptr++;
        return output;
    }
 
    /* Nothing more in the bitmap */
    return NULL;
}

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

Referenced by entryGetItem(), and tbm_iterate().

tbm_shared_iterate()

TBMIterateResult * tbm_shared_iterate

(

TBMSharedIterator *

iterator

)

Definition at line 1053 of file tidbitmap.c.

{
    TBMIterateResult *output = &iterator->output;
    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 */
            output->blockno = chunk_blockno;
            output->ntuples = -1;
            output->recheck = true;
            istate->schunkbit++;
 
            LWLockRelease(&istate->lock);
            return output;
        }
    }
 
    if (istate->spageptr < istate->npages)
    {
        PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
        int         ntuples;
 
        /* scan bitmap to extract individual offset numbers */
        ntuples = tbm_extract_page_tuple(page, output);
        output->blockno = page->blockno;
        output->ntuples = ntuples;
        output->recheck = page->recheck;
        istate->spageptr++;
 
        LWLockRelease(&istate->lock);
 
        return output;
    }
 
    LWLockRelease(&istate->lock);
 
    /* Nothing more in the bitmap */
    return NULL;
}

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

Referenced by tbm_iterate().

tbm_union()

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

Definition at line 458 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().