PostgreSQL Source Code  git master
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-2023, 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] */
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 */
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 */
75 
76 
77 /*
78  * function prototypes in nodes/bitmapset.c
79  */
80 
81 extern Bitmapset *bms_copy(const Bitmapset *a);
82 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
83 extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
84 extern Bitmapset *bms_make_singleton(int x);
85 extern void bms_free(Bitmapset *a);
86 
87 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
88 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
89 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
90 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
92 extern bool bms_is_member(int x, const Bitmapset *a);
93 extern int bms_member_index(Bitmapset *a, int x);
94 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
95 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
96 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
97 extern int bms_singleton_member(const Bitmapset *a);
98 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
99 extern int bms_num_members(const Bitmapset *a);
100 
101 /* optimized tests when we don't need to know exact membership count: */
103 
104 /* NULL is now the only allowed representation of an empty bitmapset */
105 #define bms_is_empty(a) ((a) == NULL)
106 
107 /* these routines recycle (modify or free) their non-const inputs: */
108 
109 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
110 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
111 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
112 extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
113 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
114 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
116 
117 /* support for iterating through the integer elements of a set: */
118 extern int bms_next_member(const Bitmapset *a, int prevbit);
119 extern int bms_prev_member(const Bitmapset *a, int prevbit);
120 
121 /* support for hashtables using Bitmapsets as keys: */
122 extern uint32 bms_hash_value(const Bitmapset *a);
123 extern uint32 bitmap_hash(const void *key, Size keysize);
124 extern int bitmap_match(const void *key1, const void *key2, Size keysize);
125 
126 #endif /* BITMAPSET_H */
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1165
uint32 bitmap_hash(const void *key, Size keysize)
Definition: bitmapset.c:1226
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:1051
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:97
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:396
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1106
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1212
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:363
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:612
void bms_free(Bitmapset *a)
Definition: bitmapset.c:194
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:685
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:460
int32 signedbitmapword
Definition: bitmapset.h:45
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:171
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:753
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:211
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:297
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:248
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:835
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:993
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:951
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
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:793
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
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: bitmapset.c:1236
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:712
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:486
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:527
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:138
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:80
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:652
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:879
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:581
struct Bitmapset Bitmapset
unsigned int uint32
Definition: c.h:495
signed int int32
Definition: c.h:483
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:387
size_t Size
Definition: c.h:594
int b
Definition: isn.c:70
int x
Definition: isn.c:71
int a
Definition: isn.c:69
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