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
864 drowley@postgresql.o 79 :CBC 303075523 : bms_is_valid_set(const Bitmapset *a)
80 : : {
81 : : /* NULL is the correct representation of an empty set */
82 [ + + ]: 303075523 : if (a == NULL)
83 : 142090123 : return true;
84 : :
85 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
86 [ - + ]: 160985400 : if (!IsA(a, Bitmapset))
864 drowley@postgresql.o 87 :UBC 0 : return false;
88 : :
89 : : /* trailing zero words are not allowed */
864 drowley@postgresql.o 90 [ - + ]:CBC 160985400 : if (a->words[a->nwords - 1] == 0)
864 drowley@postgresql.o 91 :UBC 0 : return false;
92 : :
864 drowley@postgresql.o 93 :CBC 160985400 : 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 *
8331 bruce@momjian.us 122 : 38477150 : bms_copy(const Bitmapset *a)
123 : : {
124 : : Bitmapset *result;
125 : : size_t size;
126 : :
864 drowley@postgresql.o 127 [ - + ]: 38477150 : Assert(bms_is_valid_set(a));
128 : :
8512 tgl@sss.pgh.pa.us 129 [ + + ]: 38477150 : if (a == NULL)
130 : 24974280 : return NULL;
131 : :
132 : 13502870 : size = BITMAPSET_SIZE(a->nwords);
133 : 13502870 : result = (Bitmapset *) palloc(size);
134 : 13502870 : memcpy(result, a, size);
135 : 13502870 : return result;
136 : : }
137 : :
138 : : /*
139 : : * bms_equal - are two bitmapsets equal? or both NULL?
140 : : */
141 : : bool
8331 bruce@momjian.us 142 : 11082857 : bms_equal(const Bitmapset *a, const Bitmapset *b)
143 : : {
144 : : int i;
145 : :
864 drowley@postgresql.o 146 [ - + ]: 11082857 : Assert(bms_is_valid_set(a));
147 [ - + ]: 11082857 : Assert(bms_is_valid_set(b));
148 : :
149 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 150 [ + + ]: 11082857 : if (a == NULL)
151 : : {
152 [ + + ]: 6444680 : if (b == NULL)
153 : 6392980 : return true;
1185 154 : 51700 : return false;
155 : : }
8512 156 [ + + ]: 4638177 : else if (b == NULL)
1185 157 : 21404 : return false;
158 : :
159 : : /* can't be equal if the word counts don't match */
1061 drowley@postgresql.o 160 [ + + ]: 4616773 : if (a->nwords != b->nwords)
1061 drowley@postgresql.o 161 :GBC 5896 : return false;
162 : :
163 : : /* check each word matches */
1061 drowley@postgresql.o 164 :CBC 4610877 : i = 0;
165 : : do
166 : : {
167 [ + + ]: 4613215 : if (a->words[i] != b->words[i])
8512 tgl@sss.pgh.pa.us 168 : 2659608 : return false;
1061 drowley@postgresql.o 169 [ + + ]: 1953607 : } while (++i < a->nwords);
170 : :
8512 tgl@sss.pgh.pa.us 171 : 1951269 : 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
3063 183 : 23186 : bms_compare(const Bitmapset *a, const Bitmapset *b)
184 : : {
185 : : int i;
186 : :
864 drowley@postgresql.o 187 [ - + ]: 23186 : Assert(bms_is_valid_set(a));
188 [ - + ]: 23186 : Assert(bms_is_valid_set(b));
189 : :
190 : : /* Handle cases where either input is NULL */
3063 tgl@sss.pgh.pa.us 191 [ + + ]: 23186 : if (a == NULL)
1185 tgl@sss.pgh.pa.us 192 [ + + ]:GBC 4 : return (b == NULL) ? 0 : -1;
3063 tgl@sss.pgh.pa.us 193 [ + + ]:CBC 23182 : else if (b == NULL)
1185 tgl@sss.pgh.pa.us 194 :GBC 2 : return +1;
195 : :
196 : : /* the set with the most words must be greater */
1061 drowley@postgresql.o 197 [ + + ]:CBC 23180 : if (a->nwords != b->nwords)
1061 drowley@postgresql.o 198 [ - + ]:GBC 21 : return (a->nwords > b->nwords) ? +1 : -1;
199 : :
1061 drowley@postgresql.o 200 :CBC 23159 : i = a->nwords - 1;
201 : : do
202 : : {
3063 tgl@sss.pgh.pa.us 203 : 23159 : bitmapword aw = a->words[i];
204 : 23159 : bitmapword bw = b->words[i];
205 : :
206 [ + + ]: 23159 : if (aw != bw)
207 [ + + ]: 23158 : return (aw > bw) ? +1 : -1;
1061 drowley@postgresql.o 208 [ - + ]:GBC 1 : } while (--i >= 0);
3063 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 *
8512 tgl@sss.pgh.pa.us 216 :CBC 13102042 : bms_make_singleton(int x)
217 : : {
218 : : Bitmapset *result;
219 : : int wordnum,
220 : : bitnum;
221 : :
222 [ + + ]: 13102042 : if (x < 0)
8348 tgl@sss.pgh.pa.us 223 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8512 tgl@sss.pgh.pa.us 224 :CBC 13102041 : wordnum = WORDNUM(x);
225 : 13102041 : bitnum = BITNUM(x);
226 : 13102041 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
1294 227 : 13102041 : result->type = T_Bitmapset;
8512 228 : 13102041 : result->nwords = wordnum + 1;
229 : 13102041 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
230 : 13102041 : return result;
231 : : }
232 : :
233 : : /*
234 : : * bms_free - free a bitmapset
235 : : *
236 : : * Same as pfree except for allowing NULL input
237 : : */
238 : : void
8331 bruce@momjian.us 239 : 32183224 : bms_free(Bitmapset *a)
240 : : {
8512 tgl@sss.pgh.pa.us 241 [ + + ]: 32183224 : if (a)
242 : 7566425 : pfree(a);
243 : 32183224 : }
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 *
8331 bruce@momjian.us 251 : 6790461 : bms_union(const Bitmapset *a, const Bitmapset *b)
252 : : {
253 : : Bitmapset *result;
254 : : const Bitmapset *other;
255 : : int otherlen;
256 : : int i;
257 : :
864 drowley@postgresql.o 258 [ - + ]: 6790461 : Assert(bms_is_valid_set(a));
259 [ - + ]: 6790461 : Assert(bms_is_valid_set(b));
260 : :
261 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 262 [ + + ]: 6790461 : if (a == NULL)
263 : 4188092 : return bms_copy(b);
264 [ + + ]: 2602369 : if (b == NULL)
265 : 1021865 : return bms_copy(a);
266 : : /* Identify shorter and longer input; copy the longer one */
267 [ + + ]: 1580504 : if (a->nwords <= b->nwords)
268 : : {
269 : 1580503 : result = bms_copy(b);
270 : 1580503 : other = a;
271 : : }
272 : : else
273 : : {
8512 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 */
8512 tgl@sss.pgh.pa.us 278 :CBC 1580504 : otherlen = other->nwords;
1061 drowley@postgresql.o 279 : 1580504 : i = 0;
280 : : do
281 : : {
8512 tgl@sss.pgh.pa.us 282 : 1581783 : result->words[i] |= other->words[i];
1061 drowley@postgresql.o 283 [ + + ]: 1581783 : } while (++i < otherlen);
8512 tgl@sss.pgh.pa.us 284 : 1580504 : 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 *
8331 bruce@momjian.us 292 : 3413131 : 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 : :
864 drowley@postgresql.o 300 [ - + ]: 3413131 : Assert(bms_is_valid_set(a));
301 [ - + ]: 3413131 : Assert(bms_is_valid_set(b));
302 : :
303 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 304 [ + + + + ]: 3413131 : if (a == NULL || b == NULL)
305 : 1936421 : return NULL;
306 : :
307 : : /* Identify shorter and longer input; copy the shorter one */
308 [ + + ]: 1476710 : if (a->nwords <= b->nwords)
309 : : {
310 : 1476709 : result = bms_copy(a);
311 : 1476709 : other = b;
312 : : }
313 : : else
314 : : {
8512 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 */
8512 tgl@sss.pgh.pa.us 319 :CBC 1476710 : resultlen = result->nwords;
1061 drowley@postgresql.o 320 : 1476710 : lastnonzero = -1;
321 : 1476710 : i = 0;
322 : : do
323 : : {
8512 tgl@sss.pgh.pa.us 324 : 1477989 : result->words[i] &= other->words[i];
325 : :
1061 drowley@postgresql.o 326 [ + + ]: 1477989 : if (result->words[i] != 0)
327 : 1457122 : lastnonzero = i;
328 [ + + ]: 1477989 : } while (++i < resultlen);
329 : : /* If we computed an empty result, we must return NULL */
330 [ + + ]: 1476710 : if (lastnonzero == -1)
331 : : {
1185 tgl@sss.pgh.pa.us 332 : 19708 : pfree(result);
333 : 19708 : return NULL;
334 : : }
335 : :
336 : : /* get rid of trailing zero words */
1061 drowley@postgresql.o 337 : 1457002 : result->nwords = lastnonzero + 1;
8512 tgl@sss.pgh.pa.us 338 : 1457002 : 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 *
8331 bruce@momjian.us 346 : 4226863 : bms_difference(const Bitmapset *a, const Bitmapset *b)
347 : : {
348 : : Bitmapset *result;
349 : : int i;
350 : :
864 drowley@postgresql.o 351 [ - + ]: 4226863 : Assert(bms_is_valid_set(a));
352 [ - + ]: 4226863 : Assert(bms_is_valid_set(b));
353 : :
354 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 355 [ + + ]: 4226863 : if (a == NULL)
356 : 2243237 : return NULL;
357 [ + + ]: 1983626 : if (b == NULL)
358 : 976672 : 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 : : */
1185 365 [ + + ]: 1006954 : if (!bms_nonempty_difference(a, b))
366 : 743522 : return NULL;
367 : :
368 : : /* Copy the left input */
8512 369 : 263432 : result = bms_copy(a);
370 : :
371 : : /* And remove b's bits from result */
1061 drowley@postgresql.o 372 [ + + ]: 263432 : 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 : : */
1061 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 : : {
1061 drowley@postgresql.o 386 :CBC 263430 : int lastnonzero = -1;
387 : :
388 : : /* we may need to remove trailing zero words from the result. */
389 : 263430 : i = 0;
390 : : do
391 : : {
392 : 263431 : result->words[i] &= ~b->words[i];
393 : :
394 : : /* remember the last non-zero word */
395 [ + + ]: 263431 : if (result->words[i] != 0)
396 : 263430 : lastnonzero = i;
397 [ + + ]: 263431 : } while (++i < result->nwords);
398 : :
399 : : /* trim off trailing zero words */
400 : 263430 : result->nwords = lastnonzero + 1;
401 : : }
402 [ - + ]: 263432 : Assert(result->nwords != 0);
403 : :
404 : : /* Need not check for empty result, since we handled that case above */
8512 tgl@sss.pgh.pa.us 405 : 263432 : return result;
406 : : }
407 : :
408 : : /*
409 : : * bms_is_subset - is A a subset of B?
410 : : */
411 : : bool
8331 bruce@momjian.us 412 : 22095487 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
413 : : {
414 : : int i;
415 : :
864 drowley@postgresql.o 416 [ - + ]: 22095487 : Assert(bms_is_valid_set(a));
417 [ - + ]: 22095487 : Assert(bms_is_valid_set(b));
418 : :
419 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 420 [ + + ]: 22095487 : if (a == NULL)
421 : 4908621 : return true; /* empty set is a subset of anything */
422 [ + + ]: 17186866 : if (b == NULL)
1185 423 : 318967 : return false;
424 : :
425 : : /* 'a' can't be a subset of 'b' if it contains more words */
1061 drowley@postgresql.o 426 [ + + ]: 16867899 : if (a->nwords > b->nwords)
1061 drowley@postgresql.o 427 :GBC 2 : return false;
428 : :
429 : : /* Check all 'a' members are set in 'b' */
1061 drowley@postgresql.o 430 :CBC 16867897 : i = 0;
431 : : do
432 : : {
8335 bruce@momjian.us 433 [ + + ]: 16867897 : if ((a->words[i] & ~b->words[i]) != 0)
8512 tgl@sss.pgh.pa.us 434 : 5746885 : return false;
1061 drowley@postgresql.o 435 [ - + ]: 11121012 : } while (++i < a->nwords);
8512 tgl@sss.pgh.pa.us 436 : 11121012 : 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
5237 445 : 2153480 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
446 : : {
447 : : BMS_Comparison result;
448 : : int shortlen;
449 : : int i;
450 : :
864 drowley@postgresql.o 451 [ - + ]: 2153480 : Assert(bms_is_valid_set(a));
452 [ - + ]: 2153480 : Assert(bms_is_valid_set(b));
453 : :
454 : : /* Handle cases where either input is NULL */
5237 tgl@sss.pgh.pa.us 455 [ + + ]: 2153480 : if (a == NULL)
456 : : {
457 [ + + ]: 1789330 : if (b == NULL)
458 : 1737911 : return BMS_EQUAL;
1185 459 : 51419 : return BMS_SUBSET1;
460 : : }
5237 461 [ + + ]: 364150 : if (b == NULL)
1185 462 : 185702 : return BMS_SUBSET2;
463 : :
464 : : /* Check common words */
5237 465 : 178448 : result = BMS_EQUAL; /* status so far */
466 : 178448 : shortlen = Min(a->nwords, b->nwords);
1061 drowley@postgresql.o 467 : 178448 : i = 0;
468 : : do
469 : : {
5102 bruce@momjian.us 470 : 178451 : bitmapword aword = a->words[i];
471 : 178451 : bitmapword bword = b->words[i];
472 : :
5237 tgl@sss.pgh.pa.us 473 [ + + ]: 178451 : if ((aword & ~bword) != 0)
474 : : {
475 : : /* a is not a subset of b */
476 [ + + ]: 48439 : if (result == BMS_SUBSET1)
5237 tgl@sss.pgh.pa.us 477 :GBC 2 : return BMS_DIFFERENT;
5237 tgl@sss.pgh.pa.us 478 :CBC 48437 : result = BMS_SUBSET2;
479 : : }
480 [ + + ]: 178449 : if ((bword & ~aword) != 0)
481 : : {
482 : : /* b is not a subset of a */
483 [ + + ]: 51359 : if (result == BMS_SUBSET2)
484 : 45068 : return BMS_DIFFERENT;
485 : 6291 : result = BMS_SUBSET1;
486 : : }
1061 drowley@postgresql.o 487 [ + + ]: 133381 : } while (++i < shortlen);
488 : : /* Check extra words */
5237 tgl@sss.pgh.pa.us 489 [ + + ]: 133378 : if (a->nwords > b->nwords)
490 : : {
491 : : /* if a has more words then a is not a subset of b */
1061 drowley@postgresql.o 492 [ + + ]:GBC 2 : if (result == BMS_SUBSET1)
493 : 1 : return BMS_DIFFERENT;
494 : 1 : return BMS_SUBSET2;
495 : : }
5237 tgl@sss.pgh.pa.us 496 [ + + ]:CBC 133376 : else if (a->nwords < b->nwords)
497 : : {
498 : : /* if b has more words then b is not a subset of a */
1061 drowley@postgresql.o 499 [ + + ]:GBC 4 : if (result == BMS_SUBSET2)
500 : 2 : return BMS_DIFFERENT;
501 : 2 : return BMS_SUBSET1;
502 : : }
5237 tgl@sss.pgh.pa.us 503 :CBC 133372 : return result;
504 : : }
505 : :
506 : : /*
507 : : * bms_is_member - is X a member of A?
508 : : */
509 : : bool
8331 bruce@momjian.us 510 : 12810089 : bms_is_member(int x, const Bitmapset *a)
511 : : {
512 : : int wordnum,
513 : : bitnum;
514 : :
864 drowley@postgresql.o 515 [ - + ]: 12810089 : Assert(bms_is_valid_set(a));
516 : :
517 : : /* XXX better to just return false for x<0 ? */
8512 tgl@sss.pgh.pa.us 518 [ + + ]: 12810089 : if (x < 0)
8348 tgl@sss.pgh.pa.us 519 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8512 tgl@sss.pgh.pa.us 520 [ + + ]:CBC 12810088 : if (a == NULL)
521 : 7319731 : return false;
522 : :
523 : 5490357 : wordnum = WORDNUM(x);
524 : 5490357 : bitnum = BITNUM(x);
525 [ + + ]: 5490357 : if (wordnum >= a->nwords)
526 : 433 : return false;
527 [ + + ]: 5489924 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528 : 3826389 : return true;
529 : 1663535 : 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
2621 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 : :
864 drowley@postgresql.o 546 [ - + ]: 4427 : Assert(bms_is_valid_set(a));
547 : :
548 : : /* return -1 if not a member of the bitmap */
2621 tomas.vondra@postgre 549 [ + + ]: 4427 : if (!bms_is_member(x, a))
2621 tomas.vondra@postgre 550 :GBC 2 : return -1;
551 : :
2621 tomas.vondra@postgre 552 :CBC 4425 : wordnum = WORDNUM(x);
553 : 4425 : bitnum = BITNUM(x);
554 : :
555 : : /* count bits in preceding words */
96 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 : : */
2621 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
8331 bruce@momjian.us 575 : 25393908 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
576 : : {
577 : : int shortlen;
578 : : int i;
579 : :
864 drowley@postgresql.o 580 [ - + ]: 25393908 : Assert(bms_is_valid_set(a));
581 [ - + ]: 25393908 : Assert(bms_is_valid_set(b));
582 : :
583 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 584 [ + + + + ]: 25393908 : if (a == NULL || b == NULL)
585 : 16917940 : return false;
586 : : /* Check words in common */
587 : 8475968 : shortlen = Min(a->nwords, b->nwords);
1061 drowley@postgresql.o 588 : 8475968 : i = 0;
589 : : do
590 : : {
8512 tgl@sss.pgh.pa.us 591 [ + + ]: 8475968 : if ((a->words[i] & b->words[i]) != 0)
592 : 5050905 : return true;
1061 drowley@postgresql.o 593 [ - + ]: 3425063 : } while (++i < shortlen);
8512 tgl@sss.pgh.pa.us 594 : 3425063 : return false;
595 : : }
596 : :
597 : : /*
598 : : * bms_overlap_list - does a set overlap an integer list?
599 : : */
600 : : bool
3351 rhodiumtoad@postgres 601 : 1529 : bms_overlap_list(const Bitmapset *a, const List *b)
602 : : {
603 : : ListCell *lc;
604 : : int wordnum,
605 : : bitnum;
606 : :
864 drowley@postgresql.o 607 [ - + ]: 1529 : Assert(bms_is_valid_set(a));
608 : :
3351 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)
3351 rhodiumtoad@postgres 617 [ + - ]:GBC 2 : elog(ERROR, "negative bitmapset member not allowed");
3351 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
8331 bruce@momjian.us 634 : 3043190 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
635 : : {
636 : : int i;
637 : :
864 drowley@postgresql.o 638 [ - + ]: 3043190 : Assert(bms_is_valid_set(a));
639 [ - + ]: 3043190 : Assert(bms_is_valid_set(b));
640 : :
641 : : /* Handle cases where either input is NULL */
8371 tgl@sss.pgh.pa.us 642 [ + + ]: 3043190 : if (a == NULL)
643 : 4248 : return false;
644 [ + + ]: 3038942 : if (b == NULL)
1185 tgl@sss.pgh.pa.us 645 :GBC 1 : return true;
646 : : /* if 'a' has more words then it must contain additional members */
1061 drowley@postgresql.o 647 [ + + ]:CBC 3038941 : if (a->nwords > b->nwords)
1061 drowley@postgresql.o 648 :GBC 3 : return true;
649 : : /* Check all 'a' members are set in 'b' */
1061 drowley@postgresql.o 650 :CBC 3038938 : i = 0;
651 : : do
652 : : {
8335 bruce@momjian.us 653 [ + + ]: 3038938 : if ((a->words[i] & ~b->words[i]) != 0)
8371 tgl@sss.pgh.pa.us 654 : 1378667 : return true;
1061 drowley@postgresql.o 655 [ - + ]: 1660271 : } while (++i < a->nwords);
8371 tgl@sss.pgh.pa.us 656 : 1660271 : 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
8331 bruce@momjian.us 665 : 17741 : bms_singleton_member(const Bitmapset *a)
666 : : {
8335 667 : 17741 : int result = -1;
668 : : int nwords;
669 : : int wordnum;
670 : :
864 drowley@postgresql.o 671 [ - + ]: 17741 : Assert(bms_is_valid_set(a));
672 : :
8512 tgl@sss.pgh.pa.us 673 [ + + ]: 17741 : if (a == NULL)
8348 tgl@sss.pgh.pa.us 674 [ + - ]:GBC 1 : elog(ERROR, "bitmapset is empty");
675 : :
8512 tgl@sss.pgh.pa.us 676 :CBC 17740 : nwords = a->nwords;
1061 drowley@postgresql.o 677 : 17740 : wordnum = 0;
678 : : do
679 : : {
8512 tgl@sss.pgh.pa.us 680 : 17740 : bitmapword w = a->words[wordnum];
681 : :
682 [ + - ]: 17740 : if (w != 0)
683 : : {
684 [ + - + + ]: 17740 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
8348 tgl@sss.pgh.pa.us 685 [ + - ]:GBC 1 : elog(ERROR, "bitmapset has multiple members");
8512 tgl@sss.pgh.pa.us 686 :CBC 17739 : result = wordnum * BITS_PER_BITMAPWORD;
2661 687 : 17739 : result += bmw_rightmost_one_pos(w);
688 : : }
1061 drowley@postgresql.o 689 [ - + ]: 17739 : } while (++wordnum < nwords);
690 : :
691 : : /* we don't expect non-NULL sets to be empty */
692 [ - + ]: 17739 : Assert(result >= 0);
8512 tgl@sss.pgh.pa.us 693 : 17739 : 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
4201 708 : 2148294 : bms_get_singleton_member(const Bitmapset *a, int *member)
709 : : {
710 : 2148294 : int result = -1;
711 : : int nwords;
712 : : int wordnum;
713 : :
864 drowley@postgresql.o 714 [ - + ]: 2148294 : Assert(bms_is_valid_set(a));
715 : :
4201 tgl@sss.pgh.pa.us 716 [ + + ]: 2148294 : if (a == NULL)
4201 tgl@sss.pgh.pa.us 717 :GBC 2 : return false;
718 : :
4201 tgl@sss.pgh.pa.us 719 :CBC 2148292 : nwords = a->nwords;
1061 drowley@postgresql.o 720 : 2148292 : wordnum = 0;
721 : : do
722 : : {
4201 tgl@sss.pgh.pa.us 723 : 2148298 : bitmapword w = a->words[wordnum];
724 : :
725 [ + + ]: 2148298 : if (w != 0)
726 : : {
727 [ + - + + ]: 2148292 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
728 : 400884 : return false;
729 : 1747408 : result = wordnum * BITS_PER_BITMAPWORD;
2661 730 : 1747408 : result += bmw_rightmost_one_pos(w);
731 : : }
1061 drowley@postgresql.o 732 [ + + ]: 1747414 : } while (++wordnum < nwords);
733 : :
734 : : /* we don't expect non-NULL sets to be empty */
735 [ - + ]: 1747408 : Assert(result >= 0);
4201 tgl@sss.pgh.pa.us 736 : 1747408 : *member = result;
737 : 1747408 : return true;
738 : : }
739 : :
740 : : /*
741 : : * bms_num_members - count members of set
742 : : */
743 : : int
8331 bruce@momjian.us 744 : 2011848 : bms_num_members(const Bitmapset *a)
745 : : {
864 drowley@postgresql.o 746 [ - + ]: 2011848 : Assert(bms_is_valid_set(a));
747 : :
8512 tgl@sss.pgh.pa.us 748 [ + + ]: 2011848 : if (a == NULL)
749 : 277955 : return 0;
750 : :
751 : : /* fast-path for common case */
96 nathan@postgresql.or 752 [ + + ]:GNC 1733893 : if (a->nwords == 1)
753 : 1733507 : 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
8331 bruce@momjian.us 765 :CBC 1666379 : bms_membership(const Bitmapset *a)
766 : : {
8512 tgl@sss.pgh.pa.us 767 : 1666379 : BMS_Membership result = BMS_EMPTY_SET;
768 : : int nwords;
769 : : int wordnum;
770 : :
864 drowley@postgresql.o 771 [ - + ]: 1666379 : Assert(bms_is_valid_set(a));
772 : :
8512 tgl@sss.pgh.pa.us 773 [ + + ]: 1666379 : if (a == NULL)
774 : 413 : return BMS_EMPTY_SET;
775 : :
776 : 1665966 : nwords = a->nwords;
1061 drowley@postgresql.o 777 : 1665966 : wordnum = 0;
778 : : do
779 : : {
8512 tgl@sss.pgh.pa.us 780 : 1666082 : bitmapword w = a->words[wordnum];
781 : :
782 [ + + ]: 1666082 : if (w != 0)
783 : : {
784 [ + - + + ]: 1665966 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
785 : 601952 : return BMS_MULTIPLE;
786 : 1064014 : result = BMS_SINGLETON;
787 : : }
1061 drowley@postgresql.o 788 [ + + ]: 1064130 : } while (++wordnum < nwords);
8512 tgl@sss.pgh.pa.us 789 : 1064014 : 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 *
8331 bruce@momjian.us 799 : 17753901 : bms_add_member(Bitmapset *a, int x)
800 : : {
801 : : int wordnum,
802 : : bitnum;
803 : :
864 drowley@postgresql.o 804 [ - + ]: 17753901 : Assert(bms_is_valid_set(a));
805 : :
8512 tgl@sss.pgh.pa.us 806 [ + + ]: 17753901 : if (x < 0)
8348 tgl@sss.pgh.pa.us 807 [ + - ]:GBC 2 : elog(ERROR, "negative bitmapset member not allowed");
8512 tgl@sss.pgh.pa.us 808 [ + + ]:CBC 17753899 : if (a == NULL)
809 : 9640972 : return bms_make_singleton(x);
810 : :
811 : 8112927 : wordnum = WORDNUM(x);
812 : 8112927 : bitnum = BITNUM(x);
813 : :
814 : : /* enlarge the set if necessary */
815 [ + + ]: 8112927 : if (wordnum >= a->nwords)
816 : : {
4625 heikki.linnakangas@i 817 : 507 : int oldnwords = a->nwords;
818 : : int i;
819 : :
820 : 507 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
821 : 507 : a->nwords = wordnum + 1;
822 : : /* zero out the enlarged portion */
1061 drowley@postgresql.o 823 : 507 : i = oldnwords;
824 : : do
825 : : {
4625 heikki.linnakangas@i 826 : 53838 : a->words[i] = 0;
1061 drowley@postgresql.o 827 [ + + ]: 53838 : } while (++i < a->nwords);
828 : : }
829 : :
864 830 : 8112927 : 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 : :
8512 tgl@sss.pgh.pa.us 841 : 8112927 : 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 *
8331 bruce@momjian.us 852 : 1502841 : bms_del_member(Bitmapset *a, int x)
853 : : {
854 : : int wordnum,
855 : : bitnum;
856 : :
864 drowley@postgresql.o 857 [ - + ]: 1502841 : Assert(bms_is_valid_set(a));
858 : :
8512 tgl@sss.pgh.pa.us 859 [ + + ]: 1502841 : if (x < 0)
8348 tgl@sss.pgh.pa.us 860 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
8512 tgl@sss.pgh.pa.us 861 [ + + ]:CBC 1502840 : if (a == NULL)
862 : 547227 : return NULL;
863 : :
864 : 955613 : wordnum = WORDNUM(x);
865 : 955613 : 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 */
1061 drowley@postgresql.o 872 [ - + ]: 955613 : if (unlikely(wordnum >= a->nwords))
1061 drowley@postgresql.o 873 :UBC 0 : return a;
874 : :
1061 drowley@postgresql.o 875 :CBC 955613 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
876 : :
877 : : /* when last word becomes empty, trim off all trailing empty words */
878 [ + + + + ]: 955613 : 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 [ + + ]: 557123 : for (int i = wordnum - 1; i >= 0; i--)
882 : : {
1061 drowley@postgresql.o 883 [ + + ]:GBC 112662 : if (a->words[i] != 0)
884 : : {
885 : 275 : a->nwords = i + 1;
886 : 275 : return a;
887 : : }
888 : : }
889 : :
890 : : /* the set is now empty */
1185 tgl@sss.pgh.pa.us 891 :CBC 444461 : pfree(a);
892 : 444461 : return NULL;
893 : : }
8512 894 : 510877 : return a;
895 : : }
896 : :
897 : : /*
898 : : * bms_add_members - like bms_union, but left input is recycled when possible
899 : : */
900 : : Bitmapset *
8331 bruce@momjian.us 901 : 19938501 : bms_add_members(Bitmapset *a, const Bitmapset *b)
902 : : {
903 : : Bitmapset *result;
904 : : const Bitmapset *other;
905 : : int otherlen;
906 : : int i;
907 : :
864 drowley@postgresql.o 908 [ - + ]: 19938501 : Assert(bms_is_valid_set(a));
909 [ - + ]: 19938501 : Assert(bms_is_valid_set(b));
910 : :
911 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 912 [ + + ]: 19938501 : if (a == NULL)
913 : 14293588 : return bms_copy(b);
914 [ + + ]: 5644913 : if (b == NULL)
915 : : {
916 : : #ifdef REALLOCATE_BITMAPSETS
917 : : a = bms_copy_and_free(a);
918 : : #endif
919 : :
920 : 3572273 : return a;
921 : : }
922 : : /* Identify shorter and longer input; copy the longer one if needed */
923 [ + + ]: 2072640 : if (a->nwords < b->nwords)
924 : : {
8512 tgl@sss.pgh.pa.us 925 :GBC 17 : result = bms_copy(b);
926 : 17 : other = a;
927 : : }
928 : : else
929 : : {
8512 tgl@sss.pgh.pa.us 930 :CBC 2072623 : result = a;
931 : 2072623 : other = b;
932 : : }
933 : : /* And union the shorter input into the result */
934 : 2072640 : otherlen = other->nwords;
1061 drowley@postgresql.o 935 : 2072640 : i = 0;
936 : : do
937 : : {
8512 tgl@sss.pgh.pa.us 938 : 2073276 : result->words[i] |= other->words[i];
1061 drowley@postgresql.o 939 [ + + ]: 2073276 : } while (++i < otherlen);
8512 tgl@sss.pgh.pa.us 940 [ + + ]: 2072640 : if (result != a)
8512 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 : :
8512 tgl@sss.pgh.pa.us 947 :CBC 2072640 : 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 *
862 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)
862 drowley@postgresql.o 964 :GBC 1 : return bms_copy(b);
862 drowley@postgresql.o 965 [ + + ]:CBC 11240 : if (b == NULL)
966 : : {
862 drowley@postgresql.o 967 :GBC 1 : pfree(a);
968 : 1 : return NULL;
969 : : }
970 : :
862 drowley@postgresql.o 971 [ + + ]:CBC 11239 : if (a->nwords < b->nwords)
862 drowley@postgresql.o 972 :GBC 1 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
973 : :
862 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 *
3104 rhaas@postgresql.org 1003 : 44879 : bms_add_range(Bitmapset *a, int lower, int upper)
1004 : : {
1005 : : int lwordnum,
1006 : : lbitnum,
1007 : : uwordnum,
1008 : : ushiftbits,
1009 : : wordnum;
1010 : :
864 drowley@postgresql.o 1011 [ - + ]: 44879 : Assert(bms_is_valid_set(a));
1012 : :
1013 : : /* do nothing if nothing is called for, without further checking */
2861 alvherre@alvh.no-ip. 1014 [ + + ]: 44879 : 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 [ + + ]: 44856 : if (lower < 0)
3104 rhaas@postgresql.org 1024 [ + - ]:GBC 1 : elog(ERROR, "negative bitmapset member not allowed");
3104 rhaas@postgresql.org 1025 :CBC 44855 : uwordnum = WORDNUM(upper);
1026 : :
1027 [ + + ]: 44855 : if (a == NULL)
1028 : : {
1029 : 34825 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1294 tgl@sss.pgh.pa.us 1030 : 34825 : a->type = T_Bitmapset;
3104 rhaas@postgresql.org 1031 : 34825 : a->nwords = uwordnum + 1;
1032 : : }
1033 [ + + ]: 10030 : else if (uwordnum >= a->nwords)
1034 : : {
3104 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 */
1061 drowley@postgresql.o 1042 : 3 : i = oldnwords;
1043 : : do
1044 : : {
3104 rhaas@postgresql.org 1045 : 5 : a->words[i] = 0;
1061 drowley@postgresql.o 1046 [ + + ]: 5 : } while (++i < a->nwords);
1047 : : }
1048 : :
3104 rhaas@postgresql.org 1049 :CBC 44855 : wordnum = lwordnum = WORDNUM(lower);
1050 : :
1051 : 44855 : lbitnum = BITNUM(lower);
1052 : 44855 : 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 [ + + ]: 44855 : if (lwordnum == uwordnum)
1059 : : {
1060 : 43907 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
3063 tgl@sss.pgh.pa.us 1061 : 43907 : & (~(bitmapword) 0) >> ushiftbits;
1062 : : }
1063 : : else
1064 : : {
1065 : : /* turn on lbitnum and all bits left of it */
3104 rhaas@postgresql.org 1066 :GBC 948 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1067 : :
1068 : : /* turn on all bits for any intermediate words */
1069 [ + + ]: 983 : while (wordnum < uwordnum)
1070 : 35 : a->words[wordnum++] = ~(bitmapword) 0;
1071 : :
1072 : : /* turn on upper's bit and all bits right of it. */
1073 : 948 : 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 : :
3104 rhaas@postgresql.org 1085 :CBC 44855 : return a;
1086 : : }
1087 : :
1088 : : /*
1089 : : * bms_int_members - like bms_intersect, but left input is recycled when
1090 : : * possible
1091 : : */
1092 : : Bitmapset *
8331 bruce@momjian.us 1093 : 624273 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1094 : : {
1095 : : int lastnonzero;
1096 : : int shortlen;
1097 : : int i;
1098 : :
864 drowley@postgresql.o 1099 [ - + ]: 624273 : Assert(bms_is_valid_set(a));
1100 [ - + ]: 624273 : Assert(bms_is_valid_set(b));
1101 : :
1102 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 1103 [ + + ]: 624273 : if (a == NULL)
1104 : 19736 : return NULL;
1105 [ + + ]: 604537 : if (b == NULL)
1106 : : {
1107 : 3340 : pfree(a);
1108 : 3340 : return NULL;
1109 : : }
1110 : :
1111 : : /* Intersect b into a; we need never copy */
1112 : 601197 : shortlen = Min(a->nwords, b->nwords);
1061 drowley@postgresql.o 1113 : 601197 : lastnonzero = -1;
1114 : 601197 : i = 0;
1115 : : do
1116 : : {
8512 tgl@sss.pgh.pa.us 1117 : 601198 : a->words[i] &= b->words[i];
1118 : :
1061 drowley@postgresql.o 1119 [ + + ]: 601198 : if (a->words[i] != 0)
1120 : 507148 : lastnonzero = i;
1121 [ + + ]: 601198 : } while (++i < shortlen);
1122 : :
1123 : : /* If we computed an empty result, we must return NULL */
1124 [ + + ]: 601197 : if (lastnonzero == -1)
1125 : : {
1185 tgl@sss.pgh.pa.us 1126 : 94050 : pfree(a);
1127 : 94050 : return NULL;
1128 : : }
1129 : :
1130 : : /* get rid of trailing zero words */
1061 drowley@postgresql.o 1131 : 507147 : a->nwords = lastnonzero + 1;
1132 : :
1133 : : #ifdef REALLOCATE_BITMAPSETS
1134 : : a = bms_copy_and_free(a);
1135 : : #endif
1136 : :
8512 tgl@sss.pgh.pa.us 1137 : 507147 : 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 *
8331 bruce@momjian.us 1145 : 1803120 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1146 : : {
1147 : : int i;
1148 : :
864 drowley@postgresql.o 1149 [ - + ]: 1803120 : Assert(bms_is_valid_set(a));
1150 [ - + ]: 1803120 : Assert(bms_is_valid_set(b));
1151 : :
1152 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 1153 [ + + ]: 1803120 : if (a == NULL)
1154 : 781921 : return NULL;
1155 [ + + ]: 1021199 : if (b == NULL)
1156 : : {
1157 : : #ifdef REALLOCATE_BITMAPSETS
1158 : : a = bms_copy_and_free(a);
1159 : : #endif
1160 : :
864 drowley@postgresql.o 1161 : 160969 : return a;
1162 : : }
1163 : :
1164 : : /* Remove b's bits from a; we need never copy */
1061 1165 [ + + ]: 860230 : 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 : : */
1061 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 : : {
1061 drowley@postgresql.o 1179 :CBC 860229 : int lastnonzero = -1;
1180 : :
1181 : : /* we may need to remove trailing zero words from the result. */
1182 : 860229 : i = 0;
1183 : : do
1184 : : {
1185 : 860237 : a->words[i] &= ~b->words[i];
1186 : :
1187 : : /* remember the last non-zero word */
1188 [ + + ]: 860237 : if (a->words[i] != 0)
1189 : 196489 : lastnonzero = i;
1190 [ + + ]: 860237 : } while (++i < a->nwords);
1191 : :
1192 : : /* check if 'a' has become empty */
1193 [ + + ]: 860229 : if (lastnonzero == -1)
1194 : : {
1195 : 663742 : pfree(a);
1196 : 663742 : return NULL;
1197 : : }
1198 : :
1199 : : /* trim off any trailing zero words */
1200 : 196487 : a->nwords = lastnonzero + 1;
1201 : : }
1202 : :
1203 : : #ifdef REALLOCATE_BITMAPSETS
1204 : : a = bms_copy_and_free(a);
1205 : : #endif
1206 : :
8512 tgl@sss.pgh.pa.us 1207 : 196488 : return a;
1208 : : }
1209 : :
1210 : : /*
1211 : : * bms_join - like bms_union, but *either* input *may* be recycled
1212 : : */
1213 : : Bitmapset *
8331 bruce@momjian.us 1214 : 1359107 : bms_join(Bitmapset *a, Bitmapset *b)
1215 : : {
1216 : : Bitmapset *result;
1217 : : Bitmapset *other;
1218 : : int otherlen;
1219 : : int i;
1220 : :
864 drowley@postgresql.o 1221 [ - + ]: 1359107 : Assert(bms_is_valid_set(a));
1222 [ - + ]: 1359107 : Assert(bms_is_valid_set(b));
1223 : :
1224 : : /* Handle cases where either input is NULL */
8512 tgl@sss.pgh.pa.us 1225 [ + + ]: 1359107 : if (a == NULL)
1226 : : {
1227 : : #ifdef REALLOCATE_BITMAPSETS
1228 : : b = bms_copy_and_free(b);
1229 : : #endif
1230 : :
1231 : 528648 : return b;
1232 : : }
1233 [ + + ]: 830459 : if (b == NULL)
1234 : : {
1235 : : #ifdef REALLOCATE_BITMAPSETS
1236 : : a = bms_copy_and_free(a);
1237 : : #endif
1238 : :
864 drowley@postgresql.o 1239 : 146923 : return a;
1240 : : }
1241 : :
1242 : : /* Identify shorter and longer input; use longer one as result */
8512 tgl@sss.pgh.pa.us 1243 [ + + ]: 683536 : if (a->nwords < b->nwords)
1244 : : {
8512 tgl@sss.pgh.pa.us 1245 :GBC 2 : result = b;
1246 : 2 : other = a;
1247 : : }
1248 : : else
1249 : : {
8512 tgl@sss.pgh.pa.us 1250 :CBC 683534 : result = a;
1251 : 683534 : other = b;
1252 : : }
1253 : : /* And union the shorter input into the result */
1254 : 683536 : otherlen = other->nwords;
1061 drowley@postgresql.o 1255 : 683536 : i = 0;
1256 : : do
1257 : : {
8512 tgl@sss.pgh.pa.us 1258 : 683536 : result->words[i] |= other->words[i];
1061 drowley@postgresql.o 1259 [ - + ]: 683536 : } while (++i < otherlen);
8512 tgl@sss.pgh.pa.us 1260 [ + - ]: 683536 : if (other != result) /* pure paranoia */
1261 : 683536 : pfree(other);
1262 : :
1263 : : #ifdef REALLOCATE_BITMAPSETS
1264 : : result = bms_copy_and_free(result);
1265 : : #endif
1266 : :
1267 : 683536 : 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
4201 1290 : 22713696 : bms_next_member(const Bitmapset *a, int prevbit)
1291 : : {
47 drowley@postgresql.o 1292 :GNC 22713696 : unsigned int currbit = prevbit;
1293 : : int nwords;
1294 : : bitmapword mask;
1295 : :
864 drowley@postgresql.o 1296 [ - + ]:CBC 22713696 : Assert(bms_is_valid_set(a));
1297 : :
4201 tgl@sss.pgh.pa.us 1298 [ + + ]: 22713696 : if (a == NULL)
1299 : 6435407 : return -2;
1300 : 16278289 : nwords = a->nwords;
1301 : :
1302 : : /* use an unsigned int to avoid the risk that int overflows */
47 drowley@postgresql.o 1303 :GNC 16278289 : currbit++;
1304 : 16278289 : mask = (~(bitmapword) 0) << BITNUM(currbit);
1305 [ + + ]: 21719944 : for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
1306 : : {
4201 tgl@sss.pgh.pa.us 1307 :CBC 16280398 : bitmapword w = a->words[wordnum];
1308 : :
1309 : : /* ignore bits before currbit */
1310 : 16280398 : w &= mask;
1311 : :
1312 [ + + ]: 16280398 : if (w != 0)
1313 : : {
1314 : : int result;
1315 : :
1316 : 10838743 : result = wordnum * BITS_PER_BITMAPWORD;
2661 1317 : 10838743 : result += bmw_rightmost_one_pos(w);
4201 1318 : 10838743 : return result;
1319 : : }
1320 : :
1321 : : /* in subsequent words, consider all bits */
1322 : 5441655 : mask = (~(bitmapword) 0);
1323 : : }
1324 : 5439546 : 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
2975 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 : :
864 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 : : */
2975 alvherre@alvh.no-ip. 1364 [ + + - + ]: 18 : if (a == NULL || prevbit == 0)
2975 alvherre@alvh.no-ip. 1365 :GBC 2 : return -2;
1366 : :
1367 : : /* Validate callers didn't give us something out of range */
47 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);
2975 alvherre@alvh.no-ip. 1381 :CBC 16 : mask = (~(bitmapword) 0) >> ushiftbits;
47 drowley@postgresql.o 1382 [ + + ]:GNC 21 : for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
1383 : : {
2975 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;
2661 tgl@sss.pgh.pa.us 1394 : 11 : result += bmw_leftmost_one_pos(w);
2975 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
7661 tgl@sss.pgh.pa.us 1408 : 5121 : bms_hash_value(const Bitmapset *a)
1409 : : {
864 drowley@postgresql.o 1410 [ - + ]: 5121 : Assert(bms_is_valid_set(a));
1411 : :
6938 tgl@sss.pgh.pa.us 1412 [ + + ]: 5121 : if (a == NULL)
7661 tgl@sss.pgh.pa.us 1413 :GBC 4 : return 0; /* All empty sets hash to 0 */
6938 tgl@sss.pgh.pa.us 1414 :CBC 5117 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1061 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
2287 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 : : }
|
