PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, PostgreSQL Global Development Group
15  *
16  * src/include/nodes/bitmapset.h
17  *
18  *-------------------------------------------------------------------------
19  */
20 #ifndef BITMAPSET_H
21 #define BITMAPSET_H
22 
23 /*
24  * Data representation
25  */
26 
27 /* The unit size can be adjusted by changing these three declarations: */
28 #define BITS_PER_BITMAPWORD 32
29 typedef uint32 bitmapword; /* must be an unsigned type */
30 typedef int32 signedbitmapword; /* must be the matching signed type */
31 
32 typedef struct Bitmapset
33 {
34  int nwords; /* number of words in array */
35  bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
36 } Bitmapset;
37 
38 
39 /* result of bms_subset_compare */
40 typedef enum
41 {
42  BMS_EQUAL, /* sets are equal */
43  BMS_SUBSET1, /* first set is a subset of the second */
44  BMS_SUBSET2, /* second set is a subset of the first */
45  BMS_DIFFERENT /* neither set is a subset of the other */
47 
48 /* result of bms_membership */
49 typedef enum
50 {
51  BMS_EMPTY_SET, /* 0 members */
52  BMS_SINGLETON, /* 1 member */
53  BMS_MULTIPLE /* >1 member */
55 
56 
57 /*
58  * function prototypes in nodes/bitmapset.c
59  */
60 
61 extern Bitmapset *bms_copy(const Bitmapset *a);
62 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
63 extern Bitmapset *bms_make_singleton(int x);
64 extern void bms_free(Bitmapset *a);
65 
66 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
67 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
68 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
69 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
70 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
71 extern bool bms_is_member(int x, const Bitmapset *a);
72 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
73 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
74 extern int bms_singleton_member(const Bitmapset *a);
75 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
76 extern int bms_num_members(const Bitmapset *a);
77 
78 /* optimized tests when we don't need to know exact membership count: */
79 extern BMS_Membership bms_membership(const Bitmapset *a);
80 extern bool bms_is_empty(const Bitmapset *a);
81 
82 /* these routines recycle (modify or free) their non-const inputs: */
83 
84 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
85 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
86 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
87 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
88 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
89 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
90 
91 /* support for iterating through the integer elements of a set: */
92 extern int bms_first_member(Bitmapset *a);
93 extern int bms_next_member(const Bitmapset *a, int prevbit);
94 
95 /* support for hashtables using Bitmapsets as keys: */
96 extern uint32 bms_hash_value(const Bitmapset *a);
97 
98 #endif /* BITMAPSET_H */
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:787
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:575
int nwords
Definition: bitmapset.h:34
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:464
uint32 bitmapword
Definition: bitmapset.h:29
signed int int32
Definition: c.h:253
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:178
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:705
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:539
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:668
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:808
BMS_Membership
Definition: bitmapset.h:49
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:855
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:35
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:496
unsigned int uint32
Definition: c.h:265
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:419
int32 signedbitmapword
Definition: bitmapset.h:30
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:907
void bms_free(Bitmapset *a)
Definition: bitmapset.c:200
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:604
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:344
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:954
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:761
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:725
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
BMS_Comparison
Definition: bitmapset.h:40
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:283
struct Bitmapset Bitmapset