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, 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-2022, PostgreSQL Global Development Group
15  *
16  * IDENTIFICATION
17  * src/backend/nodes/bitmapset.c
18  *
19  *-------------------------------------------------------------------------
20  */
21 #include "postgres.h"
22 
23 #include "common/hashfn.h"
24 #include "nodes/bitmapset.h"
25 #include "nodes/pg_list.h"
26 #include "port/pg_bitutils.h"
27 
28 
29 #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
30 #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
31 
32 #define BITMAPSET_SIZE(nwords) \
33  (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
34 
35 /*----------
36  * This is a well-known cute trick for isolating the rightmost one-bit
37  * in a word. It assumes two's complement arithmetic. Consider any
38  * nonzero value, and focus attention on the rightmost one. The value is
39  * then something like
40  * xxxxxx10000
41  * where x's are unspecified bits. The two's complement negative is formed
42  * by inverting all the bits and adding one. Inversion gives
43  * yyyyyy01111
44  * where each y is the inverse of the corresponding x. Incrementing gives
45  * yyyyyy10000
46  * and then ANDing with the original value gives
47  * 00000010000
48  * This works for all cases except original value = zero, where of course
49  * we get zero.
50  *----------
51  */
52 #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
53 
54 #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x))
55 
56 /* Select appropriate bit-twiddling functions for bitmap word size */
57 #if BITS_PER_BITMAPWORD == 32
58 #define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w)
59 #define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w)
60 #define bmw_popcount(w) pg_popcount32(w)
61 #elif BITS_PER_BITMAPWORD == 64
62 #define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w)
63 #define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w)
64 #define bmw_popcount(w) pg_popcount64(w)
65 #else
66 #error "invalid BITS_PER_BITMAPWORD"
67 #endif
68 
69 
70 /*
71  * bms_copy - make a palloc'd copy of a bitmapset
72  */
73 Bitmapset *
75 {
76  Bitmapset *result;
77  size_t size;
78 
79  if (a == NULL)
80  return NULL;
81  size = BITMAPSET_SIZE(a->nwords);
82  result = (Bitmapset *) palloc(size);
83  memcpy(result, a, size);
84  return result;
85 }
86 
87 /*
88  * bms_equal - are two bitmapsets equal?
89  *
90  * This is logical not physical equality; in particular, a NULL pointer will
91  * be reported as equal to a palloc'd value containing no members.
92  */
93 bool
94 bms_equal(const Bitmapset *a, const Bitmapset *b)
95 {
96  const Bitmapset *shorter;
97  const Bitmapset *longer;
98  int shortlen;
99  int longlen;
100  int i;
101 
102  /* Handle cases where either input is NULL */
103  if (a == NULL)
104  {
105  if (b == NULL)
106  return true;
107  return bms_is_empty(b);
108  }
109  else if (b == NULL)
110  return bms_is_empty(a);
111  /* Identify shorter and longer input */
112  if (a->nwords <= b->nwords)
113  {
114  shorter = a;
115  longer = b;
116  }
117  else
118  {
119  shorter = b;
120  longer = a;
121  }
122  /* And process */
123  shortlen = shorter->nwords;
124  for (i = 0; i < shortlen; i++)
125  {
126  if (shorter->words[i] != longer->words[i])
127  return false;
128  }
129  longlen = longer->nwords;
130  for (; i < longlen; i++)
131  {
132  if (longer->words[i] != 0)
133  return false;
134  }
135  return true;
136 }
137 
138 /*
139  * bms_compare - qsort-style comparator for bitmapsets
140  *
141  * This guarantees to report values as equal iff bms_equal would say they are
142  * equal. Otherwise, the highest-numbered bit that is set in one value but
143  * not the other determines the result. (This rule means that, for example,
144  * {6} is greater than {5}, which seems plausible.)
145  */
146 int
148 {
149  int shortlen;
150  int i;
151 
152  /* Handle cases where either input is NULL */
153  if (a == NULL)
154  return bms_is_empty(b) ? 0 : -1;
155  else if (b == NULL)
156  return bms_is_empty(a) ? 0 : +1;
157  /* Handle cases where one input is longer than the other */
158  shortlen = Min(a->nwords, b->nwords);
159  for (i = shortlen; i < a->nwords; i++)
160  {
161  if (a->words[i] != 0)
162  return +1;
163  }
164  for (i = shortlen; i < b->nwords; i++)
165  {
166  if (b->words[i] != 0)
167  return -1;
168  }
169  /* Process words in common */
170  i = shortlen;
171  while (--i >= 0)
172  {
173  bitmapword aw = a->words[i];
174  bitmapword bw = b->words[i];
175 
176  if (aw != bw)
177  return (aw > bw) ? +1 : -1;
178  }
179  return 0;
180 }
181 
182 /*
183  * bms_make_singleton - build a bitmapset containing a single member
184  */
185 Bitmapset *
187 {
188  Bitmapset *result;
189  int wordnum,
190  bitnum;
191 
192  if (x < 0)
193  elog(ERROR, "negative bitmapset member not allowed");
194  wordnum = WORDNUM(x);
195  bitnum = BITNUM(x);
196  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
197  result->type = T_Bitmapset;
198  result->nwords = wordnum + 1;
199  result->words[wordnum] = ((bitmapword) 1 << bitnum);
200  return result;
201 }
202 
203 /*
204  * bms_free - free a bitmapset
205  *
206  * Same as pfree except for allowing NULL input
207  */
208 void
210 {
211  if (a)
212  pfree(a);
213 }
214 
215 
216 /*
217  * These operations all make a freshly palloc'd result,
218  * leaving their inputs untouched
219  */
220 
221 
222 /*
223  * bms_union - set union
224  */
225 Bitmapset *
226 bms_union(const Bitmapset *a, const Bitmapset *b)
227 {
228  Bitmapset *result;
229  const Bitmapset *other;
230  int otherlen;
231  int i;
232 
233  /* Handle cases where either input is NULL */
234  if (a == NULL)
235  return bms_copy(b);
236  if (b == NULL)
237  return bms_copy(a);
238  /* Identify shorter and longer input; copy the longer one */
239  if (a->nwords <= b->nwords)
240  {
241  result = bms_copy(b);
242  other = a;
243  }
244  else
245  {
246  result = bms_copy(a);
247  other = b;
248  }
249  /* And union the shorter input into the result */
250  otherlen = other->nwords;
251  for (i = 0; i < otherlen; i++)
252  result->words[i] |= other->words[i];
253  return result;
254 }
255 
256 /*
257  * bms_intersect - set intersection
258  */
259 Bitmapset *
261 {
262  Bitmapset *result;
263  const Bitmapset *other;
264  int resultlen;
265  int i;
266 
267  /* Handle cases where either input is NULL */
268  if (a == NULL || b == NULL)
269  return NULL;
270  /* Identify shorter and longer input; copy the shorter one */
271  if (a->nwords <= b->nwords)
272  {
273  result = bms_copy(a);
274  other = b;
275  }
276  else
277  {
278  result = bms_copy(b);
279  other = a;
280  }
281  /* And intersect the longer input with the result */
282  resultlen = result->nwords;
283  for (i = 0; i < resultlen; i++)
284  result->words[i] &= other->words[i];
285  return result;
286 }
287 
288 /*
289  * bms_difference - set difference (ie, A without members of B)
290  */
291 Bitmapset *
293 {
294  Bitmapset *result;
295  int shortlen;
296  int i;
297 
298  /* Handle cases where either input is NULL */
299  if (a == NULL)
300  return NULL;
301  if (b == NULL)
302  return bms_copy(a);
303  /* Copy the left input */
304  result = bms_copy(a);
305  /* And remove b's bits from result */
306  shortlen = Min(a->nwords, b->nwords);
307  for (i = 0; i < shortlen; i++)
308  result->words[i] &= ~b->words[i];
309  return result;
310 }
311 
312 /*
313  * bms_is_subset - is A a subset of B?
314  */
315 bool
317 {
318  int shortlen;
319  int longlen;
320  int i;
321 
322  /* Handle cases where either input is NULL */
323  if (a == NULL)
324  return true; /* empty set is a subset of anything */
325  if (b == NULL)
326  return bms_is_empty(a);
327  /* Check common words */
328  shortlen = Min(a->nwords, b->nwords);
329  for (i = 0; i < shortlen; i++)
330  {
331  if ((a->words[i] & ~b->words[i]) != 0)
332  return false;
333  }
334  /* Check extra words */
335  if (a->nwords > b->nwords)
336  {
337  longlen = a->nwords;
338  for (; i < longlen; i++)
339  {
340  if (a->words[i] != 0)
341  return false;
342  }
343  }
344  return true;
345 }
346 
347 /*
348  * bms_subset_compare - compare A and B for equality/subset relationships
349  *
350  * This is more efficient than testing bms_is_subset in both directions.
351  */
354 {
355  BMS_Comparison result;
356  int shortlen;
357  int longlen;
358  int i;
359 
360  /* Handle cases where either input is NULL */
361  if (a == NULL)
362  {
363  if (b == NULL)
364  return BMS_EQUAL;
365  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
366  }
367  if (b == NULL)
368  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
369  /* Check common words */
370  result = BMS_EQUAL; /* status so far */
371  shortlen = Min(a->nwords, b->nwords);
372  for (i = 0; i < shortlen; i++)
373  {
374  bitmapword aword = a->words[i];
375  bitmapword bword = b->words[i];
376 
377  if ((aword & ~bword) != 0)
378  {
379  /* a is not a subset of b */
380  if (result == BMS_SUBSET1)
381  return BMS_DIFFERENT;
382  result = BMS_SUBSET2;
383  }
384  if ((bword & ~aword) != 0)
385  {
386  /* b is not a subset of a */
387  if (result == BMS_SUBSET2)
388  return BMS_DIFFERENT;
389  result = BMS_SUBSET1;
390  }
391  }
392  /* Check extra words */
393  if (a->nwords > b->nwords)
394  {
395  longlen = a->nwords;
396  for (; i < longlen; i++)
397  {
398  if (a->words[i] != 0)
399  {
400  /* a is not a subset of b */
401  if (result == BMS_SUBSET1)
402  return BMS_DIFFERENT;
403  result = BMS_SUBSET2;
404  }
405  }
406  }
407  else if (a->nwords < b->nwords)
408  {
409  longlen = b->nwords;
410  for (; i < longlen; i++)
411  {
412  if (b->words[i] != 0)
413  {
414  /* b is not a subset of a */
415  if (result == BMS_SUBSET2)
416  return BMS_DIFFERENT;
417  result = BMS_SUBSET1;
418  }
419  }
420  }
421  return result;
422 }
423 
424 /*
425  * bms_is_member - is X a member of A?
426  */
427 bool
429 {
430  int wordnum,
431  bitnum;
432 
433  /* XXX better to just return false for x<0 ? */
434  if (x < 0)
435  elog(ERROR, "negative bitmapset member not allowed");
436  if (a == NULL)
437  return false;
438  wordnum = WORDNUM(x);
439  bitnum = BITNUM(x);
440  if (wordnum >= a->nwords)
441  return false;
442  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
443  return true;
444  return false;
445 }
446 
447 /*
448  * bms_member_index
449  * determine 0-based index of member x in the bitmap
450  *
451  * Returns (-1) when x is not a member.
452  */
453 int
455 {
456  int i;
457  int bitnum;
458  int wordnum;
459  int result = 0;
460  bitmapword mask;
461 
462  /* return -1 if not a member of the bitmap */
463  if (!bms_is_member(x, a))
464  return -1;
465 
466  wordnum = WORDNUM(x);
467  bitnum = BITNUM(x);
468 
469  /* count bits in preceding words */
470  for (i = 0; i < wordnum; i++)
471  {
472  bitmapword w = a->words[i];
473 
474  /* No need to count the bits in a zero word */
475  if (w != 0)
476  result += bmw_popcount(w);
477  }
478 
479  /*
480  * Now add bits of the last word, but only those before the item. We can
481  * do that by applying a mask and then using popcount again. To get
482  * 0-based index, we want to count only preceding bits, not the item
483  * itself, so we subtract 1.
484  */
485  mask = ((bitmapword) 1 << bitnum) - 1;
486  result += bmw_popcount(a->words[wordnum] & mask);
487 
488  return result;
489 }
490 
491 /*
492  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
493  */
494 bool
496 {
497  int shortlen;
498  int i;
499 
500  /* Handle cases where either input is NULL */
501  if (a == NULL || b == NULL)
502  return false;
503  /* Check words in common */
504  shortlen = Min(a->nwords, b->nwords);
505  for (i = 0; i < shortlen; i++)
506  {
507  if ((a->words[i] & b->words[i]) != 0)
508  return true;
509  }
510  return false;
511 }
512 
513 /*
514  * bms_overlap_list - does a set overlap an integer list?
515  */
516 bool
518 {
519  ListCell *lc;
520  int wordnum,
521  bitnum;
522 
523  if (a == NULL || b == NIL)
524  return false;
525 
526  foreach(lc, b)
527  {
528  int x = lfirst_int(lc);
529 
530  if (x < 0)
531  elog(ERROR, "negative bitmapset member not allowed");
532  wordnum = WORDNUM(x);
533  bitnum = BITNUM(x);
534  if (wordnum < a->nwords)
535  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
536  return true;
537  }
538 
539  return false;
540 }
541 
542 /*
543  * bms_nonempty_difference - do sets have a nonempty difference?
544  *
545  * i.e., are any members set in 'a' that are not also set in 'b'.
546  */
547 bool
549 {
550  int shortlen;
551  int i;
552 
553  /* Handle cases where either input is NULL */
554  if (a == NULL)
555  return false;
556  if (b == NULL)
557  return !bms_is_empty(a);
558  /* Check words in common */
559  shortlen = Min(a->nwords, b->nwords);
560  for (i = 0; i < shortlen; i++)
561  {
562  if ((a->words[i] & ~b->words[i]) != 0)
563  return true;
564  }
565  /* Check extra words in a */
566  for (; i < a->nwords; i++)
567  {
568  if (a->words[i] != 0)
569  return true;
570  }
571  return false;
572 }
573 
574 /*
575  * bms_singleton_member - return the sole integer member of set
576  *
577  * Raises error if |a| is not 1.
578  */
579 int
581 {
582  int result = -1;
583  int nwords;
584  int wordnum;
585 
586  if (a == NULL)
587  elog(ERROR, "bitmapset is empty");
588  nwords = a->nwords;
589  for (wordnum = 0; wordnum < nwords; wordnum++)
590  {
591  bitmapword w = a->words[wordnum];
592 
593  if (w != 0)
594  {
595  if (result >= 0 || HAS_MULTIPLE_ONES(w))
596  elog(ERROR, "bitmapset has multiple members");
597  result = wordnum * BITS_PER_BITMAPWORD;
598  result += bmw_rightmost_one_pos(w);
599  }
600  }
601  if (result < 0)
602  elog(ERROR, "bitmapset is empty");
603  return result;
604 }
605 
606 /*
607  * bms_get_singleton_member
608  *
609  * Test whether the given set is a singleton.
610  * If so, set *member to the value of its sole member, and return true.
611  * If not, return false, without changing *member.
612  *
613  * This is more convenient and faster than calling bms_membership() and then
614  * bms_singleton_member(), if we don't care about distinguishing empty sets
615  * from multiple-member sets.
616  */
617 bool
619 {
620  int result = -1;
621  int nwords;
622  int wordnum;
623 
624  if (a == NULL)
625  return false;
626  nwords = a->nwords;
627  for (wordnum = 0; wordnum < nwords; wordnum++)
628  {
629  bitmapword w = a->words[wordnum];
630 
631  if (w != 0)
632  {
633  if (result >= 0 || HAS_MULTIPLE_ONES(w))
634  return false;
635  result = wordnum * BITS_PER_BITMAPWORD;
636  result += bmw_rightmost_one_pos(w);
637  }
638  }
639  if (result < 0)
640  return false;
641  *member = result;
642  return true;
643 }
644 
645 /*
646  * bms_num_members - count members of set
647  */
648 int
650 {
651  int result = 0;
652  int nwords;
653  int wordnum;
654 
655  if (a == NULL)
656  return 0;
657  nwords = a->nwords;
658  for (wordnum = 0; wordnum < nwords; wordnum++)
659  {
660  bitmapword w = a->words[wordnum];
661 
662  /* No need to count the bits in a zero word */
663  if (w != 0)
664  result += bmw_popcount(w);
665  }
666  return result;
667 }
668 
669 /*
670  * bms_membership - does a set have zero, one, or multiple members?
671  *
672  * This is faster than making an exact count with bms_num_members().
673  */
676 {
677  BMS_Membership result = BMS_EMPTY_SET;
678  int nwords;
679  int wordnum;
680 
681  if (a == NULL)
682  return BMS_EMPTY_SET;
683  nwords = a->nwords;
684  for (wordnum = 0; wordnum < nwords; wordnum++)
685  {
686  bitmapword w = a->words[wordnum];
687 
688  if (w != 0)
689  {
690  if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
691  return BMS_MULTIPLE;
692  result = BMS_SINGLETON;
693  }
694  }
695  return result;
696 }
697 
698 /*
699  * bms_is_empty - is a set empty?
700  *
701  * This is even faster than bms_membership().
702  */
703 bool
705 {
706  int nwords;
707  int wordnum;
708 
709  if (a == NULL)
710  return true;
711  nwords = a->nwords;
712  for (wordnum = 0; wordnum < nwords; wordnum++)
713  {
714  bitmapword w = a->words[wordnum];
715 
716  if (w != 0)
717  return false;
718  }
719  return true;
720 }
721 
722 
723 /*
724  * These operations all "recycle" their non-const inputs, ie, either
725  * return the modified input or pfree it if it can't hold the result.
726  *
727  * These should generally be used in the style
728  *
729  * foo = bms_add_member(foo, x);
730  */
731 
732 
733 /*
734  * bms_add_member - add a specified member to set
735  *
736  * Input set is modified or recycled!
737  */
738 Bitmapset *
740 {
741  int wordnum,
742  bitnum;
743 
744  if (x < 0)
745  elog(ERROR, "negative bitmapset member not allowed");
746  if (a == NULL)
747  return bms_make_singleton(x);
748  wordnum = WORDNUM(x);
749  bitnum = BITNUM(x);
750 
751  /* enlarge the set if necessary */
752  if (wordnum >= a->nwords)
753  {
754  int oldnwords = a->nwords;
755  int i;
756 
757  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
758  a->nwords = wordnum + 1;
759  /* zero out the enlarged portion */
760  for (i = oldnwords; i < a->nwords; i++)
761  a->words[i] = 0;
762  }
763 
764  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
765  return a;
766 }
767 
768 /*
769  * bms_del_member - remove a specified member from set
770  *
771  * No error if x is not currently a member of set
772  *
773  * Input set is modified in-place!
774  */
775 Bitmapset *
777 {
778  int wordnum,
779  bitnum;
780 
781  if (x < 0)
782  elog(ERROR, "negative bitmapset member not allowed");
783  if (a == NULL)
784  return NULL;
785  wordnum = WORDNUM(x);
786  bitnum = BITNUM(x);
787  if (wordnum < a->nwords)
788  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
789  return a;
790 }
791 
792 /*
793  * bms_add_members - like bms_union, but left input is recycled
794  */
795 Bitmapset *
797 {
798  Bitmapset *result;
799  const Bitmapset *other;
800  int otherlen;
801  int i;
802 
803  /* Handle cases where either input is NULL */
804  if (a == NULL)
805  return bms_copy(b);
806  if (b == NULL)
807  return a;
808  /* Identify shorter and longer input; copy the longer one if needed */
809  if (a->nwords < b->nwords)
810  {
811  result = bms_copy(b);
812  other = a;
813  }
814  else
815  {
816  result = a;
817  other = b;
818  }
819  /* And union the shorter input into the result */
820  otherlen = other->nwords;
821  for (i = 0; i < otherlen; i++)
822  result->words[i] |= other->words[i];
823  if (result != a)
824  pfree(a);
825  return result;
826 }
827 
828 /*
829  * bms_add_range
830  * Add members in the range of 'lower' to 'upper' to the set.
831  *
832  * Note this could also be done by calling bms_add_member in a loop, however,
833  * using this function will be faster when the range is large as we work at
834  * the bitmapword level rather than at bit level.
835  */
836 Bitmapset *
838 {
839  int lwordnum,
840  lbitnum,
841  uwordnum,
842  ushiftbits,
843  wordnum;
844 
845  /* do nothing if nothing is called for, without further checking */
846  if (upper < lower)
847  return a;
848 
849  if (lower < 0)
850  elog(ERROR, "negative bitmapset member not allowed");
851  uwordnum = WORDNUM(upper);
852 
853  if (a == NULL)
854  {
855  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
856  a->type = T_Bitmapset;
857  a->nwords = uwordnum + 1;
858  }
859  else if (uwordnum >= a->nwords)
860  {
861  int oldnwords = a->nwords;
862  int i;
863 
864  /* ensure we have enough words to store the upper bit */
865  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
866  a->nwords = uwordnum + 1;
867  /* zero out the enlarged portion */
868  for (i = oldnwords; i < a->nwords; i++)
869  a->words[i] = 0;
870  }
871 
872  wordnum = lwordnum = WORDNUM(lower);
873 
874  lbitnum = BITNUM(lower);
875  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
876 
877  /*
878  * Special case when lwordnum is the same as uwordnum we must perform the
879  * upper and lower masking on the word.
880  */
881  if (lwordnum == uwordnum)
882  {
883  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
884  & (~(bitmapword) 0) >> ushiftbits;
885  }
886  else
887  {
888  /* turn on lbitnum and all bits left of it */
889  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
890 
891  /* turn on all bits for any intermediate words */
892  while (wordnum < uwordnum)
893  a->words[wordnum++] = ~(bitmapword) 0;
894 
895  /* turn on upper's bit and all bits right of it. */
896  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
897  }
898 
899  return a;
900 }
901 
902 /*
903  * bms_int_members - like bms_intersect, but left input is recycled
904  */
905 Bitmapset *
907 {
908  int shortlen;
909  int i;
910 
911  /* Handle cases where either input is NULL */
912  if (a == NULL)
913  return NULL;
914  if (b == NULL)
915  {
916  pfree(a);
917  return NULL;
918  }
919  /* Intersect b into a; we need never copy */
920  shortlen = Min(a->nwords, b->nwords);
921  for (i = 0; i < shortlen; i++)
922  a->words[i] &= b->words[i];
923  for (; i < a->nwords; i++)
924  a->words[i] = 0;
925  return a;
926 }
927 
928 /*
929  * bms_del_members - like bms_difference, but left input is recycled
930  */
931 Bitmapset *
933 {
934  int shortlen;
935  int i;
936 
937  /* Handle cases where either input is NULL */
938  if (a == NULL)
939  return NULL;
940  if (b == NULL)
941  return a;
942  /* Remove b's bits from a; we need never copy */
943  shortlen = Min(a->nwords, b->nwords);
944  for (i = 0; i < shortlen; i++)
945  a->words[i] &= ~b->words[i];
946  return a;
947 }
948 
949 /*
950  * bms_join - like bms_union, but *both* inputs are recycled
951  */
952 Bitmapset *
954 {
955  Bitmapset *result;
956  Bitmapset *other;
957  int otherlen;
958  int i;
959 
960  /* Handle cases where either input is NULL */
961  if (a == NULL)
962  return b;
963  if (b == NULL)
964  return a;
965  /* Identify shorter and longer input; use longer one as result */
966  if (a->nwords < b->nwords)
967  {
968  result = b;
969  other = a;
970  }
971  else
972  {
973  result = a;
974  other = b;
975  }
976  /* And union the shorter input into the result */
977  otherlen = other->nwords;
978  for (i = 0; i < otherlen; i++)
979  result->words[i] |= other->words[i];
980  if (other != result) /* pure paranoia */
981  pfree(other);
982  return result;
983 }
984 
985 /*
986  * bms_first_member - find and remove first member of a set
987  *
988  * Returns -1 if set is empty. NB: set is destructively modified!
989  *
990  * This is intended as support for iterating through the members of a set.
991  * The typical pattern is
992  *
993  * while ((x = bms_first_member(inputset)) >= 0)
994  * process member x;
995  *
996  * CAUTION: this destroys the content of "inputset". If the set must
997  * not be modified, use bms_next_member instead.
998  */
999 int
1001 {
1002  int nwords;
1003  int wordnum;
1004 
1005  if (a == NULL)
1006  return -1;
1007  nwords = a->nwords;
1008  for (wordnum = 0; wordnum < nwords; wordnum++)
1009  {
1010  bitmapword w = a->words[wordnum];
1011 
1012  if (w != 0)
1013  {
1014  int result;
1015 
1016  w = RIGHTMOST_ONE(w);
1017  a->words[wordnum] &= ~w;
1018 
1019  result = wordnum * BITS_PER_BITMAPWORD;
1020  result += bmw_rightmost_one_pos(w);
1021  return result;
1022  }
1023  }
1024  return -1;
1025 }
1026 
1027 /*
1028  * bms_next_member - find next member of a set
1029  *
1030  * Returns smallest member greater than "prevbit", or -2 if there is none.
1031  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
1032  *
1033  * This is intended as support for iterating through the members of a set.
1034  * The typical pattern is
1035  *
1036  * x = -1;
1037  * while ((x = bms_next_member(inputset, x)) >= 0)
1038  * process member x;
1039  *
1040  * Notice that when there are no more members, we return -2, not -1 as you
1041  * might expect. The rationale for that is to allow distinguishing the
1042  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1043  * It makes no difference in simple loop usage, but complex iteration logic
1044  * might need such an ability.
1045  */
1046 int
1047 bms_next_member(const Bitmapset *a, int prevbit)
1048 {
1049  int nwords;
1050  int wordnum;
1051  bitmapword mask;
1052 
1053  if (a == NULL)
1054  return -2;
1055  nwords = a->nwords;
1056  prevbit++;
1057  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1058  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1059  {
1060  bitmapword w = a->words[wordnum];
1061 
1062  /* ignore bits before prevbit */
1063  w &= mask;
1064 
1065  if (w != 0)
1066  {
1067  int result;
1068 
1069  result = wordnum * BITS_PER_BITMAPWORD;
1070  result += bmw_rightmost_one_pos(w);
1071  return result;
1072  }
1073 
1074  /* in subsequent words, consider all bits */
1075  mask = (~(bitmapword) 0);
1076  }
1077  return -2;
1078 }
1079 
1080 /*
1081  * bms_prev_member - find prev member of a set
1082  *
1083  * Returns largest member less than "prevbit", or -2 if there is none.
1084  * "prevbit" must NOT be more than one above the highest possible bit that can
1085  * be set at the Bitmapset at its current size.
1086  *
1087  * To ease finding the highest set bit for the initial loop, the special
1088  * prevbit value of -1 can be passed to have the function find the highest
1089  * valued member in the set.
1090  *
1091  * This is intended as support for iterating through the members of a set in
1092  * reverse. The typical pattern is
1093  *
1094  * x = -1;
1095  * while ((x = bms_prev_member(inputset, x)) >= 0)
1096  * process member x;
1097  *
1098  * Notice that when there are no more members, we return -2, not -1 as you
1099  * might expect. The rationale for that is to allow distinguishing the
1100  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1101  * It makes no difference in simple loop usage, but complex iteration logic
1102  * might need such an ability.
1103  */
1104 
1105 int
1106 bms_prev_member(const Bitmapset *a, int prevbit)
1107 {
1108  int wordnum;
1109  int ushiftbits;
1110  bitmapword mask;
1111 
1112  /*
1113  * If set is NULL or if there are no more bits to the right then we've
1114  * nothing to do.
1115  */
1116  if (a == NULL || prevbit == 0)
1117  return -2;
1118 
1119  /* transform -1 to the highest possible bit we could have set */
1120  if (prevbit == -1)
1121  prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
1122  else
1123  prevbit--;
1124 
1125  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
1126  mask = (~(bitmapword) 0) >> ushiftbits;
1127  for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
1128  {
1129  bitmapword w = a->words[wordnum];
1130 
1131  /* mask out bits left of prevbit */
1132  w &= mask;
1133 
1134  if (w != 0)
1135  {
1136  int result;
1137 
1138  result = wordnum * BITS_PER_BITMAPWORD;
1139  result += bmw_leftmost_one_pos(w);
1140  return result;
1141  }
1142 
1143  /* in subsequent words, consider all bits */
1144  mask = (~(bitmapword) 0);
1145  }
1146  return -2;
1147 }
1148 
1149 /*
1150  * bms_hash_value - compute a hash key for a Bitmapset
1151  *
1152  * Note: we must ensure that any two bitmapsets that are bms_equal() will
1153  * hash to the same value; in practice this means that trailing all-zero
1154  * words must not affect the result. Hence we strip those before applying
1155  * hash_any().
1156  */
1157 uint32
1159 {
1160  int lastword;
1161 
1162  if (a == NULL)
1163  return 0; /* All empty sets hash to 0 */
1164  for (lastword = a->nwords; --lastword >= 0;)
1165  {
1166  if (a->words[lastword] != 0)
1167  break;
1168  }
1169  if (lastword < 0)
1170  return 0; /* All empty sets hash to 0 */
1171  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1172  (lastword + 1) * sizeof(bitmapword)));
1173 }
1174 
1175 /*
1176  * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
1177  *
1178  * Note: don't forget to specify bitmap_match as the match function!
1179  */
1180 uint32
1181 bitmap_hash(const void *key, Size keysize)
1182 {
1183  Assert(keysize == sizeof(Bitmapset *));
1184  return bms_hash_value(*((const Bitmapset *const *) key));
1185 }
1186 
1187 /*
1188  * bitmap_match - match function to use with bitmap_hash
1189  */
1190 int
1191 bitmap_match(const void *key1, const void *key2, Size keysize)
1192 {
1193  Assert(keysize == sizeof(Bitmapset *));
1194  return !bms_equal(*((const Bitmapset *const *) key1),
1195  *((const Bitmapset *const *) key2));
1196 }
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:32
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.c:59
int bms_prev_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1106
uint32 bitmap_hash(const void *key, Size keysize)
Definition: bitmapset.c:1181
#define WORDNUM(x)
Definition: bitmapset.c:29
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:953
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:353
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1047
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1158
#define bmw_leftmost_one_pos(w)
Definition: bitmapset.c:58
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:580
void bms_free(Bitmapset *a)
Definition: bitmapset.c:209
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:649
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:428
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:186
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:739
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:226
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:260
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:796
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:932
#define BITNUM(x)
Definition: bitmapset.c:30
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:906
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:776
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:54
int bitmap_match(const void *key1, const void *key2, Size keysize)
Definition: bitmapset.c:1191
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:675
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:454
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
int bms_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:147
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
#define RIGHTMOST_ONE(x)
Definition: bitmapset.c:52
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:618
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:837
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:1000
#define bmw_popcount(w)
Definition: bitmapset.c:60
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:548
bool bms_overlap_list(const Bitmapset *a, const List *b)
Definition: bitmapset.c:517
BMS_Comparison
Definition: bitmapset.h:63
@ BMS_DIFFERENT
Definition: bitmapset.h:67
@ BMS_SUBSET1
Definition: bitmapset.h:65
@ BMS_EQUAL
Definition: bitmapset.h:64
@ BMS_SUBSET2
Definition: bitmapset.h:66
BMS_Membership
Definition: bitmapset.h:72
@ BMS_SINGLETON
Definition: bitmapset.h:74
@ BMS_EMPTY_SET
Definition: bitmapset.h:73
@ BMS_MULTIPLE
Definition: bitmapset.h:75
uint32 bitmapword
Definition: bitmapset.h:46
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:45
unsigned int uint32
Definition: c.h:442
#define Min(x, y)
Definition: c.h:937
size_t Size
Definition: c.h:541
#define ERROR
Definition: elog.h:35
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
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1306
void * palloc0(Size size)
Definition: mcxt.c:1230
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1321
void * palloc(Size size)
Definition: mcxt.c:1199
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:48
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:79
#define NIL
Definition: pg_list.h:66
#define lfirst_int(lc)
Definition: pg_list.h:171
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:570
int nwords
Definition: bitmapset.h:56
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:57
Definition: pg_list.h:52