PostgreSQL Source Code: src/include/nodes/tidbitmap.h Source File

PostgreSQL Source Code git master
tidbitmap.h
Go to the documentation of this file.
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
83extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa);
84extern void tbm_free(TIDBitmap *tbm);
85extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp);
86
87extern void tbm_add_tuples(TIDBitmap *tbm,
88 const ItemPointer tids, int ntids,
89 bool recheck);
90extern void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno);
91
92extern void tbm_union(TIDBitmap *a, const TIDBitmap *b);
93extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b);
94
95extern int tbm_extract_page_tuple(TBMIterateResult *iteritem,
96 OffsetNumber *offsets,
97 uint32 max_offsets);
98
99extern bool tbm_is_empty(const TIDBitmap *tbm);
100
101extern TBMPrivateIterator *tbm_begin_private_iterate(TIDBitmap *tbm);
102extern dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm);
103extern bool tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres);
104extern bool tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres);
105extern void tbm_end_private_iterate(TBMPrivateIterator *iterator);
106extern void tbm_end_shared_iterate(TBMSharedIterator *iterator);
107extern TBMSharedIterator *tbm_attach_shared_iterate(dsa_area *dsa,
108 dsa_pointer dp);
109extern int tbm_calculate_entries(Size maxbytes);
110
111extern TBMIterator tbm_begin_iterate(TIDBitmap *tbm,
112 dsa_area *dsa, dsa_pointer dsp);
113extern void tbm_end_iterate(TBMIterator *iterator);
114
115extern bool tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres);
116
117static inline bool
118 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 return !iterator->i.private_iterator;
125}
126
127#endif /* TIDBITMAP_H */
uint32 BlockNumber
Definition: block.h:31
uint32_t uint32
Definition: c.h:538
size_t Size
Definition: c.h:610
uint64 dsa_pointer
Definition: dsa.h:62
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
uint16 OffsetNumber
Definition: off.h:24
bool recheck
Definition: tidbitmap.h:71
void * internal_page
Definition: tidbitmap.h:78
BlockNumber blockno
Definition: tidbitmap.h:63
TBMSharedIterator * shared_iterator
Definition: tidbitmap.h:56
union TBMIterator::@111 i
TBMPrivateIterator * private_iterator
Definition: tidbitmap.h:55
bool shared
Definition: tidbitmap.h:52
Definition: dsa.c:348
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:312
struct TBMIterateResult TBMIterateResult
bool tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres)
Definition: tidbitmap.c:1618
bool tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres)
Definition: tidbitmap.c:1058
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:367
bool tbm_is_empty(const TIDBitmap *tbm)
Definition: tidbitmap.c:660
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1598
void tbm_end_shared_iterate(TBMSharedIterator *iterator)
Definition: tidbitmap.c:1163
struct TBMIterator TBMIterator
dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:755
void tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
Definition: tidbitmap.c:530
void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp)
Definition: tidbitmap.c:331
bool tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres)
Definition: tidbitmap.c:978
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:433
TBMSharedIterator * tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
Definition: tidbitmap.c:1466
TBMIterator tbm_begin_iterate(TIDBitmap *tbm, dsa_area *dsa, dsa_pointer dsp)
Definition: tidbitmap.c:1575
int tbm_extract_page_tuple(TBMIterateResult *iteritem, OffsetNumber *offsets, uint32 max_offsets)
Definition: tidbitmap.c:902
void tbm_union(TIDBitmap *a, const TIDBitmap *b)
Definition: tidbitmap.c:448
void tbm_end_private_iterate(TBMPrivateIterator *iterator)
Definition: tidbitmap.c:1151
TIDBitmap * tbm_create(Size maxbytes, dsa_area *dsa)
Definition: tidbitmap.c:256
TBMPrivateIterator * tbm_begin_private_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:679
int tbm_calculate_entries(Size maxbytes)
Definition: tidbitmap.c:1546
static bool tbm_exhausted(TBMIterator *iterator)
Definition: tidbitmap.h:118

AltStyle によって変換されたページ (->オリジナル) /