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