PostgreSQL Source Code git master
multibitmapset.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * multibitmapset.c
4 * Lists of Bitmapsets
5 *
6 * A multibitmapset is useful in situations where members of a set can
7 * be identified by two small integers; for example, varno and varattno
8 * of a group of Vars within a query. The implementation is a List of
9 * Bitmapsets, so that the empty set can be represented by NIL. (But,
10 * as with Bitmapsets, that's not the only allowed representation.)
11 * The zero-based index of a List element is the first identifying value,
12 * and the (also zero-based) index of a bit within that Bitmapset is
13 * the second identifying value. There is no expectation that the
14 * Bitmapsets should all be the same size.
15 *
16 * The available operations on multibitmapsets are intended to parallel
17 * those on bitmapsets, for example union and intersection. So far only
18 * a small fraction of that has been built out; we'll add more as needed.
19 *
20 *
21 * Copyright (c) 2022-2025, PostgreSQL Global Development Group
22 *
23 * IDENTIFICATION
24 * src/backend/nodes/multibitmapset.c
25 *
26 *-------------------------------------------------------------------------
27 */
28#include "postgres.h"
29
31
32
33/*
34 * mbms_add_member
35 * Add a new member to a multibitmapset.
36 *
37 * The new member is identified by "listidx", the zero-based index of the
38 * List element it should go into, and "bitidx", which specifies the bit
39 * number to be set therein.
40 *
41 * This is like bms_add_member, but for multibitmapsets.
42 */
43List *
44mbms_add_member(List *a, int listidx, int bitidx)
45{
46 Bitmapset *bms;
47 ListCell *lc;
48
49 if (listidx < 0 || bitidx < 0)
50 elog(ERROR, "negative multibitmapset member index not allowed");
51 /* Add empty elements as needed */
52 while (list_length(a) <= listidx)
53 a = lappend(a, NULL);
54 /* Update the target element */
55 lc = list_nth_cell(a, listidx);
56 bms = lfirst_node(Bitmapset, lc);
57 bms = bms_add_member(bms, bitidx);
58 lfirst(lc) = bms;
59 return a;
60}
61
62/*
63 * mbms_add_members
64 * Add all members of set b to set a.
65 *
66 * This is a UNION operation, but the left input is modified in-place.
67 *
68 * This is like bms_add_members, but for multibitmapsets.
69 */
70List *
72{
74 *lcb;
75
76 /* Add empty elements to a, as needed */
77 while (list_length(a) < list_length(b))
78 a = lappend(a, NULL);
79 /* forboth will stop at the end of the shorter list, which is fine */
80 forboth(lca, a, lcb, b)
81 {
83 const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
84
85 bmsa = bms_add_members(bmsa, bmsb);
86 lfirst(lca) = bmsa;
87 }
88 return a;
89}
90
91/*
92 * mbms_int_members
93 * Reduce set a to its intersection with set b.
94 *
95 * This is an INTERSECT operation, but the left input is modified in-place.
96 *
97 * This is like bms_int_members, but for multibitmapsets.
98 */
99List *
101{
102 ListCell *lca,
103 *lcb;
104
105 /* Remove any elements of a that are no longer of use */
107 /* forboth will stop at the end of the shorter list, which is fine */
108 forboth(lca, a, lcb, b)
109 {
111 const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
112
113 bmsa = bms_int_members(bmsa, bmsb);
114 lfirst(lca) = bmsa;
115 }
116 return a;
117}
118
119/*
120 * mbms_is_member
121 * Is listidx/bitidx a member of A?
122 *
123 * This is like bms_is_member, but for multibitmapsets.
124 */
125bool
126mbms_is_member(int listidx, int bitidx, const List *a)
127{
128 const Bitmapset *bms;
129
130 /* XXX better to just return false for negative indexes? */
131 if (listidx < 0 || bitidx < 0)
132 elog(ERROR, "negative multibitmapset member index not allowed");
133 if (listidx >= list_length(a))
134 return false;
135 bms = list_nth_node(Bitmapset, a, listidx);
136 return bms_is_member(bitidx, bms);
137}
138
139/*
140 * mbms_overlap_sets
141 * Identify the bitmapsets having common members in a and b.
142 *
143 * The result is a bitmapset of the list indexes of bitmapsets that overlap.
144 */
145Bitmapset *
147{
148 Bitmapset *result = NULL;
149 ListCell *lca,
150 *lcb;
151
152 /* forboth will stop at the end of the shorter list, which is fine */
153 forboth(lca, a, lcb, b)
154 {
155 const Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
156 const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
157
158 if (bms_overlap(bmsa, bmsb))
159 result = bms_add_member(result, foreach_current_index(lca));
160 }
161 return result;
162}
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1109
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
int b
Definition: isn.c:71
int a
Definition: isn.c:70
List * lappend(List *list, void *datum)
Definition: list.c:339
List * list_truncate(List *list, int new_size)
Definition: list.c:631
Datum lca(PG_FUNCTION_ARGS)
Definition: ltree_op.c:568
List * mbms_add_members(List *a, const List *b)
List * mbms_add_member(List *a, int listidx, int bitidx)
bool mbms_is_member(int listidx, int bitidx, const List *a)
List * mbms_int_members(List *a, const List *b)
Bitmapset * mbms_overlap_sets(const List *a, const List *b)
#define lfirst(lc)
Definition: pg_list.h:172
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static int list_length(const List *l)
Definition: pg_list.h:152
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:518
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403
static ListCell * list_nth_cell(const List *list, int n)
Definition: pg_list.h:277
#define list_nth_node(type, list, n)
Definition: pg_list.h:327
Definition: pg_list.h:54