| 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 |
|
| 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 * |
| 71 |
mbms_add_members(List *a, const List *b) |
| 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 |
{ |
| 82 |
Bitmapset *bmsa = lfirst_node(Bitmapset, lca); |
| 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 * |
| 100 |
mbms_int_members(List *a, const List *b) |
| 101 |
{ |
| 102 |
ListCell *lca, |
| 103 |
*lcb; |
| 104 |
|
| 105 |
/* Remove any elements of a that are no longer of use */ |
| 106 |
a = list_truncate(a, list_length(b)); |
| 107 |
/* forboth will stop at the end of the shorter list, which is fine */ |
| 108 |
forboth(lca, a, lcb, b) |
| 109 |
{ |
| 110 |
Bitmapset *bmsa = lfirst_node(Bitmapset, lca); |
| 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 |
} |