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