Debian Codegraph @

src/include/nodes/bitmapset.h

raw
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 */
26 struct 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
38 typedef uint64 bitmapword; /* must be an unsigned type */
39 typedef int64 signedbitmapword; /* must be the matching signed type */
40
41 #else
42
43 #define BITS_PER_BITMAPWORD 32
44 typedef uint32 bitmapword; /* must be an unsigned type */
45 typedef int32 signedbitmapword; /* must be the matching signed type */
46
47 #endif
48
49 typedef struct Bitmapset
50 {
51 pg_node_attr(custom_copy_equal, special_read_write, no_query_jumble)
52
53 NodeTag type;
54 int nwords; /* number of words in array */
55 bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
56 } Bitmapset;
57
58
59 /* result of bms_subset_compare */
60 typedef 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 */
66 } BMS_Comparison;
67
68 /* result of bms_membership */
69 typedef enum
70 {
71 BMS_EMPTY_SET, /* 0 members */
72 BMS_SINGLETON, /* 1 member */
73 BMS_MULTIPLE, /* >1 member */
74 } BMS_Membership;
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
94 extern Bitmapset *bms_copy(const Bitmapset *a);
95 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
96 extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
97 extern Bitmapset *bms_make_singleton(int x);
98 extern void bms_free(Bitmapset *a);
99
100 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
101 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
102 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
103 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
104 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
105 extern bool bms_is_member(int x, const Bitmapset *a);
106 extern int bms_member_index(Bitmapset *a, int x);
107 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
108 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
109 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
110 extern int bms_singleton_member(const Bitmapset *a);
111 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
112 extern int bms_num_members(const Bitmapset *a);
113
114 /* optimized tests when we don't need to know exact membership count: */
115 extern BMS_Membership bms_membership(const Bitmapset *a);
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
122 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
123 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
124 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
125 extern Bitmapset *bms_replace_members(Bitmapset *a, const Bitmapset *b);
126 extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
127 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
128 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
129 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
130
131 /* support for iterating through the integer elements of a set: */
132 extern int bms_next_member(const Bitmapset *a, int prevbit);
133 extern int bms_prev_member(const Bitmapset *a, int prevbit);
134
135 /* support for hashtables using Bitmapsets as keys: */
136 extern uint32 bms_hash_value(const Bitmapset *a);
137 extern uint32 bitmap_hash(const void *key, Size keysize);
138 extern int bitmap_match(const void *key1, const void *key2, Size keysize);
139
140 #endif /* BITMAPSET_H */