Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tidbitmap.h
       4             :  *    PostgreSQL tuple-id (TID) bitmap package
       5             :  *
       6             :  * This module provides bitmap data structures that are spiritually
       7             :  * similar to Bitmapsets, but are specially adapted to store sets of
       8             :  * tuple identifiers (TIDs), or ItemPointers.  In particular, the division
       9             :  * of an ItemPointer into BlockNumber and OffsetNumber is catered for.
      10             :  * Also, since we wish to be able to store very large tuple sets in
      11             :  * memory with this data structure, we support "lossy" storage, in which
      12             :  * we no longer remember individual tuple offsets on a page but only the
      13             :  * fact that a particular page needs to be visited.
      14             :  *
      15             :  *
      16             :  * Copyright (c) 2003-2025, PostgreSQL Global Development Group
      17             :  *
      18             :  * src/include/nodes/tidbitmap.h
      19             :  *
      20             :  *-------------------------------------------------------------------------
      21             :  */
      22             : #ifndef TIDBITMAP_H
      23             : #define TIDBITMAP_H
      24             : 
      25             : #include "storage/itemptr.h"
      26             : #include "utils/dsa.h"
      27             : 
      28             : /*
      29             :  * The maximum number of tuples per page is not large (typically 256 with
      30             :  * 8K pages, or 1024 with 32K pages).  So there's not much point in making
      31             :  * the per-page bitmaps variable size.  We just legislate that the size
      32             :  * is this:
      33             :  */
      34             : #define TBM_MAX_TUPLES_PER_PAGE  MaxHeapTuplesPerPage
      35             : 
      36             : /*
      37             :  * Actual bitmap representation is private to tidbitmap.c.  Callers can
      38             :  * do IsA(x, TIDBitmap) on it, but nothing else.
      39             :  */
      40             : typedef struct TIDBitmap TIDBitmap;
      41             : 
      42             : /* Likewise, TBMPrivateIterator is private */
      43             : typedef struct TBMPrivateIterator TBMPrivateIterator;
      44             : typedef struct TBMSharedIterator TBMSharedIterator;
      45             : 
      46             : /*
      47             :  * Callers with both private and shared implementations can use this unified
      48             :  * API.
      49             :  */
      50             : typedef struct TBMIterator
      51             : {
      52             :     bool        shared;
      53             :     union
      54             :     {
      55             :         TBMPrivateIterator *private_iterator;
      56             :         TBMSharedIterator *shared_iterator;
      57             :     }           i;
      58             : } TBMIterator;
      59             : 
      60             : /* Result structure for tbm_iterate */
      61             : typedef struct TBMIterateResult
      62             : {
      63             :     BlockNumber blockno;        /* block number containing tuples */
      64             : 
      65             :     bool        lossy;
      66             : 
      67             :     /*
      68             :      * Whether or not the tuples should be rechecked. This is always true if
      69             :      * the page is lossy but may also be true if the query requires recheck.
      70             :      */
      71             :     bool        recheck;
      72             : 
      73             :     /*
      74             :      * Pointer to the page containing the bitmap for this block. It is a void *
      75             :      * to avoid exposing the details of the tidbitmap PagetableEntry to API
      76             :      * users.
      77             :      */
      78             :     void       *internal_page;
      79             : } TBMIterateResult;
      80             : 
      81             : /* function prototypes in nodes/tidbitmap.c */
      82             : 
      83             : extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa);
      84             : extern void tbm_free(TIDBitmap *tbm);
      85             : extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp);
      86             : 
      87             : extern void tbm_add_tuples(TIDBitmap *tbm,
      88             :                            const ItemPointer tids, int ntids,
      89             :                            bool recheck);
      90             : extern void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno);
      91             : 
      92             : extern void tbm_union(TIDBitmap *a, const TIDBitmap *b);
      93             : extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b);
      94             : 
      95             : extern int  tbm_extract_page_tuple(TBMIterateResult *iteritem,
      96             :                                    OffsetNumber *offsets,
      97             :                                    uint32 max_offsets);
      98             : 
      99             : extern bool tbm_is_empty(const TIDBitmap *tbm);
     100             : 
     101             : extern TBMPrivateIterator *tbm_begin_private_iterate(TIDBitmap *tbm);
     102             : extern dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm);
     103             : extern bool tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres);
     104             : extern bool tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres);
     105             : extern void tbm_end_private_iterate(TBMPrivateIterator *iterator);
     106             : extern void tbm_end_shared_iterate(TBMSharedIterator *iterator);
     107             : extern TBMSharedIterator *tbm_attach_shared_iterate(dsa_area *dsa,
     108             :                                                     dsa_pointer dp);
     109             : extern int  tbm_calculate_entries(Size maxbytes);
     110             : 
     111             : extern TBMIterator tbm_begin_iterate(TIDBitmap *tbm,
     112             :                                      dsa_area *dsa, dsa_pointer dsp);
     113             : extern void tbm_end_iterate(TBMIterator *iterator);
     114             : 
     115             : extern bool tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres);
     116             : 
     117             : static inline bool
     118       20162 : tbm_exhausted(TBMIterator *iterator)
     119             : {
     120             :     /*
     121             :      * It doesn't matter if we check the private or shared iterator here. If
     122             :      * tbm_end_iterate() was called, they will be NULL
     123             :      */
     124       20162 :     return !iterator->i.private_iterator;
     125             : }
     126             : 
     127             : #endif                          /* TIDBITMAP_H */