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 *
bms_copy(const Bitmapset * a)111 bms_copy(const Bitmapset *a)
112 {
113 Bitmapset *result;
114 size_t size;
115
116 if (a == NULL)
117 return NULL;
118 size = BITMAPSET_SIZE(a->nwords);
119 result = (Bitmapset *) palloc(size);
120 memcpy(result, a, size);
121 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
bms_equal(const Bitmapset * a,const Bitmapset * b)131 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 if (a == NULL)
141 {
142 if (b == NULL)
143 return true;
144 return bms_is_empty(b);
145 }
146 else if (b == NULL)
147 return bms_is_empty(a);
148 /* Identify shorter and longer input */
149 if (a->nwords <= b->nwords)
150 {
151 shorter = a;
152 longer = b;
153 }
154 else
155 {
156 shorter = b;
157 longer = a;
158 }
159 /* And process */
160 shortlen = shorter->nwords;
161 for (i = 0; i < shortlen; i++)
162 {
163 if (shorter->words[i] != longer->words[i])
164 return false;
165 }
166 longlen = longer->nwords;
167 for (; i < longlen; i++)
168 {
169 if (longer->words[i] != 0)
170 return false;
171 }
172 return true;
173 }
174
175 /*
176 * bms_make_singleton - build a bitmapset containing a single member
177 */
178 Bitmapset *
bms_make_singleton(int x)179 bms_make_singleton(int x)
180 {
181 Bitmapset *result;
182 int wordnum,
183 bitnum;
184
185 if (x < 0)
186 elog(ERROR, "negative bitmapset member not allowed");
187 wordnum = WORDNUM(x);
188 bitnum = BITNUM(x);
189 result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
190 result->nwords = wordnum + 1;
191 result->words[wordnum] = ((bitmapword) 1 << bitnum);
192 return result;
193 }
194
195 /*
196 * bms_free - free a bitmapset
197 *
198 * Same as pfree except for allowing NULL input
199 */
200 void
bms_free(Bitmapset * a)201 bms_free(Bitmapset *a)
202 {
203 if (a)
204 pfree(a);
205 }
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 *
bms_union(const Bitmapset * a,const Bitmapset * b)218 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 if (a == NULL)
227 return bms_copy(b);
228 if (b == NULL)
229 return bms_copy(a);
230 /* Identify shorter and longer input; copy the longer one */
231 if (a->nwords <= b->nwords)
232 {
233 result = bms_copy(b);
234 other = a;
235 }
236 else
237 {
238 result = bms_copy(a);
239 other = b;
240 }
241 /* And union the shorter input into the result */
242 otherlen = other->nwords;
243 for (i = 0; i < otherlen; i++)
244 result->words[i] |= other->words[i];
245 return result;
246 }
247
248 /*
249 * bms_intersect - set intersection
250 */
251 Bitmapset *
bms_intersect(const Bitmapset * a,const Bitmapset * b)252 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 if (a == NULL || b == NULL)
261 return NULL;
262 /* Identify shorter and longer input; copy the shorter one */
263 if (a->nwords <= b->nwords)
264 {
265 result = bms_copy(a);
266 other = b;
267 }
268 else
269 {
270 result = bms_copy(b);
271 other = a;
272 }
273 /* And intersect the longer input with the result */
274 resultlen = result->nwords;
275 for (i = 0; i < resultlen; i++)
276 result->words[i] &= other->words[i];
277 return result;
278 }
279
280 /*
281 * bms_difference - set difference (ie, A without members of B)
282 */
283 Bitmapset *
bms_difference(const Bitmapset * a,const Bitmapset * b)284 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 if (a == NULL)
292 return NULL;
293 if (b == NULL)
294 return bms_copy(a);
295 /* Copy the left input */
296 result = bms_copy(a);
297 /* And remove b's bits from result */
298 shortlen = Min(a->nwords, b->nwords);
299 for (i = 0; i < shortlen; i++)
300 result->words[i] &= ~b->words[i];
301 return result;
302 }
303
304 /*
305 * bms_is_subset - is A a subset of B?
306 */
307 bool
bms_is_subset(const Bitmapset * a,const Bitmapset * b)308 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 if (a == NULL)
316 return true; /* empty set is a subset of anything */
317 if (b == NULL)
318 return bms_is_empty(a);
319 /* Check common words */
320 shortlen = Min(a->nwords, b->nwords);
321 for (i = 0; i < shortlen; i++)
322 {
323 if ((a->words[i] & ~b->words[i]) != 0)
324 return false;
325 }
326 /* Check extra words */
327 if (a->nwords > b->nwords)
328 {
329 longlen = a->nwords;
330 for (; i < longlen; i++)
331 {
332 if (a->words[i] != 0)
333 return false;
334 }
335 }
336 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
bms_subset_compare(const Bitmapset * a,const Bitmapset * b)345 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 if (a == NULL)
354 {
355 if (b == NULL)
356 return BMS_EQUAL;
357 return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
358 }
359 if (b == NULL)
360 return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
361 /* Check common words */
362 result = BMS_EQUAL; /* status so far */
363 shortlen = Min(a->nwords, b->nwords);
364 for (i = 0; i < shortlen; i++)
365 {
366 bitmapword aword = a->words[i];
367 bitmapword bword = b->words[i];
368
369 if ((aword & ~bword) != 0)
370 {
371 /* a is not a subset of b */
372 if (result == BMS_SUBSET1)
373 return BMS_DIFFERENT;
374 result = BMS_SUBSET2;
375 }
376 if ((bword & ~aword) != 0)
377 {
378 /* b is not a subset of a */
379 if (result == BMS_SUBSET2)
380 return BMS_DIFFERENT;
381 result = BMS_SUBSET1;
382 }
383 }
384 /* Check extra words */
385 if (a->nwords > b->nwords)
386 {
387 longlen = a->nwords;
388 for (; i < longlen; i++)
389 {
390 if (a->words[i] != 0)
391 {
392 /* a is not a subset of b */
393 if (result == BMS_SUBSET1)
394 return BMS_DIFFERENT;
395 result = BMS_SUBSET2;
396 }
397 }
398 }
399 else if (a->nwords < b->nwords)
400 {
401 longlen = b->nwords;
402 for (; i < longlen; i++)
403 {
404 if (b->words[i] != 0)
405 {
406 /* b is not a subset of a */
407 if (result == BMS_SUBSET2)
408 return BMS_DIFFERENT;
409 result = BMS_SUBSET1;
410 }
411 }
412 }
413 return result;
414 }
415
416 /*
417 * bms_is_member - is X a member of A?
418 */
419 bool
bms_is_member(int x,const Bitmapset * a)420 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 if (x < 0)
427 elog(ERROR, "negative bitmapset member not allowed");
428 if (a == NULL)
429 return false;
430 wordnum = WORDNUM(x);
431 bitnum = BITNUM(x);
432 if (wordnum >= a->nwords)
433 return false;
434 if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
435 return true;
436 return false;
437 }
438
439 /*
440 * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
441 */
442 bool
bms_overlap(const Bitmapset * a,const Bitmapset * b)443 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 if (a == NULL || b == NULL)
450 return false;
451 /* Check words in common */
452 shortlen = Min(a->nwords, b->nwords);
453 for (i = 0; i < shortlen; i++)
454 {
455 if ((a->words[i] & b->words[i]) != 0)
456 return true;
457 }
458 return false;
459 }
460
461 /*
462 * bms_overlap_list - does a set overlap an integer list?
463 */
464 bool
bms_overlap_list(const Bitmapset * a,const List * b)465 bms_overlap_list(const Bitmapset *a, const List *b)
466 {
467 ListCell *lc;
468 int wordnum,
469 bitnum;
470
471 if (a == NULL || b == NIL)
472 return false;
473
474 foreach(lc, b)
475 {
476 int x = lfirst_int(lc);
477
478 if (x < 0)
479 elog(ERROR, "negative bitmapset member not allowed");
480 wordnum = WORDNUM(x);
481 bitnum = BITNUM(x);
482 if (wordnum < a->nwords)
483 if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
484 return true;
485 }
486
487 return false;
488 }
489
490 /*
491 * bms_nonempty_difference - do sets have a nonempty difference?
492 */
493 bool
bms_nonempty_difference(const Bitmapset * a,const Bitmapset * b)494 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 if (a == NULL)
501 return false;
502 if (b == NULL)
503 return !bms_is_empty(a);
504 /* Check words in common */
505 shortlen = Min(a->nwords, b->nwords);
506 for (i = 0; i < shortlen; i++)
507 {
508 if ((a->words[i] & ~b->words[i]) != 0)
509 return true;
510 }
511 /* Check extra words in a */
512 for (; i < a->nwords; i++)
513 {
514 if (a->words[i] != 0)
515 return true;
516 }
517 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
bms_singleton_member(const Bitmapset * a)526 bms_singleton_member(const Bitmapset *a)
527 {
528 int result = -1;
529 int nwords;
530 int wordnum;
531
532 if (a == NULL)
533 elog(ERROR, "bitmapset is empty");
534 nwords = a->nwords;
535 for (wordnum = 0; wordnum < nwords; wordnum++)
536 {
537 bitmapword w = a->words[wordnum];
538
539 if (w != 0)
540 {
541 if (result >= 0 || HAS_MULTIPLE_ONES(w))
542 elog(ERROR, "bitmapset has multiple members");
543 result = wordnum * BITS_PER_BITMAPWORD;
544 while ((w & 255) == 0)
545 {
546 w >>= 8;
547 result += 8;
548 }
549 result += rightmost_one_pos[w & 255];
550 }
551 }
552 if (result < 0)
553 elog(ERROR, "bitmapset is empty");
554 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
bms_get_singleton_member(const Bitmapset * a,int * member)569 bms_get_singleton_member(const Bitmapset *a, int *member)
570 {
571 int result = -1;
572 int nwords;
573 int wordnum;
574
575 if (a == NULL)
576 return false;
577 nwords = a->nwords;
578 for (wordnum = 0; wordnum < nwords; wordnum++)
579 {
580 bitmapword w = a->words[wordnum];
581
582 if (w != 0)
583 {
584 if (result >= 0 || HAS_MULTIPLE_ONES(w))
585 return false;
586 result = wordnum * BITS_PER_BITMAPWORD;
587 while ((w & 255) == 0)
588 {
589 w >>= 8;
590 result += 8;
591 }
592 result += rightmost_one_pos[w & 255];
593 }
594 }
595 if (result < 0)
596 return false;
597 *member = result;
598 return true;
599 }
600
601 /*
602 * bms_num_members - count members of set
603 */
604 int
bms_num_members(const Bitmapset * a)605 bms_num_members(const Bitmapset *a)
606 {
607 int result = 0;
608 int nwords;
609 int wordnum;
610
611 if (a == NULL)
612 return 0;
613 nwords = a->nwords;
614 for (wordnum = 0; wordnum < nwords; wordnum++)
615 {
616 bitmapword w = a->words[wordnum];
617
618 /* we assume here that bitmapword is an unsigned type */
619 while (w != 0)
620 {
621 result += number_of_ones[w & 255];
622 w >>= 8;
623 }
624 }
625 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
bms_membership(const Bitmapset * a)634 bms_membership(const Bitmapset *a)
635 {
636 BMS_Membership result = BMS_EMPTY_SET;
637 int nwords;
638 int wordnum;
639
640 if (a == NULL)
641 return BMS_EMPTY_SET;
642 nwords = a->nwords;
643 for (wordnum = 0; wordnum < nwords; wordnum++)
644 {
645 bitmapword w = a->words[wordnum];
646
647 if (w != 0)
648 {
649 if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
650 return BMS_MULTIPLE;
651 result = BMS_SINGLETON;
652 }
653 }
654 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
bms_is_empty(const Bitmapset * a)663 bms_is_empty(const Bitmapset *a)
664 {
665 int nwords;
666 int wordnum;
667
668 if (a == NULL)
669 return true;
670 nwords = a->nwords;
671 for (wordnum = 0; wordnum < nwords; wordnum++)
672 {
673 bitmapword w = a->words[wordnum];
674
675 if (w != 0)
676 return false;
677 }
678 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 *
bms_add_member(Bitmapset * a,int x)698 bms_add_member(Bitmapset *a, int x)
699 {
700 int wordnum,
701 bitnum;
702
703 if (x < 0)
704 elog(ERROR, "negative bitmapset member not allowed");
705 if (a == NULL)
706 return bms_make_singleton(x);
707 wordnum = WORDNUM(x);
708 bitnum = BITNUM(x);
709
710 /* enlarge the set if necessary */
711 if (wordnum >= a->nwords)
712 {
713 int oldnwords = a->nwords;
714 int i;
715
716 a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
717 a->nwords = wordnum + 1;
718 /* zero out the enlarged portion */
719 for (i = oldnwords; i < a->nwords; i++)
720 a->words[i] = 0;
721 }
722
723 a->words[wordnum] |= ((bitmapword) 1 << bitnum);
724 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 *
bms_del_member(Bitmapset * a,int x)735 bms_del_member(Bitmapset *a, int x)
736 {
737 int wordnum,
738 bitnum;
739
740 if (x < 0)
741 elog(ERROR, "negative bitmapset member not allowed");
742 if (a == NULL)
743 return NULL;
744 wordnum = WORDNUM(x);
745 bitnum = BITNUM(x);
746 if (wordnum < a->nwords)
747 a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
748 return a;
749 }
750
751 /*
752 * bms_add_members - like bms_union, but left input is recycled
753 */
754 Bitmapset *
bms_add_members(Bitmapset * a,const Bitmapset * b)755 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 if (a == NULL)
764 return bms_copy(b);
765 if (b == NULL)
766 return a;
767 /* Identify shorter and longer input; copy the longer one if needed */
768 if (a->nwords < b->nwords)
769 {
770 result = bms_copy(b);
771 other = a;
772 }
773 else
774 {
775 result = a;
776 other = b;
777 }
778 /* And union the shorter input into the result */
779 otherlen = other->nwords;
780 for (i = 0; i < otherlen; i++)
781 result->words[i] |= other->words[i];
782 if (result != a)
783 pfree(a);
784 return result;
785 }
786
787 /*
788 * bms_int_members - like bms_intersect, but left input is recycled
789 */
790 Bitmapset *
bms_int_members(Bitmapset * a,const Bitmapset * b)791 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 if (a == NULL)
798 return NULL;
799 if (b == NULL)
800 {
801 pfree(a);
802 return NULL;
803 }
804 /* Intersect b into a; we need never copy */
805 shortlen = Min(a->nwords, b->nwords);
806 for (i = 0; i < shortlen; i++)
807 a->words[i] &= b->words[i];
808 for (; i < a->nwords; i++)
809 a->words[i] = 0;
810 return a;
811 }
812
813 /*
814 * bms_del_members - like bms_difference, but left input is recycled
815 */
816 Bitmapset *
bms_del_members(Bitmapset * a,const Bitmapset * b)817 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 if (a == NULL)
824 return NULL;
825 if (b == NULL)
826 return a;
827 /* Remove b's bits from a; we need never copy */
828 shortlen = Min(a->nwords, b->nwords);
829 for (i = 0; i < shortlen; i++)
830 a->words[i] &= ~b->words[i];
831 return a;
832 }
833
834 /*
835 * bms_join - like bms_union, but *both* inputs are recycled
836 */
837 Bitmapset *
bms_join(Bitmapset * a,Bitmapset * b)838 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 if (a == NULL)
847 return b;
848 if (b == NULL)
849 return a;
850 /* Identify shorter and longer input; use longer one as result */
851 if (a->nwords < b->nwords)
852 {
853 result = b;
854 other = a;
855 }
856 else
857 {
858 result = a;
859 other = b;
860 }
861 /* And union the shorter input into the result */
862 otherlen = other->nwords;
863 for (i = 0; i < otherlen; i++)
864 result->words[i] |= other->words[i];
865 if (other != result) /* pure paranoia */
866 pfree(other);
867 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
bms_first_member(Bitmapset * a)885 bms_first_member(Bitmapset *a)
886 {
887 int nwords;
888 int wordnum;
889
890 if (a == NULL)
891 return -1;
892 nwords = a->nwords;
893 for (wordnum = 0; wordnum < nwords; wordnum++)
894 {
895 bitmapword w = a->words[wordnum];
896
897 if (w != 0)
898 {
899 int result;
900
901 w = RIGHTMOST_ONE(w);
902 a->words[wordnum] &= ~w;
903
904 result = wordnum * BITS_PER_BITMAPWORD;
905 while ((w & 255) == 0)
906 {
907 w >>= 8;
908 result += 8;
909 }
910 result += rightmost_one_pos[w & 255];
911 return result;
912 }
913 }
914 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
bms_next_member(const Bitmapset * a,int prevbit)937 bms_next_member(const Bitmapset *a, int prevbit)
938 {
939 int nwords;
940 int wordnum;
941 bitmapword mask;
942
943 if (a == NULL)
944 return -2;
945 nwords = a->nwords;
946 prevbit++;
947 mask = (~(bitmapword) 0) << BITNUM(prevbit);
948 for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
949 {
950 bitmapword w = a->words[wordnum];
951
952 /* ignore bits before prevbit */
953 w &= mask;
954
955 if (w != 0)
956 {
957 int result;
958
959 result = wordnum * BITS_PER_BITMAPWORD;
960 while ((w & 255) == 0)
961 {
962 w >>= 8;
963 result += 8;
964 }
965 result += rightmost_one_pos[w & 255];
966 return result;
967 }
968
969 /* in subsequent words, consider all bits */
970 mask = (~(bitmapword) 0);
971 }
972 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
bms_hash_value(const Bitmapset * a)984 bms_hash_value(const Bitmapset *a)
985 {
986 int lastword;
987
988 if (a == NULL)
989 return 0; /* All empty sets hash to 0 */
990 for (lastword = a->nwords; --lastword >= 0;)
991 {
992 if (a->words[lastword] != 0)
993 break;
994 }
995 if (lastword < 0)
996 return 0; /* All empty sets hash to 0 */
997 return DatumGetUInt32(hash_any((const unsigned char *) a->words,
998 (lastword + 1) * sizeof(bitmapword)));
999 }
1000