Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * bitmapset.c
4 : : * PostgreSQL generic bitmap set package
5 : : *
6 : : * A bitmap set can represent any set of nonnegative integers, although
7 : : * it is mainly intended for sets where the maximum value is not large,
8 : : * say at most a few hundred. By convention, we always represent a set with
9 : : * the minimum possible number of words, i.e, there are never any trailing
10 : : * zero words. Enforcing this requires that an empty set is represented as
11 : : * NULL. Because an empty Bitmapset is represented as NULL, a non-NULL
12 : : * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to
13 : : * speed up various loops over the Bitmapset's words array by using "do while"
14 : : * loops instead of "for" loops. This means the code does not waste time
15 : : * checking the loop condition before the first iteration. For Bitmapsets
16 : : * containing only a single word (likely the majority of them) this halves the
17 : : * number of loop condition checks.
18 : : *
19 : : * Callers must ensure that the set returned by functions in this file which
20 : : * adjust the members of an existing set is assigned to all pointers pointing
21 : : * to that existing set. No guarantees are made that we'll ever modify the
22 : : * existing set in-place and return it.
23 : : *
24 : : * To help find bugs caused by callers failing to record the return value of
25 : : * the function which manipulates an existing set, we support building with
26 : : * REALLOCATE_BITMAPSETS. This results in the set being reallocated each time
27 : : * the set is altered and the existing being pfreed. This is useful as if any
28 : : * references still exist to the old set, we're more likely to notice as
29 : : * any users of the old set will be accessing pfree'd memory. This option is
30 : : * only intended to be used for debugging.
31 : : *
32 : : * Copyright (c) 2003-2026, PostgreSQL Global Development Group
33 : : *
34 : : * IDENTIFICATION
35 : : * src/backend/nodes/bitmapset.c
36 : : *
37 : : *-------------------------------------------------------------------------
38 : : */
39 : : #include "postgres.h"
40 : :
41 : : #include "common/hashfn.h"
42 : : #include "nodes/bitmapset.h"
43 : : #include "nodes/pg_list.h"
44 : : #include "port/pg_bitutils.h"
45 : :
46 : :
47 : : #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
48 : : #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
49 : :
50 : : #define BITMAPSET_SIZE(nwords) \
51 : : (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
52 : :
53 : : /*----------
54 : : * This is a well-known cute trick for isolating the rightmost one-bit
55 : : * in a word. It assumes two's complement arithmetic. Consider any
56 : : * nonzero value, and focus attention on the rightmost one. The value is
57 : : * then something like
58 : : * xxxxxx10000
59 : : * where x's are unspecified bits. The two's complement negative is formed
60 : : * by inverting all the bits and adding one. Inversion gives
61 : : * yyyyyy01111
62 : : * where each y is the inverse of the corresponding x. Incrementing gives
63 : : * yyyyyy10000
64 : : * and then ANDing with the original value gives
65 : : * 00000010000
66 : : * This works for all cases except original value = zero, where of course
67 : : * we get zero.
68 : : *----------
69 : : */
70 : : #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
71 : :
72 : : #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x))
73 : :
74 : : #ifdef USE_ASSERT_CHECKING
75 : : /*
76 : : * bms_is_valid_set - for cassert builds to check for valid sets
77 : : */
78 : : static bool
79 : 34076419 : bms_is_valid_set(const Bitmapset *a)
80 : : {
81 : : /* NULL is the correct representation of an empty set */
82 [ + + ]: 34076419 : if (a == NULL)
83 : 13581726 : return true;
84 : :
85 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
86 [ + - ]: 20494693 : if (!IsA(a, Bitmapset))
87 : 0 : return false;
88 : :
89 : : /* trailing zero words are not allowed */
90 [ + - ]: 20494693 : if (a->words[a->nwords - 1] == 0)
91 : 0 : return false;
92 : :
93 : 20494693 : return true;
94 : 34076419 : }
95 : : #endif
96 : :
97 : : #ifdef REALLOCATE_BITMAPSETS
98 : : /*
99 : : * bms_copy_and_free
100 : : * Only required in REALLOCATE_BITMAPSETS builds. Provide a simple way
101 : : * to return a freshly allocated set and pfree the original.
102 : : *
103 : : * Note: callers which accept multiple sets must be careful when calling this
104 : : * function to clone one parameter as other parameters may point to the same
105 : : * set. A good option is to call this just before returning the resulting
106 : : * set.
107 : : */
108 : : static Bitmapset *
109 : : bms_copy_and_free(Bitmapset *a)
110 : : {
111 : : Bitmapset *c = bms_copy(a);
112 : :
113 : : bms_free(a);
114 : : return c;
115 : : }
116 : : #endif
117 : :
118 : : /*
119 : : * bms_copy - make a palloc'd copy of a bitmapset
120 : : */
121 : : Bitmapset *
122 : 3763805 : bms_copy(const Bitmapset *a)
123 : : {
124 : 3763805 : Bitmapset *result;
125 : 3763805 : size_t size;
126 : :
127 [ + - ]: 3763805 : Assert(bms_is_valid_set(a));
128 : :
129 [ + + ]: 3763805 : if (a == NULL)
130 : 1826041 : return NULL;
131 : :
132 : 1937764 : size = BITMAPSET_SIZE(a->nwords);
133 : 1937764 : result = (Bitmapset *) palloc(size);
134 : 1937764 : memcpy(result, a, size);
135 : 1937764 : return result;
136 : 3763805 : }
137 : :
138 : : /*
139 : : * bms_equal - are two bitmapsets equal? or both NULL?
140 : : */
141 : : bool
142 : 1531871 : bms_equal(const Bitmapset *a, const Bitmapset *b)
143 : : {
144 : 1531871 : int i;
145 : :
146 [ + - ]: 1531871 : Assert(bms_is_valid_set(a));
147 [ + - ]: 1531871 : Assert(bms_is_valid_set(b));
148 : :
149 : : /* Handle cases where either input is NULL */
150 [ + + ]: 1531871 : if (a == NULL)
151 : : {
152 [ + + ]: 1072834 : if (b == NULL)
153 : 1065881 : return true;
154 : 6953 : return false;
155 : : }
156 [ + + ]: 459037 : else if (b == NULL)
157 : 1267 : return false;
158 : :
159 : : /* can't be equal if the word counts don't match */
160 [ - + ]: 457770 : if (a->nwords != b->nwords)
161 : 0 : return false;
162 : :
163 : : /* check each word matches */
164 : 457770 : i = 0;
165 : 457770 : do
166 : : {
167 [ + + ]: 457770 : if (a->words[i] != b->words[i])
168 : 219096 : return false;
169 [ + - ]: 238674 : } while (++i < a->nwords);
170 : :
171 : 238674 : return true;
172 : 1531871 : }
173 : :
174 : : /*
175 : : * bms_compare - qsort-style comparator for bitmapsets
176 : : *
177 : : * This guarantees to report values as equal iff bms_equal would say they are
178 : : * equal. Otherwise, the highest-numbered bit that is set in one value but
179 : : * not the other determines the result. (This rule means that, for example,
180 : : * {6} is greater than {5}, which seems plausible.)
181 : : */
182 : : int
183 : 3865 : bms_compare(const Bitmapset *a, const Bitmapset *b)
184 : : {
185 : 3865 : int i;
186 : :
187 [ + - ]: 3865 : Assert(bms_is_valid_set(a));
188 [ + - ]: 3865 : Assert(bms_is_valid_set(b));
189 : :
190 : : /* Handle cases where either input is NULL */
191 [ + - ]: 3865 : if (a == NULL)
192 : 0 : return (b == NULL) ? 0 : -1;
193 [ + - ]: 3865 : else if (b == NULL)
194 : 0 : return +1;
195 : :
196 : : /* the set with the most words must be greater */
197 [ - + ]: 3865 : if (a->nwords != b->nwords)
198 : 0 : return (a->nwords > b->nwords) ? +1 : -1;
199 : :
200 : 3865 : i = a->nwords - 1;
201 : 3865 : do
202 : : {
203 : 3865 : bitmapword aw = a->words[i];
204 : 3865 : bitmapword bw = b->words[i];
205 : :
206 [ + - ]: 3865 : if (aw != bw)
207 : 3865 : return (aw > bw) ? +1 : -1;
208 [ + - # # ]: 3865 : } while (--i >= 0);
209 : 0 : return 0;
210 : 3865 : }
211 : :
212 : : /*
213 : : * bms_make_singleton - build a bitmapset containing a single member
214 : : */
215 : : Bitmapset *
216 : 2036813 : bms_make_singleton(int x)
217 : : {
218 : 2036813 : Bitmapset *result;
219 : 2036813 : int wordnum,
220 : : bitnum;
221 : :
222 [ + - ]: 2036813 : if (x < 0)
223 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
224 : 2036813 : wordnum = WORDNUM(x);
225 : 2036813 : bitnum = BITNUM(x);
226 : 2036813 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
227 : 2036813 : result->type = T_Bitmapset;
228 : 2036813 : result->nwords = wordnum + 1;
229 : 2036813 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
230 : 4073626 : return result;
231 : 2036813 : }
232 : :
233 : : /*
234 : : * bms_free - free a bitmapset
235 : : *
236 : : * Same as pfree except for allowing NULL input
237 : : */
238 : : void
239 : 2279174 : bms_free(Bitmapset *a)
240 : : {
241 [ + + ]: 2279174 : if (a)
242 : 760477 : pfree(a);
243 : 2279174 : }
244 : :
245 : :
246 : : /*
247 : : * bms_union - create and return a new set containing all members from both
248 : : * input sets. Both inputs are left unmodified.
249 : : */
250 : : Bitmapset *
251 : 779994 : bms_union(const Bitmapset *a, const Bitmapset *b)
252 : : {
253 : 779994 : Bitmapset *result;
254 : 779994 : const Bitmapset *other;
255 : 779994 : int otherlen;
256 : 779994 : int i;
257 : :
258 [ + - ]: 779994 : Assert(bms_is_valid_set(a));
259 [ + - ]: 779994 : Assert(bms_is_valid_set(b));
260 : :
261 : : /* Handle cases where either input is NULL */
262 [ + + ]: 779994 : if (a == NULL)
263 : 501428 : return bms_copy(b);
264 [ + + ]: 278566 : if (b == NULL)
265 : 126846 : return bms_copy(a);
266 : : /* Identify shorter and longer input; copy the longer one */
267 [ + - ]: 151720 : if (a->nwords <= b->nwords)
268 : : {
269 : 151720 : result = bms_copy(b);
270 : 151720 : other = a;
271 : 151720 : }
272 : : else
273 : : {
274 : 0 : result = bms_copy(a);
275 : 0 : other = b;
276 : : }
277 : : /* And union the shorter input into the result */
278 : 151720 : otherlen = other->nwords;
279 : 151720 : i = 0;
280 : 151720 : do
281 : : {
282 : 151720 : result->words[i] |= other->words[i];
283 [ - + ]: 151720 : } while (++i < otherlen);
284 : 151720 : return result;
285 : 779994 : }
286 : :
287 : : /*
288 : : * bms_intersect - create and return a new set containing members which both
289 : : * input sets have in common. Both inputs are left unmodified.
290 : : */
291 : : Bitmapset *
292 : 414368 : bms_intersect(const Bitmapset *a, const Bitmapset *b)
293 : : {
294 : 414368 : Bitmapset *result;
295 : 414368 : const Bitmapset *other;
296 : 414368 : int lastnonzero;
297 : 414368 : int resultlen;
298 : 414368 : int i;
299 : :
300 [ + - ]: 414368 : Assert(bms_is_valid_set(a));
301 [ + - ]: 414368 : Assert(bms_is_valid_set(b));
302 : :
303 : : /* Handle cases where either input is NULL */
304 [ + + + + ]: 414368 : if (a == NULL || b == NULL)
305 : 207535 : return NULL;
306 : :
307 : : /* Identify shorter and longer input; copy the shorter one */
308 [ + - ]: 206833 : if (a->nwords <= b->nwords)
309 : : {
310 : 206833 : result = bms_copy(a);
311 : 206833 : other = b;
312 : 206833 : }
313 : : else
314 : : {
315 : 0 : result = bms_copy(b);
316 : 0 : other = a;
317 : : }
318 : : /* And intersect the longer input with the result */
319 : 206833 : resultlen = result->nwords;
320 : 206833 : lastnonzero = -1;
321 : 206833 : i = 0;
322 : 206833 : do
323 : : {
324 : 206833 : result->words[i] &= other->words[i];
325 : :
326 [ + + ]: 206833 : if (result->words[i] != 0)
327 : 204626 : lastnonzero = i;
328 [ - + ]: 206833 : } while (++i < resultlen);
329 : : /* If we computed an empty result, we must return NULL */
330 [ + + ]: 206833 : if (lastnonzero == -1)
331 : : {
332 : 2207 : pfree(result);
333 : 2207 : return NULL;
334 : : }
335 : :
336 : : /* get rid of trailing zero words */
337 : 204626 : result->nwords = lastnonzero + 1;
338 : 204626 : return result;
339 : 414368 : }
340 : :
341 : : /*
342 : : * bms_difference - create and return a new set containing all the members of
343 : : * 'a' without the members of 'b'.
344 : : */
345 : : Bitmapset *
346 : 469954 : bms_difference(const Bitmapset *a, const Bitmapset *b)
347 : : {
348 : 469954 : Bitmapset *result;
349 : 469954 : int i;
350 : :
351 [ + - ]: 469954 : Assert(bms_is_valid_set(a));
352 [ + - ]: 469954 : Assert(bms_is_valid_set(b));
353 : :
354 : : /* Handle cases where either input is NULL */
355 [ + + ]: 469954 : if (a == NULL)
356 : 252802 : return NULL;
357 [ + + ]: 217152 : if (b == NULL)
358 : 119321 : return bms_copy(a);
359 : :
360 : : /*
361 : : * In Postgres' usage, an empty result is a very common case, so it's
362 : : * worth optimizing for that by testing bms_nonempty_difference(). This
363 : : * saves us a palloc/pfree cycle compared to checking after-the-fact.
364 : : */
365 [ + + ]: 97831 : if (!bms_nonempty_difference(a, b))
366 : 70769 : return NULL;
367 : :
368 : : /* Copy the left input */
369 : 27062 : result = bms_copy(a);
370 : :
371 : : /* And remove b's bits from result */
372 [ - + ]: 27062 : if (result->nwords > b->nwords)
373 : : {
374 : : /*
375 : : * We'll never need to remove trailing zero words when 'a' has more
376 : : * words than 'b' as the additional words must be non-zero.
377 : : */
378 : 0 : i = 0;
379 : 0 : do
380 : : {
381 : 0 : result->words[i] &= ~b->words[i];
382 [ # # ]: 0 : } while (++i < b->nwords);
383 : 0 : }
384 : : else
385 : : {
386 : 27062 : int lastnonzero = -1;
387 : :
388 : : /* we may need to remove trailing zero words from the result. */
389 : 27062 : i = 0;
390 : 27062 : do
391 : : {
392 : 27062 : result->words[i] &= ~b->words[i];
393 : :
394 : : /* remember the last non-zero word */
395 [ + - ]: 27062 : if (result->words[i] != 0)
396 : 27062 : lastnonzero = i;
397 [ + - ]: 27062 : } while (++i < result->nwords);
398 : :
399 : : /* trim off trailing zero words */
400 : 27062 : result->nwords = lastnonzero + 1;
401 : 27062 : }
402 [ + - ]: 27062 : Assert(result->nwords != 0);
403 : :
404 : : /* Need not check for empty result, since we handled that case above */
405 : 27062 : return result;
406 : 469954 : }
407 : :
408 : : /*
409 : : * bms_is_subset - is A a subset of B?
410 : : */
411 : : bool
412 : 2366320 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
413 : : {
414 : 2366320 : int i;
415 : :
416 [ + - ]: 2366320 : Assert(bms_is_valid_set(a));
417 [ + - ]: 2366320 : Assert(bms_is_valid_set(b));
418 : :
419 : : /* Handle cases where either input is NULL */
420 [ + + ]: 2366320 : if (a == NULL)
421 : 589098 : return true; /* empty set is a subset of anything */
422 [ + + ]: 1777222 : if (b == NULL)
423 : 34665 : return false;
424 : :
425 : : /* 'a' can't be a subset of 'b' if it contains more words */
426 [ - + ]: 1742557 : if (a->nwords > b->nwords)
427 : 0 : return false;
428 : :
429 : : /* Check all 'a' members are set in 'b' */
430 : 1742557 : i = 0;
431 : 1742557 : do
432 : : {
433 [ + + ]: 1742557 : if ((a->words[i] & ~b->words[i]) != 0)
434 : 625926 : return false;
435 [ + - ]: 1116631 : } while (++i < a->nwords);
436 : 1116631 : return true;
437 : 2366320 : }
438 : :
439 : : /*
440 : : * bms_subset_compare - compare A and B for equality/subset relationships
441 : : *
442 : : * This is more efficient than testing bms_is_subset in both directions.
443 : : */
444 : : BMS_Comparison
445 : 250532 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
446 : : {
447 : 250532 : BMS_Comparison result;
448 : 250532 : int shortlen;
449 : 250532 : int i;
450 : :
451 [ + - ]: 250532 : Assert(bms_is_valid_set(a));
452 [ + - ]: 250532 : Assert(bms_is_valid_set(b));
453 : :
454 : : /* Handle cases where either input is NULL */
455 [ + + ]: 250532 : if (a == NULL)
456 : : {
457 [ + + ]: 213160 : if (b == NULL)
458 : 206094 : return BMS_EQUAL;
459 : 7066 : return BMS_SUBSET1;
460 : : }
461 [ + + ]: 37372 : if (b == NULL)
462 : 17697 : return BMS_SUBSET2;
463 : :
464 : : /* Check common words */
465 : 19675 : result = BMS_EQUAL; /* status so far */
466 [ - + ]: 19675 : shortlen = Min(a->nwords, b->nwords);
467 : 19675 : i = 0;
468 : 19675 : do
469 : : {
470 : 19675 : bitmapword aword = a->words[i];
471 : 19675 : bitmapword bword = b->words[i];
472 : :
473 [ + + ]: 19675 : if ((aword & ~bword) != 0)
474 : : {
475 : : /* a is not a subset of b */
476 [ - + ]: 5277 : if (result == BMS_SUBSET1)
477 : 0 : return BMS_DIFFERENT;
478 : 5277 : result = BMS_SUBSET2;
479 : 5277 : }
480 [ + + ]: 19675 : if ((bword & ~aword) != 0)
481 : : {
482 : : /* b is not a subset of a */
483 [ + + ]: 5250 : if (result == BMS_SUBSET2)
484 : 4802 : return BMS_DIFFERENT;
485 : 448 : result = BMS_SUBSET1;
486 : 448 : }
487 [ + + - + ]: 19675 : } while (++i < shortlen);
488 : : /* Check extra words */
489 [ - + ]: 14873 : if (a->nwords > b->nwords)
490 : : {
491 : : /* if a has more words then a is not a subset of b */
492 [ # # ]: 0 : if (result == BMS_SUBSET1)
493 : 0 : return BMS_DIFFERENT;
494 : 0 : return BMS_SUBSET2;
495 : : }
496 [ - + ]: 14873 : else if (a->nwords < b->nwords)
497 : : {
498 : : /* if b has more words then b is not a subset of a */
499 [ # # ]: 0 : if (result == BMS_SUBSET2)
500 : 0 : return BMS_DIFFERENT;
501 : 0 : return BMS_SUBSET1;
502 : : }
503 : 14873 : return result;
504 : 250532 : }
505 : :
506 : : /*
507 : : * bms_is_member - is X a member of A?
508 : : */
509 : : bool
510 : 3398219 : bms_is_member(int x, const Bitmapset *a)
511 : : {
512 : 3398219 : int wordnum,
513 : : bitnum;
514 : :
515 [ + - ]: 3398219 : Assert(bms_is_valid_set(a));
516 : :
517 : : /* XXX better to just return false for x<0 ? */
518 [ + - ]: 3398219 : if (x < 0)
519 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
520 [ + + ]: 3398219 : if (a == NULL)
521 : 1163052 : return false;
522 : :
523 : 2235167 : wordnum = WORDNUM(x);
524 : 2235167 : bitnum = BITNUM(x);
525 [ + + ]: 2235167 : if (wordnum >= a->nwords)
526 : 25 : return false;
527 [ + + ]: 2235142 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528 : 2071643 : return true;
529 : 163499 : return false;
530 : 3398219 : }
531 : :
532 : : /*
533 : : * bms_member_index
534 : : * determine 0-based index of member x in the bitmap
535 : : *
536 : : * Returns (-1) when x is not a member.
537 : : */
538 : : int
539 : 884 : bms_member_index(Bitmapset *a, int x)
540 : : {
541 : 884 : int bitnum;
542 : 884 : int wordnum;
543 : 884 : int result = 0;
544 : 884 : bitmapword mask;
545 : :
546 [ + - ]: 884 : Assert(bms_is_valid_set(a));
547 : :
548 : : /* return -1 if not a member of the bitmap */
549 [ - + ]: 884 : if (!bms_is_member(x, a))
550 : 0 : return -1;
551 : :
552 : 884 : wordnum = WORDNUM(x);
553 : 884 : bitnum = BITNUM(x);
554 : :
555 : : /* count bits in preceding words */
556 [ - + ]: 884 : for (int i = 0; i < wordnum; i++)
557 : : {
558 : 0 : bitmapword w = a->words[i];
559 : :
560 : : /* No need to count the bits in a zero word */
561 [ # # ]: 0 : if (w != 0)
562 : 0 : result += bmw_popcount(w);
563 : 0 : }
564 : :
565 : : /*
566 : : * Now add bits of the last word, but only those before the item. We can
567 : : * do that by applying a mask and then using popcount again. To get
568 : : * 0-based index, we want to count only preceding bits, not the item
569 : : * itself, so we subtract 1.
570 : : */
571 : 884 : mask = ((bitmapword) 1 << bitnum) - 1;
572 : 884 : result += bmw_popcount(a->words[wordnum] & mask);
573 : :
574 : 884 : return result;
575 : 884 : }
576 : :
577 : : /*
578 : : * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
579 : : */
580 : : bool
581 : 2099641 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
582 : : {
583 : 2099641 : int shortlen;
584 : 2099641 : int i;
585 : :
586 [ + - ]: 2099641 : Assert(bms_is_valid_set(a));
587 [ + - ]: 2099641 : Assert(bms_is_valid_set(b));
588 : :
589 : : /* Handle cases where either input is NULL */
590 [ + + + + ]: 2099641 : if (a == NULL || b == NULL)
591 : 1294472 : return false;
592 : : /* Check words in common */
593 [ - + ]: 805169 : shortlen = Min(a->nwords, b->nwords);
594 : 805169 : i = 0;
595 : 805169 : do
596 : : {
597 [ + + ]: 805169 : if ((a->words[i] & b->words[i]) != 0)
598 : 463907 : return true;
599 [ + - ]: 341262 : } while (++i < shortlen);
600 : 341262 : return false;
601 : 2099641 : }
602 : :
603 : : /*
604 : : * bms_overlap_list - does a set overlap an integer list?
605 : : */
606 : : bool
607 : 278 : bms_overlap_list(const Bitmapset *a, const List *b)
608 : : {
609 : 278 : ListCell *lc;
610 : 278 : int wordnum,
611 : : bitnum;
612 : :
613 [ + - ]: 278 : Assert(bms_is_valid_set(a));
614 : :
615 [ + + + + ]: 278 : if (a == NULL || b == NIL)
616 : 255 : return false;
617 : :
618 [ + - + + : 56 : foreach(lc, b)
+ + + + ]
619 : : {
620 : 33 : int x = lfirst_int(lc);
621 : :
622 [ + - ]: 33 : if (x < 0)
623 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
624 : 33 : wordnum = WORDNUM(x);
625 : 33 : bitnum = BITNUM(x);
626 [ - + ]: 33 : if (wordnum < a->nwords)
627 [ + + ]: 33 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
628 : 13 : return true;
629 [ + + ]: 33 : }
630 : :
631 : 10 : return false;
632 : 278 : }
633 : :
634 : : /*
635 : : * bms_nonempty_difference - do sets have a nonempty difference?
636 : : *
637 : : * i.e., are any members set in 'a' that are not also set in 'b'.
638 : : */
639 : : bool
640 : 341259 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
641 : : {
642 : 341259 : int i;
643 : :
644 [ + - ]: 341259 : Assert(bms_is_valid_set(a));
645 [ + - ]: 341259 : Assert(bms_is_valid_set(b));
646 : :
647 : : /* Handle cases where either input is NULL */
648 [ + + ]: 341259 : if (a == NULL)
649 : 586 : return false;
650 [ + - ]: 340673 : if (b == NULL)
651 : 0 : return true;
652 : : /* if 'a' has more words then it must contain additional members */
653 [ - + ]: 340673 : if (a->nwords > b->nwords)
654 : 0 : return true;
655 : : /* Check all 'a' members are set in 'b' */
656 : 340673 : i = 0;
657 : 340673 : do
658 : : {
659 [ + + ]: 340673 : if ((a->words[i] & ~b->words[i]) != 0)
660 : 119153 : return true;
661 [ + - ]: 221520 : } while (++i < a->nwords);
662 : 221520 : return false;
663 : 341259 : }
664 : :
665 : : /*
666 : : * bms_singleton_member - return the sole integer member of set
667 : : *
668 : : * Raises error if |a| is not 1.
669 : : */
670 : : int
671 : 67682 : bms_singleton_member(const Bitmapset *a)
672 : : {
673 : 67682 : int result = -1;
674 : 67682 : int nwords;
675 : 67682 : int wordnum;
676 : :
677 [ + - ]: 67682 : Assert(bms_is_valid_set(a));
678 : :
679 [ + - ]: 67682 : if (a == NULL)
680 [ # # # # ]: 0 : elog(ERROR, "bitmapset is empty");
681 : :
682 : 67682 : nwords = a->nwords;
683 : 67682 : wordnum = 0;
684 : 67682 : do
685 : : {
686 : 67682 : bitmapword w = a->words[wordnum];
687 : :
688 [ - + ]: 67682 : if (w != 0)
689 : : {
690 [ + - ]: 67682 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
691 [ # # # # ]: 0 : elog(ERROR, "bitmapset has multiple members");
692 : 67682 : result = wordnum * BITS_PER_BITMAPWORD;
693 : 67682 : result += bmw_rightmost_one_pos(w);
694 : 67682 : }
695 [ - + ]: 67682 : } while (++wordnum < nwords);
696 : :
697 : : /* we don't expect non-NULL sets to be empty */
698 [ + - ]: 67682 : Assert(result >= 0);
699 : 135364 : return result;
700 : 67682 : }
701 : :
702 : : /*
703 : : * bms_get_singleton_member
704 : : *
705 : : * Test whether the given set is a singleton.
706 : : * If so, set *member to the value of its sole member, and return true.
707 : : * If not, return false, without changing *member.
708 : : *
709 : : * This is more convenient and faster than calling bms_membership() and then
710 : : * bms_singleton_member(), if we don't care about distinguishing empty sets
711 : : * from multiple-member sets.
712 : : */
713 : : bool
714 : 228355 : bms_get_singleton_member(const Bitmapset *a, int *member)
715 : : {
716 : 228355 : int result = -1;
717 : 228355 : int nwords;
718 : 228355 : int wordnum;
719 : :
720 [ + - ]: 228355 : Assert(bms_is_valid_set(a));
721 : :
722 [ + - ]: 228355 : if (a == NULL)
723 : 0 : return false;
724 : :
725 : 228355 : nwords = a->nwords;
726 : 228355 : wordnum = 0;
727 : 228355 : do
728 : : {
729 : 228355 : bitmapword w = a->words[wordnum];
730 : :
731 [ - + ]: 228355 : if (w != 0)
732 : : {
733 [ + - + + ]: 228355 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
734 : 36787 : return false;
735 : 191568 : result = wordnum * BITS_PER_BITMAPWORD;
736 : 191568 : result += bmw_rightmost_one_pos(w);
737 : 191568 : }
738 [ + + - + ]: 228355 : } while (++wordnum < nwords);
739 : :
740 : : /* we don't expect non-NULL sets to be empty */
741 [ + - ]: 191568 : Assert(result >= 0);
742 : 191568 : *member = result;
743 : 191568 : return true;
744 : 228355 : }
745 : :
746 : : /*
747 : : * bms_num_members - count members of set
748 : : */
749 : : int
750 : 756122 : bms_num_members(const Bitmapset *a)
751 : : {
752 : 756122 : int result = 0;
753 : 756122 : int nwords;
754 : 756122 : int wordnum;
755 : :
756 [ + - ]: 756122 : Assert(bms_is_valid_set(a));
757 : :
758 [ + + ]: 756122 : if (a == NULL)
759 : 53104 : return 0;
760 : :
761 : 703018 : nwords = a->nwords;
762 : 703018 : wordnum = 0;
763 : 703018 : do
764 : : {
765 : 703018 : bitmapword w = a->words[wordnum];
766 : :
767 : : /* No need to count the bits in a zero word */
768 [ - + ]: 703018 : if (w != 0)
769 : 703018 : result += bmw_popcount(w);
770 [ - + ]: 703018 : } while (++wordnum < nwords);
771 : 703018 : return result;
772 : 756122 : }
773 : :
774 : : /*
775 : : * bms_membership - does a set have zero, one, or multiple members?
776 : : *
777 : : * This is faster than making an exact count with bms_num_members().
778 : : */
779 : : BMS_Membership
780 : 345195 : bms_membership(const Bitmapset *a)
781 : : {
782 : 345195 : BMS_Membership result = BMS_EMPTY_SET;
783 : 345195 : int nwords;
784 : 345195 : int wordnum;
785 : :
786 [ + - ]: 345195 : Assert(bms_is_valid_set(a));
787 : :
788 [ + + ]: 345195 : if (a == NULL)
789 : 80 : return BMS_EMPTY_SET;
790 : :
791 : 345115 : nwords = a->nwords;
792 : 345115 : wordnum = 0;
793 : 345115 : do
794 : : {
795 : 345115 : bitmapword w = a->words[wordnum];
796 : :
797 [ - + ]: 345115 : if (w != 0)
798 : : {
799 [ + - + + ]: 345115 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
800 : 128766 : return BMS_MULTIPLE;
801 : 216349 : result = BMS_SINGLETON;
802 : 216349 : }
803 [ + + + - ]: 345115 : } while (++wordnum < nwords);
804 : 216349 : return result;
805 : 345195 : }
806 : :
807 : :
808 : : /*
809 : : * bms_add_member - add a specified member to set
810 : : *
811 : : * 'a' is recycled when possible.
812 : : */
813 : : Bitmapset *
814 : 2618146 : bms_add_member(Bitmapset *a, int x)
815 : : {
816 : 2618146 : int wordnum,
817 : : bitnum;
818 : :
819 [ + - ]: 2618146 : Assert(bms_is_valid_set(a));
820 : :
821 [ + - ]: 2618146 : if (x < 0)
822 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
823 [ + + ]: 2618146 : if (a == NULL)
824 : 1623842 : return bms_make_singleton(x);
825 : :
826 : 994304 : wordnum = WORDNUM(x);
827 : 994304 : bitnum = BITNUM(x);
828 : :
829 : : /* enlarge the set if necessary */
830 [ + + ]: 994304 : if (wordnum >= a->nwords)
831 : : {
832 : 10 : int oldnwords = a->nwords;
833 : 10 : int i;
834 : :
835 : 10 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
836 : 10 : a->nwords = wordnum + 1;
837 : : /* zero out the enlarged portion */
838 : 10 : i = oldnwords;
839 : 10 : do
840 : : {
841 : 58 : a->words[i] = 0;
842 [ + + ]: 58 : } while (++i < a->nwords);
843 : 10 : }
844 : :
845 : 994304 : a->words[wordnum] |= ((bitmapword) 1 << bitnum);
846 : :
847 : : #ifdef REALLOCATE_BITMAPSETS
848 : :
849 : : /*
850 : : * There's no guarantee that the repalloc returned a new pointer, so copy
851 : : * and free unconditionally here.
852 : : */
853 : : a = bms_copy_and_free(a);
854 : : #endif
855 : :
856 : 994304 : return a;
857 : 2618146 : }
858 : :
859 : : /*
860 : : * bms_del_member - remove a specified member from set
861 : : *
862 : : * No error if x is not currently a member of set
863 : : *
864 : : * 'a' is recycled when possible.
865 : : */
866 : : Bitmapset *
867 : 197976 : bms_del_member(Bitmapset *a, int x)
868 : : {
869 : 197976 : int wordnum,
870 : : bitnum;
871 : :
872 [ + - ]: 197976 : Assert(bms_is_valid_set(a));
873 : :
874 [ + - ]: 197976 : if (x < 0)
875 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
876 [ + + ]: 197976 : if (a == NULL)
877 : 64173 : return NULL;
878 : :
879 : 133803 : wordnum = WORDNUM(x);
880 : 133803 : bitnum = BITNUM(x);
881 : :
882 : : #ifdef REALLOCATE_BITMAPSETS
883 : : a = bms_copy_and_free(a);
884 : : #endif
885 : :
886 : : /* member can't exist. Return 'a' unmodified */
887 [ - + ]: 133803 : if (unlikely(wordnum >= a->nwords))
888 : 0 : return a;
889 : :
890 : 133803 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
891 : :
892 : : /* when last word becomes empty, trim off all trailing empty words */
893 [ + + - + ]: 133803 : if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
894 : : {
895 : : /* find the last non-empty word and make that the new final word */
896 [ - + - + ]: 59074 : for (int i = wordnum - 1; i >= 0; i--)
897 : : {
898 [ # # ]: 0 : if (a->words[i] != 0)
899 : : {
900 : 0 : a->nwords = i + 1;
901 : 0 : return a;
902 : : }
903 : 0 : }
904 : :
905 : : /* the set is now empty */
906 : 59074 : pfree(a);
907 : 59074 : return NULL;
908 : : }
909 : 74729 : return a;
910 : 197976 : }
911 : :
912 : : /*
913 : : * bms_add_members - like bms_union, but left input is recycled when possible
914 : : */
915 : : Bitmapset *
916 : 1318172 : bms_add_members(Bitmapset *a, const Bitmapset *b)
917 : : {
918 : 1318172 : Bitmapset *result;
919 : 1318172 : const Bitmapset *other;
920 : 1318172 : int otherlen;
921 : 1318172 : int i;
922 : :
923 [ + - ]: 1318172 : Assert(bms_is_valid_set(a));
924 [ + - ]: 1318172 : Assert(bms_is_valid_set(b));
925 : :
926 : : /* Handle cases where either input is NULL */
927 [ + + ]: 1318172 : if (a == NULL)
928 : 694180 : return bms_copy(b);
929 [ + + ]: 623992 : if (b == NULL)
930 : : {
931 : : #ifdef REALLOCATE_BITMAPSETS
932 : : a = bms_copy_and_free(a);
933 : : #endif
934 : :
935 : 416086 : return a;
936 : : }
937 : : /* Identify shorter and longer input; copy the longer one if needed */
938 [ - + ]: 207906 : if (a->nwords < b->nwords)
939 : : {
940 : 0 : result = bms_copy(b);
941 : 0 : other = a;
942 : 0 : }
943 : : else
944 : : {
945 : 207906 : result = a;
946 : 207906 : other = b;
947 : : }
948 : : /* And union the shorter input into the result */
949 : 207906 : otherlen = other->nwords;
950 : 207906 : i = 0;
951 : 207906 : do
952 : : {
953 : 207906 : result->words[i] |= other->words[i];
954 [ - + ]: 207906 : } while (++i < otherlen);
955 [ + - ]: 207906 : if (result != a)
956 : 0 : pfree(a);
957 : : #ifdef REALLOCATE_BITMAPSETS
958 : : else
959 : : result = bms_copy_and_free(result);
960 : : #endif
961 : :
962 : 207906 : return result;
963 : 1318172 : }
964 : :
965 : : /*
966 : : * bms_replace_members
967 : : * Remove all existing members from 'a' and repopulate the set with members
968 : : * from 'b', recycling 'a', when possible.
969 : : */
970 : : Bitmapset *
971 : 2247 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
972 : : {
973 : 2247 : int i;
974 : :
975 [ + - ]: 2247 : Assert(bms_is_valid_set(a));
976 [ + - ]: 2247 : Assert(bms_is_valid_set(b));
977 : :
978 [ + - ]: 2247 : if (a == NULL)
979 : 0 : return bms_copy(b);
980 [ + - ]: 2247 : if (b == NULL)
981 : : {
982 : 0 : pfree(a);
983 : 0 : return NULL;
984 : : }
985 : :
986 [ + - ]: 2247 : if (a->nwords < b->nwords)
987 : 0 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
988 : :
989 : 2247 : i = 0;
990 : 2247 : do
991 : : {
992 : 2247 : a->words[i] = b->words[i];
993 [ - + ]: 2247 : } while (++i < b->nwords);
994 : :
995 : 2247 : a->nwords = b->nwords;
996 : :
997 : : #ifdef REALLOCATE_BITMAPSETS
998 : :
999 : : /*
1000 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1001 : : * and free unconditionally here.
1002 : : */
1003 : : a = bms_copy_and_free(a);
1004 : : #endif
1005 : :
1006 : 2247 : return a;
1007 : 2247 : }
1008 : :
1009 : : /*
1010 : : * bms_add_range
1011 : : * Add members in the range of 'lower' to 'upper' to the set.
1012 : : *
1013 : : * Note this could also be done by calling bms_add_member in a loop, however,
1014 : : * using this function will be faster when the range is large as we work at
1015 : : * the bitmapword level rather than at bit level.
1016 : : */
1017 : : Bitmapset *
1018 : 6690 : bms_add_range(Bitmapset *a, int lower, int upper)
1019 : : {
1020 : 6690 : int lwordnum,
1021 : : lbitnum,
1022 : : uwordnum,
1023 : : ushiftbits,
1024 : : wordnum;
1025 : :
1026 [ + - ]: 6690 : Assert(bms_is_valid_set(a));
1027 : :
1028 : : /* do nothing if nothing is called for, without further checking */
1029 [ + + ]: 6690 : if (upper < lower)
1030 : : {
1031 : : #ifdef REALLOCATE_BITMAPSETS
1032 : : a = bms_copy_and_free(a);
1033 : : #endif
1034 : :
1035 : 4 : return a;
1036 : : }
1037 : :
1038 [ + - ]: 6686 : if (lower < 0)
1039 [ # # # # ]: 0 : elog(ERROR, "negative bitmapset member not allowed");
1040 : 6686 : uwordnum = WORDNUM(upper);
1041 : :
1042 [ + + ]: 6686 : if (a == NULL)
1043 : : {
1044 : 6679 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1045 : 6679 : a->type = T_Bitmapset;
1046 : 6679 : a->nwords = uwordnum + 1;
1047 : 6679 : }
1048 [ + - ]: 7 : else if (uwordnum >= a->nwords)
1049 : : {
1050 : 0 : int oldnwords = a->nwords;
1051 : 0 : int i;
1052 : :
1053 : : /* ensure we have enough words to store the upper bit */
1054 : 0 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1055 : 0 : a->nwords = uwordnum + 1;
1056 : : /* zero out the enlarged portion */
1057 : 0 : i = oldnwords;
1058 : 0 : do
1059 : : {
1060 : 0 : a->words[i] = 0;
1061 [ # # ]: 0 : } while (++i < a->nwords);
1062 : 0 : }
1063 : :
1064 : 6686 : wordnum = lwordnum = WORDNUM(lower);
1065 : :
1066 : 6686 : lbitnum = BITNUM(lower);
1067 : 6686 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
1068 : :
1069 : : /*
1070 : : * Special case when lwordnum is the same as uwordnum we must perform the
1071 : : * upper and lower masking on the word.
1072 : : */
1073 [ + - ]: 6686 : if (lwordnum == uwordnum)
1074 : : {
1075 : 13372 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
1076 : 6686 : & (~(bitmapword) 0) >> ushiftbits;
1077 : 6686 : }
1078 : : else
1079 : : {
1080 : : /* turn on lbitnum and all bits left of it */
1081 : 0 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1082 : :
1083 : : /* turn on all bits for any intermediate words */
1084 [ # # ]: 0 : while (wordnum < uwordnum)
1085 : 0 : a->words[wordnum++] = ~(bitmapword) 0;
1086 : :
1087 : : /* turn on upper's bit and all bits right of it. */
1088 : 0 : a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
1089 : : }
1090 : :
1091 : : #ifdef REALLOCATE_BITMAPSETS
1092 : :
1093 : : /*
1094 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1095 : : * and free unconditionally here.
1096 : : */
1097 : : a = bms_copy_and_free(a);
1098 : : #endif
1099 : :
1100 : 6686 : return a;
1101 : 6690 : }
1102 : :
1103 : : /*
1104 : : * bms_int_members - like bms_intersect, but left input is recycled when
1105 : : * possible
1106 : : */
1107 : : Bitmapset *
1108 : 63839 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1109 : : {
1110 : 63839 : int lastnonzero;
1111 : 63839 : int shortlen;
1112 : 63839 : int i;
1113 : :
1114 [ + - ]: 63839 : Assert(bms_is_valid_set(a));
1115 [ + - ]: 63839 : Assert(bms_is_valid_set(b));
1116 : :
1117 : : /* Handle cases where either input is NULL */
1118 [ + + ]: 63839 : if (a == NULL)
1119 : 2221 : return NULL;
1120 [ + + ]: 61618 : if (b == NULL)
1121 : : {
1122 : 500 : pfree(a);
1123 : 500 : return NULL;
1124 : : }
1125 : :
1126 : : /* Intersect b into a; we need never copy */
1127 [ - + ]: 61118 : shortlen = Min(a->nwords, b->nwords);
1128 : 61118 : lastnonzero = -1;
1129 : 61118 : i = 0;
1130 : 61118 : do
1131 : : {
1132 : 61118 : a->words[i] &= b->words[i];
1133 : :
1134 [ + + ]: 61118 : if (a->words[i] != 0)
1135 : 51286 : lastnonzero = i;
1136 [ - + ]: 61118 : } while (++i < shortlen);
1137 : :
1138 : : /* If we computed an empty result, we must return NULL */
1139 [ + + ]: 61118 : if (lastnonzero == -1)
1140 : : {
1141 : 9832 : pfree(a);
1142 : 9832 : return NULL;
1143 : : }
1144 : :
1145 : : /* get rid of trailing zero words */
1146 : 51286 : a->nwords = lastnonzero + 1;
1147 : :
1148 : : #ifdef REALLOCATE_BITMAPSETS
1149 : : a = bms_copy_and_free(a);
1150 : : #endif
1151 : :
1152 : 51286 : return a;
1153 : 63839 : }
1154 : :
1155 : : /*
1156 : : * bms_del_members - delete members in 'a' that are set in 'b'. 'a' is
1157 : : * recycled when possible.
1158 : : */
1159 : : Bitmapset *
1160 : 183506 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1161 : : {
1162 : 183506 : int i;
1163 : :
1164 [ + - ]: 183506 : Assert(bms_is_valid_set(a));
1165 [ + - ]: 183506 : Assert(bms_is_valid_set(b));
1166 : :
1167 : : /* Handle cases where either input is NULL */
1168 [ + + ]: 183506 : if (a == NULL)
1169 : 87168 : return NULL;
1170 [ + + ]: 96338 : if (b == NULL)
1171 : : {
1172 : : #ifdef REALLOCATE_BITMAPSETS
1173 : : a = bms_copy_and_free(a);
1174 : : #endif
1175 : :
1176 : 22060 : return a;
1177 : : }
1178 : :
1179 : : /* Remove b's bits from a; we need never copy */
1180 [ - + ]: 74278 : if (a->nwords > b->nwords)
1181 : : {
1182 : : /*
1183 : : * We'll never need to remove trailing zero words when 'a' has more
1184 : : * words than 'b'.
1185 : : */
1186 : 0 : i = 0;
1187 : 0 : do
1188 : : {
1189 : 0 : a->words[i] &= ~b->words[i];
1190 [ # # ]: 0 : } while (++i < b->nwords);
1191 : 0 : }
1192 : : else
1193 : : {
1194 : 74278 : int lastnonzero = -1;
1195 : :
1196 : : /* we may need to remove trailing zero words from the result. */
1197 : 74278 : i = 0;
1198 : 74278 : do
1199 : : {
1200 : 74278 : a->words[i] &= ~b->words[i];
1201 : :
1202 : : /* remember the last non-zero word */
1203 [ + + ]: 74278 : if (a->words[i] != 0)
1204 : 16254 : lastnonzero = i;
1205 [ - + ]: 74278 : } while (++i < a->nwords);
1206 : :
1207 : : /* check if 'a' has become empty */
1208 [ + + ]: 74278 : if (lastnonzero == -1)
1209 : : {
1210 : 58024 : pfree(a);
1211 : 58024 : return NULL;
1212 : : }
1213 : :
1214 : : /* trim off any trailing zero words */
1215 : 16254 : a->nwords = lastnonzero + 1;
1216 [ + + ]: 74278 : }
1217 : :
1218 : : #ifdef REALLOCATE_BITMAPSETS
1219 : : a = bms_copy_and_free(a);
1220 : : #endif
1221 : :
1222 : 16254 : return a;
1223 : 183506 : }
1224 : :
1225 : : /*
1226 : : * bms_join - like bms_union, but *either* input *may* be recycled
1227 : : */
1228 : : Bitmapset *
1229 : 208477 : bms_join(Bitmapset *a, Bitmapset *b)
1230 : : {
1231 : 208477 : Bitmapset *result;
1232 : 208477 : Bitmapset *other;
1233 : 208477 : int otherlen;
1234 : 208477 : int i;
1235 : :
1236 [ + - ]: 208477 : Assert(bms_is_valid_set(a));
1237 [ + - ]: 208477 : Assert(bms_is_valid_set(b));
1238 : :
1239 : : /* Handle cases where either input is NULL */
1240 [ + + ]: 208477 : if (a == NULL)
1241 : : {
1242 : : #ifdef REALLOCATE_BITMAPSETS
1243 : : b = bms_copy_and_free(b);
1244 : : #endif
1245 : :
1246 : 70618 : return b;
1247 : : }
1248 [ + + ]: 137859 : if (b == NULL)
1249 : : {
1250 : : #ifdef REALLOCATE_BITMAPSETS
1251 : : a = bms_copy_and_free(a);
1252 : : #endif
1253 : :
1254 : 12787 : return a;
1255 : : }
1256 : :
1257 : : /* Identify shorter and longer input; use longer one as result */
1258 [ - + ]: 125072 : if (a->nwords < b->nwords)
1259 : : {
1260 : 0 : result = b;
1261 : 0 : other = a;
1262 : 0 : }
1263 : : else
1264 : : {
1265 : 125072 : result = a;
1266 : 125072 : other = b;
1267 : : }
1268 : : /* And union the shorter input into the result */
1269 : 125072 : otherlen = other->nwords;
1270 : 125072 : i = 0;
1271 : 125072 : do
1272 : : {
1273 : 125072 : result->words[i] |= other->words[i];
1274 [ - + ]: 125072 : } while (++i < otherlen);
1275 [ - + ]: 125072 : if (other != result) /* pure paranoia */
1276 : 125072 : pfree(other);
1277 : :
1278 : : #ifdef REALLOCATE_BITMAPSETS
1279 : : result = bms_copy_and_free(result);
1280 : : #endif
1281 : :
1282 : 125072 : return result;
1283 : 208477 : }
1284 : :
1285 : : /*
1286 : : * bms_next_member - find next member of a set
1287 : : *
1288 : : * Returns smallest member greater than "prevbit", or -2 if there is none.
1289 : : * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
1290 : : *
1291 : : * This is intended as support for iterating through the members of a set.
1292 : : * The typical pattern is
1293 : : *
1294 : : * x = -1;
1295 : : * while ((x = bms_next_member(inputset, x)) >= 0)
1296 : : * process member x;
1297 : : *
1298 : : * Notice that when there are no more members, we return -2, not -1 as you
1299 : : * might expect. The rationale for that is to allow distinguishing the
1300 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1301 : : * It makes no difference in simple loop usage, but complex iteration logic
1302 : : * might need such an ability.
1303 : : */
1304 : : int
1305 : 2624195 : bms_next_member(const Bitmapset *a, int prevbit)
1306 : : {
1307 : 2624195 : int nwords;
1308 : 2624195 : bitmapword mask;
1309 : :
1310 [ + - ]: 2624195 : Assert(bms_is_valid_set(a));
1311 : :
1312 [ + + ]: 2624195 : if (a == NULL)
1313 : 403416 : return -2;
1314 : 2220779 : nwords = a->nwords;
1315 : 2220779 : prevbit++;
1316 : 2220779 : mask = (~(bitmapword) 0) << BITNUM(prevbit);
1317 [ + + + + ]: 4441558 : for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1318 : : {
1319 : 2220779 : bitmapword w = a->words[wordnum];
1320 : :
1321 : : /* ignore bits before prevbit */
1322 : 2220779 : w &= mask;
1323 : :
1324 [ + + ]: 2220779 : if (w != 0)
1325 : : {
1326 : 1448880 : int result;
1327 : :
1328 : 1448880 : result = wordnum * BITS_PER_BITMAPWORD;
1329 : 1448880 : result += bmw_rightmost_one_pos(w);
1330 : 1448880 : return result;
1331 : 1448880 : }
1332 : :
1333 : : /* in subsequent words, consider all bits */
1334 : 771899 : mask = (~(bitmapword) 0);
1335 [ + + ]: 2220779 : }
1336 : 771899 : return -2;
1337 : 2624195 : }
1338 : :
1339 : : /*
1340 : : * bms_prev_member - find prev member of a set
1341 : : *
1342 : : * Returns largest member less than "prevbit", or -2 if there is none.
1343 : : * "prevbit" must NOT be more than one above the highest possible bit that can
1344 : : * be set in the Bitmapset at its current size.
1345 : : *
1346 : : * To ease finding the highest set bit for the initial loop, the special
1347 : : * prevbit value of -1 can be passed to have the function find the highest
1348 : : * valued member in the set.
1349 : : *
1350 : : * This is intended as support for iterating through the members of a set in
1351 : : * reverse. The typical pattern is
1352 : : *
1353 : : * x = -1;
1354 : : * while ((x = bms_prev_member(inputset, x)) >= 0)
1355 : : * process member x;
1356 : : *
1357 : : * Notice that when there are no more members, we return -2, not -1 as you
1358 : : * might expect. The rationale for that is to allow distinguishing the
1359 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1360 : : * It makes no difference in simple loop usage, but complex iteration logic
1361 : : * might need such an ability.
1362 : : */
1363 : :
1364 : : int
1365 : 3 : bms_prev_member(const Bitmapset *a, int prevbit)
1366 : : {
1367 : 3 : int ushiftbits;
1368 : 3 : bitmapword mask;
1369 : :
1370 [ + - ]: 3 : Assert(bms_is_valid_set(a));
1371 : :
1372 : : /*
1373 : : * If set is NULL or if there are no more bits to the right then we've
1374 : : * nothing to do.
1375 : : */
1376 [ + - - + ]: 3 : if (a == NULL || prevbit == 0)
1377 : 0 : return -2;
1378 : :
1379 : : /* Validate callers didn't give us something out of range */
1380 [ + - ]: 3 : Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
1381 [ + - ]: 3 : Assert(prevbit >= -1);
1382 : :
1383 : : /* transform -1 to the highest possible bit we could have set */
1384 [ + - ]: 3 : if (prevbit == -1)
1385 : 0 : prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1386 : : else
1387 : 3 : prevbit--;
1388 : :
1389 : 3 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1390 : 3 : mask = (~(bitmapword) 0) >> ushiftbits;
1391 [ + + + + ]: 6 : for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1392 : : {
1393 : 3 : bitmapword w = a->words[wordnum];
1394 : :
1395 : : /* mask out bits left of prevbit */
1396 : 3 : w &= mask;
1397 : :
1398 [ + + ]: 3 : if (w != 0)
1399 : : {
1400 : 2 : int result;
1401 : :
1402 : 2 : result = wordnum * BITS_PER_BITMAPWORD;
1403 : 2 : result += bmw_leftmost_one_pos(w);
1404 : 2 : return result;
1405 : 2 : }
1406 : :
1407 : : /* in subsequent words, consider all bits */
1408 : 1 : mask = (~(bitmapword) 0);
1409 [ + + ]: 3 : }
1410 : 1 : return -2;
1411 : 3 : }
1412 : :
1413 : : /*
1414 : : * bms_hash_value - compute a hash key for a Bitmapset
1415 : : */
1416 : : uint32
1417 : 779 : bms_hash_value(const Bitmapset *a)
1418 : : {
1419 [ + - ]: 779 : Assert(bms_is_valid_set(a));
1420 : :
1421 [ + - ]: 779 : if (a == NULL)
1422 : 0 : return 0; /* All empty sets hash to 0 */
1423 : 1558 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1424 : 779 : a->nwords * sizeof(bitmapword)));
1425 : 779 : }
1426 : :
1427 : : /*
1428 : : * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
1429 : : *
1430 : : * Note: don't forget to specify bitmap_match as the match function!
1431 : : */
1432 : : uint32
1433 : 779 : bitmap_hash(const void *key, Size keysize)
1434 : : {
1435 [ + - ]: 779 : Assert(keysize == sizeof(Bitmapset *));
1436 : 779 : return bms_hash_value(*((const Bitmapset *const *) key));
1437 : : }
1438 : :
1439 : : /*
1440 : : * bitmap_match - match function to use with bitmap_hash
1441 : : */
1442 : : int
1443 : 397 : bitmap_match(const void *key1, const void *key2, Size keysize)
1444 : : {
1445 [ + - ]: 397 : Assert(keysize == sizeof(Bitmapset *));
1446 : 794 : return !bms_equal(*((const Bitmapset *const *) key1),
1447 : 397 : *((const Bitmapset *const *) key2));
1448 : : }
|
