/src/postgres/src/include/nodes/tidbitmap.h
Line | Count | Source |
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 | 0 | #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 | | tbm_exhausted(TBMIterator *iterator) |
119 | 0 | { |
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 | 0 | return !iterator->i.private_iterator; |
125 | 0 | } Unexecuted instantiation: fuzzer_initialize.c:tbm_exhausted Unexecuted instantiation: brin.c:tbm_exhausted Unexecuted instantiation: detoast.c:tbm_exhausted Unexecuted instantiation: reloptions.c:tbm_exhausted Unexecuted instantiation: toast_internals.c:tbm_exhausted Unexecuted instantiation: ginbtree.c:tbm_exhausted Unexecuted instantiation: ginbulk.c:tbm_exhausted Unexecuted instantiation: gindatapage.c:tbm_exhausted Unexecuted instantiation: ginentrypage.c:tbm_exhausted Unexecuted instantiation: ginfast.c:tbm_exhausted Unexecuted instantiation: ginget.c:tbm_exhausted Unexecuted instantiation: gininsert.c:tbm_exhausted Unexecuted instantiation: ginlogic.c:tbm_exhausted Unexecuted instantiation: ginpostinglist.c:tbm_exhausted Unexecuted instantiation: ginscan.c:tbm_exhausted Unexecuted instantiation: ginutil.c:tbm_exhausted Unexecuted instantiation: ginvacuum.c:tbm_exhausted Unexecuted instantiation: ginvalidate.c:tbm_exhausted Unexecuted instantiation: ginxlog.c:tbm_exhausted Unexecuted instantiation: gistbuild.c:tbm_exhausted Unexecuted instantiation: gistget.c:tbm_exhausted Unexecuted instantiation: gistscan.c:tbm_exhausted Unexecuted instantiation: hash.c:tbm_exhausted Unexecuted instantiation: hashsearch.c:tbm_exhausted Unexecuted instantiation: hashutil.c:tbm_exhausted Unexecuted instantiation: heapam.c:tbm_exhausted Unexecuted instantiation: heapam_handler.c:tbm_exhausted Unexecuted instantiation: heapam_indexscan.c:tbm_exhausted Unexecuted instantiation: heapam_visibility.c:tbm_exhausted Unexecuted instantiation: heapam_xlog.c:tbm_exhausted Unexecuted instantiation: heaptoast.c:tbm_exhausted Unexecuted instantiation: hio.c:tbm_exhausted Unexecuted instantiation: pruneheap.c:tbm_exhausted Unexecuted instantiation: rewriteheap.c:tbm_exhausted Unexecuted instantiation: vacuumlazy.c:tbm_exhausted Unexecuted instantiation: genam.c:tbm_exhausted Unexecuted instantiation: indexam.c:tbm_exhausted Unexecuted instantiation: nbtdedup.c:tbm_exhausted Unexecuted instantiation: nbtinsert.c:tbm_exhausted Unexecuted instantiation: nbtpage.c:tbm_exhausted Unexecuted instantiation: nbtpreprocesskeys.c:tbm_exhausted Unexecuted instantiation: nbtreadpage.c:tbm_exhausted Unexecuted instantiation: nbtree.c:tbm_exhausted Unexecuted instantiation: nbtsearch.c:tbm_exhausted Unexecuted instantiation: nbtsort.c:tbm_exhausted Unexecuted instantiation: nbtsplitloc.c:tbm_exhausted Unexecuted instantiation: nbtutils.c:tbm_exhausted Unexecuted instantiation: spgdoinsert.c:tbm_exhausted Unexecuted instantiation: spginsert.c:tbm_exhausted Unexecuted instantiation: spgkdtreeproc.c:tbm_exhausted Unexecuted instantiation: spgproc.c:tbm_exhausted Unexecuted instantiation: spgquadtreeproc.c:tbm_exhausted Unexecuted instantiation: spgscan.c:tbm_exhausted Unexecuted instantiation: spgutils.c:tbm_exhausted Unexecuted instantiation: spgvacuum.c:tbm_exhausted Unexecuted instantiation: spgxlog.c:tbm_exhausted Unexecuted instantiation: tableam.c:tbm_exhausted Unexecuted instantiation: tableam_indexscan.c:tbm_exhausted Unexecuted instantiation: tableamapi.c:tbm_exhausted Unexecuted instantiation: xact.c:tbm_exhausted Unexecuted instantiation: bootstrap.c:tbm_exhausted Unexecuted instantiation: aclchk.c:tbm_exhausted Unexecuted instantiation: dependency.c:tbm_exhausted Unexecuted instantiation: heap.c:tbm_exhausted Unexecuted instantiation: index.c:tbm_exhausted Unexecuted instantiation: indexing.c:tbm_exhausted Unexecuted instantiation: objectaddress.c:tbm_exhausted Unexecuted instantiation: pg_db_role_setting.c:tbm_exhausted Unexecuted instantiation: pg_publication.c:tbm_exhausted Unexecuted instantiation: pg_subscription.c:tbm_exhausted Unexecuted instantiation: toasting.c:tbm_exhausted Unexecuted instantiation: gram.c:tbm_exhausted Unexecuted instantiation: alter.c:tbm_exhausted Unexecuted instantiation: analyze.c:tbm_exhausted Unexecuted instantiation: constraint.c:tbm_exhausted Unexecuted instantiation: copyfrom.c:tbm_exhausted Unexecuted instantiation: copyfromparse.c:tbm_exhausted Unexecuted instantiation: copyto.c:tbm_exhausted Unexecuted instantiation: createas.c:tbm_exhausted Unexecuted instantiation: dbcommands.c:tbm_exhausted Unexecuted instantiation: event_trigger.c:tbm_exhausted Unexecuted instantiation: explain.c:tbm_exhausted Unexecuted instantiation: indexcmds.c:tbm_exhausted Unexecuted instantiation: matview.c:tbm_exhausted Unexecuted instantiation: repack.c:tbm_exhausted Unexecuted instantiation: tablecmds.c:tbm_exhausted Unexecuted instantiation: tablespace.c:tbm_exhausted Unexecuted instantiation: trigger.c:tbm_exhausted Unexecuted instantiation: typecmds.c:tbm_exhausted Unexecuted instantiation: vacuum.c:tbm_exhausted Unexecuted instantiation: execCurrent.c:tbm_exhausted Unexecuted instantiation: execIndexing.c:tbm_exhausted Unexecuted instantiation: execMain.c:tbm_exhausted Unexecuted instantiation: execPartition.c:tbm_exhausted Unexecuted instantiation: execReplication.c:tbm_exhausted Unexecuted instantiation: execUtils.c:tbm_exhausted Unexecuted instantiation: nodeBitmapAnd.c:tbm_exhausted Unexecuted instantiation: nodeBitmapHeapscan.c:tbm_exhausted Unexecuted instantiation: nodeBitmapIndexscan.c:tbm_exhausted Unexecuted instantiation: nodeBitmapOr.c:tbm_exhausted Unexecuted instantiation: nodeIndexonlyscan.c:tbm_exhausted Unexecuted instantiation: nodeIndexscan.c:tbm_exhausted Unexecuted instantiation: nodeLockRows.c:tbm_exhausted Unexecuted instantiation: nodeModifyTable.c:tbm_exhausted Unexecuted instantiation: nodeSamplescan.c:tbm_exhausted Unexecuted instantiation: nodeSeqscan.c:tbm_exhausted Unexecuted instantiation: nodeTidrangescan.c:tbm_exhausted Unexecuted instantiation: nodeTidscan.c:tbm_exhausted Unexecuted instantiation: spi.c:tbm_exhausted Unexecuted instantiation: copyfuncs.c:tbm_exhausted Unexecuted instantiation: equalfuncs.c:tbm_exhausted Unexecuted instantiation: outfuncs.c:tbm_exhausted Unexecuted instantiation: queryjumblefuncs.c:tbm_exhausted Unexecuted instantiation: readfuncs.c:tbm_exhausted Unexecuted instantiation: tidbitmap.c:tbm_exhausted Unexecuted instantiation: costsize.c:tbm_exhausted Unexecuted instantiation: plancat.c:tbm_exhausted Unexecuted instantiation: partbounds.c:tbm_exhausted Unexecuted instantiation: autovacuum.c:tbm_exhausted Unexecuted instantiation: datachecksum_state.c:tbm_exhausted Unexecuted instantiation: conflict.c:tbm_exhausted Unexecuted instantiation: launcher.c:tbm_exhausted Unexecuted instantiation: reorderbuffer.c:tbm_exhausted Unexecuted instantiation: worker.c:tbm_exhausted Unexecuted instantiation: rewriteHandler.c:tbm_exhausted Unexecuted instantiation: attribute_stats.c:tbm_exhausted Unexecuted instantiation: extended_stats_funcs.c:tbm_exhausted Unexecuted instantiation: relation_stats.c:tbm_exhausted Unexecuted instantiation: bufmgr.c:tbm_exhausted Unexecuted instantiation: utility.c:tbm_exhausted Unexecuted instantiation: geo_spgist.c:tbm_exhausted Unexecuted instantiation: ri_triggers.c:tbm_exhausted Unexecuted instantiation: ruleutils.c:tbm_exhausted Unexecuted instantiation: selfuncs.c:tbm_exhausted Unexecuted instantiation: tid.c:tbm_exhausted Unexecuted instantiation: trigfuncs.c:tbm_exhausted Unexecuted instantiation: tsquery_rewrite.c:tbm_exhausted Unexecuted instantiation: tsvector_op.c:tbm_exhausted Unexecuted instantiation: xml.c:tbm_exhausted Unexecuted instantiation: catcache.c:tbm_exhausted Unexecuted instantiation: evtcache.c:tbm_exhausted Unexecuted instantiation: funccache.c:tbm_exhausted Unexecuted instantiation: relcache.c:tbm_exhausted Unexecuted instantiation: postinit.c:tbm_exhausted Unexecuted instantiation: guc_tables.c:tbm_exhausted Unexecuted instantiation: simple_query_fuzzer.c:tbm_exhausted |
126 | | |
127 | | #endif /* TIDBITMAP_H */ |