Age Owner Branch data TLA 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
920 drowley@postgresql.o 80 :CBC 301585570 : bms_is_valid_set(const Bitmapset *a)
81 : : {
82 : : /* NULL is the correct representation of an empty set */
83 [ + + ]: 301585570 : if (a == NULL)
84 : 140281908 : return true;
85 : :
86 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
87 [ - + ]: 161303662 : if (!IsA(a, Bitmapset))
920 drowley@postgresql.o 88 :UBC 0 : return false;
89 : :
90 : : /* trailing zero words are not allowed */
920 drowley@postgresql.o 91 [ - + ]:CBC 161303662 : if (a->words[a->nwords - 1] == 0)
920 drowley@postgresql.o 92 :UBC 0 : return false;
93 : :
920 drowley@postgresql.o 94 :CBC 161303662 : 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 *
8387 bruce@momjian.us 123 : 38094503 : bms_copy(const Bitmapset *a)
124 : : {
125 : : Bitmapset *result;
126 : : size_t size;
127 : :
920 drowley@postgresql.o 128 [ - + ]: 38094503 : Assert(bms_is_valid_set(a));
129 : :
8568 tgl@sss.pgh.pa.us 130 [ + + ]: 38094503 : if (a == NULL)
131 : 24620138 : return NULL;
132 : :
133 : 13474365 : size = BITMAPSET_SIZE(a->nwords);
134 : 13474365 : result = (Bitmapset *) palloc(size);
135 : 13474365 : memcpy(result, a, size);
136 : 13474365 : return result;
137 : : }
138 : :
139 : : /*
140 : : * bms_equal - are two bitmapsets equal? or both NULL?
141 : : */
142 : : bool
8387 bruce@momjian.us 143 : 10887729 : bms_equal(const Bitmapset *a, const Bitmapset *b)
144 : : {
145 : : int i;
146 : :
920 drowley@postgresql.o 147 [ - + ]: 10887729 : Assert(bms_is_valid_set(a));
148 [ - + ]: 10887729 : Assert(bms_is_valid_set(b));
149 : :
150 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 151 [ + + ]: 10887729 : if (a == NULL)
152 : : {
153 [ + + ]: 6401212 : if (b == NULL)
154 : 6350805 : return true;
1241 155 : 50407 : return false;
156 : : }
8568 157 [ + + ]: 4486517 : else if (b == NULL)
1241 158 : 21576 : return false;
159 : :
160 : : /* can't be equal if the word counts don't match */
1117 drowley@postgresql.o 161 [ + + ]: 4464941 : if (a->nwords != b->nwords)
162 : 5896 : return false;
163 : :
164 : : /* check each word matches */
165 : 4459045 : i = 0;
166 : : do
167 : : {
168 [ + + ]: 4476505 : if (a->words[i] != b->words[i])
8568 tgl@sss.pgh.pa.us 169 : 2549925 : return false;
1117 drowley@postgresql.o 170 [ + + ]: 1926580 : } while (++i < a->nwords);
171 : :
8568 tgl@sss.pgh.pa.us 172 : 1909120 : 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
3119 184 : 22220 : bms_compare(const Bitmapset *a, const Bitmapset *b)
185 : : {
186 : : int i;
187 : :
920 drowley@postgresql.o 188 [ - + ]: 22220 : Assert(bms_is_valid_set(a));
189 [ - + ]: 22220 : Assert(bms_is_valid_set(b));
190 : :
191 : : /* Handle cases where either input is NULL */
3119 tgl@sss.pgh.pa.us 192 [ + + ]: 22220 : if (a == NULL)
1241 193 [ + + ]: 4 : return (b == NULL) ? 0 : -1;
3119 194 [ + + ]: 22216 : else if (b == NULL)
1241 195 : 2 : return +1;
196 : :
197 : : /* the set with the most words must be greater */
1117 drowley@postgresql.o 198 [ + + ]: 22214 : if (a->nwords != b->nwords)
199 [ - + ]: 21 : return (a->nwords > b->nwords) ? +1 : -1;
200 : :
201 : 22193 : i = a->nwords - 1;
202 : : do
203 : : {
3119 tgl@sss.pgh.pa.us 204 : 22193 : bitmapword aw = a->words[i];
205 : 22193 : bitmapword bw = b->words[i];
206 : :
207 [ + + ]: 22193 : if (aw != bw)
208 [ + + ]: 22192 : return (aw > bw) ? +1 : -1;
1117 drowley@postgresql.o 209 [ - + ]: 1 : } while (--i >= 0);
3119 tgl@sss.pgh.pa.us 210 : 1 : return 0;
211 : : }
212 : :
213 : : /*
214 : : * bms_make_singleton - build a bitmapset containing a single member
215 : : */
216 : : Bitmapset *
8568 217 : 12627879 : bms_make_singleton(int x)
218 : : {
219 : : Bitmapset *result;
220 : : int wordnum,
221 : : bitnum;
222 : :
223 [ + + ]: 12627879 : if (x < 0)
8404 224 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
8568 225 : 12627878 : wordnum = WORDNUM(x);
226 : 12627878 : bitnum = BITNUM(x);
227 : 12627878 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
1350 228 : 12627878 : result->type = T_Bitmapset;
8568 229 : 12627878 : result->nwords = wordnum + 1;
230 : 12627878 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
231 : 12627878 : return result;
232 : : }
233 : :
234 : : /*
235 : : * bms_free - free a bitmapset
236 : : *
237 : : * Same as pfree except for allowing NULL input
238 : : */
239 : : void
8387 bruce@momjian.us 240 : 31719361 : bms_free(Bitmapset *a)
241 : : {
8568 tgl@sss.pgh.pa.us 242 [ + + ]: 31719361 : if (a)
243 : 7234333 : pfree(a);
244 : 31719361 : }
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 *
8387 bruce@momjian.us 252 : 6755160 : bms_union(const Bitmapset *a, const Bitmapset *b)
253 : : {
254 : : Bitmapset *result;
255 : : const Bitmapset *other;
256 : : int otherlen;
257 : : int i;
258 : :
920 drowley@postgresql.o 259 [ - + ]: 6755160 : Assert(bms_is_valid_set(a));
260 [ - + ]: 6755160 : Assert(bms_is_valid_set(b));
261 : :
262 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 263 [ + + ]: 6755160 : if (a == NULL)
264 : 4060570 : return bms_copy(b);
265 [ + + ]: 2694590 : if (b == NULL)
266 : 999942 : return bms_copy(a);
267 : : /* Identify shorter and longer input; copy the longer one */
268 [ + + ]: 1694648 : if (a->nwords <= b->nwords)
269 : : {
270 : 1694647 : result = bms_copy(b);
271 : 1694647 : 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 : 1694648 : otherlen = other->nwords;
1117 drowley@postgresql.o 280 : 1694648 : i = 0;
281 : : do
282 : : {
8568 tgl@sss.pgh.pa.us 283 : 1695927 : result->words[i] |= other->words[i];
1117 drowley@postgresql.o 284 [ + + ]: 1695927 : } while (++i < otherlen);
8568 tgl@sss.pgh.pa.us 285 : 1694648 : 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 *
8387 bruce@momjian.us 293 : 3358001 : 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 : :
920 drowley@postgresql.o 301 [ - + ]: 3358001 : Assert(bms_is_valid_set(a));
302 [ - + ]: 3358001 : Assert(bms_is_valid_set(b));
303 : :
304 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 305 [ + + + + ]: 3358001 : if (a == NULL || b == NULL)
306 : 1907196 : return NULL;
307 : :
308 : : /* Identify shorter and longer input; copy the shorter one */
309 [ + + ]: 1450805 : if (a->nwords <= b->nwords)
310 : : {
311 : 1450804 : result = bms_copy(a);
312 : 1450804 : 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 : 1450805 : resultlen = result->nwords;
1117 drowley@postgresql.o 321 : 1450805 : lastnonzero = -1;
322 : 1450805 : i = 0;
323 : : do
324 : : {
8568 tgl@sss.pgh.pa.us 325 : 1452084 : result->words[i] &= other->words[i];
326 : :
1117 drowley@postgresql.o 327 [ + + ]: 1452084 : if (result->words[i] != 0)
328 : 1430962 : lastnonzero = i;
329 [ + + ]: 1452084 : } while (++i < resultlen);
330 : : /* If we computed an empty result, we must return NULL */
331 [ + + ]: 1450805 : if (lastnonzero == -1)
332 : : {
1241 tgl@sss.pgh.pa.us 333 : 19994 : pfree(result);
334 : 19994 : return NULL;
335 : : }
336 : :
337 : : /* get rid of trailing zero words */
1117 drowley@postgresql.o 338 : 1430811 : result->nwords = lastnonzero + 1;
8568 tgl@sss.pgh.pa.us 339 : 1430811 : 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 *
8387 bruce@momjian.us 347 : 4306393 : bms_difference(const Bitmapset *a, const Bitmapset *b)
348 : : {
349 : : Bitmapset *result;
350 : : int i;
351 : :
920 drowley@postgresql.o 352 [ - + ]: 4306393 : Assert(bms_is_valid_set(a));
353 [ - + ]: 4306393 : Assert(bms_is_valid_set(b));
354 : :
355 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 356 [ + + ]: 4306393 : if (a == NULL)
357 : 2232401 : return NULL;
358 [ + + ]: 2073992 : if (b == NULL)
359 : 979787 : 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 : : */
1241 366 [ + + ]: 1094205 : if (!bms_nonempty_difference(a, b))
367 : 811104 : return NULL;
368 : :
369 : : /* Copy the left input */
8568 370 : 283101 : result = bms_copy(a);
371 : :
372 : : /* And remove b's bits from result */
1117 drowley@postgresql.o 373 [ + + ]: 283101 : 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 : 283099 : int lastnonzero = -1;
388 : :
389 : : /* we may need to remove trailing zero words from the result. */
390 : 283099 : i = 0;
391 : : do
392 : : {
393 : 283100 : result->words[i] &= ~b->words[i];
394 : :
395 : : /* remember the last non-zero word */
396 [ + + ]: 283100 : if (result->words[i] != 0)
397 : 283099 : lastnonzero = i;
398 [ + + ]: 283100 : } while (++i < result->nwords);
399 : :
400 : : /* trim off trailing zero words */
401 : 283099 : result->nwords = lastnonzero + 1;
402 : : }
403 [ - + ]: 283101 : Assert(result->nwords != 0);
404 : :
405 : : /* Need not check for empty result, since we handled that case above */
8568 tgl@sss.pgh.pa.us 406 : 283101 : 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 *
16 drowley@postgresql.o 419 :GNC 604508 : 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 [ - + ]: 604508 : Assert(bms_is_valid_set(a));
431 : :
432 : : /* nothing to do for empty sets */
433 [ + + ]: 604508 : if (a == NULL)
434 : 503655 : return NULL;
435 : :
436 : 100853 : old_nwords = a->nwords;
437 : 100853 : offset_words = WORDNUM(offset);
438 : 100853 : offset_bits = BITNUM(offset);
439 : 100853 : high_bit = bmw_leftmost_one_pos(a->words[a->nwords - 1]);
440 : 100853 : 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 [ + + ]: 100853 : 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 [ + + ]: 100851 : else if (new_highest < 0)
447 : 2 : return NULL;
448 : :
449 : 100849 : new_nwords = WORDNUM(new_highest) + 1;
450 : 100849 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(new_nwords));
451 : 100849 : result->type = T_Bitmapset;
452 : 100849 : result->nwords = new_nwords;
453 : :
454 : : /* handle zero and positive offsets (bitshift left) */
455 [ + + ]: 100849 : 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 [ + + ]: 100246 : if (offset_bits == 0)
463 : : {
464 : 6 : 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 [ - + ]: 52 : Assert(i + offset_words < new_nwords);
473 : 52 : result->words[i + offset_words] = a->words[i];
474 [ + + ]: 52 : } while (++i < old_nwords);
475 : : }
476 : : else
477 : : {
478 : 100240 : int carry_bits = BITS_PER_BITMAPWORD - offset_bits;
479 : 100240 : bitmapword prev_carry = 0;
480 : 100240 : int i = 0;
481 : :
482 : : do
483 : : {
484 : 107391 : bitmapword carry = (a->words[i] >> carry_bits);
485 : :
486 [ - + ]: 107391 : Assert(i + offset_words < new_nwords);
487 : : /* shift bits up and carry bits from the previous word */
488 : 107391 : result->words[i + offset_words] = (a->words[i] << offset_bits) | prev_carry;
489 : 107391 : prev_carry = carry;
490 [ + + ]: 107391 : } while (++i < old_nwords);
491 : 100240 : 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 : 603 : offset_words = 0 - offset_words;
500 : 603 : offset_bits = 0 - offset_bits;
501 : :
502 : : /* as above, special case shifting only by whole words */
503 [ + + ]: 603 : if (offset_bits == 0)
504 : : {
505 : 7 : int i = 0;
506 : :
507 : : do
508 : : {
509 [ - + ]: 43 : Assert(i + offset_words < old_nwords);
510 : 43 : result->words[i] = a->words[i + offset_words];
511 [ + + ]: 43 : } while (++i < new_nwords);
512 : : }
513 : : else
514 : : {
515 : 596 : int carry_bits = BITS_PER_BITMAPWORD - offset_bits;
516 : 596 : bitmapword prev_carry = 0;
517 : 596 : int i = new_nwords - 1;
518 : :
519 : : /* carry bits from any word just above where the loop starts */
520 [ + + ]: 596 : 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 : 5841 : bitmapword carry = (a->words[i + offset_words] << carry_bits);
530 : :
531 [ - + ]: 5841 : Assert(i + offset_words < old_nwords);
532 : :
533 : : /* shift bits down and carry bits from the previous word */
534 : 5841 : result->words[i] = (a->words[i + offset_words] >> offset_bits) | prev_carry;
535 : 5841 : prev_carry = carry;
536 [ + + ]: 5841 : } while (--i >= 0);
537 : : }
538 : : }
539 : :
540 : 100849 : return result;
541 : : }
542 : :
543 : : /*
544 : : * bms_is_subset - is A a subset of B?
545 : : */
546 : : bool
8387 bruce@momjian.us 547 :CBC 21660484 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
548 : : {
549 : : int i;
550 : :
920 drowley@postgresql.o 551 [ - + ]: 21660484 : Assert(bms_is_valid_set(a));
552 [ - + ]: 21660484 : Assert(bms_is_valid_set(b));
553 : :
554 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 555 [ + + ]: 21660484 : if (a == NULL)
556 : 4800330 : return true; /* empty set is a subset of anything */
557 [ + + ]: 16860154 : if (b == NULL)
1241 558 : 293741 : return false;
559 : :
560 : : /* 'a' can't be a subset of 'b' if it contains more words */
1117 drowley@postgresql.o 561 [ + + ]: 16566413 : if (a->nwords > b->nwords)
562 : 2 : return false;
563 : :
564 : : /* Check all 'a' members are set in 'b' */
565 : 16566411 : i = 0;
566 : : do
567 : : {
8391 bruce@momjian.us 568 [ + + ]: 16566411 : if ((a->words[i] & ~b->words[i]) != 0)
8568 tgl@sss.pgh.pa.us 569 : 5685948 : return false;
1117 drowley@postgresql.o 570 [ - + ]: 10880463 : } while (++i < a->nwords);
8568 tgl@sss.pgh.pa.us 571 : 10880463 : 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
5293 580 : 2180298 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
581 : : {
582 : : BMS_Comparison result;
583 : : int shortlen;
584 : : int i;
585 : :
920 drowley@postgresql.o 586 [ - + ]: 2180298 : Assert(bms_is_valid_set(a));
587 [ - + ]: 2180298 : Assert(bms_is_valid_set(b));
588 : :
589 : : /* Handle cases where either input is NULL */
5293 tgl@sss.pgh.pa.us 590 [ + + ]: 2180298 : if (a == NULL)
591 : : {
592 [ + + ]: 1803084 : if (b == NULL)
593 : 1752782 : return BMS_EQUAL;
1241 594 : 50302 : return BMS_SUBSET1;
595 : : }
5293 596 [ + + ]: 377214 : if (b == NULL)
1241 597 : 190580 : return BMS_SUBSET2;
598 : :
599 : : /* Check common words */
5293 600 : 186634 : result = BMS_EQUAL; /* status so far */
601 : 186634 : shortlen = Min(a->nwords, b->nwords);
1117 drowley@postgresql.o 602 : 186634 : i = 0;
603 : : do
604 : : {
5158 bruce@momjian.us 605 : 186637 : bitmapword aword = a->words[i];
606 : 186637 : bitmapword bword = b->words[i];
607 : :
5293 tgl@sss.pgh.pa.us 608 [ + + ]: 186637 : if ((aword & ~bword) != 0)
609 : : {
610 : : /* a is not a subset of b */
611 [ + + ]: 53946 : if (result == BMS_SUBSET1)
612 : 2 : return BMS_DIFFERENT;
613 : 53944 : result = BMS_SUBSET2;
614 : : }
615 [ + + ]: 186635 : if ((bword & ~aword) != 0)
616 : : {
617 : : /* b is not a subset of a */
618 [ + + ]: 56319 : if (result == BMS_SUBSET2)
619 : 48788 : return BMS_DIFFERENT;
620 : 7531 : result = BMS_SUBSET1;
621 : : }
1117 drowley@postgresql.o 622 [ + + ]: 137847 : } while (++i < shortlen);
623 : : /* Check extra words */
5293 tgl@sss.pgh.pa.us 624 [ + + ]: 137844 : if (a->nwords > b->nwords)
625 : : {
626 : : /* if a has more words then a is not a subset of b */
1117 drowley@postgresql.o 627 [ + + ]: 2 : if (result == BMS_SUBSET1)
628 : 1 : return BMS_DIFFERENT;
629 : 1 : return BMS_SUBSET2;
630 : : }
5293 tgl@sss.pgh.pa.us 631 [ + + ]: 137842 : else if (a->nwords < b->nwords)
632 : : {
633 : : /* if b has more words then b is not a subset of a */
1117 drowley@postgresql.o 634 [ + + ]: 4 : if (result == BMS_SUBSET2)
635 : 2 : return BMS_DIFFERENT;
636 : 2 : return BMS_SUBSET1;
637 : : }
5293 tgl@sss.pgh.pa.us 638 : 137838 : return result;
639 : : }
640 : :
641 : : /*
642 : : * bms_is_member - is X a member of A?
643 : : */
644 : : bool
8387 bruce@momjian.us 645 : 13520203 : bms_is_member(int x, const Bitmapset *a)
646 : : {
647 : : int wordnum,
648 : : bitnum;
649 : :
920 drowley@postgresql.o 650 [ - + ]: 13520203 : Assert(bms_is_valid_set(a));
651 : :
652 : : /* XXX better to just return false for x<0 ? */
8568 tgl@sss.pgh.pa.us 653 [ + + ]: 13520203 : if (x < 0)
8404 654 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
8568 655 [ + + ]: 13520202 : if (a == NULL)
656 : 7045807 : return false;
657 : :
658 : 6474395 : wordnum = WORDNUM(x);
659 : 6474395 : bitnum = BITNUM(x);
660 [ + + ]: 6474395 : if (wordnum >= a->nwords)
661 : 297 : return false;
662 [ + + ]: 6474098 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
663 : 4038617 : return true;
664 : 2435481 : 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
2677 tomas.vondra@postgre 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 : :
920 drowley@postgresql.o 681 [ - + ]: 4427 : Assert(bms_is_valid_set(a));
682 : :
683 : : /* return -1 if not a member of the bitmap */
2677 tomas.vondra@postgre 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 */
152 nathan@postgresql.or 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 : : */
2677 tomas.vondra@postgre 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
8387 bruce@momjian.us 710 : 25004021 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
711 : : {
712 : : int shortlen;
713 : : int i;
714 : :
920 drowley@postgresql.o 715 [ - + ]: 25004021 : Assert(bms_is_valid_set(a));
716 [ - + ]: 25004021 : Assert(bms_is_valid_set(b));
717 : :
718 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 719 [ + + + + ]: 25004021 : if (a == NULL || b == NULL)
720 : 16677818 : return false;
721 : : /* Check words in common */
722 : 8326203 : shortlen = Min(a->nwords, b->nwords);
1117 drowley@postgresql.o 723 : 8326203 : i = 0;
724 : : do
725 : : {
8568 tgl@sss.pgh.pa.us 726 [ + + ]: 8326203 : if ((a->words[i] & b->words[i]) != 0)
727 : 4934808 : return true;
1117 drowley@postgresql.o 728 [ - + ]: 3391395 : } while (++i < shortlen);
8568 tgl@sss.pgh.pa.us 729 : 3391395 : return false;
730 : : }
731 : :
732 : : /*
733 : : * bms_overlap_list - does a set overlap an integer list?
734 : : */
735 : : bool
3407 rhodiumtoad@postgres 736 : 1529 : bms_overlap_list(const Bitmapset *a, const List *b)
737 : : {
738 : : ListCell *lc;
739 : : int wordnum,
740 : : bitnum;
741 : :
920 drowley@postgresql.o 742 [ - + ]: 1529 : Assert(bms_is_valid_set(a));
743 : :
3407 rhodiumtoad@postgres 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
8387 bruce@momjian.us 769 : 3048250 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
770 : : {
771 : : int i;
772 : :
920 drowley@postgresql.o 773 [ - + ]: 3048250 : Assert(bms_is_valid_set(a));
774 [ - + ]: 3048250 : Assert(bms_is_valid_set(b));
775 : :
776 : : /* Handle cases where either input is NULL */
8427 tgl@sss.pgh.pa.us 777 [ + + ]: 3048250 : if (a == NULL)
778 : 4361 : return false;
779 [ + + ]: 3043889 : if (b == NULL)
1241 780 : 1 : return true;
781 : : /* if 'a' has more words then it must contain additional members */
1117 drowley@postgresql.o 782 [ + + ]: 3043888 : if (a->nwords > b->nwords)
783 : 3 : return true;
784 : : /* Check all 'a' members are set in 'b' */
785 : 3043885 : i = 0;
786 : : do
787 : : {
8391 bruce@momjian.us 788 [ + + ]: 3043885 : if ((a->words[i] & ~b->words[i]) != 0)
8427 tgl@sss.pgh.pa.us 789 : 1327104 : return true;
1117 drowley@postgresql.o 790 [ - + ]: 1716781 : } while (++i < a->nwords);
8427 tgl@sss.pgh.pa.us 791 : 1716781 : 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
8387 bruce@momjian.us 800 : 17648 : bms_singleton_member(const Bitmapset *a)
801 : : {
8391 802 : 17648 : int result = -1;
803 : : int nwords;
804 : : int wordnum;
805 : :
920 drowley@postgresql.o 806 [ - + ]: 17648 : Assert(bms_is_valid_set(a));
807 : :
8568 tgl@sss.pgh.pa.us 808 [ + + ]: 17648 : if (a == NULL)
8404 809 [ + - ]: 1 : elog(ERROR, "bitmapset is empty");
810 : :
8568 811 : 17647 : nwords = a->nwords;
1117 drowley@postgresql.o 812 : 17647 : wordnum = 0;
813 : : do
814 : : {
8568 tgl@sss.pgh.pa.us 815 : 17647 : bitmapword w = a->words[wordnum];
816 : :
817 [ + - ]: 17647 : if (w != 0)
818 : : {
819 [ + - + + ]: 17647 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
8404 820 [ + - ]: 1 : elog(ERROR, "bitmapset has multiple members");
8568 821 : 17646 : result = wordnum * BITS_PER_BITMAPWORD;
2717 822 : 17646 : result += bmw_rightmost_one_pos(w);
823 : : }
1117 drowley@postgresql.o 824 [ - + ]: 17646 : } while (++wordnum < nwords);
825 : :
826 : : /* we don't expect non-NULL sets to be empty */
827 [ - + ]: 17646 : Assert(result >= 0);
8568 tgl@sss.pgh.pa.us 828 : 17646 : 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
4257 843 : 2144344 : bms_get_singleton_member(const Bitmapset *a, int *member)
844 : : {
845 : 2144344 : int result = -1;
846 : : int nwords;
847 : : int wordnum;
848 : :
920 drowley@postgresql.o 849 [ - + ]: 2144344 : Assert(bms_is_valid_set(a));
850 : :
4257 tgl@sss.pgh.pa.us 851 [ + + ]: 2144344 : if (a == NULL)
852 : 2 : return false;
853 : :
854 : 2144342 : nwords = a->nwords;
1117 drowley@postgresql.o 855 : 2144342 : wordnum = 0;
856 : : do
857 : : {
4257 tgl@sss.pgh.pa.us 858 : 2144348 : bitmapword w = a->words[wordnum];
859 : :
860 [ + + ]: 2144348 : if (w != 0)
861 : : {
862 [ + - + + ]: 2144342 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
863 : 415984 : return false;
864 : 1728358 : result = wordnum * BITS_PER_BITMAPWORD;
2717 865 : 1728358 : result += bmw_rightmost_one_pos(w);
866 : : }
1117 drowley@postgresql.o 867 [ + + ]: 1728364 : } while (++wordnum < nwords);
868 : :
869 : : /* we don't expect non-NULL sets to be empty */
870 [ - + ]: 1728358 : Assert(result >= 0);
4257 tgl@sss.pgh.pa.us 871 : 1728358 : *member = result;
872 : 1728358 : return true;
873 : : }
874 : :
875 : : /*
876 : : * bms_num_members - count members of set
877 : : */
878 : : int
8387 bruce@momjian.us 879 : 2000848 : bms_num_members(const Bitmapset *a)
880 : : {
920 drowley@postgresql.o 881 [ - + ]: 2000848 : Assert(bms_is_valid_set(a));
882 : :
8568 tgl@sss.pgh.pa.us 883 [ + + ]: 2000848 : if (a == NULL)
884 : 279488 : return 0;
885 : :
886 : : /* fast-path for common case */
152 nathan@postgresql.or 887 [ + + ]: 1721360 : if (a->nwords == 1)
888 : 1720974 : 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
8387 bruce@momjian.us 900 : 1652832 : bms_membership(const Bitmapset *a)
901 : : {
8568 tgl@sss.pgh.pa.us 902 : 1652832 : BMS_Membership result = BMS_EMPTY_SET;
903 : : int nwords;
904 : : int wordnum;
905 : :
920 drowley@postgresql.o 906 [ - + ]: 1652832 : Assert(bms_is_valid_set(a));
907 : :
8568 tgl@sss.pgh.pa.us 908 [ + + ]: 1652832 : if (a == NULL)
909 : 413 : return BMS_EMPTY_SET;
910 : :
911 : 1652419 : nwords = a->nwords;
1117 drowley@postgresql.o 912 : 1652419 : wordnum = 0;
913 : : do
914 : : {
8568 tgl@sss.pgh.pa.us 915 : 1652535 : bitmapword w = a->words[wordnum];
916 : :
917 [ + + ]: 1652535 : if (w != 0)
918 : : {
919 [ + - + + ]: 1652419 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
920 : 609643 : return BMS_MULTIPLE;
921 : 1042776 : result = BMS_SINGLETON;
922 : : }
1117 drowley@postgresql.o 923 [ + + ]: 1042892 : } while (++wordnum < nwords);
8568 tgl@sss.pgh.pa.us 924 : 1042776 : 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 *
8387 bruce@momjian.us 934 : 17895334 : bms_add_member(Bitmapset *a, int x)
935 : : {
936 : : int wordnum,
937 : : bitnum;
938 : :
920 drowley@postgresql.o 939 [ - + ]: 17895334 : Assert(bms_is_valid_set(a));
940 : :
8568 tgl@sss.pgh.pa.us 941 [ + + ]: 17895334 : if (x < 0)
8404 942 [ + - ]: 2 : elog(ERROR, "negative bitmapset member not allowed");
8568 943 [ + + ]: 17895332 : if (a == NULL)
944 : 9191219 : return bms_make_singleton(x);
945 : :
946 : 8704113 : wordnum = WORDNUM(x);
947 : 8704113 : bitnum = BITNUM(x);
948 : :
949 : : /* enlarge the set if necessary */
950 [ + + ]: 8704113 : if (wordnum >= a->nwords)
951 : : {
4681 heikki.linnakangas@i 952 : 15351 : int oldnwords = a->nwords;
953 : : int i;
954 : :
955 : 15351 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
956 : 15351 : a->nwords = wordnum + 1;
957 : : /* zero out the enlarged portion */
1117 drowley@postgresql.o 958 : 15351 : i = oldnwords;
959 : : do
960 : : {
4681 heikki.linnakangas@i 961 : 34232 : a->words[i] = 0;
1117 drowley@postgresql.o 962 [ + + ]: 34232 : } while (++i < a->nwords);
963 : : }
964 : :
920 965 : 8704113 : 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 : :
8568 tgl@sss.pgh.pa.us 976 : 8704113 : 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 *
8387 bruce@momjian.us 987 : 1481459 : bms_del_member(Bitmapset *a, int x)
988 : : {
989 : : int wordnum,
990 : : bitnum;
991 : :
920 drowley@postgresql.o 992 [ - + ]: 1481459 : Assert(bms_is_valid_set(a));
993 : :
8568 tgl@sss.pgh.pa.us 994 [ + + ]: 1481459 : if (x < 0)
8404 995 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
8568 996 [ + + ]: 1481458 : if (a == NULL)
997 : 528639 : return NULL;
998 : :
999 : 952819 : wordnum = WORDNUM(x);
1000 : 952819 : 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 */
1117 drowley@postgresql.o 1007 [ - + ]: 952819 : if (unlikely(wordnum >= a->nwords))
1117 drowley@postgresql.o 1008 :UBC 0 : return a;
1009 : :
1117 drowley@postgresql.o 1010 :CBC 952819 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
1011 : :
1012 : : /* when last word becomes empty, trim off all trailing empty words */
1013 [ + + + + ]: 952819 : 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 [ + + ]: 460884 : for (int i = wordnum - 1; i >= 0; i--)
1017 : : {
1018 [ + + ]: 20837 : if (a->words[i] != 0)
1019 : : {
1020 : 126 : a->nwords = i + 1;
1021 : 126 : return a;
1022 : : }
1023 : : }
1024 : :
1025 : : /* the set is now empty */
1241 tgl@sss.pgh.pa.us 1026 : 440047 : pfree(a);
1027 : 440047 : return NULL;
1028 : : }
8568 1029 : 512646 : return a;
1030 : : }
1031 : :
1032 : : /*
1033 : : * bms_add_members - like bms_union, but left input is recycled when possible
1034 : : */
1035 : : Bitmapset *
8387 bruce@momjian.us 1036 : 19843358 : bms_add_members(Bitmapset *a, const Bitmapset *b)
1037 : : {
1038 : : Bitmapset *result;
1039 : : const Bitmapset *other;
1040 : : int otherlen;
1041 : : int i;
1042 : :
920 drowley@postgresql.o 1043 [ - + ]: 19843358 : Assert(bms_is_valid_set(a));
1044 [ - + ]: 19843358 : Assert(bms_is_valid_set(b));
1045 : :
1046 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 1047 [ + + ]: 19843358 : if (a == NULL)
1048 : 14206447 : return bms_copy(b);
1049 [ + + ]: 5636911 : if (b == NULL)
1050 : : {
1051 : : #ifdef REALLOCATE_BITMAPSETS
1052 : : a = bms_copy_and_free(a);
1053 : : #endif
1054 : :
1055 : 3583547 : return a;
1056 : : }
1057 : : /* Identify shorter and longer input; copy the longer one if needed */
1058 [ + + ]: 2053364 : if (a->nwords < b->nwords)
1059 : : {
1060 : 17 : result = bms_copy(b);
1061 : 17 : other = a;
1062 : : }
1063 : : else
1064 : : {
1065 : 2053347 : result = a;
1066 : 2053347 : other = b;
1067 : : }
1068 : : /* And union the shorter input into the result */
1069 : 2053364 : otherlen = other->nwords;
1117 drowley@postgresql.o 1070 : 2053364 : i = 0;
1071 : : do
1072 : : {
8568 tgl@sss.pgh.pa.us 1073 : 2054000 : result->words[i] |= other->words[i];
1117 drowley@postgresql.o 1074 [ + + ]: 2054000 : } while (++i < otherlen);
8568 tgl@sss.pgh.pa.us 1075 [ + + ]: 2053364 : if (result != a)
1076 : 17 : pfree(a);
1077 : : #ifdef REALLOCATE_BITMAPSETS
1078 : : else
1079 : : result = bms_copy_and_free(result);
1080 : : #endif
1081 : :
1082 : 2053364 : 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 *
918 drowley@postgresql.o 1091 : 11241 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
1092 : : {
1093 : : int i;
1094 : :
1095 [ - + ]: 11241 : Assert(bms_is_valid_set(a));
1096 [ - + ]: 11241 : 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 *
3160 rhaas@postgresql.org 1138 : 45125 : bms_add_range(Bitmapset *a, int lower, int upper)
1139 : : {
1140 : : int lwordnum,
1141 : : lbitnum,
1142 : : uwordnum,
1143 : : ushiftbits,
1144 : : wordnum;
1145 : :
920 drowley@postgresql.o 1146 [ - + ]: 45125 : Assert(bms_is_valid_set(a));
1147 : :
1148 : : /* do nothing if nothing is called for, without further checking */
2917 alvherre@alvh.no-ip. 1149 [ + + ]: 45125 : if (upper < lower)
1150 : : {
1151 : : #ifdef REALLOCATE_BITMAPSETS
1152 : : a = bms_copy_and_free(a);
1153 : : #endif
1154 : :
1155 : 23 : return a;
1156 : : }
1157 : :
tgl@sss.pgh.pa.us 1158 [ + + ]: 45102 : if (lower < 0)
3160 rhaas@postgresql.org 1159 [ + - ]: 1 : elog(ERROR, "negative bitmapset member not allowed");
1160 : 45101 : uwordnum = WORDNUM(upper);
1161 : :
1162 [ + + ]: 45101 : if (a == NULL)
1163 : : {
1164 : 35071 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1350 tgl@sss.pgh.pa.us 1165 : 35071 : a->type = T_Bitmapset;
3160 rhaas@postgresql.org 1166 : 35071 : a->nwords = uwordnum + 1;
1167 : : }
1168 [ + + ]: 10030 : else if (uwordnum >= a->nwords)
1169 : : {
1170 : 2 : int oldnwords = a->nwords;
1171 : : int i;
1172 : :
1173 : : /* ensure we have enough words to store the upper bit */
1174 : 2 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1175 : 2 : a->nwords = uwordnum + 1;
1176 : : /* zero out the enlarged portion */
1117 drowley@postgresql.o 1177 : 2 : i = oldnwords;
1178 : : do
1179 : : {
3160 rhaas@postgresql.org 1180 : 4 : a->words[i] = 0;
1117 drowley@postgresql.o 1181 [ + + ]: 4 : } while (++i < a->nwords);
1182 : : }
1183 : :
3160 rhaas@postgresql.org 1184 : 45101 : wordnum = lwordnum = WORDNUM(lower);
1185 : :
1186 : 45101 : lbitnum = BITNUM(lower);
1187 : 45101 : 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 [ + + ]: 45101 : if (lwordnum == uwordnum)
1194 : : {
1195 : 44130 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
3119 tgl@sss.pgh.pa.us 1196 : 44130 : & (~(bitmapword) 0) >> ushiftbits;
1197 : : }
1198 : : else
1199 : : {
1200 : : /* turn on lbitnum and all bits left of it */
3160 rhaas@postgresql.org 1201 : 971 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1202 : :
1203 : : /* turn on all bits for any intermediate words */
1204 [ + + ]: 1006 : while (wordnum < uwordnum)
1205 : 35 : a->words[wordnum++] = ~(bitmapword) 0;
1206 : :
1207 : : /* turn on upper's bit and all bits right of it. */
1208 : 971 : 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 : 45101 : return a;
1221 : : }
1222 : :
1223 : : /*
1224 : : * bms_int_members - like bms_intersect, but left input is recycled when
1225 : : * possible
1226 : : */
1227 : : Bitmapset *
8387 bruce@momjian.us 1228 : 619860 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1229 : : {
1230 : : int lastnonzero;
1231 : : int shortlen;
1232 : : int i;
1233 : :
920 drowley@postgresql.o 1234 [ - + ]: 619860 : Assert(bms_is_valid_set(a));
1235 [ - + ]: 619860 : Assert(bms_is_valid_set(b));
1236 : :
1237 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 1238 [ + + ]: 619860 : if (a == NULL)
1239 : 19888 : return NULL;
1240 [ + + ]: 599972 : if (b == NULL)
1241 : : {
1242 : 3191 : pfree(a);
1243 : 3191 : return NULL;
1244 : : }
1245 : :
1246 : : /* Intersect b into a; we need never copy */
1247 : 596781 : shortlen = Min(a->nwords, b->nwords);
1117 drowley@postgresql.o 1248 : 596781 : lastnonzero = -1;
1249 : 596781 : i = 0;
1250 : : do
1251 : : {
8568 tgl@sss.pgh.pa.us 1252 : 596782 : a->words[i] &= b->words[i];
1253 : :
1117 drowley@postgresql.o 1254 [ + + ]: 596782 : if (a->words[i] != 0)
1255 : 492324 : lastnonzero = i;
1256 [ + + ]: 596782 : } while (++i < shortlen);
1257 : :
1258 : : /* If we computed an empty result, we must return NULL */
1259 [ + + ]: 596781 : if (lastnonzero == -1)
1260 : : {
1241 tgl@sss.pgh.pa.us 1261 : 104458 : pfree(a);
1262 : 104458 : return NULL;
1263 : : }
1264 : :
1265 : : /* get rid of trailing zero words */
1117 drowley@postgresql.o 1266 : 492323 : a->nwords = lastnonzero + 1;
1267 : :
1268 : : #ifdef REALLOCATE_BITMAPSETS
1269 : : a = bms_copy_and_free(a);
1270 : : #endif
1271 : :
8568 tgl@sss.pgh.pa.us 1272 : 492323 : 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 *
8387 bruce@momjian.us 1280 : 1768835 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1281 : : {
1282 : : int i;
1283 : :
920 drowley@postgresql.o 1284 [ - + ]: 1768835 : Assert(bms_is_valid_set(a));
1285 [ - + ]: 1768835 : Assert(bms_is_valid_set(b));
1286 : :
1287 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 1288 [ + + ]: 1768835 : if (a == NULL)
1289 : 781021 : return NULL;
1290 [ + + ]: 987814 : if (b == NULL)
1291 : : {
1292 : : #ifdef REALLOCATE_BITMAPSETS
1293 : : a = bms_copy_and_free(a);
1294 : : #endif
1295 : :
920 drowley@postgresql.o 1296 : 158398 : return a;
1297 : : }
1298 : :
1299 : : /* Remove b's bits from a; we need never copy */
1117 1300 [ + + ]: 829416 : 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 : 829415 : int lastnonzero = -1;
1315 : :
1316 : : /* we may need to remove trailing zero words from the result. */
1317 : 829415 : i = 0;
1318 : : do
1319 : : {
1320 : 829423 : a->words[i] &= ~b->words[i];
1321 : :
1322 : : /* remember the last non-zero word */
1323 [ + + ]: 829423 : if (a->words[i] != 0)
1324 : 182973 : lastnonzero = i;
1325 [ + + ]: 829423 : } while (++i < a->nwords);
1326 : :
1327 : : /* check if 'a' has become empty */
1328 [ + + ]: 829415 : if (lastnonzero == -1)
1329 : : {
1330 : 646444 : pfree(a);
1331 : 646444 : return NULL;
1332 : : }
1333 : :
1334 : : /* trim off any trailing zero words */
1335 : 182971 : a->nwords = lastnonzero + 1;
1336 : : }
1337 : :
1338 : : #ifdef REALLOCATE_BITMAPSETS
1339 : : a = bms_copy_and_free(a);
1340 : : #endif
1341 : :
8568 tgl@sss.pgh.pa.us 1342 : 182972 : return a;
1343 : : }
1344 : :
1345 : : /*
1346 : : * bms_join - like bms_union, but *either* input *may* be recycled
1347 : : */
1348 : : Bitmapset *
8387 bruce@momjian.us 1349 : 1340060 : bms_join(Bitmapset *a, Bitmapset *b)
1350 : : {
1351 : : Bitmapset *result;
1352 : : Bitmapset *other;
1353 : : int otherlen;
1354 : : int i;
1355 : :
920 drowley@postgresql.o 1356 [ - + ]: 1340060 : Assert(bms_is_valid_set(a));
1357 [ - + ]: 1340060 : Assert(bms_is_valid_set(b));
1358 : :
1359 : : /* Handle cases where either input is NULL */
8568 tgl@sss.pgh.pa.us 1360 [ + + ]: 1340060 : if (a == NULL)
1361 : : {
1362 : : #ifdef REALLOCATE_BITMAPSETS
1363 : : b = bms_copy_and_free(b);
1364 : : #endif
1365 : :
1366 : 530323 : return b;
1367 : : }
1368 [ + + ]: 809737 : if (b == NULL)
1369 : : {
1370 : : #ifdef REALLOCATE_BITMAPSETS
1371 : : a = bms_copy_and_free(a);
1372 : : #endif
1373 : :
920 drowley@postgresql.o 1374 : 133144 : return a;
1375 : : }
1376 : :
1377 : : /* Identify shorter and longer input; use longer one as result */
8568 tgl@sss.pgh.pa.us 1378 [ + + ]: 676593 : if (a->nwords < b->nwords)
1379 : : {
1380 : 2 : result = b;
1381 : 2 : other = a;
1382 : : }
1383 : : else
1384 : : {
1385 : 676591 : result = a;
1386 : 676591 : other = b;
1387 : : }
1388 : : /* And union the shorter input into the result */
1389 : 676593 : otherlen = other->nwords;
1117 drowley@postgresql.o 1390 : 676593 : i = 0;
1391 : : do
1392 : : {
8568 tgl@sss.pgh.pa.us 1393 : 676593 : result->words[i] |= other->words[i];
1117 drowley@postgresql.o 1394 [ - + ]: 676593 : } while (++i < otherlen);
8568 tgl@sss.pgh.pa.us 1395 [ + - ]: 676593 : if (other != result) /* pure paranoia */
1396 : 676593 : pfree(other);
1397 : :
1398 : : #ifdef REALLOCATE_BITMAPSETS
1399 : : result = bms_copy_and_free(result);
1400 : : #endif
1401 : :
1402 : 676593 : 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
4257 1425 : 22505851 : bms_next_member(const Bitmapset *a, int prevbit)
1426 : : {
103 drowley@postgresql.o 1427 : 22505851 : unsigned int currbit = prevbit;
1428 : : int nwords;
1429 : : bitmapword mask;
1430 : :
920 1431 [ - + ]: 22505851 : Assert(bms_is_valid_set(a));
1432 : :
4257 tgl@sss.pgh.pa.us 1433 [ + + ]: 22505851 : if (a == NULL)
1434 : 6020024 : return -2;
1435 : 16485827 : nwords = a->nwords;
1436 : :
1437 : : /* use an unsigned int to avoid the risk that int overflows */
103 drowley@postgresql.o 1438 : 16485827 : currbit++;
1439 : 16485827 : mask = (~(bitmapword) 0) << BITNUM(currbit);
1440 [ + + ]: 21861234 : for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
1441 : : {
4257 tgl@sss.pgh.pa.us 1442 : 16497000 : bitmapword w = a->words[wordnum];
1443 : :
1444 : : /* ignore bits before currbit */
1445 : 16497000 : w &= mask;
1446 : :
1447 [ + + ]: 16497000 : if (w != 0)
1448 : : {
1449 : : int result;
1450 : :
1451 : 11121593 : result = wordnum * BITS_PER_BITMAPWORD;
2717 1452 : 11121593 : result += bmw_rightmost_one_pos(w);
4257 1453 : 11121593 : return result;
1454 : : }
1455 : :
1456 : : /* in subsequent words, consider all bits */
1457 : 5375407 : mask = (~(bitmapword) 0);
1458 : : }
1459 : 5364234 : 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
3031 alvherre@alvh.no-ip. 1487 : 18 : bms_prev_member(const Bitmapset *a, int prevbit)
1488 : : {
1489 : : unsigned int currbit;
1490 : : int ushiftbits;
1491 : : bitmapword mask;
1492 : :
920 drowley@postgresql.o 1493 [ - + ]: 18 : 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 : : */
3031 alvherre@alvh.no-ip. 1499 [ + + - + ]: 18 : if (a == NULL || prevbit == 0)
1500 : 2 : return -2;
1501 : :
1502 : : /* Validate callers didn't give us something out of range */
103 drowley@postgresql.o 1503 [ + + - + ]: 16 : 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);
3031 alvherre@alvh.no-ip. 1516 : 16 : mask = (~(bitmapword) 0) >> ushiftbits;
103 drowley@postgresql.o 1517 [ + + ]: 21 : for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
1518 : : {
3031 alvherre@alvh.no-ip. 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;
2717 tgl@sss.pgh.pa.us 1529 : 11 : result += bmw_leftmost_one_pos(w);
3031 alvherre@alvh.no-ip. 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
7717 tgl@sss.pgh.pa.us 1543 : 5121 : bms_hash_value(const Bitmapset *a)
1544 : : {
920 drowley@postgresql.o 1545 [ - + ]: 5121 : Assert(bms_is_valid_set(a));
1546 : :
6994 tgl@sss.pgh.pa.us 1547 [ + + ]: 5121 : if (a == NULL)
7717 1548 : 4 : return 0; /* All empty sets hash to 0 */
6994 1549 : 5117 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1117 drowley@postgresql.o 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
2343 rhaas@postgresql.org 1559 : 5114 : bitmap_hash(const void *key, Size keysize)
1560 : : {
1561 [ - + ]: 5114 : 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 [ - + ]: 2885 : Assert(keysize == sizeof(Bitmapset *));
1572 : 2885 : return !bms_equal(*((const Bitmapset *const *) key1),
1573 : : *((const Bitmapset *const *) key2));
1574 : : }
|
