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

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  )

extern

Definition at line 432 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  )

extern

Definition at line 367 of file tidbitmap.c.

{
    BlockNumber currblk = InvalidBlockNumber;
    PagetableEntry *page = NULL;    /* only valid when currblk is valid */
 
    Assert(tbm->iterating == TBM_NOT_ITERATING);
    for (int 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, fb(), 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  )

extern

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 = palloc0_object(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(), fb(), and palloc0_object.

Referenced by tbm_begin_iterate().

tbm_begin_iterate()

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

extern

Definition at line 1571 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, fb(), TBMIterator::shared, tbm_attach_shared_iterate(), and tbm_begin_private_iterate().

Referenced by BitmapTableScanSetup().

tbm_begin_private_iterate()

TBMPrivateIterator * tbm_begin_private_iterate ( TIDBitmap *  tbm )

extern

Definition at line 676 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 = palloc_object(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, fb(), i, PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::mcxt, MemoryContextAlloc(), TIDBitmap::nchunks, TIDBitmap::npages, TIDBitmap::pagetable, palloc_object, qsort, TIDBitmap::schunks, TIDBitmap::spages, TIDBitmap::status, 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 )

extern

Definition at line 1542 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 fb(), Max, and Min.

Referenced by compute_bitmap_pages(), and tbm_create().

tbm_create()

TIDBitmap * tbm_create ( Size  maxbytes, dsa_area *  dsa  )

extern

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, fb(), 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 )

extern

Definition at line 1594 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, fb(), 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 )

extern

Definition at line 1147 of file tidbitmap.c.

{
    pfree(iterator);
}

References fb(), and pfree().

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

tbm_end_shared_iterate()

void tbm_end_shared_iterate ( TBMSharedIterator *  iterator )

extern

Definition at line 1159 of file tidbitmap.c.

{
    pfree(iterator);
}

References fb(), and 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 fb().

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

tbm_extract_page_tuple()

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

extern

Definition at line 899 of file tidbitmap.c.

{
    PagetableEntry *page = iteritem->internal_page;
    int         ntuples = 0;
 
    for (int 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, fb(), PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by BitmapHeapScanNextBlock(), and entryGetItem().

tbm_free()

void tbm_free ( TIDBitmap *  tbm )

extern

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 fb(), 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  )

extern

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, fb(), pg_atomic_sub_fetch_u32(), PTEntryArray::refcount, and PTIterationArray::refcount.

Referenced by ExecBitmapHeapReInitializeDSM().

tbm_intersect()

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

extern

Definition at line 528 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, elog, ERROR, fb(), i, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

tbm_is_empty()

bool tbm_is_empty ( const TIDBitmap *  tbm )

extern

Definition at line 657 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  )

extern

Definition at line 1614 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, fb(), 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 )

extern

Definition at line 752 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, fb(), i, idx(), PTIterationArray::index, PagetableEntry::ischunk, TIDBitmap::iterating, LWLockInitialize(), TIDBitmap::maxentries, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, TIDBitmap::pagetable, pg_atomic_add_fetch_u32(), pg_atomic_init_u32(), TIDBitmap::ptchunks, PTEntryArray::ptentry, TIDBitmap::ptpages, qsort_arg(), PTEntryArray::refcount, PTIterationArray::refcount, 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()

bool tbm_private_iterate ( TBMPrivateIterator *  iterator, TBMIterateResult *  tbmres  )

extern

Definition at line 974 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, TIDBitmap::entry1, fb(), InvalidBlockNumber, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, PAGES_PER_CHUNK, PagetableEntry::recheck, TIDBitmap::schunks, TIDBitmap::spages, TIDBitmap::status, 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  )

extern

Definition at line 1054 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, fb(), InvalidBlockNumber, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), PAGES_PER_CHUNK, PagetableEntry::recheck, and tbm_advance_schunkbit().

Referenced by tbm_iterate().

tbm_union()

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

extern

Definition at line 447 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, fb(), i, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().