Age Owner Branch data TLA Line data Source code
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 *
515 tgl@sss.pgh.pa.us 44 :CBC 51248 : mbms_add_member(List *a, int listidx, int bitidx)
45 : : {
46 : : Bitmapset *bms;
47 : : ListCell *lc;
48 : :
49 [ + - - + ]: 51248 : if (listidx < 0 || bitidx < 0)
515 tgl@sss.pgh.pa.us 50 [ # # ]:UBC 0 : elog(ERROR, "negative multibitmapset member index not allowed");
51 : : /* Add empty elements as needed */
515 tgl@sss.pgh.pa.us 52 [ + + ]:CBC 248188 : while (list_length(a) <= listidx)
53 : 196940 : a = lappend(a, NULL);
54 : : /* Update the target element */
55 : 51248 : lc = list_nth_cell(a, listidx);
56 : 51248 : bms = lfirst_node(Bitmapset, lc);
57 : 51248 : bms = bms_add_member(bms, bitidx);
58 : 51248 : lfirst(lc) = bms;
59 : 51248 : 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 : 131485 : mbms_add_members(List *a, const List *b)
72 : : {
73 : : ListCell *lca,
74 : : *lcb;
75 : :
76 : : /* Add empty elements to a, as needed */
77 [ + + ]: 367826 : while (list_length(a) < list_length(b))
78 : 236341 : a = lappend(a, NULL);
79 : : /* forboth will stop at the end of the shorter list, which is fine */
80 [ + + + + : 462255 : forboth(lca, a, lcb, b)
+ + + + +
+ + + +
+ ]
81 : : {
82 : 330770 : Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
83 : 330770 : const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
84 : :
85 : 330770 : bmsa = bms_add_members(bmsa, bmsb);
86 : 330770 : lfirst(lca) = bmsa;
87 : : }
88 : 131485 : 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 : 154 : 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 : 154 : a = list_truncate(a, list_length(b));
107 : : /* forboth will stop at the end of the shorter list, which is fine */
108 [ + + + + : 1264 : forboth(lca, a, lcb, b)
+ + + + +
+ + - +
+ ]
109 : : {
110 : 1110 : Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
111 : 1110 : const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
112 : :
113 : 1110 : bmsa = bms_int_members(bmsa, bmsb);
114 : 1110 : lfirst(lca) = bmsa;
115 : : }
116 : 154 : 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
515 tgl@sss.pgh.pa.us 126 :UBC 0 : 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 [ # # # # ]: 0 : if (listidx < 0 || bitidx < 0)
132 [ # # ]: 0 : elog(ERROR, "negative multibitmapset member index not allowed");
133 [ # # ]: 0 : if (listidx >= list_length(a))
134 : 0 : return false;
135 : 0 : bms = list_nth_node(Bitmapset, a, listidx);
136 : 0 : 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 *
515 tgl@sss.pgh.pa.us 146 :CBC 21117 : mbms_overlap_sets(const List *a, const List *b)
147 : : {
148 : 21117 : Bitmapset *result = NULL;
149 : : ListCell *lca,
150 : : *lcb;
151 : :
152 : : /* forboth will stop at the end of the shorter list, which is fine */
153 [ + + + + : 23095 : forboth(lca, a, lcb, b)
+ + + + +
+ + + +
+ ]
154 : : {
155 : 1978 : const Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
156 : 1978 : const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
157 : :
158 [ + + ]: 1978 : if (bms_overlap(bmsa, bmsb))
159 : 510 : result = bms_add_member(result, foreach_current_index(lca));
160 : : }
161 : 21117 : return result;
162 : : }
|
