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 */
26struct 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
38typedef uint64 bitmapword; /* must be an unsigned type */
39typedef int64 signedbitmapword; /* must be the matching signed type */
40
41#else
42
43#define BITS_PER_BITMAPWORD 32
44typedef uint32 bitmapword; /* must be an unsigned type */
45typedef int32 signedbitmapword; /* must be the matching signed type */
46
47#endif
48
49typedef 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 */
57typedef 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 */
63} BMS_Comparison;
64
65/* result of bms_membership */
66typedef enum
67{
68 BMS_EMPTY_SET, /* 0 members */
69 BMS_SINGLETON, /* 1 member */
70 BMS_MULTIPLE /* >1 member */
71} BMS_Membership;
72
73
74/*
75 * function prototypes in nodes/bitmapset.c
76 */
77
78extern Bitmapset *bms_copy(const Bitmapset *a);
79extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
80extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
81extern Bitmapset *bms_make_singleton(int x);
82extern void bms_free(Bitmapset *a);
83
84extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
85extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
86extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
87extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
88extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
89extern bool bms_is_member(int x, const Bitmapset *a);
90extern int bms_member_index(Bitmapset *a, int x);
91extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
92extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
93extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
94extern int bms_singleton_member(const Bitmapset *a);
95extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
96extern int bms_num_members(const Bitmapset *a);
97
98/* optimized tests when we don't need to know exact membership count: */
99extern BMS_Membership bms_membership(const Bitmapset *a);
100extern bool bms_is_empty(const Bitmapset *a);
101
102/* these routines recycle (modify or free) their non-const inputs: */
103
104extern Bitmapset *bms_add_member(Bitmapset *a, int x);
105extern Bitmapset *bms_del_member(Bitmapset *a, int x);
106extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
107extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
108extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
109extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
110extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
111
112/* support for iterating through the integer elements of a set: */
113extern int bms_first_member(Bitmapset *a);
114extern int bms_next_member(const Bitmapset *a, int prevbit);
115extern int bms_prev_member(const Bitmapset *a, int prevbit);
116
117/* support for hashtables using Bitmapsets as keys: */
118extern uint32 bms_hash_value(const Bitmapset *a);
119
120#endif /* BITMAPSET_H */
121