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