| 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, we always represent the |
| 9 |
* empty set by a NULL pointer. |
| 10 |
* |
| 11 |
* |
| 12 |
* Copyright (c) 2003-2025, PostgreSQL Global Development Group |
| 13 |
* |
| 14 |
* src/include/nodes/bitmapset.h |
| 15 |
* |
| 16 |
*------------------------------------------------------------------------- |
| 17 |
*/ |
| 18 |
#ifndef BITMAPSET_H |
| 19 |
#define BITMAPSET_H |
| 20 |
|
| 21 |
#include "nodes/nodes.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 |
pg_node_attr(custom_copy_equal, special_read_write, no_query_jumble) |
| 52 |
|
| 53 |
NodeTag type; |
| 54 |
int nwords; /* number of words in array */ |
| 55 |
bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */ |
| 56 |
} Bitmapset; |
| 57 |
|
| 58 |
|
| 59 |
/* result of bms_subset_compare */ |
| 60 |
typedef enum |
| 61 |
{ |
| 62 |
BMS_EQUAL, /* sets are equal */ |
| 63 |
BMS_SUBSET1, /* first set is a subset of the second */ |
| 64 |
BMS_SUBSET2, /* second set is a subset of the first */ |
| 65 |
BMS_DIFFERENT, /* neither set is a subset of the other */ |
| 66 |
} BMS_Comparison; |
| 67 |
|
| 68 |
/* result of bms_membership */ |
| 69 |
typedef enum |
| 70 |
{ |
| 71 |
BMS_EMPTY_SET, /* 0 members */ |
| 72 |
BMS_SINGLETON, /* 1 member */ |
| 73 |
BMS_MULTIPLE, /* >1 member */ |
| 74 |
} BMS_Membership; |
| 75 |
|
| 76 |
/* Select appropriate bit-twiddling functions for bitmap word size */ |
| 77 |
#if BITS_PER_BITMAPWORD == 32 |
| 78 |
#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w) |
| 79 |
#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w) |
| 80 |
#define bmw_popcount(w) pg_popcount32(w) |
| 81 |
#elif BITS_PER_BITMAPWORD == 64 |
| 82 |
#define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w) |
| 83 |
#define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w) |
| 84 |
#define bmw_popcount(w) pg_popcount64(w) |
| 85 |
#else |
| 86 |
#error "invalid BITS_PER_BITMAPWORD" |
| 87 |
#endif |
| 88 |
|
| 89 |
|
| 90 |
/* |
| 91 |
* function prototypes in nodes/bitmapset.c |
| 92 |
*/ |
| 93 |
|
| 94 |
extern Bitmapset *bms_copy(const Bitmapset *a); |
| 95 |
extern bool bms_equal(const Bitmapset *a, const Bitmapset *b); |
| 96 |
extern int bms_compare(const Bitmapset *a, const Bitmapset *b); |
| 97 |
extern Bitmapset *bms_make_singleton(int x); |
| 98 |
extern void bms_free(Bitmapset *a); |
| 99 |
|
| 100 |
extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b); |
| 101 |
extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b); |
| 102 |
extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b); |
| 103 |
extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b); |
| 104 |
extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b); |
| 105 |
extern bool bms_is_member(int x, const Bitmapset *a); |
| 106 |
extern int bms_member_index(Bitmapset *a, int x); |
| 107 |
extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b); |
| 108 |
extern bool bms_overlap_list(const Bitmapset *a, const struct List *b); |
| 109 |
extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b); |
| 110 |
extern int bms_singleton_member(const Bitmapset *a); |
| 111 |
extern bool bms_get_singleton_member(const Bitmapset *a, int *member); |
| 112 |
extern int bms_num_members(const Bitmapset *a); |
| 113 |
|
| 114 |
/* optimized tests when we don't need to know exact membership count: */ |
| 115 |
extern BMS_Membership bms_membership(const Bitmapset *a); |
| 116 |
|
| 117 |
/* NULL is now the only allowed representation of an empty bitmapset */ |
| 118 |
#define bms_is_empty(a) ((a) == NULL) |
| 119 |
|
| 120 |
/* these routines recycle (modify or free) their non-const inputs: */ |
| 121 |
|
| 122 |
extern Bitmapset *bms_add_member(Bitmapset *a, int x); |
| 123 |
extern Bitmapset *bms_del_member(Bitmapset *a, int x); |
| 124 |
extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b); |
| 125 |
extern Bitmapset *bms_replace_members(Bitmapset *a, const Bitmapset *b); |
| 126 |
extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper); |
| 127 |
extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b); |
| 128 |
extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b); |
| 129 |
extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b); |
| 130 |
|
| 131 |
/* support for iterating through the integer elements of a set: */ |
| 132 |
extern int bms_next_member(const Bitmapset *a, int prevbit); |
| 133 |
extern int bms_prev_member(const Bitmapset *a, int prevbit); |
| 134 |
|
| 135 |
/* support for hashtables using Bitmapsets as keys: */ |
| 136 |
extern uint32 bms_hash_value(const Bitmapset *a); |
| 137 |
extern uint32 bitmap_hash(const void *key, Size keysize); |
| 138 |
extern int bitmap_match(const void *key1, const void *key2, Size keysize); |
| 139 |
|
| 140 |
#endif /* BITMAPSET_H */ |