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