Debian Codegraph @

src/include/nodes/tidbitmap.h

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