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  * Forward decl to save including pg_list.h
25  */
26 struct List;
27 
28 /*
29  * Data representation
30  */
31 
32 /* The unit size can be adjusted by changing these three declarations: */
33 #define BITS_PER_BITMAPWORD 32
34 typedef uint32 bitmapword; /* must be an unsigned type */
35 typedef int32 signedbitmapword; /* must be the matching signed type */
36 
37 typedef struct Bitmapset
38 {
39  int nwords; /* number of words in array */
40  bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
41 } Bitmapset;
42 
43 
44 /* result of bms_subset_compare */
45 typedef enum
46 {
47  BMS_EQUAL, /* sets are equal */
48  BMS_SUBSET1, /* first set is a subset of the second */
49  BMS_SUBSET2, /* second set is a subset of the first */
50  BMS_DIFFERENT /* neither set is a subset of the other */
52 
53 /* result of bms_membership */
54 typedef enum
55 {
56  BMS_EMPTY_SET, /* 0 members */
57  BMS_SINGLETON, /* 1 member */
58  BMS_MULTIPLE /* >1 member */
60 
61 
62 /*
63  * function prototypes in nodes/bitmapset.c
64  */
65 
66 extern Bitmapset *bms_copy(const Bitmapset *a);
67 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
68 extern Bitmapset *bms_make_singleton(int x);
69 extern void bms_free(Bitmapset *a);
70 
71 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
72 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
73 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
74 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
75 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
76 extern bool bms_is_member(int x, const Bitmapset *a);
77 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
78 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
79 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
80 extern int bms_singleton_member(const Bitmapset *a);
81 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
82 extern int bms_num_members(const Bitmapset *a);
83 
84 /* optimized tests when we don't need to know exact membership count: */
85 extern BMS_Membership bms_membership(const Bitmapset *a);
86 extern bool bms_is_empty(const Bitmapset *a);
87 
88 /* these routines recycle (modify or free) their non-const inputs: */
89 
90 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
91 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
92 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
93 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
94 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
95 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
96 
97 /* support for iterating through the integer elements of a set: */
98 extern int bms_first_member(Bitmapset *a);
99 extern int bms_next_member(const Bitmapset *a, int prevbit);
100 
101 /* support for hashtables using Bitmapsets as keys: */
102 extern uint32 bms_hash_value(const Bitmapset *a);
103 
104 #endif /* BITMAPSET_H */
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:817
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:605
bool bms_overlap_list(const Bitmapset *a, const struct List *b)
int nwords
Definition: bitmapset.h:39
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
uint32 bitmapword
Definition: bitmapset.h:34
signed int int32
Definition: c.h:246
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:179
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:735
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:569
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:698
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
BMS_Membership
Definition: bitmapset.h:54
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:885
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:526
unsigned int uint32
Definition: c.h:258
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:420
int32 signedbitmapword
Definition: bitmapset.h:35
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:937
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:634
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:252
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:218
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:345
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:984
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:791
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
Definition: pg_list.h:45
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
BMS_Comparison
Definition: bitmapset.h:45
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
struct Bitmapset Bitmapset