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