PostgreSQL Source Code  git master
bitmapset.c
Go to the documentation of this file.
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
79 bms_is_valid_set(const Bitmapset *a)
80 {
81  /* NULL is the correct representation of an empty set */
82  if (a == NULL)
83  return true;
84 
85  /* check the node tag is set correctly. pfree'd pointer, maybe? */
86  if (!IsA(a, Bitmapset))
87  return false;
88 
89  /* trailing zero words are not allowed */
90  if (a->words[a->nwords - 1] == 0)
91  return false;
92 
93  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 *
123 {
124  Bitmapset *result;
125  size_t size;
126 
127  Assert(bms_is_valid_set(a));
128 
129  if (a == NULL)
130  return NULL;
131 
132  size = BITMAPSET_SIZE(a->nwords);
133  result = (Bitmapset *) palloc(size);
134  memcpy(result, a, size);
135  return result;
136 }
137 
138 /*
139  * bms_equal - are two bitmapsets equal? or both NULL?
140  */
141 bool
142 bms_equal(const Bitmapset *a, const Bitmapset *b)
143 {
144  int i;
145 
146  Assert(bms_is_valid_set(a));
147  Assert(bms_is_valid_set(b));
148 
149  /* Handle cases where either input is NULL */
150  if (a == NULL)
151  {
152  if (b == NULL)
153  return true;
154  return false;
155  }
156  else if (b == NULL)
157  return false;
158 
159  /* can't be equal if the word counts don't match */
160  if (a->nwords != b->nwords)
161  return false;
162 
163  /* check each word matches */
164  i = 0;
165  do
166  {
167  if (a->words[i] != b->words[i])
168  return false;
169  } while (++i < a->nwords);
170 
171  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
184 {
185  int i;
186 
187  Assert(bms_is_valid_set(a));
188  Assert(bms_is_valid_set(b));
189 
190  /* Handle cases where either input is NULL */
191  if (a == NULL)
192  return (b == NULL) ? 0 : -1;
193  else if (b == NULL)
194  return +1;
195 
196  /* the set with the most words must be greater */
197  if (a->nwords != b->nwords)
198  return (a->nwords > b->nwords) ? +1 : -1;
199 
200  i = a->nwords - 1;
201  do
202  {
203  bitmapword aw = a->words[i];
204  bitmapword bw = b->words[i];
205 
206  if (aw != bw)
207  return (aw > bw) ? +1 : -1;
208  } while (--i >= 0);
209  return 0;
210 }
211 
212 /*
213  * bms_make_singleton - build a bitmapset containing a single member
214  */
215 Bitmapset *
217 {
218  Bitmapset *result;
219  int wordnum,
220  bitnum;
221 
222  if (x < 0)
223  elog(ERROR, "negative bitmapset member not allowed");
224  wordnum = WORDNUM(x);
225  bitnum = BITNUM(x);
226  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
227  result->type = T_Bitmapset;
228  result->nwords = wordnum + 1;
229  result->words[wordnum] = ((bitmapword) 1 << bitnum);
230  return result;
231 }
232 
233 /*
234  * bms_free - free a bitmapset
235  *
236  * Same as pfree except for allowing NULL input
237  */
238 void
240 {
241  if (a)
242  pfree(a);
243 }
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 *
251 bms_union(const Bitmapset *a, const Bitmapset *b)
252 {
253  Bitmapset *result;
254  const Bitmapset *other;
255  int otherlen;
256  int i;
257 
258  Assert(bms_is_valid_set(a));
259  Assert(bms_is_valid_set(b));
260 
261  /* Handle cases where either input is NULL */
262  if (a == NULL)
263  return bms_copy(b);
264  if (b == NULL)
265  return bms_copy(a);
266  /* Identify shorter and longer input; copy the longer one */
267  if (a->nwords <= b->nwords)
268  {
269  result = bms_copy(b);
270  other = a;
271  }
272  else
273  {
274  result = bms_copy(a);
275  other = b;
276  }
277  /* And union the shorter input into the result */
278  otherlen = other->nwords;
279  i = 0;
280  do
281  {
282  result->words[i] |= other->words[i];
283  } while (++i < otherlen);
284  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 *
293 {
294  Bitmapset *result;
295  const Bitmapset *other;
296  int lastnonzero;
297  int resultlen;
298  int i;
299 
300  Assert(bms_is_valid_set(a));
301  Assert(bms_is_valid_set(b));
302 
303  /* Handle cases where either input is NULL */
304  if (a == NULL || b == NULL)
305  return NULL;
306 
307  /* Identify shorter and longer input; copy the shorter one */
308  if (a->nwords <= b->nwords)
309  {
310  result = bms_copy(a);
311  other = b;
312  }
313  else
314  {
315  result = bms_copy(b);
316  other = a;
317  }
318  /* And intersect the longer input with the result */
319  resultlen = result->nwords;
320  lastnonzero = -1;
321  i = 0;
322  do
323  {
324  result->words[i] &= other->words[i];
325 
326  if (result->words[i] != 0)
327  lastnonzero = i;
328  } while (++i < resultlen);
329  /* If we computed an empty result, we must return NULL */
330  if (lastnonzero == -1)
331  {
332  pfree(result);
333  return NULL;
334  }
335 
336  /* get rid of trailing zero words */
337  result->nwords = lastnonzero + 1;
338  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 *
347 {
348  Bitmapset *result;
349  int i;
350 
351  Assert(bms_is_valid_set(a));
352  Assert(bms_is_valid_set(b));
353 
354  /* Handle cases where either input is NULL */
355  if (a == NULL)
356  return NULL;
357  if (b == NULL)
358  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  */
365  if (!bms_nonempty_difference(a, b))
366  return NULL;
367 
368  /* Copy the left input */
369  result = bms_copy(a);
370 
371  /* And remove b's bits from result */
372  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  */
378  i = 0;
379  do
380  {
381  result->words[i] &= ~b->words[i];
382  } while (++i < b->nwords);
383  }
384  else
385  {
386  int lastnonzero = -1;
387 
388  /* we may need to remove trailing zero words from the result. */
389  i = 0;
390  do
391  {
392  result->words[i] &= ~b->words[i];
393 
394  /* remember the last non-zero word */
395  if (result->words[i] != 0)
396  lastnonzero = i;
397  } while (++i < result->nwords);
398 
399  /* trim off trailing zero words */
400  result->nwords = lastnonzero + 1;
401  }
402  Assert(result->nwords != 0);
403 
404  /* Need not check for empty result, since we handled that case above */
405  return result;
406 }
407 
408 /*
409  * bms_is_subset - is A a subset of B?
410  */
411 bool
413 {
414  int i;
415 
416  Assert(bms_is_valid_set(a));
417  Assert(bms_is_valid_set(b));
418 
419  /* Handle cases where either input is NULL */
420  if (a == NULL)
421  return true; /* empty set is a subset of anything */
422  if (b == NULL)
423  return false;
424 
425  /* 'a' can't be a subset of 'b' if it contains more words */
426  if (a->nwords > b->nwords)
427  return false;
428 
429  /* Check all 'a' members are set in 'b' */
430  i = 0;
431  do
432  {
433  if ((a->words[i] & ~b->words[i]) != 0)
434  return false;
435  } while (++i < a->nwords);
436  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  */
446 {
447  BMS_Comparison result;
448  int shortlen;
449  int i;
450 
451  Assert(bms_is_valid_set(a));
452  Assert(bms_is_valid_set(b));
453 
454  /* Handle cases where either input is NULL */
455  if (a == NULL)
456  {
457  if (b == NULL)
458  return BMS_EQUAL;
459  return BMS_SUBSET1;
460  }
461  if (b == NULL)
462  return BMS_SUBSET2;
463 
464  /* Check common words */
465  result = BMS_EQUAL; /* status so far */
466  shortlen = Min(a->nwords, b->nwords);
467  i = 0;
468  do
469  {
470  bitmapword aword = a->words[i];
471  bitmapword bword = b->words[i];
472 
473  if ((aword & ~bword) != 0)
474  {
475  /* a is not a subset of b */
476  if (result == BMS_SUBSET1)
477  return BMS_DIFFERENT;
478  result = BMS_SUBSET2;
479  }
480  if ((bword & ~aword) != 0)
481  {
482  /* b is not a subset of a */
483  if (result == BMS_SUBSET2)
484  return BMS_DIFFERENT;
485  result = BMS_SUBSET1;
486  }
487  } while (++i < shortlen);
488  /* Check extra words */
489  if (a->nwords > b->nwords)
490  {
491  /* if a has more words then a is not a subset of b */
492  if (result == BMS_SUBSET1)
493  return BMS_DIFFERENT;
494  return BMS_SUBSET2;
495  }
496  else if (a->nwords < b->nwords)
497  {
498  /* if b has more words then b is not a subset of a */
499  if (result == BMS_SUBSET2)
500  return BMS_DIFFERENT;
501  return BMS_SUBSET1;
502  }
503  return result;
504 }
505 
506 /*
507  * bms_is_member - is X a member of A?
508  */
509 bool
511 {
512  int wordnum,
513  bitnum;
514 
515  Assert(bms_is_valid_set(a));
516 
517  /* XXX better to just return false for x<0 ? */
518  if (x < 0)
519  elog(ERROR, "negative bitmapset member not allowed");
520  if (a == NULL)
521  return false;
522 
523  wordnum = WORDNUM(x);
524  bitnum = BITNUM(x);
525  if (wordnum >= a->nwords)
526  return false;
527  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
528  return true;
529  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
540 {
541  int i;
542  int bitnum;
543  int wordnum;
544  int result = 0;
545  bitmapword mask;
546 
547  Assert(bms_is_valid_set(a));
548 
549  /* return -1 if not a member of the bitmap */
550  if (!bms_is_member(x, a))
551  return -1;
552 
553  wordnum = WORDNUM(x);
554  bitnum = BITNUM(x);
555 
556  /* count bits in preceding words */
557  for (i = 0; i < wordnum; i++)
558  {
559  bitmapword w = a->words[i];
560 
561  /* No need to count the bits in a zero word */
562  if (w != 0)
563  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  */
572  mask = ((bitmapword) 1 << bitnum) - 1;
573  result += bmw_popcount(a->words[wordnum] & mask);
574 
575  return result;
576 }
577 
578 /*
579  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
580  */
581 bool
583 {
584  int shortlen;
585  int i;
586 
587  Assert(bms_is_valid_set(a));
588  Assert(bms_is_valid_set(b));
589 
590  /* Handle cases where either input is NULL */
591  if (a == NULL || b == NULL)
592  return false;
593  /* Check words in common */
594  shortlen = Min(a->nwords, b->nwords);
595  i = 0;
596  do
597  {
598  if ((a->words[i] & b->words[i]) != 0)
599  return true;
600  } while (++i < shortlen);
601  return false;
602 }
603 
604 /*
605  * bms_overlap_list - does a set overlap an integer list?
606  */
607 bool
609 {
610  ListCell *lc;
611  int wordnum,
612  bitnum;
613 
614  Assert(bms_is_valid_set(a));
615 
616  if (a == NULL || b == NIL)
617  return false;
618 
619  foreach(lc, b)
620  {
621  int x = lfirst_int(lc);
622 
623  if (x < 0)
624  elog(ERROR, "negative bitmapset member not allowed");
625  wordnum = WORDNUM(x);
626  bitnum = BITNUM(x);
627  if (wordnum < a->nwords)
628  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
629  return true;
630  }
631 
632  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
642 {
643  int i;
644 
645  Assert(bms_is_valid_set(a));
646  Assert(bms_is_valid_set(b));
647 
648  /* Handle cases where either input is NULL */
649  if (a == NULL)
650  return false;
651  if (b == NULL)
652  return true;
653  /* if 'a' has more words then it must contain additional members */
654  if (a->nwords > b->nwords)
655  return true;
656  /* Check all 'a' members are set in 'b' */
657  i = 0;
658  do
659  {
660  if ((a->words[i] & ~b->words[i]) != 0)
661  return true;
662  } while (++i < a->nwords);
663  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
673 {
674  int result = -1;
675  int nwords;
676  int wordnum;
677 
678  Assert(bms_is_valid_set(a));
679 
680  if (a == NULL)
681  elog(ERROR, "bitmapset is empty");
682 
683  nwords = a->nwords;
684  wordnum = 0;
685  do
686  {
687  bitmapword w = a->words[wordnum];
688 
689  if (w != 0)
690  {
691  if (result >= 0 || HAS_MULTIPLE_ONES(w))
692  elog(ERROR, "bitmapset has multiple members");
693  result = wordnum * BITS_PER_BITMAPWORD;
694  result += bmw_rightmost_one_pos(w);
695  }
696  } while (++wordnum < nwords);
697 
698  /* we don't expect non-NULL sets to be empty */
699  Assert(result >= 0);
700  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
716 {
717  int result = -1;
718  int nwords;
719  int wordnum;
720 
721  Assert(bms_is_valid_set(a));
722 
723  if (a == NULL)
724  return false;
725 
726  nwords = a->nwords;
727  wordnum = 0;
728  do
729  {
730  bitmapword w = a->words[wordnum];
731 
732  if (w != 0)
733  {
734  if (result >= 0 || HAS_MULTIPLE_ONES(w))
735  return false;
736  result = wordnum * BITS_PER_BITMAPWORD;
737  result += bmw_rightmost_one_pos(w);
738  }
739  } while (++wordnum < nwords);
740 
741  /* we don't expect non-NULL sets to be empty */
742  Assert(result >= 0);
743  *member = result;
744  return true;
745 }
746 
747 /*
748  * bms_num_members - count members of set
749  */
750 int
752 {
753  int result = 0;
754  int nwords;
755  int wordnum;
756 
757  Assert(bms_is_valid_set(a));
758 
759  if (a == NULL)
760  return 0;
761 
762  nwords = a->nwords;
763  wordnum = 0;
764  do
765  {
766  bitmapword w = a->words[wordnum];
767 
768  /* No need to count the bits in a zero word */
769  if (w != 0)
770  result += bmw_popcount(w);
771  } while (++wordnum < nwords);
772  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  */
782 {
783  BMS_Membership result = BMS_EMPTY_SET;
784  int nwords;
785  int wordnum;
786 
787  Assert(bms_is_valid_set(a));
788 
789  if (a == NULL)
790  return BMS_EMPTY_SET;
791 
792  nwords = a->nwords;
793  wordnum = 0;
794  do
795  {
796  bitmapword w = a->words[wordnum];
797 
798  if (w != 0)
799  {
800  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
801  return BMS_MULTIPLE;
802  result = BMS_SINGLETON;
803  }
804  } while (++wordnum < nwords);
805  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 *
816 {
817  int wordnum,
818  bitnum;
819 
820  Assert(bms_is_valid_set(a));
821 
822  if (x < 0)
823  elog(ERROR, "negative bitmapset member not allowed");
824  if (a == NULL)
825  return bms_make_singleton(x);
826 
827  wordnum = WORDNUM(x);
828  bitnum = BITNUM(x);
829 
830  /* enlarge the set if necessary */
831  if (wordnum >= a->nwords)
832  {
833  int oldnwords = a->nwords;
834  int i;
835 
836  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
837  a->nwords = wordnum + 1;
838  /* zero out the enlarged portion */
839  i = oldnwords;
840  do
841  {
842  a->words[i] = 0;
843  } while (++i < a->nwords);
844  }
845 
846  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 
857  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 *
869 {
870  int wordnum,
871  bitnum;
872 
873  Assert(bms_is_valid_set(a));
874 
875  if (x < 0)
876  elog(ERROR, "negative bitmapset member not allowed");
877  if (a == NULL)
878  return NULL;
879 
880  wordnum = WORDNUM(x);
881  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 */
888  if (unlikely(wordnum >= a->nwords))
889  return a;
890 
891  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
892 
893  /* when last word becomes empty, trim off all trailing empty words */
894  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  for (int i = wordnum - 1; i >= 0; i--)
898  {
899  if (a->words[i] != 0)
900  {
901  a->nwords = i + 1;
902  return a;
903  }
904  }
905 
906  /* the set is now empty */
907  pfree(a);
908  return NULL;
909  }
910  return a;
911 }
912 
913 /*
914  * bms_add_members - like bms_union, but left input is recycled when possible
915  */
916 Bitmapset *
918 {
919  Bitmapset *result;
920  const Bitmapset *other;
921  int otherlen;
922  int i;
923 
924  Assert(bms_is_valid_set(a));
925  Assert(bms_is_valid_set(b));
926 
927  /* Handle cases where either input is NULL */
928  if (a == NULL)
929  return bms_copy(b);
930  if (b == NULL)
931  {
932 #ifdef REALLOCATE_BITMAPSETS
933  a = bms_copy_and_free(a);
934 #endif
935 
936  return a;
937  }
938  /* Identify shorter and longer input; copy the longer one if needed */
939  if (a->nwords < b->nwords)
940  {
941  result = bms_copy(b);
942  other = a;
943  }
944  else
945  {
946  result = a;
947  other = b;
948  }
949  /* And union the shorter input into the result */
950  otherlen = other->nwords;
951  i = 0;
952  do
953  {
954  result->words[i] |= other->words[i];
955  } while (++i < otherlen);
956  if (result != a)
957  pfree(a);
958 #ifdef REALLOCATE_BITMAPSETS
959  else
960  result = bms_copy_and_free(result);
961 #endif
962 
963  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 *
973 {
974  int i;
975 
976  Assert(bms_is_valid_set(a));
977  Assert(bms_is_valid_set(b));
978 
979  if (a == NULL)
980  return bms_copy(b);
981  if (b == NULL)
982  {
983  pfree(a);
984  return NULL;
985  }
986 
987  if (a->nwords < b->nwords)
988  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
989 
990  i = 0;
991  do
992  {
993  a->words[i] = b->words[i];
994  } while (++i < b->nwords);
995 
996  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  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 *
1020 {
1021  int lwordnum,
1022  lbitnum,
1023  uwordnum,
1024  ushiftbits,
1025  wordnum;
1026 
1027  Assert(bms_is_valid_set(a));
1028 
1029  /* do nothing if nothing is called for, without further checking */
1030  if (upper < lower)
1031  {
1032 #ifdef REALLOCATE_BITMAPSETS
1033  a = bms_copy_and_free(a);
1034 #endif
1035 
1036  return a;
1037  }
1038 
1039  if (lower < 0)
1040  elog(ERROR, "negative bitmapset member not allowed");
1041  uwordnum = WORDNUM(upper);
1042 
1043  if (a == NULL)
1044  {
1045  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
1046  a->type = T_Bitmapset;
1047  a->nwords = uwordnum + 1;
1048  }
1049  else if (uwordnum >= a->nwords)
1050  {
1051  int oldnwords = a->nwords;
1052  int i;
1053 
1054  /* ensure we have enough words to store the upper bit */
1055  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
1056  a->nwords = uwordnum + 1;
1057  /* zero out the enlarged portion */
1058  i = oldnwords;
1059  do
1060  {
1061  a->words[i] = 0;
1062  } while (++i < a->nwords);
1063  }
1064 
1065  wordnum = lwordnum = WORDNUM(lower);
1066 
1067  lbitnum = BITNUM(lower);
1068  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  if (lwordnum == uwordnum)
1075  {
1076  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
1077  & (~(bitmapword) 0) >> ushiftbits;
1078  }
1079  else
1080  {
1081  /* turn on lbitnum and all bits left of it */
1082  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
1083 
1084  /* turn on all bits for any intermediate words */
1085  while (wordnum < uwordnum)
1086  a->words[wordnum++] = ~(bitmapword) 0;
1087 
1088  /* turn on upper's bit and all bits right of it. */
1089  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 
1101  return a;
1102 }
1103 
1104 /*
1105  * bms_int_members - like bms_intersect, but left input is recycled when
1106  * possible
1107  */
1108 Bitmapset *
1110 {
1111  int lastnonzero;
1112  int shortlen;
1113  int i;
1114 
1115  Assert(bms_is_valid_set(a));
1116  Assert(bms_is_valid_set(b));
1117 
1118  /* Handle cases where either input is NULL */
1119  if (a == NULL)
1120  return NULL;
1121  if (b == NULL)
1122  {
1123  pfree(a);
1124  return NULL;
1125  }
1126 
1127  /* Intersect b into a; we need never copy */
1128  shortlen = Min(a->nwords, b->nwords);
1129  lastnonzero = -1;
1130  i = 0;
1131  do
1132  {
1133  a->words[i] &= b->words[i];
1134 
1135  if (a->words[i] != 0)
1136  lastnonzero = i;
1137  } while (++i < shortlen);
1138 
1139  /* If we computed an empty result, we must return NULL */
1140  if (lastnonzero == -1)
1141  {
1142  pfree(a);
1143  return NULL;
1144  }
1145 
1146  /* get rid of trailing zero words */
1147  a->nwords = lastnonzero + 1;
1148 
1149 #ifdef REALLOCATE_BITMAPSETS
1150  a = bms_copy_and_free(a);
1151 #endif
1152 
1153  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 *
1162 {
1163  int i;
1164 
1165  Assert(bms_is_valid_set(a));
1166  Assert(bms_is_valid_set(b));
1167 
1168  /* Handle cases where either input is NULL */
1169  if (a == NULL)
1170  return NULL;
1171  if (b == NULL)
1172  {
1173 #ifdef REALLOCATE_BITMAPSETS
1174  a = bms_copy_and_free(a);
1175 #endif
1176 
1177  return a;
1178  }
1179 
1180  /* Remove b's bits from a; we need never copy */
1181  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  */
1187  i = 0;
1188  do
1189  {
1190  a->words[i] &= ~b->words[i];
1191  } while (++i < b->nwords);
1192  }
1193  else
1194  {
1195  int lastnonzero = -1;
1196 
1197  /* we may need to remove trailing zero words from the result. */
1198  i = 0;
1199  do
1200  {
1201  a->words[i] &= ~b->words[i];
1202 
1203  /* remember the last non-zero word */
1204  if (a->words[i] != 0)
1205  lastnonzero = i;
1206  } while (++i < a->nwords);
1207 
1208  /* check if 'a' has become empty */
1209  if (lastnonzero == -1)
1210  {
1211  pfree(a);
1212  return NULL;
1213  }
1214 
1215  /* trim off any trailing zero words */
1216  a->nwords = lastnonzero + 1;
1217  }
1218 
1219 #ifdef REALLOCATE_BITMAPSETS
1220  a = bms_copy_and_free(a);
1221 #endif
1222 
1223  return a;
1224 }
1225 
1226 /*
1227  * bms_join - like bms_union, but *either* input *may* be recycled
1228  */
1229 Bitmapset *
1231 {
1232  Bitmapset *result;
1233  Bitmapset *other;
1234  int otherlen;
1235  int i;
1236 
1237  Assert(bms_is_valid_set(a));
1238  Assert(bms_is_valid_set(b));
1239 
1240  /* Handle cases where either input is NULL */
1241  if (a == NULL)
1242  {
1243 #ifdef REALLOCATE_BITMAPSETS
1244  b = bms_copy_and_free(b);
1245 #endif
1246 
1247  return b;
1248  }
1249  if (b == NULL)
1250  {
1251 #ifdef REALLOCATE_BITMAPSETS
1252  a = bms_copy_and_free(a);
1253 #endif
1254 
1255  return a;
1256  }
1257 
1258  /* Identify shorter and longer input; use longer one as result */
1259  if (a->nwords < b->nwords)
1260  {
1261  result = b;
1262  other = a;
1263  }
1264  else
1265  {
1266  result = a;
1267  other = b;
1268  }
1269  /* And union the shorter input into the result */
1270  otherlen = other->nwords;
1271  i = 0;
1272  do
1273  {
1274  result->words[i] |= other->words[i];
1275  } while (++i < otherlen);
1276  if (other != result) /* pure paranoia */
1277  pfree(other);
1278 
1279 #ifdef REALLOCATE_BITMAPSETS
1280  result = bms_copy_and_free(result);
1281 #endif
1282 
1283  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
1306 bms_next_member(const Bitmapset *a, int prevbit)
1307 {
1308  int nwords;
1309  int wordnum;
1310  bitmapword mask;
1311 
1312  Assert(bms_is_valid_set(a));
1313 
1314  if (a == NULL)
1315  return -2;
1316  nwords = a->nwords;
1317  prevbit++;
1318  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1319  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1320  {
1321  bitmapword w = a->words[wordnum];
1322 
1323  /* ignore bits before prevbit */
1324  w &= mask;
1325 
1326  if (w != 0)
1327  {
1328  int result;
1329 
1330  result = wordnum * BITS_PER_BITMAPWORD;
1331  result += bmw_rightmost_one_pos(w);
1332  return result;
1333  }
1334 
1335  /* in subsequent words, consider all bits */
1336  mask = (~(bitmapword) 0);
1337  }
1338  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
1367 bms_prev_member(const Bitmapset *a, int prevbit)
1368 {
1369  int wordnum;
1370  int ushiftbits;
1371  bitmapword mask;
1372 
1373  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  */
1379  if (a == NULL || prevbit == 0)
1380  return -2;
1381 
1382  /* transform -1 to the highest possible bit we could have set */
1383  if (prevbit == -1)
1384  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1385  else
1386  prevbit--;
1387 
1388  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1389  mask = (~(bitmapword) 0) >> ushiftbits;
1390  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1391  {
1392  bitmapword w = a->words[wordnum];
1393 
1394  /* mask out bits left of prevbit */
1395  w &= mask;
1396 
1397  if (w != 0)
1398  {
1399  int result;
1400 
1401  result = wordnum * BITS_PER_BITMAPWORD;
1402  result += bmw_leftmost_one_pos(w);
1403  return result;
1404  }
1405 
1406  /* in subsequent words, consider all bits */
1407  mask = (~(bitmapword) 0);
1408  }
1409  return -2;
1410 }
1411 
1412 /*
1413  * bms_hash_value - compute a hash key for a Bitmapset
1414  */
1415 uint32
1417 {
1418  Assert(bms_is_valid_set(a));
1419 
1420  if (a == NULL)
1421  return 0; /* All empty sets hash to 0 */
1422  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1423  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
1432 bitmap_hash(const void *key, Size keysize)
1433 {
1434  Assert(keysize == sizeof(Bitmapset *));
1435  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 bitmap_match(const void *key1, const void *key2, Size keysize)
1443 {
1444  Assert(keysize == sizeof(Bitmapset *));
1445  return !bms_equal(*((const Bitmapset *const *) key1),
1446  *((const Bitmapset *const *) key2));
1447 }
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:50
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1367
uint32 bitmap_hash(const void *key, Size keysize)
Definition: bitmapset.c:1432
#define WORDNUM(x)
Definition: bitmapset.c:47
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:1230
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:445
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1306
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1416
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:672
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:751
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
#define BITNUM(x)
Definition: bitmapset.c:48
Bitmapset * bms_replace_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:972
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1109
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:868
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:72
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: bitmapset.c:1442
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:539
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
int bms_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:183
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:715
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641
bool bms_overlap_list(const Bitmapset *a, const List *b)
Definition: bitmapset.c:608
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.h:79
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.h:78
BMS_Comparison
Definition: bitmapset.h:61
@ BMS_DIFFERENT
Definition: bitmapset.h:65
@ BMS_SUBSET1
Definition: bitmapset.h:63
@ BMS_EQUAL
Definition: bitmapset.h:62
@ BMS_SUBSET2
Definition: bitmapset.h:64
BMS_Membership
Definition: bitmapset.h:70
@ BMS_SINGLETON
Definition: bitmapset.h:72
@ BMS_EMPTY_SET
Definition: bitmapset.h:71
@ BMS_MULTIPLE
Definition: bitmapset.h:73
uint32 bitmapword
Definition: bitmapset.h:44
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
#define bmw_popcount(w)
Definition: bitmapset.h:80
unsigned int uint32
Definition: c.h:493
#define Min(x, y)
Definition: c.h:991
#define unlikely(x)
Definition: c.h:298
size_t Size
Definition: c.h:592
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
int b
Definition: isn.c:70
int x
Definition: isn.c:71
int a
Definition: isn.c:69
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc0(Size size)
Definition: mcxt.c:1334
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1528
void * palloc(Size size)
Definition: mcxt.c:1304
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
#define NIL
Definition: pg_list.h:68
#define lfirst_int(lc)
Definition: pg_list.h:173
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222
char * c
static pg_noinline void Size size
Definition: slab.c:607
int nwords
Definition: bitmapset.h:54
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:55
Definition: pg_list.h:54