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, a NULL pointer is always
9  * accepted by all operations to represent the empty set. (But beware
10  * that this is not the only representation of the empty set. Use
11  * bms_is_empty() in preference to testing for NULL.)
12  *
13  *
14  * Copyright (c) 2003-2022, PostgreSQL Global Development Group
15  *
16  * src/include/nodes/bitmapset.h
17  *
18  *-------------------------------------------------------------------------
19  */
20 #ifndef BITMAPSET_H
21 #define BITMAPSET_H
22 
23 #include "nodes/nodes.h"
24 
25 /*
26  * Forward decl to save including pg_list.h
27  */
28 struct List;
29 
30 /*
31  * Data representation
32  *
33  * Larger bitmap word sizes generally give better performance, so long as
34  * they're not wider than the processor can handle efficiently. We use
35  * 64-bit words if pointers are that large, else 32-bit words.
36  */
37 #if SIZEOF_VOID_P >= 8
38 
39 #define BITS_PER_BITMAPWORD 64
40 typedef uint64 bitmapword; /* must be an unsigned type */
41 typedef int64 signedbitmapword; /* must be the matching signed type */
42 
43 #else
44 
45 #define BITS_PER_BITMAPWORD 32
46 typedef uint32 bitmapword; /* must be an unsigned type */
47 typedef int32 signedbitmapword; /* must be the matching signed type */
48 
49 #endif
50 
51 typedef struct Bitmapset
52 {
53  pg_node_attr(custom_copy_equal, special_read_write)
54 
55  NodeTag type;
56  int nwords; /* number of words in array */
57  bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
59 
60 
61 /* result of bms_subset_compare */
62 typedef enum
63 {
64  BMS_EQUAL, /* sets are equal */
65  BMS_SUBSET1, /* first set is a subset of the second */
66  BMS_SUBSET2, /* second set is a subset of the first */
67  BMS_DIFFERENT /* neither set is a subset of the other */
69 
70 /* result of bms_membership */
71 typedef enum
72 {
73  BMS_EMPTY_SET, /* 0 members */
74  BMS_SINGLETON, /* 1 member */
75  BMS_MULTIPLE /* >1 member */
77 
78 
79 /*
80  * function prototypes in nodes/bitmapset.c
81  */
82 
83 extern Bitmapset *bms_copy(const Bitmapset *a);
84 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
85 extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
86 extern Bitmapset *bms_make_singleton(int x);
87 extern void bms_free(Bitmapset *a);
88 
89 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
90 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
91 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
92 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
94 extern bool bms_is_member(int x, const Bitmapset *a);
95 extern int bms_member_index(Bitmapset *a, int x);
96 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
97 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
98 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
99 extern int bms_singleton_member(const Bitmapset *a);
100 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
101 extern int bms_num_members(const Bitmapset *a);
102 
103 /* optimized tests when we don't need to know exact membership count: */
105 extern bool bms_is_empty(const Bitmapset *a);
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_first_member(Bitmapset *a);
119 extern int bms_next_member(const Bitmapset *a, int prevbit);
120 extern int bms_prev_member(const Bitmapset *a, int prevbit);
121 
122 /* support for hashtables using Bitmapsets as keys: */
123 extern uint32 bms_hash_value(const Bitmapset *a);
124 extern uint32 bitmap_hash(const void *key, Size keysize);
125 extern int bitmap_match(const void *key1, const void *key2, Size keysize);
126 
127 #endif /* BITMAPSET_H */
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1106
uint32 bitmap_hash(const void *key, Size keysize)
Definition: bitmapset.c:1181
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:953
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:353
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1047
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1158
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:580
void bms_free(Bitmapset *a)
Definition: bitmapset.c:209
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:649
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:428
int32 signedbitmapword
Definition: bitmapset.h:47
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:186
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:739
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:226
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:260
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:796
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:932
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:906
BMS_Comparison
Definition: bitmapset.h:63
@ BMS_DIFFERENT
Definition: bitmapset.h:67
@ BMS_SUBSET1
Definition: bitmapset.h:65
@ BMS_EQUAL
Definition: bitmapset.h:64
@ BMS_SUBSET2
Definition: bitmapset.h:66
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:776
BMS_Membership
Definition: bitmapset.h:72
@ BMS_SINGLETON
Definition: bitmapset.h:74
@ BMS_EMPTY_SET
Definition: bitmapset.h:73
@ BMS_MULTIPLE
Definition: bitmapset.h:75
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: bitmapset.c:1191
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:675
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:454
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
uint32 bitmapword
Definition: bitmapset.h:46
bool bms_overlap_list(const Bitmapset *a, const struct List *b)
int bms_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:147
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:618
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:837
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:1000
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:548
struct Bitmapset Bitmapset
unsigned int uint32
Definition: c.h:442
signed int int32
Definition: c.h:430
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:362
size_t Size
Definition: c.h:541
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:48
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:79
pg_node_attr(custom_copy_equal, special_read_write) NodeTag type
int nwords
Definition: bitmapset.h:56
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:57
Definition: pg_list.h:52