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
24namespace duckdb_libpgquery {
25
26/*
27 * Forward decl to save including pg_list.h
28 */
29struct PGList;
30
31/*
32 * Data representation
33 */
34
35/* The unit size can be adjusted by changing these three declarations: */
36#define BITS_PER_BITMAPWORD 32
37typedef uint32_t bitmapword; /* must be an unsigned type */
38typedef int32_t signedbitmapword; /* must be the matching signed type */
39
40typedef struct PGBitmapset {
41 int nwords; /* number of words in array */
42 bitmapword words[1]; /* really [nwords] */
43} PGBitmapset;
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 * function prototypes in nodes/bitmapset.c
62 */
63
64PGBitmapset *bms_copy(const PGBitmapset *a);
65bool bms_equal(const PGBitmapset *a, const PGBitmapset *b);
66PGBitmapset *bms_make_singleton(int x);
67void bms_free(PGBitmapset *a);
68
69PGBitmapset *bms_union(const PGBitmapset *a, const PGBitmapset *b);
70PGBitmapset *bms_intersect(const PGBitmapset *a, const PGBitmapset *b);
71PGBitmapset *bms_difference(const PGBitmapset *a, const PGBitmapset *b);
72bool bms_is_subset(const PGBitmapset *a, const PGBitmapset *b);
73PG_BMS_Comparison bms_subset_compare(const PGBitmapset *a, const PGBitmapset *b);
74bool bms_is_member(int x, const PGBitmapset *a);
75bool bms_overlap(const PGBitmapset *a, const PGBitmapset *b);
76bool bms_overlap_list(const PGBitmapset *a, const struct PGList *b);
77bool bms_nonempty_difference(const PGBitmapset *a, const PGBitmapset *b);
78int bms_singleton_member(const PGBitmapset *a);
79bool bms_get_singleton_member(const PGBitmapset *a, int *member);
80int bms_num_members(const PGBitmapset *a);
81
82/* optimized tests when we don't need to know exact membership count: */
83PG_BMS_Membership bms_membership(const PGBitmapset *a);
84bool bms_is_empty(const PGBitmapset *a);
85
86/* these routines recycle (modify or free) their non-const inputs: */
87
88PGBitmapset *bms_add_member(PGBitmapset *a, int x);
89PGBitmapset *bms_del_member(PGBitmapset *a, int x);
90PGBitmapset *bms_add_members(PGBitmapset *a, const PGBitmapset *b);
91PGBitmapset *bms_int_members(PGBitmapset *a, const PGBitmapset *b);
92PGBitmapset *bms_del_members(PGBitmapset *a, const PGBitmapset *b);
93PGBitmapset *bms_join(PGBitmapset *a, PGBitmapset *b);
94
95/* support for iterating through the integer elements of a set: */
96int bms_first_member(PGBitmapset *a);
97int bms_next_member(const PGBitmapset *a, int prevbit);
98
99/* support for hashtables using Bitmapsets as keys: */
100uint32_t bms_hash_value(const PGBitmapset *a);
101
102}