PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
bitmapset.h
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * bitmapset.h
4 * PostgreSQL generic bitmap set package
5 *
6 * A bitmap set can represent any set of nonnegative integers, although
7 * it is mainly intended for sets where the maximum value is not large,
8 * say at most a few hundred. By convention, we always represent the
9 * empty set by a NULL pointer.
10 *
11 *
12 * Copyright (c) 2003-2025, PostgreSQL Global Development Group
13 *
14 * src/include/nodes/bitmapset.h
15 *
16 *-------------------------------------------------------------------------
17 */
18#ifndef BITMAPSET_H
19#define BITMAPSET_H
20
21#include "nodes/nodes.h"
22
23/*
24 * Forward decl to save including pg_list.h
25 */
26struct List;
27
28/*
29 * Data representation
30 *
31 * Larger bitmap word sizes generally give better performance, so long as
32 * they're not wider than the processor can handle efficiently. We use
33 * 64-bit words if pointers are that large, else 32-bit words.
34 */
35#if SIZEOF_VOID_P >= 8
36
37#define BITS_PER_BITMAPWORD 64
38typedef uint64 bitmapword; /* must be an unsigned type */
39typedef int64 signedbitmapword; /* must be the matching signed type */
40
41#else
42
43#define BITS_PER_BITMAPWORD 32
44typedef uint32 bitmapword; /* must be an unsigned type */
45typedef int32 signedbitmapword; /* must be the matching signed type */
46
47#endif
48
49typedef struct Bitmapset
50{
51 pg_node_attr(custom_copy_equal, special_read_write, no_query_jumble)
52
54 int nwords; /* number of words in array */
55 bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
57
58
59/* result of bms_subset_compare */
60typedef enum
61{
62 BMS_EQUAL, /* sets are equal */
63 BMS_SUBSET1, /* first set is a subset of the second */
64 BMS_SUBSET2, /* second set is a subset of the first */
65 BMS_DIFFERENT, /* neither set is a subset of the other */
67
68/* result of bms_membership */
69typedef enum
70{
71 BMS_EMPTY_SET, /* 0 members */
72 BMS_SINGLETON, /* 1 member */
73 BMS_MULTIPLE, /* >1 member */
75
76/* Select appropriate bit-twiddling functions for bitmap word size */
77#if BITS_PER_BITMAPWORD == 32
78#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w)
79#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w)
80#define bmw_popcount(w) pg_popcount32(w)
81#elif BITS_PER_BITMAPWORD == 64
82#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w)
83#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w)
84#define bmw_popcount(w) pg_popcount64(w)
85#else
86#error "invalid BITS_PER_BITMAPWORD"
87#endif
88
89
90/*
91 * function prototypes in nodes/bitmapset.c
92 */
93
94extern Bitmapset *bms_copy(const Bitmapset *a);
95extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
96extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
97extern Bitmapset *bms_make_singleton(int x);
98extern void bms_free(Bitmapset *a);
99
100extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
101extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
102extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
103extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
105extern bool bms_is_member(int x, const Bitmapset *a);
106extern int bms_member_index(Bitmapset *a, int x);
107extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
108extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
109extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
110extern int bms_singleton_member(const Bitmapset *a);
111extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
112extern int bms_num_members(const Bitmapset *a);
113
114/* optimized tests when we don't need to know exact membership count: */
116
117/* NULL is now the only allowed representation of an empty bitmapset */
118#define bms_is_empty(a) ((a) == NULL)
119
120/* these routines recycle (modify or free) their non-const inputs: */
121
122extern Bitmapset *bms_add_member(Bitmapset *a, int x);
123extern Bitmapset *bms_del_member(Bitmapset *a, int x);
126extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
130
131/* support for iterating through the integer elements of a set: */
132extern int bms_next_member(const Bitmapset *a, int prevbit);
133extern int bms_prev_member(const Bitmapset *a, int prevbit);
134
135/* support for hashtables using Bitmapsets as keys: */
136extern uint32 bms_hash_value(const Bitmapset *a);
137extern uint32 bitmap_hash(const void *key, Size keysize);
138extern int bitmap_match(const void *key1, const void *key2, Size keysize);
139
140#endif /* BITMAPSET_H */
Bitmapset * bms_replace_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:972
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1367
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1109
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
uint32 bitmap_hash(const void *key, Size keysize)
Definition: bitmapset.c:1432
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:445
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1306
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1416
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:868
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:672
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:751
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
int32 signedbitmapword
Definition: bitmapset.h:45
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
BMS_Comparison
Definition: bitmapset.h:61
@ BMS_DIFFERENT
Definition: bitmapset.h:65
@ BMS_SUBSET1
Definition: bitmapset.h:63
@ BMS_EQUAL
Definition: bitmapset.h:62
@ BMS_SUBSET2
Definition: bitmapset.h:64
BMS_Membership
Definition: bitmapset.h:70
@ BMS_SINGLETON
Definition: bitmapset.h:72
@ BMS_EMPTY_SET
Definition: bitmapset.h:71
@ BMS_MULTIPLE
Definition: bitmapset.h:73
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: bitmapset.c:1442
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:539
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
uint32 bitmapword
Definition: bitmapset.h:44
bool bms_overlap_list(const Bitmapset *a, const struct List *b)
int bms_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:183
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:715
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:1230
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641
struct Bitmapset Bitmapset
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
int64_t int64
Definition: c.h:499
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:434
int32_t int32
Definition: c.h:498
uint64_t uint64
Definition: c.h:503
uint32_t uint32
Definition: c.h:502
size_t Size
Definition: c.h:576
int b
Definition: isn.c:74
int x
Definition: isn.c:75
int a
Definition: isn.c:73
NodeTag
Definition: nodes.h:27
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
pg_node_attr(custom_copy_equal, special_read_write, no_query_jumble) NodeTag type
int nwords
Definition: bitmapset.h:54
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:55
Definition: pg_list.h:54
const char * type