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-2019, 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  * 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  int nwords; /* number of words in array */
52  bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */
53 } Bitmapset;
54 
55 
56 /* result of bms_subset_compare */
57 typedef enum
58 {
59  BMS_EQUAL, /* sets are equal */
60  BMS_SUBSET1, /* first set is a subset of the second */
61  BMS_SUBSET2, /* second set is a subset of the first */
62  BMS_DIFFERENT /* neither set is a subset of the other */
64 
65 /* result of bms_membership */
66 typedef enum
67 {
68  BMS_EMPTY_SET, /* 0 members */
69  BMS_SINGLETON, /* 1 member */
70  BMS_MULTIPLE /* >1 member */
72 
73 
74 /*
75  * function prototypes in nodes/bitmapset.c
76  */
77 
78 extern Bitmapset *bms_copy(const Bitmapset *a);
79 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
80 extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
81 extern Bitmapset *bms_make_singleton(int x);
82 extern void bms_free(Bitmapset *a);
83 
84 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
85 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
86 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
87 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
88 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
89 extern bool bms_is_member(int x, const Bitmapset *a);
90 extern int bms_member_index(Bitmapset *a, int x);
91 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
92 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
93 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
94 extern int bms_singleton_member(const Bitmapset *a);
95 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
96 extern int bms_num_members(const Bitmapset *a);
97 
98 /* optimized tests when we don't need to know exact membership count: */
99 extern BMS_Membership bms_membership(const Bitmapset *a);
100 extern bool bms_is_empty(const Bitmapset *a);
101 
102 /* these routines recycle (modify or free) their non-const inputs: */
103 
104 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
105 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
106 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
107 extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
108 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
109 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
110 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
111 
112 /* support for iterating through the integer elements of a set: */
113 extern int bms_first_member(Bitmapset *a);
114 extern int bms_next_member(const Bitmapset *a, int prevbit);
115 extern int bms_prev_member(const Bitmapset *a, int prevbit);
116 
117 /* support for hashtables using Bitmapsets as keys: */
118 extern uint32 bms_hash_value(const Bitmapset *a);
119 
120 #endif /* BITMAPSET_H */
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:928
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:646
bool bms_overlap_list(const Bitmapset *a, const struct List *b)
int nwords
Definition: bitmapset.h:51
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:545
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:834
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
uint32 bitmapword
Definition: bitmapset.h:44
signed int int32
Definition: c.h:347
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:186
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:773
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
Oid member
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:615
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:949
BMS_Membership
Definition: bitmapset.h:66
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:996
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:52
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:577
unsigned int uint32
Definition: c.h:359
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427
int32 signedbitmapword
Definition: bitmapset.h:45
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
int bms_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:147
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:453
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:259
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:225
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:352
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1154
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:902
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1102
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
Definition: pg_list.h:50
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
BMS_Comparison
Definition: bitmapset.h:57
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
struct Bitmapset Bitmapset