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 "common/int.h"
43 : : #include "nodes/bitmapset.h"
44 : : #include "nodes/pg_list.h"
45 : : #include "port/pg_bitutils.h"
46 : :
47 : :
48 : : #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
49 : : #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
50 : :
51 : : #define BITMAPSET_SIZE(nwords) \
52 : : (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
53 : :
54 : : /*----------
55 : : * This is a well-known cute trick for isolating the rightmost one-bit
56 : : * in a word. It assumes two's complement arithmetic. Consider any
57 : : * nonzero value, and focus attention on the rightmost one. The value is
58 : : * then something like
59 : : * xxxxxx10000
60 : : * where x's are unspecified bits. The two's complement negative is formed
61 : : * by inverting all the bits and adding one. Inversion gives
62 : : * yyyyyy01111
63 : : * where each y is the inverse of the corresponding x. Incrementing gives
64 : : * yyyyyy10000
65 : : * and then ANDing with the original value gives
66 : : * 00000010000
67 : : * This works for all cases except original value = zero, where of course
68 : : * we get zero.
69 : : *----------
70 : : */
71 : : #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
72 : :
73 : : #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x))
74 : :
75 : : #ifdef USE_ASSERT_CHECKING
76 : : /*
77 : : * bms_is_valid_set - for cassert builds to check for valid sets
78 : : */
79 : : static bool
80 : : bms_is_valid_set(const Bitmapset *a)
81 : : {
82 : : /* NULL is the correct representation of an empty set */
83 : : if (a == NULL)
84 : : return true;
85 : :
86 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
87 : : if (!IsA(a, Bitmapset))
88 : : return false;
89 : :
90 : : /* trailing zero words are not allowed */
91 : : if (a->words[a->nwords - 1] == 0)
92 : : return false;
93 : :
94 : : return true;
95 : : }
96 : : #endif
97 : :
98 : : #ifdef REALLOCATE_BITMAPSETS
99 : : /*
100 : : * bms_copy_and_free
101 : : * Only required in REALLOCATE_BITMAPSETS builds. Provide a simple way
102 : : * to return a freshly allocated set and pfree the original.
103 : : *
104 : : * Note: callers which accept multiple sets must be careful when calling this
105 : : * function to clone one parameter as other parameters may point to the same
106 : : * set. A good option is to call this just before returning the resulting
107 : : * set.
108 : : */
109 : : static Bitmapset *
110 : : bms_copy_and_free(Bitmapset *a)
111 : : {
112 : : Bitmapset *c = bms_copy(a);
113 : :
114 : : bms_free(a);
115 : : return c;
116 : : }
117 : : #endif
118 : :
119 : : /*
120 : : * bms_copy - make a palloc'd copy of a bitmapset
121 : : */
122 : : Bitmapset *
123 : 50096256 : bms_copy(const Bitmapset *a)
124 : : {
125 : : Bitmapset *result;
126 : : size_t size;
127 : :
128 : : Assert(bms_is_valid_set(a));
129 : :
130 [ + + ]: 50096256 : if (a == NULL)
131 : 35404090 : return NULL;
132 : :
133 : 14692166 : size = BITMAPSET_SIZE(a->nwords);
134 : 14692166 : result = (Bitmapset *) palloc(size);
135 : 14692166 : memcpy(result, a, size);
136 : 14692166 : return result;
137 : : }
138 : :
139 : : /*
140 : : * bms_equal - are two bitmapsets equal? or both NULL?
141 : : */
142 : : bool
143 : 19156683 : bms_equal(const Bitmapset *a, const Bitmapset *b)
144 : : {
145 : : int i;
146 : :
147 : : Assert(bms_is_valid_set(a));
148 : : Assert(bms_is_valid_set(b));
149 : :
150 : : /* Handle cases where either input is NULL */
151 [ + + ]: 19156683 : if (a == NULL)
152 : : {
153 [ + + ]: 13535211 : if (b == NULL)
154 : 13484514 : return true;
155 : 50697 : return false;
156 : : }
157 [ + + ]: 5621472 : else if (b == NULL)
158 : 19041 : return false;
159 : :
160 : : /* can't be equal if the word counts don't match */
161 [ + + ]: 5602431 : if (a->nwords != b->nwords)
162 : 5896 : return false;
163 : :
164 : : /* check each word matches */
165 : 5596535 : i = 0;
166 : : do
167 : : {
168 [ + + ]: 5614537 : if (a->words[i] != b->words[i])
169 : 2487640 : return false;
170 [ + + ]: 3126897 : } while (++i < a->nwords);
171 : :
172 : 3108895 : return true;
173 : : }
174 : :
175 : : /*
176 : : * bms_compare - qsort-style comparator for bitmapsets
177 : : *
178 : : * This guarantees to report values as equal iff bms_equal would say they are
179 : : * equal. Otherwise, the highest-numbered bit that is set in one value but
180 : : * not the other determines the result. (This rule means that, for example,
181 : : * {6} is greater than {5}, which seems plausible.)
182 : : */
183 : : int
184 : 22238 : bms_compare(const Bitmapset *a, const Bitmapset *b)
185 : : {
186 : : int i;
187 : :
188 : : Assert(bms_is_valid_set(a));
189 : : Assert(bms_is_valid_set(b));
190 : :
191 : : /* Handle cases where either input is NULL */
192 [ + + ]: 22238 : if (a == NULL)
193 [ + + ]: 4 : return (b == NULL) ? 0 : -1;
194 [ + + ]: 22234 : else if (b == NULL)
195 : 2 : return +1;
196 : :
197 : : /* the set with the most words must be greater */
198 [ + + ]: 22232 : if (a->nwords != b->nwords)
199 [ - + ]: 21 : return (a->nwords > b->nwords) ? +1 : -1;
200 : :
201 : 22211 : i = a->nwords - 1;
202 : : do
203 : : {
204 : 22211 : bitmapword aw = a->words[i];
205 : 22211 : bitmapword bw = b->words[i];
206 : :
207 [ + + ]: 22211 : if (aw != bw)
208 [ + + ]: 22210 : return (aw > bw) ? +1 : -1;
209 [ - + ]: 1 : } while (--i >= 0);
210 : 1 : return 0;
211 : : }
212 : :
213 : : /*
214 : : * bms_make_singleton - build a bitmapset containing a single member
215 : : */
216 : : Bitmapset *
217 : 14245194 : bms_make_singleton(int x)
218 : : {
219 : : Bitmapset *result;
220 : : int wordnum,
221 : : bitnum;
222 : :
223 [ + + ]: 14245194 : if (x < 0)
224 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
225 : 14245193 : wordnum = WORDNUM(x);
226 : 14245193 : bitnum = BITNUM(x);
227 : 14245193 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
228 : 14245193 : result->type = T_Bitmapset;
229 : 14245193 : result->nwords = wordnum + 1;
230 : 14245193 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
231 : 14245193 : return result;
232 : : }
233 : :
234 : : /*
235 : : * bms_free - free a bitmapset
236 : : *
237 : : * Same as pfree except for allowing NULL input
238 : : */
239 : : void
240 : 27035015 : bms_free(Bitmapset *a)
241 : : {
242 [ + + ]: 27035015 : if (a)
243 : 6516036 : pfree(a);
244 : 27035015 : }
245 : :
246 : :
247 : : /*
248 : : * bms_union - create and return a new set containing all members from both
249 : : * input sets. Both inputs are left unmodified.
250 : : */
251 : : Bitmapset *
252 : 6777021 : bms_union(const Bitmapset *a, const Bitmapset *b)
253 : : {
254 : : Bitmapset *result;
255 : : const Bitmapset *other;
256 : : int otherlen;
257 : : int i;
258 : :
259 : : Assert(bms_is_valid_set(a));
260 : : Assert(bms_is_valid_set(b));
261 : :
262 : : /* Handle cases where either input is NULL */
263 [ + + ]: 6777021 : if (a == NULL)
264 : 4085605 : return bms_copy(b);
265 [ + + ]: 2691416 : if (b == NULL)
266 : 1004482 : return bms_copy(a);
267 : : /* Identify shorter and longer input; copy the longer one */
268 [ + + ]: 1686934 : if (a->nwords <= b->nwords)
269 : : {
270 : 1686933 : result = bms_copy(b);
271 : 1686933 : other = a;
272 : : }
273 : : else
274 : : {
275 : 1 : result = bms_copy(a);
276 : 1 : other = b;
277 : : }
278 : : /* And union the shorter input into the result */
279 : 1686934 : otherlen = other->nwords;
280 : 1686934 : i = 0;
281 : : do
282 : : {
283 : 1688213 : result->words[i] |= other->words[i];
284 [ + + ]: 1688213 : } while (++i < otherlen);
285 : 1686934 : return result;
286 : : }
287 : :
288 : : /*
289 : : * bms_intersect - create and return a new set containing members which both
290 : : * input sets have in common. Both inputs are left unmodified.
291 : : */
292 : : Bitmapset *
293 : 900223 : bms_intersect(const Bitmapset *a, const Bitmapset *b)
294 : : {
295 : : Bitmapset *result;
296 : : const Bitmapset *other;
297 : : int lastnonzero;
298 : : int resultlen;
299 : : int i;
300 : :
301 : : Assert(bms_is_valid_set(a));
302 : : Assert(bms_is_valid_set(b));
303 : :
304 : : /* Handle cases where either input is NULL */
305 [ + + + + ]: 900223 : if (a == NULL || b == NULL)
306 : 151393 : return NULL;
307 : :
308 : : /* Identify shorter and longer input; copy the shorter one */
309 [ + + ]: 748830 : if (a->nwords <= b->nwords)
310 : : {
311 : 748829 : result = bms_copy(a);
312 : 748829 : other = b;
313 : : }
314 : : else
315 : : {
316 : 1 : result = bms_copy(b);
317 : 1 : other = a;
318 : : }
319 : : /* And intersect the longer input with the result */
320 : 748830 : resultlen = result->nwords;
321 : 748830 : lastnonzero = -1;
322 : 748830 : i = 0;
323 : : do
324 : : {
325 : 750109 : result->words[i] &= other->words[i];
326 : :
327 [ + + ]: 750109 : if (result->words[i] != 0)
328 : 741822 : lastnonzero = i;
329 [ + + ]: 750109 : } while (++i < resultlen);
330 : : /* If we computed an empty result, we must return NULL */
331 [ + + ]: 748830 : if (lastnonzero == -1)
332 : : {
333 : 7120 : pfree(result);
334 : 7120 : return NULL;
335 : : }
336 : :
337 : : /* get rid of trailing zero words */
338 : 741710 : result->nwords = lastnonzero + 1;
339 : 741710 : return result;
340 : : }
341 : :
342 : : /*
343 : : * bms_difference - create and return a new set containing all the members of
344 : : * 'a' without the members of 'b'.
345 : : */
346 : : Bitmapset *
347 : 1913249 : bms_difference(const Bitmapset *a, const Bitmapset *b)
348 : : {
349 : : Bitmapset *result;
350 : : int i;
351 : :
352 : : Assert(bms_is_valid_set(a));
353 : : Assert(bms_is_valid_set(b));
354 : :
355 : : /* Handle cases where either input is NULL */
356 [ + + ]: 1913249 : if (a == NULL)
357 : 475023 : return NULL;
358 [ + + ]: 1438226 : if (b == NULL)
359 : 985756 : return bms_copy(a);
360 : :
361 : : /*
362 : : * In Postgres' usage, an empty result is a very common case, so it's
363 : : * worth optimizing for that by testing bms_nonempty_difference(). This
364 : : * saves us a palloc/pfree cycle compared to checking after-the-fact.
365 : : */
366 [ + + ]: 452470 : if (!bms_nonempty_difference(a, b))
367 : 194864 : return NULL;
368 : :
369 : : /* Copy the left input */
370 : 257606 : result = bms_copy(a);
371 : :
372 : : /* And remove b's bits from result */
373 [ + + ]: 257606 : if (result->nwords > b->nwords)
374 : : {
375 : : /*
376 : : * We'll never need to remove trailing zero words when 'a' has more
377 : : * words than 'b' as the additional words must be non-zero.
378 : : */
379 : 2 : i = 0;
380 : : do
381 : : {
382 : 2 : result->words[i] &= ~b->words[i];
383 [ - + ]: 2 : } while (++i < b->nwords);
384 : : }
385 : : else
386 : : {
387 : 257604 : int lastnonzero = -1;
388 : :
389 : : /* we may need to remove trailing zero words from the result. */
390 : 257604 : i = 0;
391 : : do
392 : : {
393 : 257605 : result->words[i] &= ~b->words[i];
394 : :
395 : : /* remember the last non-zero word */
396 [ + + ]: 257605 : if (result->words[i] != 0)
397 : 257604 : lastnonzero = i;
398 [ + + ]: 257605 : } while (++i < result->nwords);
399 : :
400 : : /* trim off trailing zero words */
401 : 257604 : result->nwords = lastnonzero + 1;
402 : : }
403 : : Assert(result->nwords != 0);
404 : :
405 : : /* Need not check for empty result, since we handled that case above */
406 : 257606 : return result;
407 : : }
408 : :
409 : : /*
410 : : * bms_offset_members
411 : : * Creates a new Bitmapset with all members of 'a' adjusted to add the
412 : : * value of 'offset' to each member.
413 : : *
414 : : * Members that would become negative as a result of a negative offset will
415 : : * be removed from the set, whereas too large an offset, which would result in
416 : : * a member going > INT_MAX, will result in an ERROR.
417 : : */
418 : : Bitmapset *
419 : 590584 : bms_offset_members(const Bitmapset *a, int offset)
420 : : {
421 : : Bitmapset *result;
422 : : int offset_words;
423 : : int offset_bits;
424 : : int new_nwords;
425 : : int old_nwords;
426 : : int32 high_bit;
427 : : int old_highest;
428 : : int new_highest;
429 : :
430 : : Assert(bms_is_valid_set(a));
431 : :
432 : : /* nothing to do for empty sets */
433 [ + + ]: 590584 : if (a == NULL)
434 : 491213 : return NULL;
435 : :
436 : 99371 : old_nwords = a->nwords;
437 : 99371 : offset_words = WORDNUM(offset);
438 : 99371 : offset_bits = BITNUM(offset);
439 : 99371 : high_bit = bmw_leftmost_one_pos(a->words[a->nwords - 1]);
440 : 99371 : old_highest = (old_nwords - 1) * BITS_PER_BITMAPWORD + high_bit;
441 : :
442 : : /* don't create a set with a member that doesn't fit into an int32 */
443 [ + + ]: 99371 : if (pg_add_s32_overflow(old_highest, offset, &new_highest))
444 [ + - ]: 2 : elog(ERROR, "bitmapset overflow");
445 : : /* return NULL if the new set would be empty */
446 [ + + ]: 99369 : else if (new_highest < 0)
447 : 2 : return NULL;
448 : :
449 : 99367 : new_nwords = WORDNUM(new_highest) + 1;
450 : 99367 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(new_nwords));
451 : 99367 : result->type = T_Bitmapset;
452 : 99367 : result->nwords = new_nwords;
453 : :
454 : : /* handle zero and positive offsets (bitshift left) */
455 [ + + ]: 99367 : if (offset >= 0)
456 : : {
457 : : /*
458 : : * We special-case offsetting only by whole words, so we don't have to
459 : : * special-case bitshifting by BITS_PER_BITMAPWORD places, which has
460 : : * an undefined behavior.
461 : : */
462 [ + + ]: 98775 : if (offset_bits == 0)
463 : : {
464 : 9 : int i = 0;
465 : :
466 : : /*
467 : : * The old set is guaranteed to have at least 1 word, so use
468 : : * do/while to save the redundant initial loop bounds check.
469 : : */
470 : : do
471 : : {
472 : : Assert(i + offset_words < new_nwords);
473 : 100 : result->words[i + offset_words] = a->words[i];
474 [ + + ]: 100 : } while (++i < old_nwords);
475 : : }
476 : : else
477 : : {
478 : 98766 : int carry_bits = BITS_PER_BITMAPWORD - offset_bits;
479 : 98766 : bitmapword prev_carry = 0;
480 : 98766 : int i = 0;
481 : :
482 : : do
483 : : {
484 : 106073 : bitmapword carry = (a->words[i] >> carry_bits);
485 : :
486 : : Assert(i + offset_words < new_nwords);
487 : : /* shift bits up and carry bits from the previous word */
488 : 106073 : result->words[i + offset_words] = (a->words[i] << offset_bits) | prev_carry;
489 : 106073 : prev_carry = carry;
490 [ + + ]: 106073 : } while (++i < old_nwords);
491 : 98766 : result->words[new_nwords - 1] |= prev_carry;
492 : : }
493 : : }
494 : :
495 : : /* handle negative offset (bitshift right) */
496 : : else
497 : : {
498 : : /* make the negative offset_words and offset_bits positive */
499 : 592 : offset_words = 0 - offset_words;
500 : 592 : offset_bits = 0 - offset_bits;
501 : :
502 : : /* as above, special case shifting only by whole words */
503 [ + + ]: 592 : if (offset_bits == 0)
504 : : {
505 : 8 : int i = 0;
506 : :
507 : : do
508 : : {
509 : : Assert(i + offset_words < old_nwords);
510 : 73 : result->words[i] = a->words[i + offset_words];
511 [ + + ]: 73 : } while (++i < new_nwords);
512 : : }
513 : : else
514 : : {
515 : 584 : int carry_bits = BITS_PER_BITMAPWORD - offset_bits;
516 : 584 : bitmapword prev_carry = 0;
517 : 584 : int i = new_nwords - 1;
518 : :
519 : : /* carry bits from any word just above where the loop starts */
520 [ + + ]: 584 : if (old_nwords > new_nwords + offset_words)
521 : 33 : prev_carry = (a->words[new_nwords + offset_words] << carry_bits);
522 : :
523 : : /*
524 : : * We loop backward over the array so we correctly carry bits from
525 : : * higher words.
526 : : */
527 : : do
528 : : {
529 : 5627 : bitmapword carry = (a->words[i + offset_words] << carry_bits);
530 : :
531 : : Assert(i + offset_words < old_nwords);
532 : :
533 : : /* shift bits down and carry bits from the previous word */
534 : 5627 : result->words[i] = (a->words[i + offset_words] >> offset_bits) | prev_carry;
535 : 5627 : prev_carry = carry;
536 [ + + ]: 5627 : } while (--i >= 0);
537 : : }
538 : : }
539 : :
540 : 99367 : return result;
541 : : }
542 : :
543 : : /*
544 : : * bms_is_subset - is A a subset of B?
545 : : */
546 : : bool
547 : 16432438 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
548 : : {
549 : : int i;
550 : :
551 : : Assert(bms_is_valid_set(a));
552 : : Assert(bms_is_valid_set(b));
553 : :
554 : : /* Handle cases where either input is NULL */
555 [ + + ]: 16432438 : if (a == NULL)
556 : 1392229 : return true; /* empty set is a subset of anything */
557 [ + + ]: 15040209 : if (b == NULL)
558 : 293861 : return false;
559 : :
560 : : /* 'a' can't be a subset of 'b' if it contains more words */
561 [ + + ]: 14746348 : if (a->nwords > b->nwords)
562 : 2 : return false;
563 : :
564 : : /* Check all 'a' members are set in 'b' */
565 : 14746346 : i = 0;
566 : : do
567 : : {
568 [ + + ]: 14746346 : if ((a->words[i] & ~b->words[i]) != 0)
569 : 5674071 : return false;
570 [ - + ]: 9072275 : } while (++i < a->nwords);
571 : 9072275 : return true;
572 : : }
573 : :
574 : : /*
575 : : * bms_subset_compare - compare A and B for equality/subset relationships
576 : : *
577 : : * This is more efficient than testing bms_is_subset in both directions.
578 : : */
579 : : BMS_Comparison
580 : 2160360 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
581 : : {
582 : : BMS_Comparison result;
583 : : int shortlen;
584 : : int i;
585 : :
586 : : Assert(bms_is_valid_set(a));
587 : : Assert(bms_is_valid_set(b));
588 : :
589 : : /* Handle cases where either input is NULL */
590 [ + + ]: 2160360 : if (a == NULL)
591 : : {
592 [ + + ]: 1791034 : if (b == NULL)
593 : 1738700 : return BMS_EQUAL;
594 : 52334 : return BMS_SUBSET1;
595 : : }
596 [ + + ]: 369326 : if (b == NULL)
597 : 181629 : return BMS_SUBSET2;
598 : :
599 : : /* Check common words */
600 : 187697 : result = BMS_EQUAL; /* status so far */
601 : 187697 : shortlen = Min(a->nwords, b->nwords);
602 : 187697 : i = 0;
603 : : do
604 : : {
605 : 187700 : bitmapword aword = a->words[i];
606 : 187700 : bitmapword bword = b->words[i];
607 : :
608 [ + + ]: 187700 : if ((aword & ~bword) != 0)
609 : : {
610 : : /* a is not a subset of b */
611 [ + + ]: 53974 : if (result == BMS_SUBSET1)
612 : 2 : return BMS_DIFFERENT;
613 : 53972 : result = BMS_SUBSET2;
614 : : }
615 [ + + ]: 187698 : if ((bword & ~aword) != 0)
616 : : {
617 : : /* b is not a subset of a */
618 [ + + ]: 54893 : if (result == BMS_SUBSET2)
619 : 48820 : return BMS_DIFFERENT;
620 : 6073 : result = BMS_SUBSET1;
621 : : }
622 [ + + ]: 138878 : } while (++i < shortlen);
623 : : /* Check extra words */
624 [ + + ]: 138875 : if (a->nwords > b->nwords)
625 : : {
626 : : /* if a has more words then a is not a subset of b */
627 [ + + ]: 2 : if (result == BMS_SUBSET1)
628 : 1 : return BMS_DIFFERENT;
629 : 1 : return BMS_SUBSET2;
630 : : }
631 [ + + ]: 138873 : else if (a->nwords < b->nwords)
632 : : {
633 : : /* if b has more words then b is not a subset of a */
634 [ + + ]: 4 : if (result == BMS_SUBSET2)
635 : 2 : return BMS_DIFFERENT;
636 : 2 : return BMS_SUBSET1;
637 : : }
638 : 138869 : return result;
639 : : }
640 : :
641 : : /*
642 : : * bms_is_member - is X a member of A?
643 : : */
644 : : bool
645 : 12653234 : bms_is_member(int x, const Bitmapset *a)
646 : : {
647 : : int wordnum,
648 : : bitnum;
649 : :
650 : : Assert(bms_is_valid_set(a));
651 : :
652 : : /* XXX better to just return false for x<0 ? */
653 [ + + ]: 12653234 : if (x < 0)
654 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
655 [ + + ]: 12653233 : if (a == NULL)
656 : 6749734 : return false;
657 : :
658 : 5903499 : wordnum = WORDNUM(x);
659 : 5903499 : bitnum = BITNUM(x);
660 [ + + ]: 5903499 : if (wordnum >= a->nwords)
661 : 456 : return false;
662 [ + + ]: 5903043 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
663 : 3720197 : return true;
664 : 2182846 : return false;
665 : : }
666 : :
667 : : /*
668 : : * bms_member_index
669 : : * determine 0-based index of member x in the bitmap
670 : : *
671 : : * Returns (-1) when x is not a member.
672 : : */
673 : : int
674 : 4427 : bms_member_index(Bitmapset *a, int x)
675 : : {
676 : : int bitnum;
677 : : int wordnum;
678 : 4427 : int result = 0;
679 : : bitmapword mask;
680 : :
681 : : Assert(bms_is_valid_set(a));
682 : :
683 : : /* return -1 if not a member of the bitmap */
684 [ + + ]: 4427 : if (!bms_is_member(x, a))
685 : 2 : return -1;
686 : :
687 : 4425 : wordnum = WORDNUM(x);
688 : 4425 : bitnum = BITNUM(x);
689 : :
690 : : /* count bits in preceding words */
691 : 4425 : result += pg_popcount((const char *) a->words,
692 : : wordnum * sizeof(bitmapword));
693 : :
694 : : /*
695 : : * Now add bits of the last word, but only those before the item. We can
696 : : * do that by applying a mask and then using popcount again. To get
697 : : * 0-based index, we want to count only preceding bits, not the item
698 : : * itself, so we subtract 1.
699 : : */
700 : 4425 : mask = ((bitmapword) 1 << bitnum) - 1;
701 : 4425 : result += bmw_popcount(a->words[wordnum] & mask);
702 : :
703 : 4425 : return result;
704 : : }
705 : :
706 : : /*
707 : : * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
708 : : */
709 : : bool
710 : 14999374 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
711 : : {
712 : : int shortlen;
713 : : int i;
714 : :
715 : : Assert(bms_is_valid_set(a));
716 : : Assert(bms_is_valid_set(b));
717 : :
718 : : /* Handle cases where either input is NULL */
719 [ + + + + ]: 14999374 : if (a == NULL || b == NULL)
720 : 8489152 : return false;
721 : : /* Check words in common */
722 : 6510222 : shortlen = Min(a->nwords, b->nwords);
723 : 6510222 : i = 0;
724 : : do
725 : : {
726 [ + + ]: 6510222 : if ((a->words[i] & b->words[i]) != 0)
727 : 4120482 : return true;
728 [ - + ]: 2389740 : } while (++i < shortlen);
729 : 2389740 : return false;
730 : : }
731 : :
732 : : /*
733 : : * bms_overlap_list - does a set overlap an integer list?
734 : : */
735 : : bool
736 : 1529 : bms_overlap_list(const Bitmapset *a, const List *b)
737 : : {
738 : : ListCell *lc;
739 : : int wordnum,
740 : : bitnum;
741 : :
742 : : Assert(bms_is_valid_set(a));
743 : :
744 [ + + + + ]: 1529 : if (a == NULL || b == NIL)
745 : 1412 : return false;
746 : :
747 [ + - + + : 219 : foreach(lc, b)
+ + ]
748 : : {
749 : 170 : int x = lfirst_int(lc);
750 : :
751 [ + + ]: 170 : if (x < 0)
752 [ + - ]: 2 : elog(ERROR, "negative bitmapset member not allowed");
753 : 168 : wordnum = WORDNUM(x);
754 : 168 : bitnum = BITNUM(x);
755 [ + - ]: 168 : if (wordnum < a->nwords)
756 [ + + ]: 168 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
757 : 66 : return true;
758 : : }
759 : :
760 : 49 : return false;
761 : : }
762 : :
763 : : /*
764 : : * bms_nonempty_difference - do sets have a nonempty difference?
765 : : *
766 : : * i.e., are any members set in 'a' that are not also set in 'b'.
767 : : */
768 : : bool
769 : 2343421 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
770 : : {
771 : : int i;
772 : :
773 : : Assert(bms_is_valid_set(a));
774 : : Assert(bms_is_valid_set(b));
775 : :
776 : : /* Handle cases where either input is NULL */
777 [ + + ]: 2343421 : if (a == NULL)
778 : 4237 : return false;
779 [ + + ]: 2339184 : if (b == NULL)
780 : 1 : return true;
781 : : /* if 'a' has more words then it must contain additional members */
782 [ + + ]: 2339183 : if (a->nwords > b->nwords)
783 : 3 : return true;
784 : : /* Check all 'a' members are set in 'b' */
785 : 2339180 : i = 0;
786 : : do
787 : : {
788 [ + + ]: 2339180 : if ((a->words[i] & ~b->words[i]) != 0)
789 : 1299689 : return true;
790 [ - + ]: 1039491 : } while (++i < a->nwords);
791 : 1039491 : return false;
792 : : }
793 : :
794 : : /*
795 : : * bms_singleton_member - return the sole integer member of set
796 : : *
797 : : * Raises error if |a| is not 1.
798 : : */
799 : : int
800 : 17530 : bms_singleton_member(const Bitmapset *a)
801 : : {
802 : 17530 : int result = -1;
803 : : int nwords;
804 : : int wordnum;
805 : :
806 : : Assert(bms_is_valid_set(a));
807 : :
808 [ + + ]: 17530 : if (a == NULL)
809 [ + - ]: 1 : elog(ERROR, "bitmapset is empty");
810 : :
811 : 17529 : nwords = a->nwords;
812 : 17529 : wordnum = 0;
813 : : do
814 : : {
815 : 17529 : bitmapword w = a->words[wordnum];
816 : :
817 [ + - ]: 17529 : if (w != 0)
818 : : {
819 [ + - + + ]: 17529 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
820 [ + - ]: 1 : elog(ERROR, "bitmapset has multiple members");
821 : 17528 : result = wordnum * BITS_PER_BITMAPWORD;
822 : 17528 : result += bmw_rightmost_one_pos(w);
823 : : }
824 [ - + ]: 17528 : } while (++wordnum < nwords);
825 : :
826 : : /* we don't expect non-NULL sets to be empty */
827 : : Assert(result >= 0);
828 : 17528 : return result;
829 : : }
830 : :
831 : : /*
832 : : * bms_get_singleton_member
833 : : *
834 : : * Test whether the given set is a singleton.
835 : : * If so, set *member to the value of its sole member, and return true.
836 : : * If not, return false, without changing *member.
837 : : *
838 : : * This is more convenient and faster than calling bms_membership() and then
839 : : * bms_singleton_member(), if we don't care about distinguishing empty sets
840 : : * from multiple-member sets.
841 : : */
842 : : bool
843 : 2139998 : bms_get_singleton_member(const Bitmapset *a, int *member)
844 : : {
845 : 2139998 : int result = -1;
846 : : int nwords;
847 : : int wordnum;
848 : :
849 : : Assert(bms_is_valid_set(a));
850 : :
851 [ + + ]: 2139998 : if (a == NULL)
852 : 2 : return false;
853 : :
854 : 2139996 : nwords = a->nwords;
855 : 2139996 : wordnum = 0;
856 : : do
857 : : {
858 : 2140002 : bitmapword w = a->words[wordnum];
859 : :
860 [ + + ]: 2140002 : if (w != 0)
861 : : {
862 [ + - + + ]: 2139996 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
863 : 416015 : return false;
864 : 1723981 : result = wordnum * BITS_PER_BITMAPWORD;
865 : 1723981 : result += bmw_rightmost_one_pos(w);
866 : : }
867 [ + + ]: 1723987 : } while (++wordnum < nwords);
868 : :
869 : : /* we don't expect non-NULL sets to be empty */
870 : : Assert(result >= 0);
871 : 1723981 : *member = result;
872 : 1723981 : return true;
873 : : }
874 : :
875 : : /*
876 : : * bms_num_members - count members of set
877 : : */
878 : : int
879 : 1460313 : bms_num_members(const Bitmapset *a)
880 : : {
881 : : Assert(bms_is_valid_set(a));
882 : :
883 [ + + ]: 1460313 : if (a == NULL)
884 : 147271 : return 0;
885 : :
886 : : /* fast-path for common case */
887 [ + + ]: 1313042 : if (a->nwords == 1)
888 : 1312656 : return bmw_popcount(a->words[0]);
889 : :
890 : 386 : return pg_popcount((const char *) a->words,
891 : 386 : a->nwords * sizeof(bitmapword));
892 : : }
893 : :
894 : : /*
895 : : * bms_membership - does a set have zero, one, or multiple members?
896 : : *
897 : : * This is faster than making an exact count with bms_num_members().
898 : : */
899 : : BMS_Membership
900 : 1137758 : bms_membership(const Bitmapset *a)
901 : : {
902 : 1137758 : BMS_Membership result = BMS_EMPTY_SET;
903 : : int nwords;
904 : : int wordnum;
905 : :
906 : : Assert(bms_is_valid_set(a));
907 : :
908 [ + + ]: 1137758 : if (a == NULL)
909 : 413 : return BMS_EMPTY_SET;
910 : :
911 : 1137345 : nwords = a->nwords;
912 : 1137345 : wordnum = 0;
913 : : do
914 : : {
915 : 1137461 : bitmapword w = a->words[wordnum];
916 : :
917 [ + + ]: 1137461 : if (w != 0)
918 : : {
919 [ + - + + ]: 1137345 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
920 : 388205 : return BMS_MULTIPLE;
921 : 749140 : result = BMS_SINGLETON;
922 : : }
923 [ + + ]: 749256 : } while (++wordnum < nwords);
924 : 749140 : return result;
925 : : }
926 : :
927 : :
928 : : /*
929 : : * bms_add_member - add a specified member to set
930 : : *
931 : : * 'a' is recycled when possible.
932 : : */
933 : : Bitmapset *
934 : 21052651 : bms_add_member(Bitmapset *a, int x)
935 : : {
936 : : int wordnum,
937 : : bitnum;
938 : :
939 : : Assert(bms_is_valid_set(a));
940 : :
941 [ + + ]: 21052651 : if (x < 0)
942 [ + - ]: 2 : elog(ERROR, "negative bitmapset member not allowed");
943 [ + + ]: 21052649 : if (a == NULL)
944 : 10886320 : return bms_make_singleton(x);
945 : :
946 : 10166329 : wordnum = WORDNUM(x);
947 : 10166329 : bitnum = BITNUM(x);
948 : :
949 : : /* enlarge the set if necessary */
950 [ + + ]: 10166329 : if (wordnum >= a->nwords)
951 : : {
952 : 15699 : int oldnwords = a->nwords;
953 : : int i;
954 : :
955 : 15699 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
956 : 15699 : a->nwords = wordnum + 1;
957 : : /* zero out the enlarged portion */
958 : 15699 : i = oldnwords;
959 : : do
960 : : {
961 : 73001 : a->words[i] = 0;
962 [ + + ]: 73001 : } while (++i < a->nwords);
963 : : }
964 : :
965 : 10166329 : a->words[wordnum] |= ((bitmapword) 1 << bitnum);
966 : :
967 : : #ifdef REALLOCATE_BITMAPSETS
968 : :
969 : : /*
970 : : * There's no guarantee that the repalloc returned a new pointer, so copy
971 : : * and free unconditionally here.
972 : : */
973 : : a = bms_copy_and_free(a);
974 : : #endif
975 : :
976 : 10166329 : return a;
977 : : }
978 : :
979 : : /*
980 : : * bms_del_member - remove a specified member from set
981 : : *
982 : : * No error if x is not currently a member of set
983 : : *
984 : : * 'a' is recycled when possible.
985 : : */
986 : : Bitmapset *
987 : 1453324 : bms_del_member(Bitmapset *a, int x)
988 : : {
989 : : int wordnum,
990 : : bitnum;
991 : :
992 : : Assert(bms_is_valid_set(a));
993 : :
994 [ + + ]: 1453324 : if (x < 0)
995 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
996 [ + + ]: 1453323 : if (a == NULL)
997 : 533980 : return NULL;
998 : :
999 : 919343 : wordnum = WORDNUM(x);
1000 : 919343 : bitnum = BITNUM(x);
1001 : :
1002 : : #ifdef REALLOCATE_BITMAPSETS
1003 : : a = bms_copy_and_free(a);
1004 : : #endif
1005 : :
1006 : : /* member can't exist. Return 'a' unmodified */
1007 [ - + ]: 919343 : if (unlikely(wordnum >= a->nwords))
1008 : 0 : return a;
1009 : :
1010 : 919343 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
1011 : :
1012 : : /* when last word becomes empty, trim off all trailing empty words */
1013 [ + + + + ]: 919343 : if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
1014 : : {
1015 : : /* find the last non-empty word and make that the new final word */
1016 [ + + ]: 532017 : for (int i = wordnum - 1; i >= 0; i--)
1017 : : {
1018 [ + + ]: 90546 : if (a->words[i] != 0)
1019 : : {
1020 : 292 : a->nwords = i + 1;
1021 : 292 : return a;
1022 : : }
1023 : : }
1024 : :
1025 : : /* the set is now empty */
1026 : 441471 : pfree(a);
1027 : 441471 : return NULL;
1028 : : }
1029 : 477580 : return a;
1030 : : }
1031 : :
1032 : : /*
1033 : : * bms_add_members - like bms_union, but left input is recycled when possible
1034 : : */
1035 : : Bitmapset *
1036 : 19872823 : bms_add_members(Bitmapset *a, const Bitmapset *b)
1037 : : {
1038 : : Bitmapset *result;
1039 : : const Bitmapset *other;
1040 : : int otherlen;
1041 : : int i;
1042 : :
1043 : : Assert(bms_is_valid_set(a));
1044 : : Assert(bms_is_valid_set(b));
1045 : :
1046 : : /* Handle cases where either input is NULL */
1047 [ + + ]: 19872823 : if (a == NULL)
1048 : 14240146 : return bms_copy(b);
1049 [ + + ]: 5632677 : if (b == NULL)
1050 : : {
1051 : : #ifdef REALLOCATE_BITMAPSETS
1052 : : a = bms_copy_and_free(a);
1053 : : #endif
1054 : :
1055 : 3583776 : return a;
1056 : : }
1057 : : /* Identify shorter and longer input; copy the longer one if needed */
1058 [ + + ]: 2048901 : if (a->nwords < b->nwords)
1059 : : {
1060 : 17 : result = bms_copy(b);
1061 : 17 : other = a;
1062 : : }
1063 : : else
1064 : : {
1065 : 2048884 : result = a;
1066 : 2048884 : other = b;
1067 : : }
1068 : : /* And union the shorter input into the result */
1069 : 2048901 : otherlen = other->nwords;
1070 : 2048901 : i = 0;
1071 : : do
1072 : : {
1073 : 2049537 : result->words[i] |= other->words[i];
1074 [ + + ]: 2049537 : } while (++i < otherlen);
1075 [ + + ]: 2048901 : if (result != a)
1076 : 17 : pfree(a);
1077 : : #ifdef REALLOCATE_BITMAPSETS
1078 : : else
1079 : : result = bms_copy_and_free(result);
1080 : : #endif
1081 : :
1082 : 2048901 : return result;
1083 : : }
1084 : :
1085 : : /*
1086 : : * bms_replace_members
1087 : : * Remove all existing members from 'a' and repopulate the set with members
1088 : : * from 'b', recycling 'a', when possible.
1089 : : */
1090 : : Bitmapset *
1091 : 11241 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
1092 : : {
1093 : : int i;
1094 : :
1095 : : Assert(bms_is_valid_set(a));
1096 : : Assert(bms_is_valid_set(b));
1097 : :
1098 [ + + ]: 11241 : if (a == NULL)
1099 : 1 : return bms_copy(b);
1100 [ + + ]: 11240 : if (b == NULL)
1101 : : {
1102 : 1 : pfree(a);
1103 : 1 : return NULL;
1104 : : }
1105 : :
1106 [ + + ]: 11239 : if (a->nwords < b->nwords)
1107 : 1 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
1108 : :
1109 : 11239 : i = 0;
1110 : : do
1111 : : {
1112 : 11248 : a->words[i] = b->words[i];
1113 [ + + ]: 11248 : } while (++i < b->nwords);
1114 : :
1115 : 11239 : a->nwords = b->nwords;
1116 : :
1117 : : #ifdef REALLOCATE_BITMAPSETS
1118 : :
1119 : : /*
1120 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1121 : : * and free unconditionally here.
1122 : : */
1123 : : a = bms_copy_and_free(a);
1124 : : #endif
1125 : :
1126 : 11239 : return a;
1127 : : }
1128 : :
1129 : : /*
1130 : : * bms_add_range
1131 : : * Add members in the range of 'lower' to 'upper' to the set.
1132 : : *
1133 : : * Note this could also be done by calling bms_add_member in a loop, however,
1134 : : * using this function will be faster when the range is large as we work at
1135 : : * the bitmapword level rather than at bit level.
1136 : : */
1137 : : Bitmapset *
1138 : 45171 : bms_add_range(Bitmapset *a, int lower, int upper)
1139 : : {
1140 : : int lwordnum,
1141 : : lbitnum,
1142 : : uwordnum,
1143 : : ushiftbits,
1144 : : wordnum;
1145 : :
1146 : : Assert(bms_is_valid_set(a));
1147 : :
1148 : : /* do nothing if nothing is called for, without further checking */
1149 [ + + ]: 45171 : if (upper < lower)
1150 : : {
1151 : : #ifdef REALLOCATE_BITMAPSETS
1152 : : a = bms_copy_and_free(a);
1153 : : #endif
1154 : :
1155 : 23 : return a;
1156 : : }
1157 : :
1158 [ + + ]: 45148 : if (lower < 0)
1159 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
1160 : 45147 : uwordnum = WORDNUM(upper);
1161 : :
1162 [ + + ]: 45147 : if (a == NULL)
1163 : : {
1164 : 35117 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1165 : 35117 : a->type = T_Bitmapset;
1166 : 35117 : a->nwords = uwordnum + 1;
1167 : : }
1168 [ + + ]: 10030 : else if (uwordnum >= a->nwords)
1169 : : {
1170 : 3 : int oldnwords = a->nwords;
1171 : : int i;
1172 : :
1173 : : /* ensure we have enough words to store the upper bit */
1174 : 3 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1175 : 3 : a->nwords = uwordnum + 1;
1176 : : /* zero out the enlarged portion */
1177 : 3 : i = oldnwords;
1178 : : do
1179 : : {
1180 : 5 : a->words[i] = 0;
1181 [ + + ]: 5 : } while (++i < a->nwords);
1182 : : }
1183 : :
1184 : 45147 : wordnum = lwordnum = WORDNUM(lower);
1185 : :
1186 : 45147 : lbitnum = BITNUM(lower);
1187 : 45147 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
1188 : :
1189 : : /*
1190 : : * Special case when lwordnum is the same as uwordnum we must perform the
1191 : : * upper and lower masking on the word.
1192 : : */
1193 [ + + ]: 45147 : if (lwordnum == uwordnum)
1194 : : {
1195 : 44163 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
1196 : 44163 : & (~(bitmapword) 0) >> ushiftbits;
1197 : : }
1198 : : else
1199 : : {
1200 : : /* turn on lbitnum and all bits left of it */
1201 : 984 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1202 : :
1203 : : /* turn on all bits for any intermediate words */
1204 [ + + ]: 1019 : while (wordnum < uwordnum)
1205 : 35 : a->words[wordnum++] = ~(bitmapword) 0;
1206 : :
1207 : : /* turn on upper's bit and all bits right of it. */
1208 : 984 : a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
1209 : : }
1210 : :
1211 : : #ifdef REALLOCATE_BITMAPSETS
1212 : :
1213 : : /*
1214 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1215 : : * and free unconditionally here.
1216 : : */
1217 : : a = bms_copy_and_free(a);
1218 : : #endif
1219 : :
1220 : 45147 : return a;
1221 : : }
1222 : :
1223 : : /*
1224 : : * bms_int_members - like bms_intersect, but left input is recycled when
1225 : : * possible
1226 : : */
1227 : : Bitmapset *
1228 : 617969 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1229 : : {
1230 : : int lastnonzero;
1231 : : int shortlen;
1232 : : int i;
1233 : :
1234 : : Assert(bms_is_valid_set(a));
1235 : : Assert(bms_is_valid_set(b));
1236 : :
1237 : : /* Handle cases where either input is NULL */
1238 [ + + ]: 617969 : if (a == NULL)
1239 : 19865 : return NULL;
1240 [ + + ]: 598104 : if (b == NULL)
1241 : : {
1242 : 3229 : pfree(a);
1243 : 3229 : return NULL;
1244 : : }
1245 : :
1246 : : /* Intersect b into a; we need never copy */
1247 : 594875 : shortlen = Min(a->nwords, b->nwords);
1248 : 594875 : lastnonzero = -1;
1249 : 594875 : i = 0;
1250 : : do
1251 : : {
1252 : 594876 : a->words[i] &= b->words[i];
1253 : :
1254 [ + + ]: 594876 : if (a->words[i] != 0)
1255 : 490358 : lastnonzero = i;
1256 [ + + ]: 594876 : } while (++i < shortlen);
1257 : :
1258 : : /* If we computed an empty result, we must return NULL */
1259 [ + + ]: 594875 : if (lastnonzero == -1)
1260 : : {
1261 : 104518 : pfree(a);
1262 : 104518 : return NULL;
1263 : : }
1264 : :
1265 : : /* get rid of trailing zero words */
1266 : 490357 : a->nwords = lastnonzero + 1;
1267 : :
1268 : : #ifdef REALLOCATE_BITMAPSETS
1269 : : a = bms_copy_and_free(a);
1270 : : #endif
1271 : :
1272 : 490357 : return a;
1273 : : }
1274 : :
1275 : : /*
1276 : : * bms_del_members - delete members in 'a' that are set in 'b'. 'a' is
1277 : : * recycled when possible.
1278 : : */
1279 : : Bitmapset *
1280 : 1781759 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1281 : : {
1282 : : int i;
1283 : :
1284 : : Assert(bms_is_valid_set(a));
1285 : : Assert(bms_is_valid_set(b));
1286 : :
1287 : : /* Handle cases where either input is NULL */
1288 [ + + ]: 1781759 : if (a == NULL)
1289 : 792700 : return NULL;
1290 [ + + ]: 989059 : if (b == NULL)
1291 : : {
1292 : : #ifdef REALLOCATE_BITMAPSETS
1293 : : a = bms_copy_and_free(a);
1294 : : #endif
1295 : :
1296 : 159611 : return a;
1297 : : }
1298 : :
1299 : : /* Remove b's bits from a; we need never copy */
1300 [ + + ]: 829448 : if (a->nwords > b->nwords)
1301 : : {
1302 : : /*
1303 : : * We'll never need to remove trailing zero words when 'a' has more
1304 : : * words than 'b'.
1305 : : */
1306 : 1 : i = 0;
1307 : : do
1308 : : {
1309 : 1 : a->words[i] &= ~b->words[i];
1310 [ - + ]: 1 : } while (++i < b->nwords);
1311 : : }
1312 : : else
1313 : : {
1314 : 829447 : int lastnonzero = -1;
1315 : :
1316 : : /* we may need to remove trailing zero words from the result. */
1317 : 829447 : i = 0;
1318 : : do
1319 : : {
1320 : 829455 : a->words[i] &= ~b->words[i];
1321 : :
1322 : : /* remember the last non-zero word */
1323 [ + + ]: 829455 : if (a->words[i] != 0)
1324 : 180037 : lastnonzero = i;
1325 [ + + ]: 829455 : } while (++i < a->nwords);
1326 : :
1327 : : /* check if 'a' has become empty */
1328 [ + + ]: 829447 : if (lastnonzero == -1)
1329 : : {
1330 : 649412 : pfree(a);
1331 : 649412 : return NULL;
1332 : : }
1333 : :
1334 : : /* trim off any trailing zero words */
1335 : 180035 : a->nwords = lastnonzero + 1;
1336 : : }
1337 : :
1338 : : #ifdef REALLOCATE_BITMAPSETS
1339 : : a = bms_copy_and_free(a);
1340 : : #endif
1341 : :
1342 : 180036 : return a;
1343 : : }
1344 : :
1345 : : /*
1346 : : * bms_join - like bms_union, but *either* input *may* be recycled
1347 : : */
1348 : : Bitmapset *
1349 : 1277155 : bms_join(Bitmapset *a, Bitmapset *b)
1350 : : {
1351 : : Bitmapset *result;
1352 : : Bitmapset *other;
1353 : : int otherlen;
1354 : : int i;
1355 : :
1356 : : Assert(bms_is_valid_set(a));
1357 : : Assert(bms_is_valid_set(b));
1358 : :
1359 : : /* Handle cases where either input is NULL */
1360 [ + + ]: 1277155 : if (a == NULL)
1361 : : {
1362 : : #ifdef REALLOCATE_BITMAPSETS
1363 : : b = bms_copy_and_free(b);
1364 : : #endif
1365 : :
1366 : 529831 : return b;
1367 : : }
1368 [ + + ]: 747324 : if (b == NULL)
1369 : : {
1370 : : #ifdef REALLOCATE_BITMAPSETS
1371 : : a = bms_copy_and_free(a);
1372 : : #endif
1373 : :
1374 : 133021 : return a;
1375 : : }
1376 : :
1377 : : /* Identify shorter and longer input; use longer one as result */
1378 [ + + ]: 614303 : if (a->nwords < b->nwords)
1379 : : {
1380 : 2 : result = b;
1381 : 2 : other = a;
1382 : : }
1383 : : else
1384 : : {
1385 : 614301 : result = a;
1386 : 614301 : other = b;
1387 : : }
1388 : : /* And union the shorter input into the result */
1389 : 614303 : otherlen = other->nwords;
1390 : 614303 : i = 0;
1391 : : do
1392 : : {
1393 : 614303 : result->words[i] |= other->words[i];
1394 [ - + ]: 614303 : } while (++i < otherlen);
1395 [ + - ]: 614303 : if (other != result) /* pure paranoia */
1396 : 614303 : pfree(other);
1397 : :
1398 : : #ifdef REALLOCATE_BITMAPSETS
1399 : : result = bms_copy_and_free(result);
1400 : : #endif
1401 : :
1402 : 614303 : return result;
1403 : : }
1404 : :
1405 : : /*
1406 : : * bms_next_member - find next member of a set
1407 : : *
1408 : : * Returns smallest member greater than "prevbit", or -2 if there is none.
1409 : : * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
1410 : : *
1411 : : * This is intended as support for iterating through the members of a set.
1412 : : * The typical pattern is
1413 : : *
1414 : : * x = -1;
1415 : : * while ((x = bms_next_member(inputset, x)) >= 0)
1416 : : * process member x;
1417 : : *
1418 : : * Notice that when there are no more members, we return -2, not -1 as you
1419 : : * might expect. The rationale for that is to allow distinguishing the
1420 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1421 : : * It makes no difference in simple loop usage, but complex iteration logic
1422 : : * might need such an ability.
1423 : : */
1424 : : int
1425 : 38787010 : bms_next_member(const Bitmapset *a, int prevbit)
1426 : : {
1427 : 38787010 : unsigned int currbit = prevbit;
1428 : : int nwords;
1429 : : bitmapword mask;
1430 : :
1431 : : Assert(bms_is_valid_set(a));
1432 : :
1433 [ + + ]: 38787010 : if (a == NULL)
1434 : 16747415 : return -2;
1435 : 22039595 : nwords = a->nwords;
1436 : :
1437 : : /* use an unsigned int to avoid the risk that int overflows */
1438 : 22039595 : currbit++;
1439 : 22039595 : mask = (~(bitmapword) 0) << BITNUM(currbit);
1440 [ + + ]: 29381292 : for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
1441 : : {
1442 : 22051194 : bitmapword w = a->words[wordnum];
1443 : :
1444 : : /* ignore bits before currbit */
1445 : 22051194 : w &= mask;
1446 : :
1447 [ + + ]: 22051194 : if (w != 0)
1448 : : {
1449 : : int result;
1450 : :
1451 : 14709497 : result = wordnum * BITS_PER_BITMAPWORD;
1452 : 14709497 : result += bmw_rightmost_one_pos(w);
1453 : 14709497 : return result;
1454 : : }
1455 : :
1456 : : /* in subsequent words, consider all bits */
1457 : 7341697 : mask = (~(bitmapword) 0);
1458 : : }
1459 : 7330098 : return -2;
1460 : : }
1461 : :
1462 : : /*
1463 : : * bms_prev_member - find prev member of a set
1464 : : *
1465 : : * Returns largest member less than "prevbit", or -2 if there is none.
1466 : : * "prevbit" must NOT be more than one above the highest possible bit that can
1467 : : * be set in the Bitmapset at its current size.
1468 : : *
1469 : : * To ease finding the highest set bit for the initial loop, the special
1470 : : * prevbit value of -1 can be passed to have the function find the highest
1471 : : * valued member in the set.
1472 : : *
1473 : : * This is intended as support for iterating through the members of a set in
1474 : : * reverse. The typical pattern is
1475 : : *
1476 : : * x = -1;
1477 : : * while ((x = bms_prev_member(inputset, x)) >= 0)
1478 : : * process member x;
1479 : : *
1480 : : * Notice that when there are no more members, we return -2, not -1 as you
1481 : : * might expect. The rationale for that is to allow distinguishing the
1482 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1483 : : * It makes no difference in simple loop usage, but complex iteration logic
1484 : : * might need such an ability.
1485 : : */
1486 : : int
1487 : 18 : bms_prev_member(const Bitmapset *a, int prevbit)
1488 : : {
1489 : : unsigned int currbit;
1490 : : int ushiftbits;
1491 : : bitmapword mask;
1492 : :
1493 : : Assert(bms_is_valid_set(a));
1494 : :
1495 : : /*
1496 : : * If set is NULL or if there are no more bits to the right then we've
1497 : : * nothing to do.
1498 : : */
1499 [ + + - + ]: 18 : if (a == NULL || prevbit == 0)
1500 : 2 : return -2;
1501 : :
1502 : : /* Validate callers didn't give us something out of range */
1503 : : Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD));
1504 : :
1505 : : /*
1506 : : * Transform -1 (or any negative number) to the highest possible bit we
1507 : : * could have set. We do this in unsigned math to avoid the risk of
1508 : : * overflowing a signed int.
1509 : : */
1510 [ + + ]: 16 : if (prevbit < 0)
1511 : 1 : currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
1512 : : else
1513 : 15 : currbit = prevbit - 1;
1514 : :
1515 : 16 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
1516 : 16 : mask = (~(bitmapword) 0) >> ushiftbits;
1517 [ + + ]: 21 : for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
1518 : : {
1519 : 16 : bitmapword w = a->words[wordnum];
1520 : :
1521 : : /* mask out bits left of currbit */
1522 : 16 : w &= mask;
1523 : :
1524 [ + + ]: 16 : if (w != 0)
1525 : : {
1526 : : int result;
1527 : :
1528 : 11 : result = wordnum * BITS_PER_BITMAPWORD;
1529 : 11 : result += bmw_leftmost_one_pos(w);
1530 : 11 : return result;
1531 : : }
1532 : :
1533 : : /* in subsequent words, consider all bits */
1534 : 5 : mask = (~(bitmapword) 0);
1535 : : }
1536 : 5 : return -2;
1537 : : }
1538 : :
1539 : : /*
1540 : : * bms_hash_value - compute a hash key for a Bitmapset
1541 : : */
1542 : : uint32
1543 : 5121 : bms_hash_value(const Bitmapset *a)
1544 : : {
1545 : : Assert(bms_is_valid_set(a));
1546 : :
1547 [ + + ]: 5121 : if (a == NULL)
1548 : 4 : return 0; /* All empty sets hash to 0 */
1549 : 5117 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1550 : 5117 : a->nwords * sizeof(bitmapword)));
1551 : : }
1552 : :
1553 : : /*
1554 : : * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
1555 : : *
1556 : : * Note: don't forget to specify bitmap_match as the match function!
1557 : : */
1558 : : uint32
1559 : 5114 : bitmap_hash(const void *key, Size keysize)
1560 : : {
1561 : : Assert(keysize == sizeof(Bitmapset *));
1562 : 5114 : return bms_hash_value(*((const Bitmapset *const *) key));
1563 : : }
1564 : :
1565 : : /*
1566 : : * bitmap_match - match function to use with bitmap_hash
1567 : : */
1568 : : int
1569 : 2885 : bitmap_match(const void *key1, const void *key2, Size keysize)
1570 : : {
1571 : : Assert(keysize == sizeof(Bitmapset *));
1572 : 2885 : return !bms_equal(*((const Bitmapset *const *) key1),
1573 : : *((const Bitmapset *const *) key2));
1574 : : }
|
