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-2024, PostgreSQL Global Development Group
22  *
23  * IDENTIFICATION
24  * src/backend/nodes/multibitmapset.c
25  *
26  *-------------------------------------------------------------------------
27  */
28 #include "postgres.h"
29 
30 #include "nodes/multibitmapset.h"
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  */
43 List *
44 mbms_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  */
70 List *
72 {
73  ListCell *lca,
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  */
99 List *
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  */
125 bool
126 mbms_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  */
145 Bitmapset *
146 mbms_overlap_sets(const List *a, const List *b)
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 }
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
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1109
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:70
int a
Definition: isn.c:69
List * list_truncate(List *list, int new_size)
Definition: list.c:631
List * lappend(List *list, void *datum)
Definition: list.c:339
Datum lca(PG_FUNCTION_ARGS)
Definition: ltree_op.c:570
List * mbms_int_members(List *a, const List *b)
Bitmapset * mbms_overlap_sets(const List *a, const List *b)
bool mbms_is_member(int listidx, int bitidx, const List *a)
List * mbms_add_member(List *a, int listidx, int bitidx)
List * mbms_add_members(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