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 "access/htup_details.h" 26 : #include "storage/itemptr.h" 27 : #include "utils/dsa.h" 28 : 29 : /* 30 : * The maximum number of tuples per page is not large (typically 256 with 31 : * 8K pages, or 1024 with 32K pages). So there's not much point in making 32 : * the per-page bitmaps variable size. We just legislate that the size 33 : * is this: 34 : */ 35 : #define TBM_MAX_TUPLES_PER_PAGE MaxHeapTuplesPerPage 36 : 37 : /* 38 : * Actual bitmap representation is private to tidbitmap.c. Callers can 39 : * do IsA(x, TIDBitmap) on it, but nothing else. 40 : */ 41 : typedef struct TIDBitmap TIDBitmap; 42 : 43 : /* Likewise, TBMPrivateIterator is private */ 44 : typedef struct TBMPrivateIterator TBMPrivateIterator; 45 : typedef struct TBMSharedIterator TBMSharedIterator; 46 : 47 : /* 48 : * Callers with both private and shared implementations can use this unified 49 : * API. 50 : */ 51 : typedef struct TBMIterator 52 : { 53 : bool shared; 54 : union 55 : { 56 : TBMPrivateIterator *private_iterator; 57 : TBMSharedIterator *shared_iterator; 58 : } i; 59 : } TBMIterator; 60 : 61 : /* Result structure for tbm_iterate */ 62 : typedef struct TBMIterateResult 63 : { 64 : BlockNumber blockno; /* block number containing tuples */ 65 : 66 : bool lossy; 67 : 68 : /* 69 : * Whether or not the tuples should be rechecked. This is always true if 70 : * the page is lossy but may also be true if the query requires recheck. 71 : */ 72 : bool recheck; 73 : 74 : /* 75 : * Pointer to the page containing the bitmap for this block. It is a void * 76 : * to avoid exposing the details of the tidbitmap PagetableEntry to API 77 : * users. 78 : */ 79 : void *internal_page; 80 : } TBMIterateResult; 81 : 82 : /* function prototypes in nodes/tidbitmap.c */ 83 : 84 : extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa); 85 : extern void tbm_free(TIDBitmap *tbm); 86 : extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp); 87 : 88 : extern void tbm_add_tuples(TIDBitmap *tbm, 89 : const ItemPointer tids, int ntids, 90 : bool recheck); 91 : extern void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno); 92 : 93 : extern void tbm_union(TIDBitmap *a, const TIDBitmap *b); 94 : extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b); 95 : 96 : extern int tbm_extract_page_tuple(TBMIterateResult *iteritem, 97 : OffsetNumber *offsets, 98 : uint32 max_offsets); 99 : 100 : extern bool tbm_is_empty(const TIDBitmap *tbm); 101 : 102 : extern TBMPrivateIterator *tbm_begin_private_iterate(TIDBitmap *tbm); 103 : extern dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm); 104 : extern bool tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres); 105 : extern bool tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres); 106 : extern void tbm_end_private_iterate(TBMPrivateIterator *iterator); 107 : extern void tbm_end_shared_iterate(TBMSharedIterator *iterator); 108 : extern TBMSharedIterator *tbm_attach_shared_iterate(dsa_area *dsa, 109 : dsa_pointer dp); 110 : extern int tbm_calculate_entries(Size maxbytes); 111 : 112 : extern TBMIterator tbm_begin_iterate(TIDBitmap *tbm, 113 : dsa_area *dsa, dsa_pointer dsp); 114 : extern void tbm_end_iterate(TBMIterator *iterator); 115 : 116 : extern bool tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres); 117 : 118 : static inline bool 119 25496 : tbm_exhausted(TBMIterator *iterator) 120 : { 121 : /* 122 : * It doesn't matter if we check the private or shared iterator here. If 123 : * tbm_end_iterate() was called, they will be NULL 124 : */ 125 25496 : return !iterator->i.private_iterator; 126 : } 127 : 128 : #endif /* TIDBITMAP_H */