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, a NULL pointer is always
9 : * accepted by all operations to represent the empty set. (But beware
10 : * that this is not the only representation of the empty set. Use
11 : * bms_is_empty() in preference to testing for NULL.)
12 : *
13 : *
14 : * Copyright (c) 2003-2017, PostgreSQL Global Development Group
15 : *
16 : * IDENTIFICATION
17 : * src/backend/nodes/bitmapset.c
18 : *
19 : *-------------------------------------------------------------------------
20 : */
21 : #include "postgres.h"
22 :
23 : #include "access/hash.h"
24 : #include "nodes/pg_list.h"
25 :
26 :
27 : #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
28 : #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
29 :
30 : #define BITMAPSET_SIZE(nwords) \
31 : (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
32 :
33 : /*----------
34 : * This is a well-known cute trick for isolating the rightmost one-bit
35 : * in a word. It assumes two's complement arithmetic. Consider any
36 : * nonzero value, and focus attention on the rightmost one. The value is
37 : * then something like
38 : * xxxxxx10000
39 : * where x's are unspecified bits. The two's complement negative is formed
40 : * by inverting all the bits and adding one. Inversion gives
41 : * yyyyyy01111
42 : * where each y is the inverse of the corresponding x. Incrementing gives
43 : * yyyyyy10000
44 : * and then ANDing with the original value gives
45 : * 00000010000
46 : * This works for all cases except original value = zero, where of course
47 : * we get zero.
48 : *----------
49 : */
50 : #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
51 :
52 : #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x))
53 :
54 :
55 : /*
56 : * Lookup tables to avoid need for bit-by-bit groveling
57 : *
58 : * rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit
59 : * in a nonzero byte value x. The entry for x=0 is never used.
60 : *
61 : * number_of_ones[x] gives the number of one-bits (0-8) in a byte value x.
62 : *
63 : * We could make these tables larger and reduce the number of iterations
64 : * in the functions that use them, but bytewise shifts and masks are
65 : * especially fast on many machines, so working a byte at a time seems best.
66 : */
67 :
68 : static const uint8 rightmost_one_pos[256] = {
69 : 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
72 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
73 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
74 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
75 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
76 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
77 : 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
78 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
79 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
80 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
81 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
82 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
83 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
84 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
85 : };
86 :
87 : static const uint8 number_of_ones[256] = {
88 : 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
89 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
91 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
97 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
99 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
100 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
102 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103 : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
104 : };
105 :
106 :
107 : /*
108 : * bms_copy - make a palloc'd copy of a bitmapset
109 : */
110 : Bitmapset *
111 600710 : bms_copy(const Bitmapset *a)
112 : {
113 : Bitmapset *result;
114 : size_t size;
115 :
116 600710 : if (a == NULL)
117 329509 : return NULL;
118 271201 : size = BITMAPSET_SIZE(a->nwords);
119 271201 : result = (Bitmapset *) palloc(size);
120 271201 : memcpy(result, a, size);
121 271201 : return result;
122 : }
123 :
124 : /*
125 : * bms_equal - are two bitmapsets equal?
126 : *
127 : * This is logical not physical equality; in particular, a NULL pointer will
128 : * be reported as equal to a palloc'd value containing no members.
129 : */
130 : bool
131 193433 : bms_equal(const Bitmapset *a, const Bitmapset *b)
132 : {
133 : const Bitmapset *shorter;
134 : const Bitmapset *longer;
135 : int shortlen;
136 : int longlen;
137 : int i;
138 :
139 : /* Handle cases where either input is NULL */
140 193433 : if (a == NULL)
141 : {
142 102010 : if (b == NULL)
143 100224 : return true;
144 1786 : return bms_is_empty(b);
145 : }
146 91423 : else if (b == NULL)
147 391 : return bms_is_empty(a);
148 : /* Identify shorter and longer input */
149 91032 : if (a->nwords <= b->nwords)
150 : {
151 91032 : shorter = a;
152 91032 : longer = b;
153 : }
154 : else
155 : {
156 0 : shorter = b;
157 0 : longer = a;
158 : }
159 : /* And process */
160 91032 : shortlen = shorter->nwords;
161 135409 : for (i = 0; i < shortlen; i++)
162 : {
163 91032 : if (shorter->words[i] != longer->words[i])
164 46655 : return false;
165 : }
166 44377 : longlen = longer->nwords;
167 44377 : for (; i < longlen; i++)
168 : {
169 0 : if (longer->words[i] != 0)
170 0 : return false;
171 : }
172 44377 : return true;
173 : }
174 :
175 : /*
176 : * bms_make_singleton - build a bitmapset containing a single member
177 : */
178 : Bitmapset *
179 351634 : bms_make_singleton(int x)
180 : {
181 : Bitmapset *result;
182 : int wordnum,
183 : bitnum;
184 :
185 351634 : if (x < 0)
186 0 : elog(ERROR, "negative bitmapset member not allowed");
187 351634 : wordnum = WORDNUM(x);
188 351634 : bitnum = BITNUM(x);
189 351634 : result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
190 351634 : result->nwords = wordnum + 1;
191 351634 : result->words[wordnum] = ((bitmapword) 1 << bitnum);
192 351634 : return result;
193 : }
194 :
195 : /*
196 : * bms_free - free a bitmapset
197 : *
198 : * Same as pfree except for allowing NULL input
199 : */
200 : void
201 401884 : bms_free(Bitmapset *a)
202 : {
203 401884 : if (a)
204 172933 : pfree(a);
205 401884 : }
206 :
207 :
208 : /*
209 : * These operations all make a freshly palloc'd result,
210 : * leaving their inputs untouched
211 : */
212 :
213 :
214 : /*
215 : * bms_union - set union
216 : */
217 : Bitmapset *
218 159423 : bms_union(const Bitmapset *a, const Bitmapset *b)
219 : {
220 : Bitmapset *result;
221 : const Bitmapset *other;
222 : int otherlen;
223 : int i;
224 :
225 : /* Handle cases where either input is NULL */
226 159423 : if (a == NULL)
227 84144 : return bms_copy(b);
228 75279 : if (b == NULL)
229 38192 : return bms_copy(a);
230 : /* Identify shorter and longer input; copy the longer one */
231 37087 : if (a->nwords <= b->nwords)
232 : {
233 37087 : result = bms_copy(b);
234 37087 : other = a;
235 : }
236 : else
237 : {
238 0 : result = bms_copy(a);
239 0 : other = b;
240 : }
241 : /* And union the shorter input into the result */
242 37087 : otherlen = other->nwords;
243 74174 : for (i = 0; i < otherlen; i++)
244 37087 : result->words[i] |= other->words[i];
245 37087 : return result;
246 : }
247 :
248 : /*
249 : * bms_intersect - set intersection
250 : */
251 : Bitmapset *
252 80046 : bms_intersect(const Bitmapset *a, const Bitmapset *b)
253 : {
254 : Bitmapset *result;
255 : const Bitmapset *other;
256 : int resultlen;
257 : int i;
258 :
259 : /* Handle cases where either input is NULL */
260 80046 : if (a == NULL || b == NULL)
261 72883 : return NULL;
262 : /* Identify shorter and longer input; copy the shorter one */
263 7163 : if (a->nwords <= b->nwords)
264 : {
265 7163 : result = bms_copy(a);
266 7163 : other = b;
267 : }
268 : else
269 : {
270 0 : result = bms_copy(b);
271 0 : other = a;
272 : }
273 : /* And intersect the longer input with the result */
274 7163 : resultlen = result->nwords;
275 14326 : for (i = 0; i < resultlen; i++)
276 7163 : result->words[i] &= other->words[i];
277 7163 : return result;
278 : }
279 :
280 : /*
281 : * bms_difference - set difference (ie, A without members of B)
282 : */
283 : Bitmapset *
284 3154 : bms_difference(const Bitmapset *a, const Bitmapset *b)
285 : {
286 : Bitmapset *result;
287 : int shortlen;
288 : int i;
289 :
290 : /* Handle cases where either input is NULL */
291 3154 : if (a == NULL)
292 27 : return NULL;
293 3127 : if (b == NULL)
294 0 : return bms_copy(a);
295 : /* Copy the left input */
296 3127 : result = bms_copy(a);
297 : /* And remove b's bits from result */
298 3127 : shortlen = Min(a->nwords, b->nwords);
299 6254 : for (i = 0; i < shortlen; i++)
300 3127 : result->words[i] &= ~b->words[i];
301 3127 : return result;
302 : }
303 :
304 : /*
305 : * bms_is_subset - is A a subset of B?
306 : */
307 : bool
308 459527 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
309 : {
310 : int shortlen;
311 : int longlen;
312 : int i;
313 :
314 : /* Handle cases where either input is NULL */
315 459527 : if (a == NULL)
316 26450 : return true; /* empty set is a subset of anything */
317 433077 : if (b == NULL)
318 8560 : return bms_is_empty(a);
319 : /* Check common words */
320 424517 : shortlen = Min(a->nwords, b->nwords);
321 668069 : for (i = 0; i < shortlen; i++)
322 : {
323 424517 : if ((a->words[i] & ~b->words[i]) != 0)
324 180965 : return false;
325 : }
326 : /* Check extra words */
327 243552 : if (a->nwords > b->nwords)
328 : {
329 1141 : longlen = a->nwords;
330 1141 : for (; i < longlen; i++)
331 : {
332 1141 : if (a->words[i] != 0)
333 1141 : return false;
334 : }
335 : }
336 242411 : return true;
337 : }
338 :
339 : /*
340 : * bms_subset_compare - compare A and B for equality/subset relationships
341 : *
342 : * This is more efficient than testing bms_is_subset in both directions.
343 : */
344 : BMS_Comparison
345 57870 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
346 : {
347 : BMS_Comparison result;
348 : int shortlen;
349 : int longlen;
350 : int i;
351 :
352 : /* Handle cases where either input is NULL */
353 57870 : if (a == NULL)
354 : {
355 49143 : if (b == NULL)
356 47275 : return BMS_EQUAL;
357 1868 : return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
358 : }
359 8727 : if (b == NULL)
360 3928 : return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
361 : /* Check common words */
362 4799 : result = BMS_EQUAL; /* status so far */
363 4799 : shortlen = Min(a->nwords, b->nwords);
364 8742 : for (i = 0; i < shortlen; i++)
365 : {
366 4799 : bitmapword aword = a->words[i];
367 4799 : bitmapword bword = b->words[i];
368 :
369 4799 : if ((aword & ~bword) != 0)
370 : {
371 : /* a is not a subset of b */
372 901 : if (result == BMS_SUBSET1)
373 0 : return BMS_DIFFERENT;
374 901 : result = BMS_SUBSET2;
375 : }
376 4799 : if ((bword & ~aword) != 0)
377 : {
378 : /* b is not a subset of a */
379 942 : if (result == BMS_SUBSET2)
380 856 : return BMS_DIFFERENT;
381 86 : result = BMS_SUBSET1;
382 : }
383 : }
384 : /* Check extra words */
385 3943 : if (a->nwords > b->nwords)
386 : {
387 0 : longlen = a->nwords;
388 0 : for (; i < longlen; i++)
389 : {
390 0 : if (a->words[i] != 0)
391 : {
392 : /* a is not a subset of b */
393 0 : if (result == BMS_SUBSET1)
394 0 : return BMS_DIFFERENT;
395 0 : result = BMS_SUBSET2;
396 : }
397 : }
398 : }
399 3943 : else if (a->nwords < b->nwords)
400 : {
401 0 : longlen = b->nwords;
402 0 : for (; i < longlen; i++)
403 : {
404 0 : if (b->words[i] != 0)
405 : {
406 : /* b is not a subset of a */
407 0 : if (result == BMS_SUBSET2)
408 0 : return BMS_DIFFERENT;
409 0 : result = BMS_SUBSET1;
410 : }
411 : }
412 : }
413 3943 : return result;
414 : }
415 :
416 : /*
417 : * bms_is_member - is X a member of A?
418 : */
419 : bool
420 156424 : bms_is_member(int x, const Bitmapset *a)
421 : {
422 : int wordnum,
423 : bitnum;
424 :
425 : /* XXX better to just return false for x<0 ? */
426 156424 : if (x < 0)
427 0 : elog(ERROR, "negative bitmapset member not allowed");
428 156424 : if (a == NULL)
429 70157 : return false;
430 86267 : wordnum = WORDNUM(x);
431 86267 : bitnum = BITNUM(x);
432 86267 : if (wordnum >= a->nwords)
433 0 : return false;
434 86267 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
435 53241 : return true;
436 33026 : return false;
437 : }
438 :
439 : /*
440 : * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
441 : */
442 : bool
443 495929 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
444 : {
445 : int shortlen;
446 : int i;
447 :
448 : /* Handle cases where either input is NULL */
449 495929 : if (a == NULL || b == NULL)
450 214879 : return false;
451 : /* Check words in common */
452 281050 : shortlen = Min(a->nwords, b->nwords);
453 400793 : for (i = 0; i < shortlen; i++)
454 : {
455 281050 : if ((a->words[i] & b->words[i]) != 0)
456 161307 : return true;
457 : }
458 119743 : return false;
459 : }
460 :
461 : /*
462 : * bms_overlap_list - does a set overlap an integer list?
463 : */
464 : bool
465 159 : bms_overlap_list(const Bitmapset *a, const List *b)
466 : {
467 : ListCell *lc;
468 : int wordnum,
469 : bitnum;
470 :
471 159 : if (a == NULL || b == NIL)
472 138 : return false;
473 :
474 41 : foreach(lc, b)
475 : {
476 31 : int x = lfirst_int(lc);
477 :
478 31 : if (x < 0)
479 0 : elog(ERROR, "negative bitmapset member not allowed");
480 31 : wordnum = WORDNUM(x);
481 31 : bitnum = BITNUM(x);
482 31 : if (wordnum < a->nwords)
483 31 : if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
484 11 : return true;
485 : }
486 :
487 10 : return false;
488 : }
489 :
490 : /*
491 : * bms_nonempty_difference - do sets have a nonempty difference?
492 : */
493 : bool
494 28946 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
495 : {
496 : int shortlen;
497 : int i;
498 :
499 : /* Handle cases where either input is NULL */
500 28946 : if (a == NULL)
501 12 : return false;
502 28934 : if (b == NULL)
503 0 : return !bms_is_empty(a);
504 : /* Check words in common */
505 28934 : shortlen = Min(a->nwords, b->nwords);
506 36878 : for (i = 0; i < shortlen; i++)
507 : {
508 28934 : if ((a->words[i] & ~b->words[i]) != 0)
509 20990 : return true;
510 : }
511 : /* Check extra words in a */
512 7944 : for (; i < a->nwords; i++)
513 : {
514 0 : if (a->words[i] != 0)
515 0 : return true;
516 : }
517 7944 : return false;
518 : }
519 :
520 : /*
521 : * bms_singleton_member - return the sole integer member of set
522 : *
523 : * Raises error if |a| is not 1.
524 : */
525 : int
526 17076 : bms_singleton_member(const Bitmapset *a)
527 : {
528 17076 : int result = -1;
529 : int nwords;
530 : int wordnum;
531 :
532 17076 : if (a == NULL)
533 0 : elog(ERROR, "bitmapset is empty");
534 17076 : nwords = a->nwords;
535 34152 : for (wordnum = 0; wordnum < nwords; wordnum++)
536 : {
537 17076 : bitmapword w = a->words[wordnum];
538 :
539 17076 : if (w != 0)
540 : {
541 17076 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
542 0 : elog(ERROR, "bitmapset has multiple members");
543 17076 : result = wordnum * BITS_PER_BITMAPWORD;
544 34611 : while ((w & 255) == 0)
545 : {
546 459 : w >>= 8;
547 459 : result += 8;
548 : }
549 17076 : result += rightmost_one_pos[w & 255];
550 : }
551 : }
552 17076 : if (result < 0)
553 0 : elog(ERROR, "bitmapset is empty");
554 17076 : return result;
555 : }
556 :
557 : /*
558 : * bms_get_singleton_member
559 : *
560 : * Test whether the given set is a singleton.
561 : * If so, set *member to the value of its sole member, and return TRUE.
562 : * If not, return FALSE, without changing *member.
563 : *
564 : * This is more convenient and faster than calling bms_membership() and then
565 : * bms_singleton_member(), if we don't care about distinguishing empty sets
566 : * from multiple-member sets.
567 : */
568 : bool
569 21435 : bms_get_singleton_member(const Bitmapset *a, int *member)
570 : {
571 21435 : int result = -1;
572 : int nwords;
573 : int wordnum;
574 :
575 21435 : if (a == NULL)
576 0 : return false;
577 21435 : nwords = a->nwords;
578 38846 : for (wordnum = 0; wordnum < nwords; wordnum++)
579 : {
580 21435 : bitmapword w = a->words[wordnum];
581 :
582 21435 : if (w != 0)
583 : {
584 21435 : if (result >= 0 || HAS_MULTIPLE_ONES(w))
585 4024 : return false;
586 17411 : result = wordnum * BITS_PER_BITMAPWORD;
587 35938 : while ((w & 255) == 0)
588 : {
589 1116 : w >>= 8;
590 1116 : result += 8;
591 : }
592 17411 : result += rightmost_one_pos[w & 255];
593 : }
594 : }
595 17411 : if (result < 0)
596 0 : return false;
597 17411 : *member = result;
598 17411 : return true;
599 : }
600 :
601 : /*
602 : * bms_num_members - count members of set
603 : */
604 : int
605 5647 : bms_num_members(const Bitmapset *a)
606 : {
607 5647 : int result = 0;
608 : int nwords;
609 : int wordnum;
610 :
611 5647 : if (a == NULL)
612 0 : return 0;
613 5647 : nwords = a->nwords;
614 11294 : for (wordnum = 0; wordnum < nwords; wordnum++)
615 : {
616 5647 : bitmapword w = a->words[wordnum];
617 :
618 : /* we assume here that bitmapword is an unsigned type */
619 18466 : while (w != 0)
620 : {
621 7172 : result += number_of_ones[w & 255];
622 7172 : w >>= 8;
623 : }
624 : }
625 5647 : return result;
626 : }
627 :
628 : /*
629 : * bms_membership - does a set have zero, one, or multiple members?
630 : *
631 : * This is faster than making an exact count with bms_num_members().
632 : */
633 : BMS_Membership
634 121357 : bms_membership(const Bitmapset *a)
635 : {
636 121357 : BMS_Membership result = BMS_EMPTY_SET;
637 : int nwords;
638 : int wordnum;
639 :
640 121357 : if (a == NULL)
641 13966 : return BMS_EMPTY_SET;
642 107391 : nwords = a->nwords;
643 188931 : for (wordnum = 0; wordnum < nwords; wordnum++)
644 : {
645 107391 : bitmapword w = a->words[wordnum];
646 :
647 107391 : if (w != 0)
648 : {
649 107391 : if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
650 25851 : return BMS_MULTIPLE;
651 81540 : result = BMS_SINGLETON;
652 : }
653 : }
654 81540 : return result;
655 : }
656 :
657 : /*
658 : * bms_is_empty - is a set empty?
659 : *
660 : * This is even faster than bms_membership().
661 : */
662 : bool
663 408307 : bms_is_empty(const Bitmapset *a)
664 : {
665 : int nwords;
666 : int wordnum;
667 :
668 408307 : if (a == NULL)
669 215202 : return true;
670 193105 : nwords = a->nwords;
671 220399 : for (wordnum = 0; wordnum < nwords; wordnum++)
672 : {
673 193105 : bitmapword w = a->words[wordnum];
674 :
675 193105 : if (w != 0)
676 165811 : return false;
677 : }
678 27294 : return true;
679 : }
680 :
681 :
682 : /*
683 : * These operations all "recycle" their non-const inputs, ie, either
684 : * return the modified input or pfree it if it can't hold the result.
685 : *
686 : * These should generally be used in the style
687 : *
688 : * foo = bms_add_member(foo, x);
689 : */
690 :
691 :
692 : /*
693 : * bms_add_member - add a specified member to set
694 : *
695 : * Input set is modified or recycled!
696 : */
697 : Bitmapset *
698 471112 : bms_add_member(Bitmapset *a, int x)
699 : {
700 : int wordnum,
701 : bitnum;
702 :
703 471112 : if (x < 0)
704 0 : elog(ERROR, "negative bitmapset member not allowed");
705 471112 : if (a == NULL)
706 285173 : return bms_make_singleton(x);
707 185939 : wordnum = WORDNUM(x);
708 185939 : bitnum = BITNUM(x);
709 :
710 : /* enlarge the set if necessary */
711 185939 : if (wordnum >= a->nwords)
712 : {
713 3365 : int oldnwords = a->nwords;
714 : int i;
715 :
716 3365 : a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
717 3365 : a->nwords = wordnum + 1;
718 : /* zero out the enlarged portion */
719 6730 : for (i = oldnwords; i < a->nwords; i++)
720 3365 : a->words[i] = 0;
721 : }
722 :
723 185939 : a->words[wordnum] |= ((bitmapword) 1 << bitnum);
724 185939 : return a;
725 : }
726 :
727 : /*
728 : * bms_del_member - remove a specified member from set
729 : *
730 : * No error if x is not currently a member of set
731 : *
732 : * Input set is modified in-place!
733 : */
734 : Bitmapset *
735 53568 : bms_del_member(Bitmapset *a, int x)
736 : {
737 : int wordnum,
738 : bitnum;
739 :
740 53568 : if (x < 0)
741 0 : elog(ERROR, "negative bitmapset member not allowed");
742 53568 : if (a == NULL)
743 30614 : return NULL;
744 22954 : wordnum = WORDNUM(x);
745 22954 : bitnum = BITNUM(x);
746 22954 : if (wordnum < a->nwords)
747 22954 : a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
748 22954 : return a;
749 : }
750 :
751 : /*
752 : * bms_add_members - like bms_union, but left input is recycled
753 : */
754 : Bitmapset *
755 230450 : bms_add_members(Bitmapset *a, const Bitmapset *b)
756 : {
757 : Bitmapset *result;
758 : const Bitmapset *other;
759 : int otherlen;
760 : int i;
761 :
762 : /* Handle cases where either input is NULL */
763 230450 : if (a == NULL)
764 160654 : return bms_copy(b);
765 69796 : if (b == NULL)
766 40415 : return a;
767 : /* Identify shorter and longer input; copy the longer one if needed */
768 29381 : if (a->nwords < b->nwords)
769 : {
770 0 : result = bms_copy(b);
771 0 : other = a;
772 : }
773 : else
774 : {
775 29381 : result = a;
776 29381 : other = b;
777 : }
778 : /* And union the shorter input into the result */
779 29381 : otherlen = other->nwords;
780 58762 : for (i = 0; i < otherlen; i++)
781 29381 : result->words[i] |= other->words[i];
782 29381 : if (result != a)
783 0 : pfree(a);
784 29381 : return result;
785 : }
786 :
787 : /*
788 : * bms_int_members - like bms_intersect, but left input is recycled
789 : */
790 : Bitmapset *
791 5352 : bms_int_members(Bitmapset *a, const Bitmapset *b)
792 : {
793 : int shortlen;
794 : int i;
795 :
796 : /* Handle cases where either input is NULL */
797 5352 : if (a == NULL)
798 3405 : return NULL;
799 1947 : if (b == NULL)
800 : {
801 1 : pfree(a);
802 1 : return NULL;
803 : }
804 : /* Intersect b into a; we need never copy */
805 1946 : shortlen = Min(a->nwords, b->nwords);
806 3892 : for (i = 0; i < shortlen; i++)
807 1946 : a->words[i] &= b->words[i];
808 1946 : for (; i < a->nwords; i++)
809 0 : a->words[i] = 0;
810 1946 : return a;
811 : }
812 :
813 : /*
814 : * bms_del_members - like bms_difference, but left input is recycled
815 : */
816 : Bitmapset *
817 45452 : bms_del_members(Bitmapset *a, const Bitmapset *b)
818 : {
819 : int shortlen;
820 : int i;
821 :
822 : /* Handle cases where either input is NULL */
823 45452 : if (a == NULL)
824 20517 : return NULL;
825 24935 : if (b == NULL)
826 10651 : return a;
827 : /* Remove b's bits from a; we need never copy */
828 14284 : shortlen = Min(a->nwords, b->nwords);
829 28568 : for (i = 0; i < shortlen; i++)
830 14284 : a->words[i] &= ~b->words[i];
831 14284 : return a;
832 : }
833 :
834 : /*
835 : * bms_join - like bms_union, but *both* inputs are recycled
836 : */
837 : Bitmapset *
838 24401 : bms_join(Bitmapset *a, Bitmapset *b)
839 : {
840 : Bitmapset *result;
841 : Bitmapset *other;
842 : int otherlen;
843 : int i;
844 :
845 : /* Handle cases where either input is NULL */
846 24401 : if (a == NULL)
847 16903 : return b;
848 7498 : if (b == NULL)
849 2453 : return a;
850 : /* Identify shorter and longer input; use longer one as result */
851 5045 : if (a->nwords < b->nwords)
852 : {
853 0 : result = b;
854 0 : other = a;
855 : }
856 : else
857 : {
858 5045 : result = a;
859 5045 : other = b;
860 : }
861 : /* And union the shorter input into the result */
862 5045 : otherlen = other->nwords;
863 10090 : for (i = 0; i < otherlen; i++)
864 5045 : result->words[i] |= other->words[i];
865 5045 : if (other != result) /* pure paranoia */
866 5045 : pfree(other);
867 5045 : return result;
868 : }
869 :
870 : /*
871 : * bms_first_member - find and remove first member of a set
872 : *
873 : * Returns -1 if set is empty. NB: set is destructively modified!
874 : *
875 : * This is intended as support for iterating through the members of a set.
876 : * The typical pattern is
877 : *
878 : * while ((x = bms_first_member(inputset)) >= 0)
879 : * process member x;
880 : *
881 : * CAUTION: this destroys the content of "inputset". If the set must
882 : * not be modified, use bms_next_member instead.
883 : */
884 : int
885 50878 : bms_first_member(Bitmapset *a)
886 : {
887 : int nwords;
888 : int wordnum;
889 :
890 50878 : if (a == NULL)
891 8078 : return -1;
892 42800 : nwords = a->nwords;
893 52593 : for (wordnum = 0; wordnum < nwords; wordnum++)
894 : {
895 44210 : bitmapword w = a->words[wordnum];
896 :
897 44210 : if (w != 0)
898 : {
899 : int result;
900 :
901 34417 : w = RIGHTMOST_ONE(w);
902 34417 : a->words[wordnum] &= ~w;
903 :
904 34417 : result = wordnum * BITS_PER_BITMAPWORD;
905 105677 : while ((w & 255) == 0)
906 : {
907 36843 : w >>= 8;
908 36843 : result += 8;
909 : }
910 34417 : result += rightmost_one_pos[w & 255];
911 34417 : return result;
912 : }
913 : }
914 8383 : return -1;
915 : }
916 :
917 : /*
918 : * bms_next_member - find next member of a set
919 : *
920 : * Returns smallest member greater than "prevbit", or -2 if there is none.
921 : * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
922 : *
923 : * This is intended as support for iterating through the members of a set.
924 : * The typical pattern is
925 : *
926 : * x = -1;
927 : * while ((x = bms_next_member(inputset, x)) >= 0)
928 : * process member x;
929 : *
930 : * Notice that when there are no more members, we return -2, not -1 as you
931 : * might expect. The rationale for that is to allow distinguishing the
932 : * loop-not-started state (x == -1) from the loop-completed state (x == -2).
933 : * It makes no difference in simple loop usage, but complex iteration logic
934 : * might need such an ability.
935 : */
936 : int
937 74414 : bms_next_member(const Bitmapset *a, int prevbit)
938 : {
939 : int nwords;
940 : int wordnum;
941 : bitmapword mask;
942 :
943 74414 : if (a == NULL)
944 8807 : return -2;
945 65607 : nwords = a->nwords;
946 65607 : prevbit++;
947 65607 : mask = (~(bitmapword) 0) << BITNUM(prevbit);
948 81174 : for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
949 : {
950 65625 : bitmapword w = a->words[wordnum];
951 :
952 : /* ignore bits before prevbit */
953 65625 : w &= mask;
954 :
955 65625 : if (w != 0)
956 : {
957 : int result;
958 :
959 50058 : result = wordnum * BITS_PER_BITMAPWORD;
960 149993 : while ((w & 255) == 0)
961 : {
962 49877 : w >>= 8;
963 49877 : result += 8;
964 : }
965 50058 : result += rightmost_one_pos[w & 255];
966 50058 : return result;
967 : }
968 :
969 : /* in subsequent words, consider all bits */
970 15567 : mask = (~(bitmapword) 0);
971 : }
972 15549 : return -2;
973 : }
974 :
975 : /*
976 : * bms_hash_value - compute a hash key for a Bitmapset
977 : *
978 : * Note: we must ensure that any two bitmapsets that are bms_equal() will
979 : * hash to the same value; in practice this means that trailing all-zero
980 : * words must not affect the result. Hence we strip those before applying
981 : * hash_any().
982 : */
983 : uint32
984 240 : bms_hash_value(const Bitmapset *a)
985 : {
986 : int lastword;
987 :
988 240 : if (a == NULL)
989 0 : return 0; /* All empty sets hash to 0 */
990 480 : for (lastword = a->nwords; --lastword >= 0;)
991 : {
992 240 : if (a->words[lastword] != 0)
993 240 : break;
994 : }
995 240 : if (lastword < 0)
996 0 : return 0; /* All empty sets hash to 0 */
997 240 : return DatumGetUInt32(hash_any((const unsigned char *) a->words,
998 : (lastword + 1) * sizeof(bitmapword)));
999 : }
|
