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 PGGroup
15 *
16 * src/include/nodes/bitmapset.h
17 *
18 *-------------------------------------------------------------------------
19 */
20#pragma once
21
22#include <cstdint>
23
24/*
25 * Forward decl to save including pg_list.h
26 */
27struct PGList;
28
29/*
30 * Data representation
31 */
32
33/* The unit size can be adjusted by changing these three declarations: */
34#define BITS_PER_BITMAPWORD 32
35typedef uint32_t bitmapword; /* must be an unsigned type */
36typedef int32_t signedbitmapword; /* must be the matching signed type */
37
38typedef struct PGBitmapset
39{
40 int nwords; /* number of words in array */
41 bitmapword words[1]; /* really [nwords] */
42} PGBitmapset;
43
44
45/* result of bms_subset_compare */
46typedef enum PG_BMS_Comparison {
47 PG_BMS_EQUAL, /* sets are equal */
48 PG_BMS_SUBSET1, /* first set is a subset of the second */
49 PG_BMS_SUBSET2, /* second set is a subset of the first */
50 BMS_DIFFERENT /* neither set is a subset of the other */
51} PG_BMS_Comparison;
52
53/* result of bms_membership */
54typedef enum PG_BMS_Membership {
55 PG_BMS_EMPTY_SET, /* 0 members */
56 PG_BMS_SINGLETON, /* 1 member */
57 BMS_MULTIPLE /* >1 member */
58} PG_BMS_Membership;
59
60
61/*
62 * function prototypes in nodes/bitmapset.c
63 */
64
65extern PGBitmapset *bms_copy(const PGBitmapset *a);
66extern bool bms_equal(const PGBitmapset *a, const PGBitmapset *b);
67extern PGBitmapset *bms_make_singleton(int x);
68extern void bms_free(PGBitmapset *a);
69
70extern PGBitmapset *bms_union(const PGBitmapset *a, const PGBitmapset *b);
71extern PGBitmapset *bms_intersect(const PGBitmapset *a, const PGBitmapset *b);
72extern PGBitmapset *bms_difference(const PGBitmapset *a, const PGBitmapset *b);
73extern bool bms_is_subset(const PGBitmapset *a, const PGBitmapset *b);
74extern PG_BMS_Comparison bms_subset_compare(const PGBitmapset *a, const PGBitmapset *b);
75extern bool bms_is_member(int x, const PGBitmapset *a);
76extern bool bms_overlap(const PGBitmapset *a, const PGBitmapset *b);
77extern bool bms_overlap_list(const PGBitmapset *a, const struct PGList *b);
78extern bool bms_nonempty_difference(const PGBitmapset *a, const PGBitmapset *b);
79extern int bms_singleton_member(const PGBitmapset *a);
80extern bool bms_get_singleton_member(const PGBitmapset *a, int *member);
81extern int bms_num_members(const PGBitmapset *a);
82
83/* optimized tests when we don't need to know exact membership count: */
84extern PG_BMS_Membership bms_membership(const PGBitmapset *a);
85extern bool bms_is_empty(const PGBitmapset *a);
86
87/* these routines recycle (modify or free) their non-const inputs: */
88
89extern PGBitmapset *bms_add_member(PGBitmapset *a, int x);
90extern PGBitmapset *bms_del_member(PGBitmapset *a, int x);
91extern PGBitmapset *bms_add_members(PGBitmapset *a, const PGBitmapset *b);
92extern PGBitmapset *bms_int_members(PGBitmapset *a, const PGBitmapset *b);
93extern PGBitmapset *bms_del_members(PGBitmapset *a, const PGBitmapset *b);
94extern PGBitmapset *bms_join(PGBitmapset *a, PGBitmapset *b);
95
96/* support for iterating through the integer elements of a set: */
97extern int bms_first_member(PGBitmapset *a);
98extern int bms_next_member(const PGBitmapset *a, int prevbit);
99
100/* support for hashtables using Bitmapsets as keys: */
101extern uint32_t bms_hash_value(const PGBitmapset *a);
102
103