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-2024, 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
88 drowley@postgresql.o 79 :GNC 127992101 : bms_is_valid_set(const Bitmapset *a)
80 : : {
81 : : /* NULL is the correct representation of an empty set */
82 [ + + ]: 127992101 : if (a == NULL)
83 : 50714158 : return true;
84 : :
85 : : /* check the node tag is set correctly. pfree'd pointer, maybe? */
86 [ - + ]: 77277943 : if (!IsA(a, Bitmapset))
88 drowley@postgresql.o 87 :UNC 0 : return false;
88 : :
89 : : /* trailing zero words are not allowed */
88 drowley@postgresql.o 90 [ - + ]:GNC 77277943 : if (a->words[a->nwords - 1] == 0)
88 drowley@postgresql.o 91 :UNC 0 : return false;
92 : :
88 drowley@postgresql.o 93 :GNC 77277943 : 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 *
7555 bruce@momjian.us 122 :CBC 14476462 : bms_copy(const Bitmapset *a)
123 : : {
124 : : Bitmapset *result;
125 : : size_t size;
126 : :
88 drowley@postgresql.o 127 [ - + ]:GNC 14476462 : Assert(bms_is_valid_set(a));
128 : :
7736 tgl@sss.pgh.pa.us 129 [ + + ]:CBC 14476462 : if (a == NULL)
130 : 7855992 : return NULL;
131 : :
132 : 6620470 : size = BITMAPSET_SIZE(a->nwords);
133 : 6620470 : result = (Bitmapset *) palloc(size);
134 : 6620470 : memcpy(result, a, size);
135 : 6620470 : return result;
136 : : }
137 : :
138 : : /*
139 : : * bms_equal - are two bitmapsets equal? or both NULL?
140 : : */
141 : : bool
7555 bruce@momjian.us 142 : 5028454 : bms_equal(const Bitmapset *a, const Bitmapset *b)
143 : : {
144 : : int i;
145 : :
88 drowley@postgresql.o 146 [ - + ]:GNC 5028454 : Assert(bms_is_valid_set(a));
147 [ - + ]: 5028454 : Assert(bms_is_valid_set(b));
148 : :
149 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 150 [ + + ]:CBC 5028454 : if (a == NULL)
151 : : {
152 [ + + ]: 2839491 : if (b == NULL)
153 : 2801433 : return true;
409 154 : 38058 : return false;
155 : : }
7736 156 [ + + ]: 2188963 : else if (b == NULL)
409 157 : 14408 : return false;
158 : :
159 : : /* can't be equal if the word counts don't match */
285 drowley@postgresql.o 160 [ - + ]:GNC 2174555 : if (a->nwords != b->nwords)
285 drowley@postgresql.o 161 :UNC 0 : return false;
162 : :
163 : : /* check each word matches */
285 drowley@postgresql.o 164 :GNC 2174555 : i = 0;
165 : : do
166 : : {
167 [ + + ]: 2174555 : if (a->words[i] != b->words[i])
7736 tgl@sss.pgh.pa.us 168 :CBC 1299754 : return false;
285 drowley@postgresql.o 169 [ - + ]:GNC 874801 : } while (++i < a->nwords);
170 : :
7736 tgl@sss.pgh.pa.us 171 :CBC 874801 : 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
2287 183 : 10694 : bms_compare(const Bitmapset *a, const Bitmapset *b)
184 : : {
185 : : int i;
186 : :
88 drowley@postgresql.o 187 [ - + ]:GNC 10694 : Assert(bms_is_valid_set(a));
188 [ - + ]: 10694 : Assert(bms_is_valid_set(b));
189 : :
190 : : /* Handle cases where either input is NULL */
2287 tgl@sss.pgh.pa.us 191 [ - + ]:CBC 10694 : if (a == NULL)
409 tgl@sss.pgh.pa.us 192 [ # # ]:UBC 0 : return (b == NULL) ? 0 : -1;
2287 tgl@sss.pgh.pa.us 193 [ - + ]:CBC 10694 : else if (b == NULL)
409 tgl@sss.pgh.pa.us 194 :UBC 0 : return +1;
195 : :
196 : : /* the set with the most words must be greater */
285 drowley@postgresql.o 197 [ - + ]:GNC 10694 : if (a->nwords != b->nwords)
285 drowley@postgresql.o 198 [ # # ]:UNC 0 : return (a->nwords > b->nwords) ? +1 : -1;
199 : :
285 drowley@postgresql.o 200 :GNC 10694 : i = a->nwords - 1;
201 : : do
202 : : {
2287 tgl@sss.pgh.pa.us 203 :CBC 10694 : bitmapword aw = a->words[i];
204 : 10694 : bitmapword bw = b->words[i];
205 : :
206 [ + - ]: 10694 : if (aw != bw)
207 [ + + ]: 10694 : return (aw > bw) ? +1 : -1;
285 drowley@postgresql.o 208 [ # # ]:UNC 0 : } while (--i >= 0);
2287 tgl@sss.pgh.pa.us 209 :UBC 0 : return 0;
210 : : }
211 : :
212 : : /*
213 : : * bms_make_singleton - build a bitmapset containing a single member
214 : : */
215 : : Bitmapset *
7736 tgl@sss.pgh.pa.us 216 :CBC 5591100 : bms_make_singleton(int x)
217 : : {
218 : : Bitmapset *result;
219 : : int wordnum,
220 : : bitnum;
221 : :
222 [ - + ]: 5591100 : if (x < 0)
7572 tgl@sss.pgh.pa.us 223 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
7736 tgl@sss.pgh.pa.us 224 :CBC 5591100 : wordnum = WORDNUM(x);
225 : 5591100 : bitnum = BITNUM(x);
226 : 5591100 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
518 227 : 5591100 : result->type = T_Bitmapset;
7736 228 : 5591100 : result->nwords = wordnum + 1;
229 : 5591100 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
230 : 5591100 : return result;
231 : : }
232 : :
233 : : /*
234 : : * bms_free - free a bitmapset
235 : : *
236 : : * Same as pfree except for allowing NULL input
237 : : */
238 : : void
7555 bruce@momjian.us 239 : 10499920 : bms_free(Bitmapset *a)
240 : : {
7736 tgl@sss.pgh.pa.us 241 [ + + ]: 10499920 : if (a)
242 : 3916124 : pfree(a);
243 : 10499920 : }
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 *
7555 bruce@momjian.us 251 : 3564890 : bms_union(const Bitmapset *a, const Bitmapset *b)
252 : : {
253 : : Bitmapset *result;
254 : : const Bitmapset *other;
255 : : int otherlen;
256 : : int i;
257 : :
88 drowley@postgresql.o 258 [ - + ]:GNC 3564890 : Assert(bms_is_valid_set(a));
259 [ - + ]: 3564890 : Assert(bms_is_valid_set(b));
260 : :
261 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 262 [ + + ]:CBC 3564890 : if (a == NULL)
263 : 2302877 : return bms_copy(b);
264 [ + + ]: 1262013 : if (b == NULL)
265 : 557645 : return bms_copy(a);
266 : : /* Identify shorter and longer input; copy the longer one */
267 [ + - ]: 704368 : if (a->nwords <= b->nwords)
268 : : {
269 : 704368 : result = bms_copy(b);
270 : 704368 : other = a;
271 : : }
272 : : else
273 : : {
7736 tgl@sss.pgh.pa.us 274 :UBC 0 : result = bms_copy(a);
275 : 0 : other = b;
276 : : }
277 : : /* And union the shorter input into the result */
7736 tgl@sss.pgh.pa.us 278 :CBC 704368 : otherlen = other->nwords;
285 drowley@postgresql.o 279 :GNC 704368 : i = 0;
280 : : do
281 : : {
7736 tgl@sss.pgh.pa.us 282 :CBC 704368 : result->words[i] |= other->words[i];
285 drowley@postgresql.o 283 [ - + ]:GNC 704368 : } while (++i < otherlen);
7736 tgl@sss.pgh.pa.us 284 :CBC 704368 : 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 *
7555 bruce@momjian.us 292 : 1559233 : 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 : :
88 drowley@postgresql.o 300 [ - + ]:GNC 1559233 : Assert(bms_is_valid_set(a));
301 [ - + ]: 1559233 : Assert(bms_is_valid_set(b));
302 : :
303 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 304 [ + + + + ]:CBC 1559233 : if (a == NULL || b == NULL)
305 : 881662 : return NULL;
306 : :
307 : : /* Identify shorter and longer input; copy the shorter one */
308 [ + - ]: 677571 : if (a->nwords <= b->nwords)
309 : : {
310 : 677571 : result = bms_copy(a);
311 : 677571 : other = b;
312 : : }
313 : : else
314 : : {
7736 tgl@sss.pgh.pa.us 315 :UBC 0 : result = bms_copy(b);
316 : 0 : other = a;
317 : : }
318 : : /* And intersect the longer input with the result */
7736 tgl@sss.pgh.pa.us 319 :CBC 677571 : resultlen = result->nwords;
285 drowley@postgresql.o 320 :GNC 677571 : lastnonzero = -1;
321 : 677571 : i = 0;
322 : : do
323 : : {
7736 tgl@sss.pgh.pa.us 324 :CBC 677571 : result->words[i] &= other->words[i];
325 : :
285 drowley@postgresql.o 326 [ + + ]:GNC 677571 : if (result->words[i] != 0)
327 : 670676 : lastnonzero = i;
328 [ - + ]: 677571 : } while (++i < resultlen);
329 : : /* If we computed an empty result, we must return NULL */
330 [ + + ]: 677571 : if (lastnonzero == -1)
331 : : {
409 tgl@sss.pgh.pa.us 332 :CBC 6895 : pfree(result);
333 : 6895 : return NULL;
334 : : }
335 : :
336 : : /* get rid of trailing zero words */
285 drowley@postgresql.o 337 :GNC 670676 : result->nwords = lastnonzero + 1;
7736 tgl@sss.pgh.pa.us 338 :CBC 670676 : 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 *
7555 bruce@momjian.us 346 : 1481245 : bms_difference(const Bitmapset *a, const Bitmapset *b)
347 : : {
348 : : Bitmapset *result;
349 : : int i;
350 : :
88 drowley@postgresql.o 351 [ - + ]:GNC 1481245 : Assert(bms_is_valid_set(a));
352 [ - + ]: 1481245 : Assert(bms_is_valid_set(b));
353 : :
354 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 355 [ + + ]:CBC 1481245 : if (a == NULL)
356 : 793231 : return NULL;
357 [ + + ]: 688014 : if (b == NULL)
358 : 228504 : 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 : : */
409 365 [ + + ]: 459510 : if (!bms_nonempty_difference(a, b))
366 : 373113 : return NULL;
367 : :
368 : : /* Copy the left input */
7736 369 : 86397 : result = bms_copy(a);
370 : :
371 : : /* And remove b's bits from result */
285 drowley@postgresql.o 372 [ - + ]:GNC 86397 : 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 : : */
285 drowley@postgresql.o 378 :UNC 0 : i = 0;
379 : : do
380 : : {
381 : 0 : result->words[i] &= ~b->words[i];
382 [ # # ]: 0 : } while (++i < b->nwords);
383 : : }
384 : : else
385 : : {
285 drowley@postgresql.o 386 :GNC 86397 : int lastnonzero = -1;
387 : :
388 : : /* we may need to remove trailing zero words from the result. */
389 : 86397 : i = 0;
390 : : do
391 : : {
392 : 86397 : result->words[i] &= ~b->words[i];
393 : :
394 : : /* remember the last non-zero word */
395 [ + - ]: 86397 : if (result->words[i] != 0)
396 : 86397 : lastnonzero = i;
397 [ - + ]: 86397 : } while (++i < result->nwords);
398 : :
399 : : /* trim off trailing zero words */
400 : 86397 : result->nwords = lastnonzero + 1;
401 : : }
402 [ - + ]: 86397 : Assert(result->nwords != 0);
403 : :
404 : : /* Need not check for empty result, since we handled that case above */
7736 tgl@sss.pgh.pa.us 405 :CBC 86397 : return result;
406 : : }
407 : :
408 : : /*
409 : : * bms_is_subset - is A a subset of B?
410 : : */
411 : : bool
7555 bruce@momjian.us 412 : 10714010 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
413 : : {
414 : : int i;
415 : :
88 drowley@postgresql.o 416 [ - + ]:GNC 10714010 : Assert(bms_is_valid_set(a));
417 [ - + ]: 10714010 : Assert(bms_is_valid_set(b));
418 : :
419 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 420 [ + + ]:CBC 10714010 : if (a == NULL)
421 : 2423855 : return true; /* empty set is a subset of anything */
422 [ + + ]: 8290155 : if (b == NULL)
409 423 : 202532 : return false;
424 : :
425 : : /* 'a' can't be a subset of 'b' if it contains more words */
285 drowley@postgresql.o 426 [ - + ]:GNC 8087623 : if (a->nwords > b->nwords)
285 drowley@postgresql.o 427 :UNC 0 : return false;
428 : :
429 : : /* Check all 'a' members are set in 'b' */
285 drowley@postgresql.o 430 :GNC 8087623 : i = 0;
431 : : do
432 : : {
7559 bruce@momjian.us 433 [ + + ]:CBC 8087623 : if ((a->words[i] & ~b->words[i]) != 0)
7736 tgl@sss.pgh.pa.us 434 : 2878717 : return false;
285 drowley@postgresql.o 435 [ - + ]:GNC 5208906 : } while (++i < a->nwords);
7736 tgl@sss.pgh.pa.us 436 :CBC 5208906 : 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
4461 445 : 1034691 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
446 : : {
447 : : BMS_Comparison result;
448 : : int shortlen;
449 : : int i;
450 : :
88 drowley@postgresql.o 451 [ - + ]:GNC 1034691 : Assert(bms_is_valid_set(a));
452 [ - + ]: 1034691 : Assert(bms_is_valid_set(b));
453 : :
454 : : /* Handle cases where either input is NULL */
4461 tgl@sss.pgh.pa.us 455 [ + + ]:CBC 1034691 : if (a == NULL)
456 : : {
457 [ + + ]: 880775 : if (b == NULL)
458 : 845517 : return BMS_EQUAL;
409 459 : 35258 : return BMS_SUBSET1;
460 : : }
4461 461 [ + + ]: 153916 : if (b == NULL)
409 462 : 74498 : return BMS_SUBSET2;
463 : :
464 : : /* Check common words */
4461 465 : 79418 : result = BMS_EQUAL; /* status so far */
466 : 79418 : shortlen = Min(a->nwords, b->nwords);
285 drowley@postgresql.o 467 :GNC 79418 : i = 0;
468 : : do
469 : : {
4326 bruce@momjian.us 470 :CBC 79418 : bitmapword aword = a->words[i];
471 : 79418 : bitmapword bword = b->words[i];
472 : :
4461 tgl@sss.pgh.pa.us 473 [ + + ]: 79418 : if ((aword & ~bword) != 0)
474 : : {
475 : : /* a is not a subset of b */
476 [ - + ]: 18777 : if (result == BMS_SUBSET1)
4461 tgl@sss.pgh.pa.us 477 :UBC 0 : return BMS_DIFFERENT;
4461 tgl@sss.pgh.pa.us 478 :CBC 18777 : result = BMS_SUBSET2;
479 : : }
480 [ + + ]: 79418 : if ((bword & ~aword) != 0)
481 : : {
482 : : /* b is not a subset of a */
483 [ + + ]: 18954 : if (result == BMS_SUBSET2)
484 : 17697 : return BMS_DIFFERENT;
485 : 1257 : result = BMS_SUBSET1;
486 : : }
285 drowley@postgresql.o 487 [ - + ]:GNC 61721 : } while (++i < shortlen);
488 : : /* Check extra words */
4461 tgl@sss.pgh.pa.us 489 [ - + ]:CBC 61721 : if (a->nwords > b->nwords)
490 : : {
491 : : /* if a has more words then a is not a subset of b */
285 drowley@postgresql.o 492 [ # # ]:UNC 0 : if (result == BMS_SUBSET1)
493 : 0 : return BMS_DIFFERENT;
494 : 0 : return BMS_SUBSET2;
495 : : }
4461 tgl@sss.pgh.pa.us 496 [ - + ]:CBC 61721 : else if (a->nwords < b->nwords)
497 : : {
498 : : /* if b has more words then b is not a subset of a */
285 drowley@postgresql.o 499 [ # # ]:UNC 0 : if (result == BMS_SUBSET2)
500 : 0 : return BMS_DIFFERENT;
501 : 0 : return BMS_SUBSET1;
502 : : }
4461 tgl@sss.pgh.pa.us 503 :CBC 61721 : return result;
504 : : }
505 : :
506 : : /*
507 : : * bms_is_member - is X a member of A?
508 : : */
509 : : bool
7555 bruce@momjian.us 510 : 6750767 : bms_is_member(int x, const Bitmapset *a)
511 : : {
512 : : int wordnum,
513 : : bitnum;
514 : :
88 drowley@postgresql.o 515 [ - + ]:GNC 6750767 : Assert(bms_is_valid_set(a));
516 : :
517 : : /* XXX better to just return false for x<0 ? */
7736 tgl@sss.pgh.pa.us 518 [ - + ]:CBC 6750767 : if (x < 0)
7572 tgl@sss.pgh.pa.us 519 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
7736 tgl@sss.pgh.pa.us 520 [ + + ]:CBC 6750767 : if (a == NULL)
521 : 3944327 : return false;
522 : :
523 : 2806440 : wordnum = WORDNUM(x);
524 : 2806440 : bitnum = BITNUM(x);
525 [ + + ]: 2806440 : if (wordnum >= a->nwords)
526 : 113 : return false;
527 [ + + ]: 2806327 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528 : 1882278 : return true;
529 : 924049 : 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
1845 tomas.vondra@postgre 539 : 2019 : bms_member_index(Bitmapset *a, int x)
540 : : {
541 : : int i;
542 : : int bitnum;
543 : : int wordnum;
544 : 2019 : int result = 0;
545 : : bitmapword mask;
546 : :
88 drowley@postgresql.o 547 [ - + ]:GNC 2019 : Assert(bms_is_valid_set(a));
548 : :
549 : : /* return -1 if not a member of the bitmap */
1845 tomas.vondra@postgre 550 [ - + ]:CBC 2019 : if (!bms_is_member(x, a))
1845 tomas.vondra@postgre 551 :UBC 0 : return -1;
552 : :
1845 tomas.vondra@postgre 553 :CBC 2019 : wordnum = WORDNUM(x);
554 : 2019 : bitnum = BITNUM(x);
555 : :
556 : : /* count bits in preceding words */
557 [ - + ]: 2019 : for (i = 0; i < wordnum; i++)
558 : : {
1845 tomas.vondra@postgre 559 :UBC 0 : bitmapword w = a->words[i];
560 : :
561 : : /* No need to count the bits in a zero word */
562 [ # # ]: 0 : if (w != 0)
563 : 0 : result += bmw_popcount(w);
564 : : }
565 : :
566 : : /*
567 : : * Now add bits of the last word, but only those before the item. We can
568 : : * do that by applying a mask and then using popcount again. To get
569 : : * 0-based index, we want to count only preceding bits, not the item
570 : : * itself, so we subtract 1.
571 : : */
1845 tomas.vondra@postgre 572 :CBC 2019 : mask = ((bitmapword) 1 << bitnum) - 1;
573 : 2019 : result += bmw_popcount(a->words[wordnum] & mask);
574 : :
575 : 2019 : return result;
576 : : }
577 : :
578 : : /*
579 : : * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
580 : : */
581 : : bool
7555 bruce@momjian.us 582 : 10271518 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
583 : : {
584 : : int shortlen;
585 : : int i;
586 : :
88 drowley@postgresql.o 587 [ - + ]:GNC 10271518 : Assert(bms_is_valid_set(a));
588 [ - + ]: 10271518 : Assert(bms_is_valid_set(b));
589 : :
590 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 591 [ + + + + ]:CBC 10271518 : if (a == NULL || b == NULL)
592 : 6115397 : return false;
593 : : /* Check words in common */
594 : 4156121 : shortlen = Min(a->nwords, b->nwords);
285 drowley@postgresql.o 595 :GNC 4156121 : i = 0;
596 : : do
597 : : {
7736 tgl@sss.pgh.pa.us 598 [ + + ]:CBC 4156121 : if ((a->words[i] & b->words[i]) != 0)
599 : 2492236 : return true;
285 drowley@postgresql.o 600 [ - + ]:GNC 1663885 : } while (++i < shortlen);
7736 tgl@sss.pgh.pa.us 601 :CBC 1663885 : return false;
602 : : }
603 : :
604 : : /*
605 : : * bms_overlap_list - does a set overlap an integer list?
606 : : */
607 : : bool
2575 rhodiumtoad@postgres 608 : 653 : bms_overlap_list(const Bitmapset *a, const List *b)
609 : : {
610 : : ListCell *lc;
611 : : int wordnum,
612 : : bitnum;
613 : :
88 drowley@postgresql.o 614 [ - + ]:GNC 653 : Assert(bms_is_valid_set(a));
615 : :
2575 rhodiumtoad@postgres 616 [ + + + + ]:CBC 653 : if (a == NULL || b == NIL)
617 : 584 : return false;
618 : :
619 [ + - + + : 129 : foreach(lc, b)
+ + ]
620 : : {
621 : 99 : int x = lfirst_int(lc);
622 : :
623 [ - + ]: 99 : if (x < 0)
2575 rhodiumtoad@postgres 624 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
2575 rhodiumtoad@postgres 625 :CBC 99 : wordnum = WORDNUM(x);
626 : 99 : bitnum = BITNUM(x);
627 [ + - ]: 99 : if (wordnum < a->nwords)
628 [ + + ]: 99 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
629 : 39 : return true;
630 : : }
631 : :
632 : 30 : return false;
633 : : }
634 : :
635 : : /*
636 : : * bms_nonempty_difference - do sets have a nonempty difference?
637 : : *
638 : : * i.e., are any members set in 'a' that are not also set in 'b'.
639 : : */
640 : : bool
7555 bruce@momjian.us 641 : 1376574 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
642 : : {
643 : : int i;
644 : :
88 drowley@postgresql.o 645 [ - + ]:GNC 1376574 : Assert(bms_is_valid_set(a));
646 [ - + ]: 1376574 : Assert(bms_is_valid_set(b));
647 : :
648 : : /* Handle cases where either input is NULL */
7595 tgl@sss.pgh.pa.us 649 [ + + ]:CBC 1376574 : if (a == NULL)
650 : 36 : return false;
651 [ - + ]: 1376538 : if (b == NULL)
409 tgl@sss.pgh.pa.us 652 :UBC 0 : return true;
653 : : /* if 'a' has more words then it must contain additional members */
285 drowley@postgresql.o 654 [ - + ]:GNC 1376538 : if (a->nwords > b->nwords)
285 drowley@postgresql.o 655 :UNC 0 : return true;
656 : : /* Check all 'a' members are set in 'b' */
285 drowley@postgresql.o 657 :GNC 1376538 : i = 0;
658 : : do
659 : : {
7559 bruce@momjian.us 660 [ + + ]:CBC 1376538 : if ((a->words[i] & ~b->words[i]) != 0)
7595 tgl@sss.pgh.pa.us 661 : 630451 : return true;
285 drowley@postgresql.o 662 [ - + ]:GNC 746087 : } while (++i < a->nwords);
7595 tgl@sss.pgh.pa.us 663 :CBC 746087 : return false;
664 : : }
665 : :
666 : : /*
667 : : * bms_singleton_member - return the sole integer member of set
668 : : *
669 : : * Raises error if |a| is not 1.
670 : : */
671 : : int
7555 bruce@momjian.us 672 : 8168 : bms_singleton_member(const Bitmapset *a)
673 : : {
7559 674 : 8168 : int result = -1;
675 : : int nwords;
676 : : int wordnum;
677 : :
88 drowley@postgresql.o 678 [ - + ]:GNC 8168 : Assert(bms_is_valid_set(a));
679 : :
7736 tgl@sss.pgh.pa.us 680 [ - + ]:CBC 8168 : if (a == NULL)
7572 tgl@sss.pgh.pa.us 681 [ # # ]:UBC 0 : elog(ERROR, "bitmapset is empty");
682 : :
7736 tgl@sss.pgh.pa.us 683 :CBC 8168 : nwords = a->nwords;
285 drowley@postgresql.o 684 :GNC 8168 : wordnum = 0;
685 : : do
686 : : {
7736 tgl@sss.pgh.pa.us 687 :CBC 8168 : bitmapword w = a->words[wordnum];
688 : :
689 [ + - ]: 8168 : if (w != 0)
690 : : {
691 [ + - - + ]: 8168 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
7572 tgl@sss.pgh.pa.us 692 [ # # ]:UBC 0 : elog(ERROR, "bitmapset has multiple members");
7736 tgl@sss.pgh.pa.us 693 :CBC 8168 : result = wordnum * BITS_PER_BITMAPWORD;
1885 694 : 8168 : result += bmw_rightmost_one_pos(w);
695 : : }
285 drowley@postgresql.o 696 [ - + ]:GNC 8168 : } while (++wordnum < nwords);
697 : :
698 : : /* we don't expect non-NULL sets to be empty */
699 [ - + ]: 8168 : Assert(result >= 0);
7736 tgl@sss.pgh.pa.us 700 :CBC 8168 : return result;
701 : : }
702 : :
703 : : /*
704 : : * bms_get_singleton_member
705 : : *
706 : : * Test whether the given set is a singleton.
707 : : * If so, set *member to the value of its sole member, and return true.
708 : : * If not, return false, without changing *member.
709 : : *
710 : : * This is more convenient and faster than calling bms_membership() and then
711 : : * bms_singleton_member(), if we don't care about distinguishing empty sets
712 : : * from multiple-member sets.
713 : : */
714 : : bool
3425 715 : 959530 : bms_get_singleton_member(const Bitmapset *a, int *member)
716 : : {
717 : 959530 : int result = -1;
718 : : int nwords;
719 : : int wordnum;
720 : :
88 drowley@postgresql.o 721 [ - + ]:GNC 959530 : Assert(bms_is_valid_set(a));
722 : :
3425 tgl@sss.pgh.pa.us 723 [ - + ]:CBC 959530 : if (a == NULL)
3425 tgl@sss.pgh.pa.us 724 :LBC (12) : return false;
725 : :
3425 tgl@sss.pgh.pa.us 726 :CBC 959530 : nwords = a->nwords;
285 drowley@postgresql.o 727 :GNC 959530 : wordnum = 0;
728 : : do
729 : : {
3425 tgl@sss.pgh.pa.us 730 :CBC 959530 : bitmapword w = a->words[wordnum];
731 : :
732 [ + - ]: 959530 : if (w != 0)
733 : : {
734 [ + - + + ]: 959530 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
735 : 169898 : return false;
736 : 789632 : result = wordnum * BITS_PER_BITMAPWORD;
1885 737 : 789632 : result += bmw_rightmost_one_pos(w);
738 : : }
285 drowley@postgresql.o 739 [ - + ]:GNC 789632 : } while (++wordnum < nwords);
740 : :
741 : : /* we don't expect non-NULL sets to be empty */
742 [ - + ]: 789632 : Assert(result >= 0);
3425 tgl@sss.pgh.pa.us 743 :CBC 789632 : *member = result;
744 : 789632 : return true;
745 : : }
746 : :
747 : : /*
748 : : * bms_num_members - count members of set
749 : : */
750 : : int
7555 bruce@momjian.us 751 : 1283624 : bms_num_members(const Bitmapset *a)
752 : : {
7559 753 : 1283624 : int result = 0;
754 : : int nwords;
755 : : int wordnum;
756 : :
88 drowley@postgresql.o 757 [ - + ]:GNC 1283624 : Assert(bms_is_valid_set(a));
758 : :
7736 tgl@sss.pgh.pa.us 759 [ + + ]:CBC 1283624 : if (a == NULL)
760 : 212836 : return 0;
761 : :
762 : 1070788 : nwords = a->nwords;
285 drowley@postgresql.o 763 :GNC 1070788 : wordnum = 0;
764 : : do
765 : : {
7736 tgl@sss.pgh.pa.us 766 :CBC 1070788 : bitmapword w = a->words[wordnum];
767 : :
768 : : /* No need to count the bits in a zero word */
1885 769 [ + - ]: 1070788 : if (w != 0)
770 : 1070788 : result += bmw_popcount(w);
285 drowley@postgresql.o 771 [ - + ]:GNC 1070788 : } while (++wordnum < nwords);
7736 tgl@sss.pgh.pa.us 772 :CBC 1070788 : return result;
773 : : }
774 : :
775 : : /*
776 : : * bms_membership - does a set have zero, one, or multiple members?
777 : : *
778 : : * This is faster than making an exact count with bms_num_members().
779 : : */
780 : : BMS_Membership
7555 bruce@momjian.us 781 : 683512 : bms_membership(const Bitmapset *a)
782 : : {
7736 tgl@sss.pgh.pa.us 783 : 683512 : BMS_Membership result = BMS_EMPTY_SET;
784 : : int nwords;
785 : : int wordnum;
786 : :
88 drowley@postgresql.o 787 [ - + ]:GNC 683512 : Assert(bms_is_valid_set(a));
788 : :
7736 tgl@sss.pgh.pa.us 789 [ + + ]:CBC 683512 : if (a == NULL)
790 : 247 : return BMS_EMPTY_SET;
791 : :
792 : 683265 : nwords = a->nwords;
285 drowley@postgresql.o 793 :GNC 683265 : wordnum = 0;
794 : : do
795 : : {
7736 tgl@sss.pgh.pa.us 796 :CBC 683265 : bitmapword w = a->words[wordnum];
797 : :
798 [ + - ]: 683265 : if (w != 0)
799 : : {
800 [ + - + + ]: 683265 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
801 : 166679 : return BMS_MULTIPLE;
802 : 516586 : result = BMS_SINGLETON;
803 : : }
285 drowley@postgresql.o 804 [ - + ]:GNC 516586 : } while (++wordnum < nwords);
7736 tgl@sss.pgh.pa.us 805 :CBC 516586 : return result;
806 : : }
807 : :
808 : :
809 : : /*
810 : : * bms_add_member - add a specified member to set
811 : : *
812 : : * 'a' is recycled when possible.
813 : : */
814 : : Bitmapset *
7555 bruce@momjian.us 815 : 9100596 : bms_add_member(Bitmapset *a, int x)
816 : : {
817 : : int wordnum,
818 : : bitnum;
819 : :
88 drowley@postgresql.o 820 [ - + ]:GNC 9100596 : Assert(bms_is_valid_set(a));
821 : :
7736 tgl@sss.pgh.pa.us 822 [ - + ]:CBC 9100596 : if (x < 0)
7572 tgl@sss.pgh.pa.us 823 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
7736 tgl@sss.pgh.pa.us 824 [ + + ]:CBC 9100596 : if (a == NULL)
825 : 4604953 : return bms_make_singleton(x);
826 : :
827 : 4495643 : wordnum = WORDNUM(x);
828 : 4495643 : bitnum = BITNUM(x);
829 : :
830 : : /* enlarge the set if necessary */
831 [ + + ]: 4495643 : if (wordnum >= a->nwords)
832 : : {
3849 heikki.linnakangas@i 833 : 90 : int oldnwords = a->nwords;
834 : : int i;
835 : :
836 : 90 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
837 : 90 : a->nwords = wordnum + 1;
838 : : /* zero out the enlarged portion */
285 drowley@postgresql.o 839 :GNC 90 : i = oldnwords;
840 : : do
841 : : {
3849 heikki.linnakangas@i 842 :CBC 234 : a->words[i] = 0;
285 drowley@postgresql.o 843 [ + + ]:GNC 234 : } while (++i < a->nwords);
844 : : }
845 : :
88 drowley@postgresql.o 846 :CBC 4495643 : a->words[wordnum] |= ((bitmapword) 1 << bitnum);
847 : :
848 : : #ifdef REALLOCATE_BITMAPSETS
849 : :
850 : : /*
851 : : * There's no guarantee that the repalloc returned a new pointer, so copy
852 : : * and free unconditionally here.
853 : : */
854 : : a = bms_copy_and_free(a);
855 : : #endif
856 : :
7736 tgl@sss.pgh.pa.us 857 : 4495643 : return a;
858 : : }
859 : :
860 : : /*
861 : : * bms_del_member - remove a specified member from set
862 : : *
863 : : * No error if x is not currently a member of set
864 : : *
865 : : * 'a' is recycled when possible.
866 : : */
867 : : Bitmapset *
7555 bruce@momjian.us 868 : 1092787 : bms_del_member(Bitmapset *a, int x)
869 : : {
870 : : int wordnum,
871 : : bitnum;
872 : :
88 drowley@postgresql.o 873 [ - + ]:GNC 1092787 : Assert(bms_is_valid_set(a));
874 : :
7736 tgl@sss.pgh.pa.us 875 [ - + ]:CBC 1092787 : if (x < 0)
7572 tgl@sss.pgh.pa.us 876 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
7736 tgl@sss.pgh.pa.us 877 [ + + ]:CBC 1092787 : if (a == NULL)
878 : 587001 : return NULL;
879 : :
880 : 505786 : wordnum = WORDNUM(x);
881 : 505786 : bitnum = BITNUM(x);
882 : :
883 : : #ifdef REALLOCATE_BITMAPSETS
884 : : a = bms_copy_and_free(a);
885 : : #endif
886 : :
887 : : /* member can't exist. Return 'a' unmodified */
285 drowley@postgresql.o 888 [ - + ]:GNC 505786 : if (unlikely(wordnum >= a->nwords))
285 drowley@postgresql.o 889 :UNC 0 : return a;
890 : :
285 drowley@postgresql.o 891 :GNC 505786 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
892 : :
893 : : /* when last word becomes empty, trim off all trailing empty words */
894 [ + + + - ]: 505786 : if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
895 : : {
896 : : /* find the last non-empty word and make that the new final word */
897 [ - + ]: 229231 : for (int i = wordnum - 1; i >= 0; i--)
898 : : {
285 drowley@postgresql.o 899 [ # # ]:UNC 0 : if (a->words[i] != 0)
900 : : {
901 : 0 : a->nwords = i + 1;
902 : 0 : return a;
903 : : }
904 : : }
905 : :
906 : : /* the set is now empty */
409 tgl@sss.pgh.pa.us 907 :CBC 229231 : pfree(a);
908 : 229231 : return NULL;
909 : : }
7736 910 : 276555 : return a;
911 : : }
912 : :
913 : : /*
914 : : * bms_add_members - like bms_union, but left input is recycled when possible
915 : : */
916 : : Bitmapset *
7555 bruce@momjian.us 917 : 6124257 : bms_add_members(Bitmapset *a, const Bitmapset *b)
918 : : {
919 : : Bitmapset *result;
920 : : const Bitmapset *other;
921 : : int otherlen;
922 : : int i;
923 : :
88 drowley@postgresql.o 924 [ - + ]:GNC 6124257 : Assert(bms_is_valid_set(a));
925 [ - + ]: 6124257 : Assert(bms_is_valid_set(b));
926 : :
927 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 928 [ + + ]:CBC 6124257 : if (a == NULL)
929 : 3232392 : return bms_copy(b);
930 [ + + ]: 2891865 : if (b == NULL)
931 : : {
932 : : #ifdef REALLOCATE_BITMAPSETS
933 : : a = bms_copy_and_free(a);
934 : : #endif
935 : :
936 : 1834069 : return a;
937 : : }
938 : : /* Identify shorter and longer input; copy the longer one if needed */
939 [ - + ]: 1057796 : if (a->nwords < b->nwords)
940 : : {
7736 tgl@sss.pgh.pa.us 941 :UBC 0 : result = bms_copy(b);
942 : 0 : other = a;
943 : : }
944 : : else
945 : : {
7736 tgl@sss.pgh.pa.us 946 :CBC 1057796 : result = a;
947 : 1057796 : other = b;
948 : : }
949 : : /* And union the shorter input into the result */
950 : 1057796 : otherlen = other->nwords;
285 drowley@postgresql.o 951 :GNC 1057796 : i = 0;
952 : : do
953 : : {
7736 tgl@sss.pgh.pa.us 954 :CBC 1057796 : result->words[i] |= other->words[i];
285 drowley@postgresql.o 955 [ - + ]:GNC 1057796 : } while (++i < otherlen);
7736 tgl@sss.pgh.pa.us 956 [ - + ]:CBC 1057796 : if (result != a)
7736 tgl@sss.pgh.pa.us 957 :UBC 0 : pfree(a);
958 : : #ifdef REALLOCATE_BITMAPSETS
959 : : else
960 : : result = bms_copy_and_free(result);
961 : : #endif
962 : :
7736 tgl@sss.pgh.pa.us 963 :CBC 1057796 : return result;
964 : : }
965 : :
966 : : /*
967 : : * bms_replace_members
968 : : * Remove all existing members from 'a' and repopulate the set with members
969 : : * from 'b', recycling 'a', when possible.
970 : : */
971 : : Bitmapset *
86 drowley@postgresql.o 972 :GNC 6450 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
973 : : {
974 : : int i;
975 : :
976 [ - + ]: 6450 : Assert(bms_is_valid_set(a));
977 [ - + ]: 6450 : Assert(bms_is_valid_set(b));
978 : :
979 [ - + ]: 6450 : if (a == NULL)
86 drowley@postgresql.o 980 :UNC 0 : return bms_copy(b);
86 drowley@postgresql.o 981 [ - + ]:GNC 6450 : if (b == NULL)
982 : : {
86 drowley@postgresql.o 983 :UNC 0 : pfree(a);
984 : 0 : return NULL;
985 : : }
986 : :
86 drowley@postgresql.o 987 [ - + ]:GNC 6450 : if (a->nwords < b->nwords)
86 drowley@postgresql.o 988 :UNC 0 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
989 : :
86 drowley@postgresql.o 990 :GNC 6450 : i = 0;
991 : : do
992 : : {
993 : 6450 : a->words[i] = b->words[i];
994 [ - + ]: 6450 : } while (++i < b->nwords);
995 : :
996 : 6450 : a->nwords = b->nwords;
997 : :
998 : : #ifdef REALLOCATE_BITMAPSETS
999 : :
1000 : : /*
1001 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1002 : : * and free unconditionally here.
1003 : : */
1004 : : a = bms_copy_and_free(a);
1005 : : #endif
1006 : :
1007 : 6450 : return a;
1008 : : }
1009 : :
1010 : : /*
1011 : : * bms_add_range
1012 : : * Add members in the range of 'lower' to 'upper' to the set.
1013 : : *
1014 : : * Note this could also be done by calling bms_add_member in a loop, however,
1015 : : * using this function will be faster when the range is large as we work at
1016 : : * the bitmapword level rather than at bit level.
1017 : : */
1018 : : Bitmapset *
2328 rhaas@postgresql.org 1019 :CBC 18232 : bms_add_range(Bitmapset *a, int lower, int upper)
1020 : : {
1021 : : int lwordnum,
1022 : : lbitnum,
1023 : : uwordnum,
1024 : : ushiftbits,
1025 : : wordnum;
1026 : :
88 drowley@postgresql.o 1027 [ - + ]:GNC 18232 : Assert(bms_is_valid_set(a));
1028 : :
1029 : : /* do nothing if nothing is called for, without further checking */
2085 alvherre@alvh.no-ip. 1030 [ + + ]:CBC 18232 : if (upper < lower)
1031 : : {
1032 : : #ifdef REALLOCATE_BITMAPSETS
1033 : : a = bms_copy_and_free(a);
1034 : : #endif
1035 : :
1036 : 14 : return a;
1037 : : }
1038 : :
tgl@sss.pgh.pa.us 1039 [ - + ]: 18218 : if (lower < 0)
2328 rhaas@postgresql.org 1040 [ # # ]:UBC 0 : elog(ERROR, "negative bitmapset member not allowed");
2328 rhaas@postgresql.org 1041 :CBC 18218 : uwordnum = WORDNUM(upper);
1042 : :
1043 [ + - ]: 18218 : if (a == NULL)
1044 : : {
1045 : 18218 : a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
518 tgl@sss.pgh.pa.us 1046 : 18218 : a->type = T_Bitmapset;
2328 rhaas@postgresql.org 1047 : 18218 : a->nwords = uwordnum + 1;
1048 : : }
2328 rhaas@postgresql.org 1049 [ # # ]:UBC 0 : else if (uwordnum >= a->nwords)
1050 : : {
1051 : 0 : int oldnwords = a->nwords;
1052 : : int i;
1053 : :
1054 : : /* ensure we have enough words to store the upper bit */
1055 : 0 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1056 : 0 : a->nwords = uwordnum + 1;
1057 : : /* zero out the enlarged portion */
285 drowley@postgresql.o 1058 :UNC 0 : i = oldnwords;
1059 : : do
1060 : : {
2328 rhaas@postgresql.org 1061 :UBC 0 : a->words[i] = 0;
285 drowley@postgresql.o 1062 [ # # ]:UNC 0 : } while (++i < a->nwords);
1063 : : }
1064 : :
2328 rhaas@postgresql.org 1065 :CBC 18218 : wordnum = lwordnum = WORDNUM(lower);
1066 : :
1067 : 18218 : lbitnum = BITNUM(lower);
1068 : 18218 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
1069 : :
1070 : : /*
1071 : : * Special case when lwordnum is the same as uwordnum we must perform the
1072 : : * upper and lower masking on the word.
1073 : : */
1074 [ + - ]: 18218 : if (lwordnum == uwordnum)
1075 : : {
1076 : 18218 : a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
2287 tgl@sss.pgh.pa.us 1077 : 18218 : & (~(bitmapword) 0) >> ushiftbits;
1078 : : }
1079 : : else
1080 : : {
1081 : : /* turn on lbitnum and all bits left of it */
2328 rhaas@postgresql.org 1082 :UBC 0 : a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1083 : :
1084 : : /* turn on all bits for any intermediate words */
1085 [ # # ]: 0 : while (wordnum < uwordnum)
1086 : 0 : a->words[wordnum++] = ~(bitmapword) 0;
1087 : :
1088 : : /* turn on upper's bit and all bits right of it. */
1089 : 0 : a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
1090 : : }
1091 : :
1092 : : #ifdef REALLOCATE_BITMAPSETS
1093 : :
1094 : : /*
1095 : : * There's no guarantee that the repalloc returned a new pointer, so copy
1096 : : * and free unconditionally here.
1097 : : */
1098 : : a = bms_copy_and_free(a);
1099 : : #endif
1100 : :
2328 rhaas@postgresql.org 1101 :CBC 18218 : return a;
1102 : : }
1103 : :
1104 : : /*
1105 : : * bms_int_members - like bms_intersect, but left input is recycled when
1106 : : * possible
1107 : : */
1108 : : Bitmapset *
7555 bruce@momjian.us 1109 : 270505 : bms_int_members(Bitmapset *a, const Bitmapset *b)
1110 : : {
1111 : : int lastnonzero;
1112 : : int shortlen;
1113 : : int i;
1114 : :
88 drowley@postgresql.o 1115 [ - + ]:GNC 270505 : Assert(bms_is_valid_set(a));
1116 [ - + ]: 270505 : Assert(bms_is_valid_set(b));
1117 : :
1118 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 1119 [ + + ]:CBC 270505 : if (a == NULL)
1120 : 12898 : return NULL;
1121 [ + + ]: 257607 : if (b == NULL)
1122 : : {
1123 : 2105 : pfree(a);
1124 : 2105 : return NULL;
1125 : : }
1126 : :
1127 : : /* Intersect b into a; we need never copy */
1128 : 255502 : shortlen = Min(a->nwords, b->nwords);
285 drowley@postgresql.o 1129 :GNC 255502 : lastnonzero = -1;
1130 : 255502 : i = 0;
1131 : : do
1132 : : {
7736 tgl@sss.pgh.pa.us 1133 :CBC 255502 : a->words[i] &= b->words[i];
1134 : :
285 drowley@postgresql.o 1135 [ + + ]:GNC 255502 : if (a->words[i] != 0)
1136 : 204908 : lastnonzero = i;
1137 [ - + ]: 255502 : } while (++i < shortlen);
1138 : :
1139 : : /* If we computed an empty result, we must return NULL */
1140 [ + + ]: 255502 : if (lastnonzero == -1)
1141 : : {
409 tgl@sss.pgh.pa.us 1142 :CBC 50594 : pfree(a);
1143 : 50594 : return NULL;
1144 : : }
1145 : :
1146 : : /* get rid of trailing zero words */
285 drowley@postgresql.o 1147 :GNC 204908 : a->nwords = lastnonzero + 1;
1148 : :
1149 : : #ifdef REALLOCATE_BITMAPSETS
1150 : : a = bms_copy_and_free(a);
1151 : : #endif
1152 : :
7736 tgl@sss.pgh.pa.us 1153 :CBC 204908 : return a;
1154 : : }
1155 : :
1156 : : /*
1157 : : * bms_del_members - delete members in 'a' that are set in 'b'. 'a' is
1158 : : * recycled when possible.
1159 : : */
1160 : : Bitmapset *
7555 bruce@momjian.us 1161 : 914009 : bms_del_members(Bitmapset *a, const Bitmapset *b)
1162 : : {
1163 : : int i;
1164 : :
88 drowley@postgresql.o 1165 [ - + ]:GNC 914009 : Assert(bms_is_valid_set(a));
1166 [ - + ]: 914009 : Assert(bms_is_valid_set(b));
1167 : :
1168 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 1169 [ + + ]:CBC 914009 : if (a == NULL)
1170 : 402710 : return NULL;
1171 [ + + ]: 511299 : if (b == NULL)
1172 : : {
1173 : : #ifdef REALLOCATE_BITMAPSETS
1174 : : a = bms_copy_and_free(a);
1175 : : #endif
1176 : :
88 drowley@postgresql.o 1177 :GNC 89455 : return a;
1178 : : }
1179 : :
1180 : : /* Remove b's bits from a; we need never copy */
285 1181 [ - + ]: 421844 : if (a->nwords > b->nwords)
1182 : : {
1183 : : /*
1184 : : * We'll never need to remove trailing zero words when 'a' has more
1185 : : * words than 'b'.
1186 : : */
285 drowley@postgresql.o 1187 :UNC 0 : i = 0;
1188 : : do
1189 : : {
1190 : 0 : a->words[i] &= ~b->words[i];
1191 [ # # ]: 0 : } while (++i < b->nwords);
1192 : : }
1193 : : else
1194 : : {
285 drowley@postgresql.o 1195 :GNC 421844 : int lastnonzero = -1;
1196 : :
1197 : : /* we may need to remove trailing zero words from the result. */
1198 : 421844 : i = 0;
1199 : : do
1200 : : {
1201 : 421844 : a->words[i] &= ~b->words[i];
1202 : :
1203 : : /* remember the last non-zero word */
1204 [ + + ]: 421844 : if (a->words[i] != 0)
1205 : 79751 : lastnonzero = i;
1206 [ - + ]: 421844 : } while (++i < a->nwords);
1207 : :
1208 : : /* check if 'a' has become empty */
1209 [ + + ]: 421844 : if (lastnonzero == -1)
1210 : : {
1211 : 342093 : pfree(a);
1212 : 342093 : return NULL;
1213 : : }
1214 : :
1215 : : /* trim off any trailing zero words */
1216 : 79751 : a->nwords = lastnonzero + 1;
1217 : : }
1218 : :
1219 : : #ifdef REALLOCATE_BITMAPSETS
1220 : : a = bms_copy_and_free(a);
1221 : : #endif
1222 : :
7736 tgl@sss.pgh.pa.us 1223 :CBC 79751 : return a;
1224 : : }
1225 : :
1226 : : /*
1227 : : * bms_join - like bms_union, but *either* input *may* be recycled
1228 : : */
1229 : : Bitmapset *
7555 bruce@momjian.us 1230 : 644751 : bms_join(Bitmapset *a, Bitmapset *b)
1231 : : {
1232 : : Bitmapset *result;
1233 : : Bitmapset *other;
1234 : : int otherlen;
1235 : : int i;
1236 : :
88 drowley@postgresql.o 1237 [ - + ]:GNC 644751 : Assert(bms_is_valid_set(a));
1238 [ - + ]: 644751 : Assert(bms_is_valid_set(b));
1239 : :
1240 : : /* Handle cases where either input is NULL */
7736 tgl@sss.pgh.pa.us 1241 [ + + ]:CBC 644751 : if (a == NULL)
1242 : : {
1243 : : #ifdef REALLOCATE_BITMAPSETS
1244 : : b = bms_copy_and_free(b);
1245 : : #endif
1246 : :
1247 : 287606 : return b;
1248 : : }
1249 [ + + ]: 357145 : if (b == NULL)
1250 : : {
1251 : : #ifdef REALLOCATE_BITMAPSETS
1252 : : a = bms_copy_and_free(a);
1253 : : #endif
1254 : :
88 drowley@postgresql.o 1255 : 81339 : return a;
1256 : : }
1257 : :
1258 : : /* Identify shorter and longer input; use longer one as result */
7736 tgl@sss.pgh.pa.us 1259 [ - + ]: 275806 : if (a->nwords < b->nwords)
1260 : : {
7736 tgl@sss.pgh.pa.us 1261 :UBC 0 : result = b;
1262 : 0 : other = a;
1263 : : }
1264 : : else
1265 : : {
7736 tgl@sss.pgh.pa.us 1266 :CBC 275806 : result = a;
1267 : 275806 : other = b;
1268 : : }
1269 : : /* And union the shorter input into the result */
1270 : 275806 : otherlen = other->nwords;
285 drowley@postgresql.o 1271 :GNC 275806 : i = 0;
1272 : : do
1273 : : {
7736 tgl@sss.pgh.pa.us 1274 :CBC 275806 : result->words[i] |= other->words[i];
285 drowley@postgresql.o 1275 [ - + ]:GNC 275806 : } while (++i < otherlen);
7736 tgl@sss.pgh.pa.us 1276 [ + - ]:CBC 275806 : if (other != result) /* pure paranoia */
1277 : 275806 : pfree(other);
1278 : :
1279 : : #ifdef REALLOCATE_BITMAPSETS
1280 : : result = bms_copy_and_free(result);
1281 : : #endif
1282 : :
1283 : 275806 : return result;
1284 : : }
1285 : :
1286 : : /*
1287 : : * bms_next_member - find next member of a set
1288 : : *
1289 : : * Returns smallest member greater than "prevbit", or -2 if there is none.
1290 : : * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
1291 : : *
1292 : : * This is intended as support for iterating through the members of a set.
1293 : : * The typical pattern is
1294 : : *
1295 : : * x = -1;
1296 : : * while ((x = bms_next_member(inputset, x)) >= 0)
1297 : : * process member x;
1298 : : *
1299 : : * Notice that when there are no more members, we return -2, not -1 as you
1300 : : * might expect. The rationale for that is to allow distinguishing the
1301 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1302 : : * It makes no difference in simple loop usage, but complex iteration logic
1303 : : * might need such an ability.
1304 : : */
1305 : : int
3425 1306 : 7610531 : bms_next_member(const Bitmapset *a, int prevbit)
1307 : : {
1308 : : int nwords;
1309 : : int wordnum;
1310 : : bitmapword mask;
1311 : :
88 drowley@postgresql.o 1312 [ - + ]:GNC 7610531 : Assert(bms_is_valid_set(a));
1313 : :
3425 tgl@sss.pgh.pa.us 1314 [ + + ]:CBC 7610531 : if (a == NULL)
1315 : 894241 : return -2;
1316 : 6716290 : nwords = a->nwords;
1317 : 6716290 : prevbit++;
1318 : 6716290 : mask = (~(bitmapword) 0) << BITNUM(prevbit);
1319 [ + + ]: 8819375 : for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1320 : : {
1321 : 6716290 : bitmapword w = a->words[wordnum];
1322 : :
1323 : : /* ignore bits before prevbit */
1324 : 6716290 : w &= mask;
1325 : :
1326 [ + + ]: 6716290 : if (w != 0)
1327 : : {
1328 : : int result;
1329 : :
1330 : 4613205 : result = wordnum * BITS_PER_BITMAPWORD;
1885 1331 : 4613205 : result += bmw_rightmost_one_pos(w);
3425 1332 : 4613205 : return result;
1333 : : }
1334 : :
1335 : : /* in subsequent words, consider all bits */
1336 : 2103085 : mask = (~(bitmapword) 0);
1337 : : }
1338 : 2103085 : return -2;
1339 : : }
1340 : :
1341 : : /*
1342 : : * bms_prev_member - find prev member of a set
1343 : : *
1344 : : * Returns largest member less than "prevbit", or -2 if there is none.
1345 : : * "prevbit" must NOT be more than one above the highest possible bit that can
1346 : : * be set at the Bitmapset at its current size.
1347 : : *
1348 : : * To ease finding the highest set bit for the initial loop, the special
1349 : : * prevbit value of -1 can be passed to have the function find the highest
1350 : : * valued member in the set.
1351 : : *
1352 : : * This is intended as support for iterating through the members of a set in
1353 : : * reverse. The typical pattern is
1354 : : *
1355 : : * x = -1;
1356 : : * while ((x = bms_prev_member(inputset, x)) >= 0)
1357 : : * process member x;
1358 : : *
1359 : : * Notice that when there are no more members, we return -2, not -1 as you
1360 : : * might expect. The rationale for that is to allow distinguishing the
1361 : : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1362 : : * It makes no difference in simple loop usage, but complex iteration logic
1363 : : * might need such an ability.
1364 : : */
1365 : :
1366 : : int
2199 alvherre@alvh.no-ip. 1367 : 9 : bms_prev_member(const Bitmapset *a, int prevbit)
1368 : : {
1369 : : int wordnum;
1370 : : int ushiftbits;
1371 : : bitmapword mask;
1372 : :
88 drowley@postgresql.o 1373 [ - + ]:GNC 9 : Assert(bms_is_valid_set(a));
1374 : :
1375 : : /*
1376 : : * If set is NULL or if there are no more bits to the right then we've
1377 : : * nothing to do.
1378 : : */
2199 alvherre@alvh.no-ip. 1379 [ + - - + ]:CBC 9 : if (a == NULL || prevbit == 0)
2199 alvherre@alvh.no-ip. 1380 :UBC 0 : return -2;
1381 : :
1382 : : /* transform -1 to the highest possible bit we could have set */
2199 alvherre@alvh.no-ip. 1383 [ - + ]:CBC 9 : if (prevbit == -1)
2199 alvherre@alvh.no-ip. 1384 :UBC 0 : prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1385 : : else
2199 alvherre@alvh.no-ip. 1386 :CBC 9 : prevbit--;
1387 : :
1388 : 9 : ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1389 : 9 : mask = (~(bitmapword) 0) >> ushiftbits;
1390 [ + + ]: 12 : for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1391 : : {
1392 : 9 : bitmapword w = a->words[wordnum];
1393 : :
1394 : : /* mask out bits left of prevbit */
1395 : 9 : w &= mask;
1396 : :
1397 [ + + ]: 9 : if (w != 0)
1398 : : {
1399 : : int result;
1400 : :
1401 : 6 : result = wordnum * BITS_PER_BITMAPWORD;
1885 tgl@sss.pgh.pa.us 1402 : 6 : result += bmw_leftmost_one_pos(w);
2199 alvherre@alvh.no-ip. 1403 : 6 : return result;
1404 : : }
1405 : :
1406 : : /* in subsequent words, consider all bits */
1407 : 3 : mask = (~(bitmapword) 0);
1408 : : }
1409 : 3 : return -2;
1410 : : }
1411 : :
1412 : : /*
1413 : : * bms_hash_value - compute a hash key for a Bitmapset
1414 : : */
1415 : : uint32
6885 tgl@sss.pgh.pa.us 1416 : 2649 : bms_hash_value(const Bitmapset *a)
1417 : : {
88 drowley@postgresql.o 1418 [ - + ]:GNC 2649 : Assert(bms_is_valid_set(a));
1419 : :
6162 tgl@sss.pgh.pa.us 1420 [ - + ]:CBC 2649 : if (a == NULL)
6885 tgl@sss.pgh.pa.us 1421 :UBC 0 : return 0; /* All empty sets hash to 0 */
6162 tgl@sss.pgh.pa.us 1422 :CBC 2649 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
285 drowley@postgresql.o 1423 :GNC 2649 : a->nwords * sizeof(bitmapword)));
1424 : : }
1425 : :
1426 : : /*
1427 : : * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
1428 : : *
1429 : : * Note: don't forget to specify bitmap_match as the match function!
1430 : : */
1431 : : uint32
1511 rhaas@postgresql.org 1432 :CBC 2649 : bitmap_hash(const void *key, Size keysize)
1433 : : {
1434 [ - + ]: 2649 : Assert(keysize == sizeof(Bitmapset *));
1435 : 2649 : return bms_hash_value(*((const Bitmapset *const *) key));
1436 : : }
1437 : :
1438 : : /*
1439 : : * bitmap_match - match function to use with bitmap_hash
1440 : : */
1441 : : int
1442 : 1602 : bitmap_match(const void *key1, const void *key2, Size keysize)
1443 : : {
1444 [ - + ]: 1602 : Assert(keysize == sizeof(Bitmapset *));
1445 : 1602 : return !bms_equal(*((const Bitmapset *const *) key1),
1446 : : *((const Bitmapset *const *) key2));
1447 : : }
|
