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/*
30 * Actual bitmap representation is private to tidbitmap.c. Callers can
31 * do IsA(x, TIDBitmap) on it, but nothing else.
32 */
33typedef struct TIDBitmap TIDBitmap;
34
35/* Likewise, TBMPrivateIterator is private */
38
39/*
40 * Callers with both private and shared implementations can use this unified
41 * API.
42 */
43typedef struct TBMIterator
44{
45 bool shared;
46 union
47 {
50 } i;
52
53/* Result structure for tbm_iterate */
54typedef struct TBMIterateResult
55{
56 BlockNumber blockno; /* page number containing tuples */
57 int ntuples; /* -1 indicates lossy result */
58 bool recheck; /* should the tuples be rechecked? */
59 /* Note: recheck is always true if ntuples < 0 */
62
63/* function prototypes in nodes/tidbitmap.c */
64
65extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa);
66extern void tbm_free(TIDBitmap *tbm);
67extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp);
68
69extern void tbm_add_tuples(TIDBitmap *tbm,
70 const ItemPointer tids, int ntids,
71 bool recheck);
72extern void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno);
73
74extern void tbm_union(TIDBitmap *a, const TIDBitmap *b);
75extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b);
76
77extern bool tbm_is_empty(const TIDBitmap *tbm);
78
83extern void tbm_end_private_iterate(TBMPrivateIterator *iterator);
84extern void tbm_end_shared_iterate(TBMSharedIterator *iterator);
86 dsa_pointer dp);
87extern int tbm_calculate_entries(Size maxbytes);
88
90 dsa_area *dsa, dsa_pointer dsp);
91extern void tbm_end_iterate(TBMIterator *iterator);
92
94
95static inline bool
97{
98 /*
99 * It doesn't matter if we check the private or shared iterator here. If
100 * tbm_end_iterate() was called, they will be NULL
101 */
102 return !iterator->i.private_iterator;
103}
104
105#endif /* TIDBITMAP_H */
uint32 BlockNumber
Definition: block.h:31
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:420
size_t Size
Definition: c.h:562
uint64 dsa_pointer
Definition: dsa.h:62
int b
Definition: isn.c:69
int a
Definition: isn.c:68
uint16 OffsetNumber
Definition: off.h:24
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:60
BlockNumber blockno
Definition: tidbitmap.h:56
union TBMIterator::@109 i
TBMSharedIterator * shared_iterator
Definition: tidbitmap.h:49
TBMPrivateIterator * private_iterator
Definition: tidbitmap.h:48
bool shared
Definition: tidbitmap.h:45
Definition: dsa.c:348
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:322
struct TBMIterateResult TBMIterateResult
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:377
bool tbm_is_empty(const TIDBitmap *tbm)
Definition: tidbitmap.c:670
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1595
TBMIterateResult * tbm_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1614
void tbm_end_shared_iterate(TBMSharedIterator *iterator)
Definition: tidbitmap.c:1159
TBMIterateResult * tbm_private_iterate(TBMPrivateIterator *iterator)
Definition: tidbitmap.c:972
struct TBMIterator TBMIterator
dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:767
void tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
Definition: tidbitmap.c:540
void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp)
Definition: tidbitmap.c:341
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:443
TBMSharedIterator * tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
Definition: tidbitmap.c:1462
TBMIterator tbm_begin_iterate(TIDBitmap *tbm, dsa_area *dsa, dsa_pointer dsp)
Definition: tidbitmap.c:1572
void tbm_union(TIDBitmap *a, const TIDBitmap *b)
Definition: tidbitmap.c:458
void tbm_end_private_iterate(TBMPrivateIterator *iterator)
Definition: tidbitmap.c:1147
TIDBitmap * tbm_create(Size maxbytes, dsa_area *dsa)
Definition: tidbitmap.c:266
TBMPrivateIterator * tbm_begin_private_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:689
int tbm_calculate_entries(Size maxbytes)
Definition: tidbitmap.c:1543
TBMIterateResult * tbm_shared_iterate(TBMSharedIterator *iterator)
Definition: tidbitmap.c:1053
static bool tbm_exhausted(TBMIterator *iterator)
Definition: tidbitmap.h:96