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