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 20390 : 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 20390 : return !iterator->i.private_iterator; 125 : } 126 : 127 : #endif /* TIDBITMAP_H */