/Users/deen/code/yugabyte-db/src/postgres/src/include/nodes/bitmapset.h
Line | Count | Source |
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-2018, 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 | 44.7M | #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 */ |
51 | | } BMS_Comparison; |
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 */ |
59 | | } BMS_Membership; |
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 int bms_compare(const Bitmapset *a, const Bitmapset *b); |
69 | | extern Bitmapset *bms_make_singleton(int x); |
70 | | extern void bms_free(Bitmapset *a); |
71 | | |
72 | | extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b); |
73 | | extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b); |
74 | | extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b); |
75 | | extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b); |
76 | | extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b); |
77 | | extern bool bms_is_member(int x, const Bitmapset *a); |
78 | | extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b); |
79 | | extern bool bms_overlap_list(const Bitmapset *a, const struct List *b); |
80 | | extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b); |
81 | | extern int bms_singleton_member(const Bitmapset *a); |
82 | | extern bool bms_get_singleton_member(const Bitmapset *a, int *member); |
83 | | extern int bms_num_members(const Bitmapset *a); |
84 | | |
85 | | /* optimized tests when we don't need to know exact membership count: */ |
86 | | extern BMS_Membership bms_membership(const Bitmapset *a); |
87 | | extern bool bms_is_empty(const Bitmapset *a); |
88 | | |
89 | | /* these routines recycle (modify or free) their non-const inputs: */ |
90 | | |
91 | | extern Bitmapset *bms_add_member(Bitmapset *a, int x); |
92 | | extern Bitmapset *bms_del_member(Bitmapset *a, int x); |
93 | | extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b); |
94 | | extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper); |
95 | | extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b); |
96 | | extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b); |
97 | | extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b); |
98 | | |
99 | | /* support for iterating through the integer elements of a set: */ |
100 | | extern int bms_first_member(Bitmapset *a); |
101 | | extern int bms_next_member(const Bitmapset *a, int prevbit); |
102 | | extern int bms_prev_member(const Bitmapset *a, int prevbit); |
103 | | |
104 | | /* support for hashtables using Bitmapsets as keys: */ |
105 | | extern uint32 bms_hash_value(const Bitmapset *a); |
106 | | |
107 | | #endif /* BITMAPSET_H */ |