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