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
839 drowley@postgresql.o 79 :CBC 302554244 : bms_is_valid_set(const Bitmapset *a)
80 : : {
81 : : /* NULL is the correct representation of an empty set */
82 [ + + ]: 302554244 : if (a == NULL)
83 : 141913301 : return true;
84 : :
85 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
86 [ - + ]: 160640943 : if (!IsA(a, Bitmapset))
839 drowley@postgresql.o 87 :UBC 0 : return false;
88 : :
89 : : /* trailing zero words are not allowed */
839 drowley@postgresql.o 90 [ - + ]:CBC 160640943 : if (a->words[a->nwords - 1] == 0)
839 drowley@postgresql.o 91 :UBC 0 : return false;
92 : :
839 drowley@postgresql.o 93 :CBC 160640943 : 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 *
8306 bruce@momjian.us 122 : 38403242 : bms_copy(const Bitmapset *a)
123 : : {
124 : : Bitmapset *result;
125 : : size_t size;
126 : :
839 drowley@postgresql.o 127 [ - + ]: 38403242 : Assert(bms_is_valid_set(a));
128 : :
8487 tgl@sss.pgh.pa.us 129 [ + + ]: 38403242 : if (a == NULL)
130 : 24939468 : return NULL;
131 : :
132 : 13463774 : size = BITMAPSET_SIZE(a->nwords);
133 : 13463774 : result = (Bitmapset *) palloc(size);
134 : 13463774 : memcpy(result, a, size);
135 : 13463774 : return result;
136 : : }
137 : :
138 : : /*
139 : : * bms_equal - are two bitmapsets equal? or both NULL?
140 : : */
141 : : bool
8306 bruce@momjian.us 142 : 11067534 : bms_equal(const Bitmapset *a, const Bitmapset *b)
143 : : {
144 : : int i;
145 : :
839 drowley@postgresql.o 146 [ - + ]: 11067534 : Assert(bms_is_valid_set(a));
147 [ - + ]: 11067534 : Assert(bms_is_valid_set(b));
148 : :
149 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 150 [ + + ]: 11067534 : if (a == NULL)
151 : : {
152 [ + + ]: 6435224 : if (b == NULL)
153 : 6383990 : return true;
1160 154 : 51234 : return false;
155 : : }
8487 156 [ + + ]: 4632310 : else if (b == NULL)
1160 157 : 20876 : return false;
158 : :
159 : : /* can't be equal if the word counts don't match */
1036 drowley@postgresql.o 160 [ + + ]: 4611434 : if (a->nwords != b->nwords)
1036 drowley@postgresql.o 161 :GBC 5896 : return false;
162 : :
163 : : /* check each word matches */
1036 drowley@postgresql.o 164 :CBC 4605538 : i = 0;
165 : : do
166 : : {
167 [ + + ]: 4607876 : if (a->words[i] != b->words[i])
8487 tgl@sss.pgh.pa.us 168 : 2656631 : return false;
1036 drowley@postgresql.o 169 [ + + ]: 1951245 : } while (++i < a->nwords);
170 : :
8487 tgl@sss.pgh.pa.us 171 : 1948907 : 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
3038 183 : 23288 : bms_compare(const Bitmapset *a, const Bitmapset *b)
184 : : {
185 : : int i;
186 : :
839 drowley@postgresql.o 187 [ - + ]: 23288 : Assert(bms_is_valid_set(a));
188 [ - + ]: 23288 : Assert(bms_is_valid_set(b));
189 : :
190 : : /* Handle cases where either input is NULL */
3038 tgl@sss.pgh.pa.us 191 [ + + ]: 23288 : if (a == NULL)
1160 tgl@sss.pgh.pa.us 192 [ + + ]:GBC 4 : return (b == NULL) ? 0 : -1;
3038 tgl@sss.pgh.pa.us 193 [ + + ]:CBC 23284 : else if (b == NULL)
1160 tgl@sss.pgh.pa.us 194 :GBC 2 : return +1;
195 : :
196 : : /* the set with the most words must be greater */
1036 drowley@postgresql.o 197 [ + + ]:CBC 23282 : if (a->nwords != b->nwords)
1036 drowley@postgresql.o 198 [ - + ]:GBC 21 : return (a->nwords > b->nwords) ? +1 : -1;
199 : :
1036 drowley@postgresql.o 200 :CBC 23261 : i = a->nwords - 1;
201 : : do
202 : : {
3038 tgl@sss.pgh.pa.us 203 : 23261 : bitmapword aw = a->words[i];
204 : 23261 : bitmapword bw = b->words[i];
205 : :
206 [ + + ]: 23261 : if (aw != bw)
207 [ + + ]: 23260 : return (aw > bw) ? +1 : -1;
1036 drowley@postgresql.o 208 [ - + ]:GBC 1 : } while (--i >= 0);
3038 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 *
8487 tgl@sss.pgh.pa.us 216 :CBC 13058721 : bms_make_singleton(int x)
217 : : {
218 : : Bitmapset *result;
219 : : int wordnum,
220 : : bitnum;
221 : :
222 [ + + ]: 13058721 : if (x < 0)
8323 tgl@sss.pgh.pa.us 223 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8487 tgl@sss.pgh.pa.us 224 :CBC 13058720 : wordnum = WORDNUM(x);
225 : 13058720 : bitnum = BITNUM(x);
226 : 13058720 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
1269 227 : 13058720 : result->type = T_Bitmapset;
8487 228 : 13058720 : result->nwords = wordnum + 1;
229 : 13058720 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
230 : 13058720 : return result;
231 : : }
232 : :
233 : : /*
234 : : * bms_free - free a bitmapset
235 : : *
236 : : * Same as pfree except for allowing NULL input
237 : : */
238 : : void
8306 bruce@momjian.us 239 : 32139961 : bms_free(Bitmapset *a)
240 : : {
8487 tgl@sss.pgh.pa.us 241 [ + + ]: 32139961 : if (a)
242 : 7537269 : pfree(a);
243 : 32139961 : }
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 *
8306 bruce@momjian.us 251 : 6780557 : bms_union(const Bitmapset *a, const Bitmapset *b)
252 : : {
253 : : Bitmapset *result;
254 : : const Bitmapset *other;
255 : : int otherlen;
256 : : int i;
257 : :
839 drowley@postgresql.o 258 [ - + ]: 6780557 : Assert(bms_is_valid_set(a));
259 [ - + ]: 6780557 : Assert(bms_is_valid_set(b));
260 : :
261 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 262 [ + + ]: 6780557 : if (a == NULL)
263 : 4182376 : return bms_copy(b);
264 [ + + ]: 2598181 : if (b == NULL)
265 : 1020327 : return bms_copy(a);
266 : : /* Identify shorter and longer input; copy the longer one */
267 [ + + ]: 1577854 : if (a->nwords <= b->nwords)
268 : : {
269 : 1577853 : result = bms_copy(b);
270 : 1577853 : other = a;
271 : : }
272 : : else
273 : : {
8487 tgl@sss.pgh.pa.us 274 :GBC 1 : result = bms_copy(a);
275 : 1 : other = b;
276 : : }
277 : : /* And union the shorter input into the result */
8487 tgl@sss.pgh.pa.us 278 :CBC 1577854 : otherlen = other->nwords;
1036 drowley@postgresql.o 279 : 1577854 : i = 0;
280 : : do
281 : : {
8487 tgl@sss.pgh.pa.us 282 : 1579133 : result->words[i] |= other->words[i];
1036 drowley@postgresql.o 283 [ + + ]: 1579133 : } while (++i < otherlen);
8487 tgl@sss.pgh.pa.us 284 : 1577854 : 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 *
8306 bruce@momjian.us 292 : 3388582 : 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 : :
839 drowley@postgresql.o 300 [ - + ]: 3388582 : Assert(bms_is_valid_set(a));
301 [ - + ]: 3388582 : Assert(bms_is_valid_set(b));
302 : :
303 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 304 [ + + + + ]: 3388582 : if (a == NULL || b == NULL)
305 : 1934219 : return NULL;
306 : :
307 : : /* Identify shorter and longer input; copy the shorter one */
308 [ + + ]: 1454363 : if (a->nwords <= b->nwords)
309 : : {
310 : 1454362 : result = bms_copy(a);
311 : 1454362 : other = b;
312 : : }
313 : : else
314 : : {
8487 tgl@sss.pgh.pa.us 315 :GBC 1 : result = bms_copy(b);
316 : 1 : other = a;
317 : : }
318 : : /* And intersect the longer input with the result */
8487 tgl@sss.pgh.pa.us 319 :CBC 1454363 : resultlen = result->nwords;
1036 drowley@postgresql.o 320 : 1454363 : lastnonzero = -1;
321 : 1454363 : i = 0;
322 : : do
323 : : {
8487 tgl@sss.pgh.pa.us 324 : 1455642 : result->words[i] &= other->words[i];
325 : :
1036 drowley@postgresql.o 326 [ + + ]: 1455642 : if (result->words[i] != 0)
327 : 1434767 : lastnonzero = i;
328 [ + + ]: 1455642 : } while (++i < resultlen);
329 : : /* If we computed an empty result, we must return NULL */
330 [ + + ]: 1454363 : if (lastnonzero == -1)
331 : : {
1160 tgl@sss.pgh.pa.us 332 : 19710 : pfree(result);
333 : 19710 : return NULL;
334 : : }
335 : :
336 : : /* get rid of trailing zero words */
1036 drowley@postgresql.o 337 : 1434653 : result->nwords = lastnonzero + 1;
8487 tgl@sss.pgh.pa.us 338 : 1434653 : 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 *
8306 bruce@momjian.us 346 : 4221499 : bms_difference(const Bitmapset *a, const Bitmapset *b)
347 : : {
348 : : Bitmapset *result;
349 : : int i;
350 : :
839 drowley@postgresql.o 351 [ - + ]: 4221499 : Assert(bms_is_valid_set(a));
352 [ - + ]: 4221499 : Assert(bms_is_valid_set(b));
353 : :
354 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 355 [ + + ]: 4221499 : if (a == NULL)
356 : 2240472 : return NULL;
357 [ + + ]: 1981027 : if (b == NULL)
358 : 975071 : 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 : : */
1160 365 [ + + ]: 1005956 : if (!bms_nonempty_difference(a, b))
366 : 742858 : return NULL;
367 : :
368 : : /* Copy the left input */
8487 369 : 263098 : result = bms_copy(a);
370 : :
371 : : /* And remove b's bits from result */
1036 drowley@postgresql.o 372 [ + + ]: 263098 : 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 : : */
1036 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 : : {
1036 drowley@postgresql.o 386 :CBC 263096 : int lastnonzero = -1;
387 : :
388 : : /* we may need to remove trailing zero words from the result. */
389 : 263096 : i = 0;
390 : : do
391 : : {
392 : 263097 : result->words[i] &= ~b->words[i];
393 : :
394 : : /* remember the last non-zero word */
395 [ + + ]: 263097 : if (result->words[i] != 0)
396 : 263096 : lastnonzero = i;
397 [ + + ]: 263097 : } while (++i < result->nwords);
398 : :
399 : : /* trim off trailing zero words */
400 : 263096 : result->nwords = lastnonzero + 1;
401 : : }
402 [ - + ]: 263098 : Assert(result->nwords != 0);
403 : :
404 : : /* Need not check for empty result, since we handled that case above */
8487 tgl@sss.pgh.pa.us 405 : 263098 : return result;
406 : : }
407 : :
408 : : /*
409 : : * bms_is_subset - is A a subset of B?
410 : : */
411 : : bool
8306 bruce@momjian.us 412 : 22064804 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
413 : : {
414 : : int i;
415 : :
839 drowley@postgresql.o 416 [ - + ]: 22064804 : Assert(bms_is_valid_set(a));
417 [ - + ]: 22064804 : Assert(bms_is_valid_set(b));
418 : :
419 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 420 [ + + ]: 22064804 : if (a == NULL)
421 : 4901311 : return true; /* empty set is a subset of anything */
422 [ + + ]: 17163493 : if (b == NULL)
1160 423 : 317689 : return false;
424 : :
425 : : /* 'a' can't be a subset of 'b' if it contains more words */
1036 drowley@postgresql.o 426 [ + + ]: 16845804 : if (a->nwords > b->nwords)
1036 drowley@postgresql.o 427 :GBC 2 : return false;
428 : :
429 : : /* Check all 'a' members are set in 'b' */
1036 drowley@postgresql.o 430 :CBC 16845802 : i = 0;
431 : : do
432 : : {
8310 bruce@momjian.us 433 [ + + ]: 16845802 : if ((a->words[i] & ~b->words[i]) != 0)
8487 tgl@sss.pgh.pa.us 434 : 5736668 : return false;
1036 drowley@postgresql.o 435 [ - + ]: 11109134 : } while (++i < a->nwords);
8487 tgl@sss.pgh.pa.us 436 : 11109134 : 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
5212 445 : 2150003 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
446 : : {
447 : : BMS_Comparison result;
448 : : int shortlen;
449 : : int i;
450 : :
839 drowley@postgresql.o 451 [ - + ]: 2150003 : Assert(bms_is_valid_set(a));
452 [ - + ]: 2150003 : Assert(bms_is_valid_set(b));
453 : :
454 : : /* Handle cases where either input is NULL */
5212 tgl@sss.pgh.pa.us 455 [ + + ]: 2150003 : if (a == NULL)
456 : : {
457 [ + + ]: 1787171 : if (b == NULL)
458 : 1735229 : return BMS_EQUAL;
1160 459 : 51942 : return BMS_SUBSET1;
460 : : }
5212 461 [ + + ]: 362832 : if (b == NULL)
1160 462 : 184251 : return BMS_SUBSET2;
463 : :
464 : : /* Check common words */
5212 465 : 178581 : result = BMS_EQUAL; /* status so far */
466 : 178581 : shortlen = Min(a->nwords, b->nwords);
1036 drowley@postgresql.o 467 : 178581 : i = 0;
468 : : do
469 : : {
5077 bruce@momjian.us 470 : 178584 : bitmapword aword = a->words[i];
471 : 178584 : bitmapword bword = b->words[i];
472 : :
5212 tgl@sss.pgh.pa.us 473 [ + + ]: 178584 : if ((aword & ~bword) != 0)
474 : : {
475 : : /* a is not a subset of b */
476 [ + + ]: 48539 : if (result == BMS_SUBSET1)
5212 tgl@sss.pgh.pa.us 477 :GBC 2 : return BMS_DIFFERENT;
5212 tgl@sss.pgh.pa.us 478 :CBC 48537 : result = BMS_SUBSET2;
479 : : }
480 [ + + ]: 178582 : if ((bword & ~aword) != 0)
481 : : {
482 : : /* b is not a subset of a */
483 [ + + ]: 51286 : if (result == BMS_SUBSET2)
484 : 45165 : return BMS_DIFFERENT;
485 : 6121 : result = BMS_SUBSET1;
486 : : }
1036 drowley@postgresql.o 487 [ + + ]: 133417 : } while (++i < shortlen);
488 : : /* Check extra words */
5212 tgl@sss.pgh.pa.us 489 [ + + ]: 133414 : if (a->nwords > b->nwords)
490 : : {
491 : : /* if a has more words then a is not a subset of b */
1036 drowley@postgresql.o 492 [ + + ]:GBC 2 : if (result == BMS_SUBSET1)
493 : 1 : return BMS_DIFFERENT;
494 : 1 : return BMS_SUBSET2;
495 : : }
5212 tgl@sss.pgh.pa.us 496 [ + + ]:CBC 133412 : else if (a->nwords < b->nwords)
497 : : {
498 : : /* if b has more words then b is not a subset of a */
1036 drowley@postgresql.o 499 [ + + ]:GBC 4 : if (result == BMS_SUBSET2)
500 : 2 : return BMS_DIFFERENT;
501 : 2 : return BMS_SUBSET1;
502 : : }
5212 tgl@sss.pgh.pa.us 503 :CBC 133408 : return result;
504 : : }
505 : :
506 : : /*
507 : : * bms_is_member - is X a member of A?
508 : : */
509 : : bool
8306 bruce@momjian.us 510 : 12807563 : bms_is_member(int x, const Bitmapset *a)
511 : : {
512 : : int wordnum,
513 : : bitnum;
514 : :
839 drowley@postgresql.o 515 [ - + ]: 12807563 : Assert(bms_is_valid_set(a));
516 : :
517 : : /* XXX better to just return false for x<0 ? */
8487 tgl@sss.pgh.pa.us 518 [ + + ]: 12807563 : if (x < 0)
8323 tgl@sss.pgh.pa.us 519 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8487 tgl@sss.pgh.pa.us 520 [ + + ]:CBC 12807562 : if (a == NULL)
521 : 7312924 : return false;
522 : :
523 : 5494638 : wordnum = WORDNUM(x);
524 : 5494638 : bitnum = BITNUM(x);
525 [ + + ]: 5494638 : if (wordnum >= a->nwords)
526 : 418 : return false;
527 [ + + ]: 5494220 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528 : 3833020 : return true;
529 : 1661200 : 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
2596 tomas.vondra@postgre 539 : 4427 : bms_member_index(Bitmapset *a, int x)
540 : : {
541 : : int bitnum;
542 : : int wordnum;
543 : 4427 : int result = 0;
544 : : bitmapword mask;
545 : :
839 drowley@postgresql.o 546 [ - + ]: 4427 : Assert(bms_is_valid_set(a));
547 : :
548 : : /* return -1 if not a member of the bitmap */
2596 tomas.vondra@postgre 549 [ + + ]: 4427 : if (!bms_is_member(x, a))
2596 tomas.vondra@postgre 550 :GBC 2 : return -1;
551 : :
2596 tomas.vondra@postgre 552 :CBC 4425 : wordnum = WORDNUM(x);
553 : 4425 : bitnum = BITNUM(x);
554 : :
555 : : /* count bits in preceding words */
71 nathan@postgresql.or 556 :GNC 4425 : 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 : : */
2596 tomas.vondra@postgre 565 :CBC 4425 : mask = ((bitmapword) 1 << bitnum) - 1;
566 : 4425 : result += bmw_popcount(a->words[wordnum] & mask);
567 : :
568 : 4425 : return result;
569 : : }
570 : :
571 : : /*
572 : : * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
573 : : */
574 : : bool
8306 bruce@momjian.us 575 : 25364218 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
576 : : {
577 : : int shortlen;
578 : : int i;
579 : :
839 drowley@postgresql.o 580 [ - + ]: 25364218 : Assert(bms_is_valid_set(a));
581 [ - + ]: 25364218 : Assert(bms_is_valid_set(b));
582 : :
583 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 584 [ + + + + ]: 25364218 : if (a == NULL || b == NULL)
585 : 16898027 : return false;
586 : : /* Check words in common */
587 : 8466191 : shortlen = Min(a->nwords, b->nwords);
1036 drowley@postgresql.o 588 : 8466191 : i = 0;
589 : : do
590 : : {
8487 tgl@sss.pgh.pa.us 591 [ + + ]: 8466191 : if ((a->words[i] & b->words[i]) != 0)
592 : 5044492 : return true;
1036 drowley@postgresql.o 593 [ - + ]: 3421699 : } while (++i < shortlen);
8487 tgl@sss.pgh.pa.us 594 : 3421699 : return false;
595 : : }
596 : :
597 : : /*
598 : : * bms_overlap_list - does a set overlap an integer list?
599 : : */
600 : : bool
3326 rhodiumtoad@postgres 601 : 1529 : bms_overlap_list(const Bitmapset *a, const List *b)
602 : : {
603 : : ListCell *lc;
604 : : int wordnum,
605 : : bitnum;
606 : :
839 drowley@postgresql.o 607 [ - + ]: 1529 : Assert(bms_is_valid_set(a));
608 : :
3326 rhodiumtoad@postgres 609 [ + + + + ]: 1529 : if (a == NULL || b == NIL)
610 : 1412 : return false;
611 : :
612 [ + - + + : 219 : foreach(lc, b)
+ + ]
613 : : {
614 : 170 : int x = lfirst_int(lc);
615 : :
616 [ + + ]: 170 : if (x < 0)
3326 rhodiumtoad@postgres 617 [ + - ]:GBC 2 : elog(ERROR, "negative bitmapset member not allowed");
3326 rhodiumtoad@postgres 618 :CBC 168 : wordnum = WORDNUM(x);
619 : 168 : bitnum = BITNUM(x);
620 [ + - ]: 168 : if (wordnum < a->nwords)
621 [ + + ]: 168 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
622 : 66 : return true;
623 : : }
624 : :
625 : 49 : 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
8306 bruce@momjian.us 634 : 3017423 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
635 : : {
636 : : int i;
637 : :
839 drowley@postgresql.o 638 [ - + ]: 3017423 : Assert(bms_is_valid_set(a));
639 [ - + ]: 3017423 : Assert(bms_is_valid_set(b));
640 : :
641 : : /* Handle cases where either input is NULL */
8346 tgl@sss.pgh.pa.us 642 [ + + ]: 3017423 : if (a == NULL)
643 : 4246 : return false;
644 [ + + ]: 3013177 : if (b == NULL)
1160 tgl@sss.pgh.pa.us 645 :GBC 1 : return true;
646 : : /* if 'a' has more words then it must contain additional members */
1036 drowley@postgresql.o 647 [ + + ]:CBC 3013176 : if (a->nwords > b->nwords)
1036 drowley@postgresql.o 648 :GBC 3 : return true;
649 : : /* Check all 'a' members are set in 'b' */
1036 drowley@postgresql.o 650 :CBC 3013173 : i = 0;
651 : : do
652 : : {
8310 bruce@momjian.us 653 [ + + ]: 3013173 : if ((a->words[i] & ~b->words[i]) != 0)
8346 tgl@sss.pgh.pa.us 654 : 1375468 : return true;
1036 drowley@postgresql.o 655 [ - + ]: 1637705 : } while (++i < a->nwords);
8346 tgl@sss.pgh.pa.us 656 : 1637705 : 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
8306 bruce@momjian.us 665 : 17730 : bms_singleton_member(const Bitmapset *a)
666 : : {
8310 667 : 17730 : int result = -1;
668 : : int nwords;
669 : : int wordnum;
670 : :
839 drowley@postgresql.o 671 [ - + ]: 17730 : Assert(bms_is_valid_set(a));
672 : :
8487 tgl@sss.pgh.pa.us 673 [ + + ]: 17730 : if (a == NULL)
8323 tgl@sss.pgh.pa.us 674 [ + - ]:GBC 1 : elog(ERROR, "bitmapset is empty");
675 : :
8487 tgl@sss.pgh.pa.us 676 :CBC 17729 : nwords = a->nwords;
1036 drowley@postgresql.o 677 : 17729 : wordnum = 0;
678 : : do
679 : : {
8487 tgl@sss.pgh.pa.us 680 : 17729 : bitmapword w = a->words[wordnum];
681 : :
682 [ + - ]: 17729 : if (w != 0)
683 : : {
684 [ + - + + ]: 17729 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
8323 tgl@sss.pgh.pa.us 685 [ + - ]:GBC 1 : elog(ERROR, "bitmapset has multiple members");
8487 tgl@sss.pgh.pa.us 686 :CBC 17728 : result = wordnum * BITS_PER_BITMAPWORD;
2636 687 : 17728 : result += bmw_rightmost_one_pos(w);
688 : : }
1036 drowley@postgresql.o 689 [ - + ]: 17728 : } while (++wordnum < nwords);
690 : :
691 : : /* we don't expect non-NULL sets to be empty */
692 [ - + ]: 17728 : Assert(result >= 0);
8487 tgl@sss.pgh.pa.us 693 : 17728 : 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
4176 708 : 2144881 : bms_get_singleton_member(const Bitmapset *a, int *member)
709 : : {
710 : 2144881 : int result = -1;
711 : : int nwords;
712 : : int wordnum;
713 : :
839 drowley@postgresql.o 714 [ - + ]: 2144881 : Assert(bms_is_valid_set(a));
715 : :
4176 tgl@sss.pgh.pa.us 716 [ + + ]: 2144881 : if (a == NULL)
4176 tgl@sss.pgh.pa.us 717 :GBC 2 : return false;
718 : :
4176 tgl@sss.pgh.pa.us 719 :CBC 2144879 : nwords = a->nwords;
1036 drowley@postgresql.o 720 : 2144879 : wordnum = 0;
721 : : do
722 : : {
4176 tgl@sss.pgh.pa.us 723 : 2144885 : bitmapword w = a->words[wordnum];
724 : :
725 [ + + ]: 2144885 : if (w != 0)
726 : : {
727 [ + - + + ]: 2144879 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
728 : 400116 : return false;
729 : 1744763 : result = wordnum * BITS_PER_BITMAPWORD;
2636 730 : 1744763 : result += bmw_rightmost_one_pos(w);
731 : : }
1036 drowley@postgresql.o 732 [ + + ]: 1744769 : } while (++wordnum < nwords);
733 : :
734 : : /* we don't expect non-NULL sets to be empty */
735 [ - + ]: 1744763 : Assert(result >= 0);
4176 tgl@sss.pgh.pa.us 736 : 1744763 : *member = result;
737 : 1744763 : return true;
738 : : }
739 : :
740 : : /*
741 : : * bms_num_members - count members of set
742 : : */
743 : : int
8306 bruce@momjian.us 744 : 2010282 : bms_num_members(const Bitmapset *a)
745 : : {
839 drowley@postgresql.o 746 [ - + ]: 2010282 : Assert(bms_is_valid_set(a));
747 : :
8487 tgl@sss.pgh.pa.us 748 [ + + ]: 2010282 : if (a == NULL)
749 : 277782 : return 0;
750 : :
751 : : /* fast-path for common case */
71 nathan@postgresql.or 752 [ + + ]:GNC 1732500 : if (a->nwords == 1)
753 : 1732114 : return bmw_popcount(a->words[0]);
754 : :
755 : 386 : return pg_popcount((const char *) a->words,
756 : 386 : 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
8306 bruce@momjian.us 765 :CBC 1663963 : bms_membership(const Bitmapset *a)
766 : : {
8487 tgl@sss.pgh.pa.us 767 : 1663963 : BMS_Membership result = BMS_EMPTY_SET;
768 : : int nwords;
769 : : int wordnum;
770 : :
839 drowley@postgresql.o 771 [ - + ]: 1663963 : Assert(bms_is_valid_set(a));
772 : :
8487 tgl@sss.pgh.pa.us 773 [ + + ]: 1663963 : if (a == NULL)
774 : 413 : return BMS_EMPTY_SET;
775 : :
776 : 1663550 : nwords = a->nwords;
1036 drowley@postgresql.o 777 : 1663550 : wordnum = 0;
778 : : do
779 : : {
8487 tgl@sss.pgh.pa.us 780 : 1663666 : bitmapword w = a->words[wordnum];
781 : :
782 [ + + ]: 1663666 : if (w != 0)
783 : : {
784 [ + - + + ]: 1663550 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
785 : 601131 : return BMS_MULTIPLE;
786 : 1062419 : result = BMS_SINGLETON;
787 : : }
1036 drowley@postgresql.o 788 [ + + ]: 1062535 : } while (++wordnum < nwords);
8487 tgl@sss.pgh.pa.us 789 : 1062419 : 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 *
8306 bruce@momjian.us 799 : 17709871 : bms_add_member(Bitmapset *a, int x)
800 : : {
801 : : int wordnum,
802 : : bitnum;
803 : :
839 drowley@postgresql.o 804 [ - + ]: 17709871 : Assert(bms_is_valid_set(a));
805 : :
8487 tgl@sss.pgh.pa.us 806 [ + + ]: 17709871 : if (x < 0)
8323 tgl@sss.pgh.pa.us 807 [ + - ]:GBC 2 : elog(ERROR, "negative bitmapset member not allowed");
8487 tgl@sss.pgh.pa.us 808 [ + + ]:CBC 17709869 : if (a == NULL)
809 : 9609260 : return bms_make_singleton(x);
810 : :
811 : 8100609 : wordnum = WORDNUM(x);
812 : 8100609 : bitnum = BITNUM(x);
813 : :
814 : : /* enlarge the set if necessary */
815 [ + + ]: 8100609 : if (wordnum >= a->nwords)
816 : : {
4600 heikki.linnakangas@i 817 : 492 : int oldnwords = a->nwords;
818 : : int i;
819 : :
820 : 492 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
821 : 492 : a->nwords = wordnum + 1;
822 : : /* zero out the enlarged portion */
1036 drowley@postgresql.o 823 : 492 : i = oldnwords;
824 : : do
825 : : {
4600 heikki.linnakangas@i 826 : 51436 : a->words[i] = 0;
1036 drowley@postgresql.o 827 [ + + ]: 51436 : } while (++i < a->nwords);
828 : : }
829 : :
839 830 : 8100609 : 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 : :
8487 tgl@sss.pgh.pa.us 841 : 8100609 : 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 *
8306 bruce@momjian.us 852 : 1501776 : bms_del_member(Bitmapset *a, int x)
853 : : {
854 : : int wordnum,
855 : : bitnum;
856 : :
839 drowley@postgresql.o 857 [ - + ]: 1501776 : Assert(bms_is_valid_set(a));
858 : :
8487 tgl@sss.pgh.pa.us 859 [ + + ]: 1501776 : if (x < 0)
8323 tgl@sss.pgh.pa.us 860 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8487 tgl@sss.pgh.pa.us 861 [ + + ]:CBC 1501775 : if (a == NULL)
862 : 546761 : return NULL;
863 : :
864 : 955014 : wordnum = WORDNUM(x);
865 : 955014 : 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 */
1036 drowley@postgresql.o 872 [ - + ]: 955014 : if (unlikely(wordnum >= a->nwords))
1036 drowley@postgresql.o 873 :UBC 0 : return a;
874 : :
1036 drowley@postgresql.o 875 :CBC 955014 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
876 : :
877 : : /* when last word becomes empty, trim off all trailing empty words */
878 [ + + + + ]: 955014 : 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 [ + + ]: 553980 : for (int i = wordnum - 1; i >= 0; i--)
882 : : {
1036 drowley@postgresql.o 883 [ + + ]:GBC 109857 : if (a->words[i] != 0)
884 : : {
885 : 272 : a->nwords = i + 1;
886 : 272 : return a;
887 : : }
888 : : }
889 : :
890 : : /* the set is now empty */
1160 tgl@sss.pgh.pa.us 891 :CBC 444123 : pfree(a);
892 : 444123 : return NULL;
893 : : }
8487 894 : 510619 : return a;
895 : : }
896 : :
897 : : /*
898 : : * bms_add_members - like bms_union, but left input is recycled when possible
899 : : */
900 : : Bitmapset *
8306 bruce@momjian.us 901 : 19922628 : bms_add_members(Bitmapset *a, const Bitmapset *b)
902 : : {
903 : : Bitmapset *result;
904 : : const Bitmapset *other;
905 : : int otherlen;
906 : : int i;
907 : :
839 drowley@postgresql.o 908 [ - + ]: 19922628 : Assert(bms_is_valid_set(a));
909 [ - + ]: 19922628 : Assert(bms_is_valid_set(b));
910 : :
911 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 912 [ + + ]: 19922628 : if (a == NULL)
913 : 14284922 : return bms_copy(b);
914 [ + + ]: 5637706 : if (b == NULL)
915 : : {
916 : : #ifdef REALLOCATE_BITMAPSETS
917 : : a = bms_copy_and_free(a);
918 : : #endif
919 : :
920 : 3568218 : return a;
921 : : }
922 : : /* Identify shorter and longer input; copy the longer one if needed */
923 [ + + ]: 2069488 : if (a->nwords < b->nwords)
924 : : {
8487 tgl@sss.pgh.pa.us 925 :GBC 17 : result = bms_copy(b);
926 : 17 : other = a;
927 : : }
928 : : else
929 : : {
8487 tgl@sss.pgh.pa.us 930 :CBC 2069471 : result = a;
931 : 2069471 : other = b;
932 : : }
933 : : /* And union the shorter input into the result */
934 : 2069488 : otherlen = other->nwords;
1036 drowley@postgresql.o 935 : 2069488 : i = 0;
936 : : do
937 : : {
8487 tgl@sss.pgh.pa.us 938 : 2070124 : result->words[i] |= other->words[i];
1036 drowley@postgresql.o 939 [ + + ]: 2070124 : } while (++i < otherlen);
8487 tgl@sss.pgh.pa.us 940 [ + + ]: 2069488 : if (result != a)
8487 tgl@sss.pgh.pa.us 941 :GBC 17 : pfree(a);
942 : : #ifdef REALLOCATE_BITMAPSETS
943 : : else
944 : : result = bms_copy_and_free(result);
945 : : #endif
946 : :
8487 tgl@sss.pgh.pa.us 947 :CBC 2069488 : 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 *
837 drowley@postgresql.o 956 : 11241 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
957 : : {
958 : : int i;
959 : :
960 [ - + ]: 11241 : Assert(bms_is_valid_set(a));
961 [ - + ]: 11241 : Assert(bms_is_valid_set(b));
962 : :
963 [ + + ]: 11241 : if (a == NULL)
837 drowley@postgresql.o 964 :GBC 1 : return bms_copy(b);
837 drowley@postgresql.o 965 [ + + ]:CBC 11240 : if (b == NULL)
966 : : {
837 drowley@postgresql.o 967 :GBC 1 : pfree(a);
968 : 1 : return NULL;
969 : : }
970 : :
837 drowley@postgresql.o 971 [ + + ]:CBC 11239 : if (a->nwords < b->nwords)
837 drowley@postgresql.o 972 :GBC 1 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
973 : :
837 drowley@postgresql.o 974 :CBC 11239 : i = 0;
975 : : do
976 : : {
977 : 11248 : a->words[i] = b->words[i];
978 [ + + ]: 11248 : } while (++i < b->nwords);
979 : :
980 : 11239 : 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 : 11239 : 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 *
3079 rhaas@postgresql.org 1003 : 44887 : bms_add_range(Bitmapset *a, int lower, int upper)
1004 : : {
1005 : : int lwordnum,
1006 : : lbitnum,
1007 : : uwordnum,
1008 : : ushiftbits,
1009 : : wordnum;
1010 : :
839 drowley@postgresql.o 1011 [ - + ]: 44887 : Assert(bms_is_valid_set(a));
1012 : :
1013 : : /* do nothing if nothing is called for, without further checking */
2836 alvherre@alvh.no-ip. 1014 [ + + ]: 44887 : if (upper < lower)
1015 : : {
1016 : : #ifdef REALLOCATE_BITMAPSETS
1017 : : a = bms_copy_and_free(a);
1018 : : #endif
1019 : :
1020 : 23 : return a;
1021 : : }
1022 : :
tgl@sss.pgh.pa.us 1023 [ + + ]: 44864 : if (lower < 0)
3079 rhaas@postgresql.org 1024 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
3079 rhaas@postgresql.org 1025 :CBC 44863 : uwordnum = WORDNUM(upper);
1026 : :
1027 [ + + ]: 44863 : if (a == NULL)
1028 : : {
1029 : 34833 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1269 tgl@sss.pgh.pa.us 1030 : 34833 : a->type = T_Bitmapset;
3079 rhaas@postgresql.org 1031 : 34833 : a->nwords = uwordnum + 1;
1032 : : }
1033 [ + + ]: 10030 : else if (uwordnum >= a->nwords)
1034 : : {
3079 rhaas@postgresql.org 1035 :GBC 2 : int oldnwords = a->nwords;
1036 : : int i;
1037 : :
1038 : : /* ensure we have enough words to store the upper bit */
1039 : 2 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1040 : 2 : a->nwords = uwordnum + 1;
1041 : : /* zero out the enlarged portion */
1036 drowley@postgresql.o 1042 : 2 : i = oldnwords;
1043 : : do
1044 : : {
3079 rhaas@postgresql.org 1045 : 4 : a->words[i] = 0;
1036 drowley@postgresql.o 1046 [ + + ]: 4 : } while (++i < a->nwords);
1047 : : }
1048 : :
3079 rhaas@postgresql.org 1049 :CBC 44863 : wordnum = lwordnum = WORDNUM(lower);
1050 : :
1051 : 44863 : lbitnum = BITNUM(lower);
1052 : 44863 : 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 [ + + ]: 44863 : if (lwordnum == uwordnum)
1059 : : {
1060 : 43862 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
3038 tgl@sss.pgh.pa.us 1061 : 43862 : & (~(bitmapword) 0) >> ushiftbits;
1062 : : }
1063 : : else
1064 : : {
1065 : : /* turn on lbitnum and all bits left of it */
3079 rhaas@postgresql.org 1066 :GBC 1001 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1067 : :
1068 : : /* turn on all bits for any intermediate words */
1069 [ + + ]: 1036 : while (wordnum < uwordnum)
1070 : 35 : a->words[wordnum++] = ~(bitmapword) 0;
1071 : :
1072 : : /* turn on upper's bit and all bits right of it. */
1073 : 1001 : 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 : :
3079 rhaas@postgresql.org 1085 :CBC 44863 : return a;
1086 : : }
1087 : :
1088 : : /*
1089 : : * bms_int_members - like bms_intersect, but left input is recycled when
1090 : : * possible
1091 : : */
1092 : : Bitmapset *
8306 bruce@momjian.us 1093 : 623113 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1094 : : {
1095 : : int lastnonzero;
1096 : : int shortlen;
1097 : : int i;
1098 : :
839 drowley@postgresql.o 1099 [ - + ]: 623113 : Assert(bms_is_valid_set(a));
1100 [ - + ]: 623113 : Assert(bms_is_valid_set(b));
1101 : :
1102 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 1103 [ + + ]: 623113 : if (a == NULL)
1104 : 19509 : return NULL;
1105 [ + + ]: 603604 : if (b == NULL)
1106 : : {
1107 : 3351 : pfree(a);
1108 : 3351 : return NULL;
1109 : : }
1110 : :
1111 : : /* Intersect b into a; we need never copy */
1112 : 600253 : shortlen = Min(a->nwords, b->nwords);
1036 drowley@postgresql.o 1113 : 600253 : lastnonzero = -1;
1114 : 600253 : i = 0;
1115 : : do
1116 : : {
8487 tgl@sss.pgh.pa.us 1117 : 600254 : a->words[i] &= b->words[i];
1118 : :
1036 drowley@postgresql.o 1119 [ + + ]: 600254 : if (a->words[i] != 0)
1120 : 506248 : lastnonzero = i;
1121 [ + + ]: 600254 : } while (++i < shortlen);
1122 : :
1123 : : /* If we computed an empty result, we must return NULL */
1124 [ + + ]: 600253 : if (lastnonzero == -1)
1125 : : {
1160 tgl@sss.pgh.pa.us 1126 : 94006 : pfree(a);
1127 : 94006 : return NULL;
1128 : : }
1129 : :
1130 : : /* get rid of trailing zero words */
1036 drowley@postgresql.o 1131 : 506247 : a->nwords = lastnonzero + 1;
1132 : :
1133 : : #ifdef REALLOCATE_BITMAPSETS
1134 : : a = bms_copy_and_free(a);
1135 : : #endif
1136 : :
8487 tgl@sss.pgh.pa.us 1137 : 506247 : 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 *
8306 bruce@momjian.us 1145 : 1800431 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1146 : : {
1147 : : int i;
1148 : :
839 drowley@postgresql.o 1149 [ - + ]: 1800431 : Assert(bms_is_valid_set(a));
1150 [ - + ]: 1800431 : Assert(bms_is_valid_set(b));
1151 : :
1152 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 1153 [ + + ]: 1800431 : if (a == NULL)
1154 : 780927 : return NULL;
1155 [ + + ]: 1019504 : if (b == NULL)
1156 : : {
1157 : : #ifdef REALLOCATE_BITMAPSETS
1158 : : a = bms_copy_and_free(a);
1159 : : #endif
1160 : :
839 drowley@postgresql.o 1161 : 160813 : return a;
1162 : : }
1163 : :
1164 : : /* Remove b's bits from a; we need never copy */
1036 1165 [ + + ]: 858691 : 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 : : */
1036 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 : : {
1036 drowley@postgresql.o 1179 :CBC 858690 : int lastnonzero = -1;
1180 : :
1181 : : /* we may need to remove trailing zero words from the result. */
1182 : 858690 : i = 0;
1183 : : do
1184 : : {
1185 : 858698 : a->words[i] &= ~b->words[i];
1186 : :
1187 : : /* remember the last non-zero word */
1188 [ + + ]: 858698 : if (a->words[i] != 0)
1189 : 195824 : lastnonzero = i;
1190 [ + + ]: 858698 : } while (++i < a->nwords);
1191 : :
1192 : : /* check if 'a' has become empty */
1193 [ + + ]: 858690 : if (lastnonzero == -1)
1194 : : {
1195 : 662868 : pfree(a);
1196 : 662868 : return NULL;
1197 : : }
1198 : :
1199 : : /* trim off any trailing zero words */
1200 : 195822 : a->nwords = lastnonzero + 1;
1201 : : }
1202 : :
1203 : : #ifdef REALLOCATE_BITMAPSETS
1204 : : a = bms_copy_and_free(a);
1205 : : #endif
1206 : :
8487 tgl@sss.pgh.pa.us 1207 : 195823 : return a;
1208 : : }
1209 : :
1210 : : /*
1211 : : * bms_join - like bms_union, but *either* input *may* be recycled
1212 : : */
1213 : : Bitmapset *
8306 bruce@momjian.us 1214 : 1337224 : bms_join(Bitmapset *a, Bitmapset *b)
1215 : : {
1216 : : Bitmapset *result;
1217 : : Bitmapset *other;
1218 : : int otherlen;
1219 : : int i;
1220 : :
839 drowley@postgresql.o 1221 [ - + ]: 1337224 : Assert(bms_is_valid_set(a));
1222 [ - + ]: 1337224 : Assert(bms_is_valid_set(b));
1223 : :
1224 : : /* Handle cases where either input is NULL */
8487 tgl@sss.pgh.pa.us 1225 [ + + ]: 1337224 : if (a == NULL)
1226 : : {
1227 : : #ifdef REALLOCATE_BITMAPSETS
1228 : : b = bms_copy_and_free(b);
1229 : : #endif
1230 : :
1231 : 528717 : return b;
1232 : : }
1233 [ + + ]: 808507 : if (b == NULL)
1234 : : {
1235 : : #ifdef REALLOCATE_BITMAPSETS
1236 : : a = bms_copy_and_free(a);
1237 : : #endif
1238 : :
839 drowley@postgresql.o 1239 : 146870 : return a;
1240 : : }
1241 : :
1242 : : /* Identify shorter and longer input; use longer one as result */
8487 tgl@sss.pgh.pa.us 1243 [ + + ]: 661637 : if (a->nwords < b->nwords)
1244 : : {
8487 tgl@sss.pgh.pa.us 1245 :GBC 2 : result = b;
1246 : 2 : other = a;
1247 : : }
1248 : : else
1249 : : {
8487 tgl@sss.pgh.pa.us 1250 :CBC 661635 : result = a;
1251 : 661635 : other = b;
1252 : : }
1253 : : /* And union the shorter input into the result */
1254 : 661637 : otherlen = other->nwords;
1036 drowley@postgresql.o 1255 : 661637 : i = 0;
1256 : : do
1257 : : {
8487 tgl@sss.pgh.pa.us 1258 : 661637 : result->words[i] |= other->words[i];
1036 drowley@postgresql.o 1259 [ - + ]: 661637 : } while (++i < otherlen);
8487 tgl@sss.pgh.pa.us 1260 [ + - ]: 661637 : if (other != result) /* pure paranoia */
1261 : 661637 : pfree(other);
1262 : :
1263 : : #ifdef REALLOCATE_BITMAPSETS
1264 : : result = bms_copy_and_free(result);
1265 : : #endif
1266 : :
1267 : 661637 : 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
4176 1290 : 22693864 : bms_next_member(const Bitmapset *a, int prevbit)
1291 : : {
22 drowley@postgresql.o 1292 :GNC 22693864 : unsigned int currbit = prevbit;
1293 : : int nwords;
1294 : : bitmapword mask;
1295 : :
839 drowley@postgresql.o 1296 [ - + ]:CBC 22693864 : Assert(bms_is_valid_set(a));
1297 : :
4176 tgl@sss.pgh.pa.us 1298 [ + + ]: 22693864 : if (a == NULL)
1299 : 6431321 : return -2;
1300 : 16262543 : nwords = a->nwords;
1301 : :
1302 : : /* use an unsigned int to avoid the risk that int overflows */
22 drowley@postgresql.o 1303 :GNC 16262543 : currbit++;
1304 : 16262543 : mask = (~(bitmapword) 0) << BITNUM(currbit);
1305 [ + + ]: 21697800 : for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
1306 : : {
4176 tgl@sss.pgh.pa.us 1307 :CBC 16264680 : bitmapword w = a->words[wordnum];
1308 : :
1309 : : /* ignore bits before currbit */
1310 : 16264680 : w &= mask;
1311 : :
1312 [ + + ]: 16264680 : if (w != 0)
1313 : : {
1314 : : int result;
1315 : :
1316 : 10829423 : result = wordnum * BITS_PER_BITMAPWORD;
2636 1317 : 10829423 : result += bmw_rightmost_one_pos(w);
4176 1318 : 10829423 : return result;
1319 : : }
1320 : :
1321 : : /* in subsequent words, consider all bits */
1322 : 5435257 : mask = (~(bitmapword) 0);
1323 : : }
1324 : 5433120 : return -2;
1325 : : }
1326 : :
1327 : : /*
1328 : : * bms_prev_member - find prev member of a set
1329 : : *
1330 : : * Returns largest member less than "prevbit", or -2 if there is none.
1331 : : * "prevbit" must NOT be more than one above the highest possible bit that can
1332 : : * be set in the Bitmapset at its current size.
1333 : : *
1334 : : * To ease finding the highest set bit for the initial loop, the special
1335 : : * prevbit value of -1 can be passed to have the function find the highest
1336 : : * valued member in the set.
1337 : : *
1338 : : * This is intended as support for iterating through the members of a set in
1339 : : * reverse. The typical pattern is
1340 : : *
1341 : : * x = -1;
1342 : : * while ((x = bms_prev_member(inputset, x)) >= 0)
1343 : : * process member x;
1344 : : *
1345 : : * Notice that when there are no more members, we return -2, not -1 as you
1346 : : * might expect. The rationale for that is to allow distinguishing the
1347 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1348 : : * It makes no difference in simple loop usage, but complex iteration logic
1349 : : * might need such an ability.
1350 : : */
1351 : : int
2950 alvherre@alvh.no-ip. 1352 : 18 : bms_prev_member(const Bitmapset *a, int prevbit)
1353 : : {
1354 : : unsigned int currbit;
1355 : : int ushiftbits;
1356 : : bitmapword mask;
1357 : :
839 drowley@postgresql.o 1358 [ - + ]: 18 : Assert(bms_is_valid_set(a));
1359 : :
1360 : : /*
1361 : : * If set is NULL or if there are no more bits to the right then we've
1362 : : * nothing to do.
1363 : : */
2950 alvherre@alvh.no-ip. 1364 [ + + - + ]: 18 : if (a == NULL || prevbit == 0)
2950 alvherre@alvh.no-ip. 1365 :GBC 2 : return -2;
1366 : :
1367 : : /* Validate callers didn't give us something out of range */
22 drowley@postgresql.o 1368 [ + + - + ]:GNC 16 : Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD));
1369 : :
1370 : : /*
1371 : : * Transform -1 (or any negative number) to the highest possible bit we
1372 : : * could have set. We do this in unsigned math to avoid the risk of
1373 : : * overflowing a signed int.
1374 : : */
1375 [ + + ]: 16 : if (prevbit < 0)
1376 : 1 : currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
1377 : : else
1378 : 15 : currbit = prevbit - 1;
1379 : :
1380 : 16 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
2950 alvherre@alvh.no-ip. 1381 :CBC 16 : mask = (~(bitmapword) 0) >> ushiftbits;
22 drowley@postgresql.o 1382 [ + + ]:GNC 21 : for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
1383 : : {
2950 alvherre@alvh.no-ip. 1384 :CBC 16 : bitmapword w = a->words[wordnum];
1385 : :
1386 : : /* mask out bits left of currbit */
1387 : 16 : w &= mask;
1388 : :
1389 [ + + ]: 16 : if (w != 0)
1390 : : {
1391 : : int result;
1392 : :
1393 : 11 : result = wordnum * BITS_PER_BITMAPWORD;
2636 tgl@sss.pgh.pa.us 1394 : 11 : result += bmw_leftmost_one_pos(w);
2950 alvherre@alvh.no-ip. 1395 : 11 : return result;
1396 : : }
1397 : :
1398 : : /* in subsequent words, consider all bits */
1399 : 5 : mask = (~(bitmapword) 0);
1400 : : }
1401 : 5 : return -2;
1402 : : }
1403 : :
1404 : : /*
1405 : : * bms_hash_value - compute a hash key for a Bitmapset
1406 : : */
1407 : : uint32
7636 tgl@sss.pgh.pa.us 1408 : 5121 : bms_hash_value(const Bitmapset *a)
1409 : : {
839 drowley@postgresql.o 1410 [ - + ]: 5121 : Assert(bms_is_valid_set(a));
1411 : :
6913 tgl@sss.pgh.pa.us 1412 [ + + ]: 5121 : if (a == NULL)
7636 tgl@sss.pgh.pa.us 1413 :GBC 4 : return 0; /* All empty sets hash to 0 */
6913 tgl@sss.pgh.pa.us 1414 :CBC 5117 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1036 drowley@postgresql.o 1415 : 5117 : a->nwords * sizeof(bitmapword)));
1416 : : }
1417 : :
1418 : : /*
1419 : : * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
1420 : : *
1421 : : * Note: don't forget to specify bitmap_match as the match function!
1422 : : */
1423 : : uint32
2262 rhaas@postgresql.org 1424 : 5114 : bitmap_hash(const void *key, Size keysize)
1425 : : {
1426 [ - + ]: 5114 : Assert(keysize == sizeof(Bitmapset *));
1427 : 5114 : return bms_hash_value(*((const Bitmapset *const *) key));
1428 : : }
1429 : :
1430 : : /*
1431 : : * bitmap_match - match function to use with bitmap_hash
1432 : : */
1433 : : int
1434 : 2885 : bitmap_match(const void *key1, const void *key2, Size keysize)
1435 : : {
1436 [ - + ]: 2885 : Assert(keysize == sizeof(Bitmapset *));
1437 : 2885 : return !bms_equal(*((const Bitmapset *const *) key1),
1438 : : *((const Bitmapset *const *) key2));
1439 : : }
|
