PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, PostgreSQL Global Development Group
15  *
16  * IDENTIFICATION
17  * src/backend/nodes/bitmapset.c
18  *
19  *-------------------------------------------------------------------------
20  */
21 #include "postgres.h"
22 
23 #include "access/hash.h"
24 #include "nodes/pg_list.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 
55 /*
56  * Lookup tables to avoid need for bit-by-bit groveling
57  *
58  * rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit
59  * in a nonzero byte value x. The entry for x=0 is never used.
60  *
61  * number_of_ones[x] gives the number of one-bits (0-8) in a byte value x.
62  *
63  * We could make these tables larger and reduce the number of iterations
64  * in the functions that use them, but bytewise shifts and masks are
65  * especially fast on many machines, so working a byte at a time seems best.
66  */
67 
68 static const uint8 rightmost_one_pos[256] = {
69  0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
72  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
73  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
74  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
75  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
76  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
77  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
78  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
79  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
80  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
81  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
82  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
83  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
84  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
85 };
86 
87 static const uint8 number_of_ones[256] = {
88  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
89  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
91  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
97  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
99  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
100  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
102  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
104 };
105 
106 
107 /*
108  * bms_copy - make a palloc'd copy of a bitmapset
109  */
110 Bitmapset *
112 {
113  Bitmapset *result;
114  size_t size;
115 
116  if (a == NULL)
117  return NULL;
118  size = BITMAPSET_SIZE(a->nwords);
119  result = (Bitmapset *) palloc(size);
120  memcpy(result, a, size);
121  return result;
122 }
123 
124 /*
125  * bms_equal - are two bitmapsets equal?
126  *
127  * This is logical not physical equality; in particular, a NULL pointer will
128  * be reported as equal to a palloc'd value containing no members.
129  */
130 bool
131 bms_equal(const Bitmapset *a, const Bitmapset *b)
132 {
133  const Bitmapset *shorter;
134  const Bitmapset *longer;
135  int shortlen;
136  int longlen;
137  int i;
138 
139  /* Handle cases where either input is NULL */
140  if (a == NULL)
141  {
142  if (b == NULL)
143  return true;
144  return bms_is_empty(b);
145  }
146  else if (b == NULL)
147  return bms_is_empty(a);
148  /* Identify shorter and longer input */
149  if (a->nwords <= b->nwords)
150  {
151  shorter = a;
152  longer = b;
153  }
154  else
155  {
156  shorter = b;
157  longer = a;
158  }
159  /* And process */
160  shortlen = shorter->nwords;
161  for (i = 0; i < shortlen; i++)
162  {
163  if (shorter->words[i] != longer->words[i])
164  return false;
165  }
166  longlen = longer->nwords;
167  for (; i < longlen; i++)
168  {
169  if (longer->words[i] != 0)
170  return false;
171  }
172  return true;
173 }
174 
175 /*
176  * bms_make_singleton - build a bitmapset containing a single member
177  */
178 Bitmapset *
180 {
181  Bitmapset *result;
182  int wordnum,
183  bitnum;
184 
185  if (x < 0)
186  elog(ERROR, "negative bitmapset member not allowed");
187  wordnum = WORDNUM(x);
188  bitnum = BITNUM(x);
189  result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
190  result->nwords = wordnum + 1;
191  result->words[wordnum] = ((bitmapword) 1 << bitnum);
192  return result;
193 }
194 
195 /*
196  * bms_free - free a bitmapset
197  *
198  * Same as pfree except for allowing NULL input
199  */
200 void
202 {
203  if (a)
204  pfree(a);
205 }
206 
207 
208 /*
209  * These operations all make a freshly palloc'd result,
210  * leaving their inputs untouched
211  */
212 
213 
214 /*
215  * bms_union - set union
216  */
217 Bitmapset *
218 bms_union(const Bitmapset *a, const Bitmapset *b)
219 {
220  Bitmapset *result;
221  const Bitmapset *other;
222  int otherlen;
223  int i;
224 
225  /* Handle cases where either input is NULL */
226  if (a == NULL)
227  return bms_copy(b);
228  if (b == NULL)
229  return bms_copy(a);
230  /* Identify shorter and longer input; copy the longer one */
231  if (a->nwords <= b->nwords)
232  {
233  result = bms_copy(b);
234  other = a;
235  }
236  else
237  {
238  result = bms_copy(a);
239  other = b;
240  }
241  /* And union the shorter input into the result */
242  otherlen = other->nwords;
243  for (i = 0; i < otherlen; i++)
244  result->words[i] |= other->words[i];
245  return result;
246 }
247 
248 /*
249  * bms_intersect - set intersection
250  */
251 Bitmapset *
252 bms_intersect(const Bitmapset *a, const Bitmapset *b)
253 {
254  Bitmapset *result;
255  const Bitmapset *other;
256  int resultlen;
257  int i;
258 
259  /* Handle cases where either input is NULL */
260  if (a == NULL || b == NULL)
261  return NULL;
262  /* Identify shorter and longer input; copy the shorter one */
263  if (a->nwords <= b->nwords)
264  {
265  result = bms_copy(a);
266  other = b;
267  }
268  else
269  {
270  result = bms_copy(b);
271  other = a;
272  }
273  /* And intersect the longer input with the result */
274  resultlen = result->nwords;
275  for (i = 0; i < resultlen; i++)
276  result->words[i] &= other->words[i];
277  return result;
278 }
279 
280 /*
281  * bms_difference - set difference (ie, A without members of B)
282  */
283 Bitmapset *
284 bms_difference(const Bitmapset *a, const Bitmapset *b)
285 {
286  Bitmapset *result;
287  int shortlen;
288  int i;
289 
290  /* Handle cases where either input is NULL */
291  if (a == NULL)
292  return NULL;
293  if (b == NULL)
294  return bms_copy(a);
295  /* Copy the left input */
296  result = bms_copy(a);
297  /* And remove b's bits from result */
298  shortlen = Min(a->nwords, b->nwords);
299  for (i = 0; i < shortlen; i++)
300  result->words[i] &= ~b->words[i];
301  return result;
302 }
303 
304 /*
305  * bms_is_subset - is A a subset of B?
306  */
307 bool
308 bms_is_subset(const Bitmapset *a, const Bitmapset *b)
309 {
310  int shortlen;
311  int longlen;
312  int i;
313 
314  /* Handle cases where either input is NULL */
315  if (a == NULL)
316  return true; /* empty set is a subset of anything */
317  if (b == NULL)
318  return bms_is_empty(a);
319  /* Check common words */
320  shortlen = Min(a->nwords, b->nwords);
321  for (i = 0; i < shortlen; i++)
322  {
323  if ((a->words[i] & ~b->words[i]) != 0)
324  return false;
325  }
326  /* Check extra words */
327  if (a->nwords > b->nwords)
328  {
329  longlen = a->nwords;
330  for (; i < longlen; i++)
331  {
332  if (a->words[i] != 0)
333  return false;
334  }
335  }
336  return true;
337 }
338 
339 /*
340  * bms_subset_compare - compare A and B for equality/subset relationships
341  *
342  * This is more efficient than testing bms_is_subset in both directions.
343  */
346 {
347  BMS_Comparison result;
348  int shortlen;
349  int longlen;
350  int i;
351 
352  /* Handle cases where either input is NULL */
353  if (a == NULL)
354  {
355  if (b == NULL)
356  return BMS_EQUAL;
357  return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
358  }
359  if (b == NULL)
360  return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
361  /* Check common words */
362  result = BMS_EQUAL; /* status so far */
363  shortlen = Min(a->nwords, b->nwords);
364  for (i = 0; i < shortlen; i++)
365  {
366  bitmapword aword = a->words[i];
367  bitmapword bword = b->words[i];
368 
369  if ((aword & ~bword) != 0)
370  {
371  /* a is not a subset of b */
372  if (result == BMS_SUBSET1)
373  return BMS_DIFFERENT;
374  result = BMS_SUBSET2;
375  }
376  if ((bword & ~aword) != 0)
377  {
378  /* b is not a subset of a */
379  if (result == BMS_SUBSET2)
380  return BMS_DIFFERENT;
381  result = BMS_SUBSET1;
382  }
383  }
384  /* Check extra words */
385  if (a->nwords > b->nwords)
386  {
387  longlen = a->nwords;
388  for (; i < longlen; i++)
389  {
390  if (a->words[i] != 0)
391  {
392  /* a is not a subset of b */
393  if (result == BMS_SUBSET1)
394  return BMS_DIFFERENT;
395  result = BMS_SUBSET2;
396  }
397  }
398  }
399  else if (a->nwords < b->nwords)
400  {
401  longlen = b->nwords;
402  for (; i < longlen; i++)
403  {
404  if (b->words[i] != 0)
405  {
406  /* b is not a subset of a */
407  if (result == BMS_SUBSET2)
408  return BMS_DIFFERENT;
409  result = BMS_SUBSET1;
410  }
411  }
412  }
413  return result;
414 }
415 
416 /*
417  * bms_is_member - is X a member of A?
418  */
419 bool
420 bms_is_member(int x, const Bitmapset *a)
421 {
422  int wordnum,
423  bitnum;
424 
425  /* XXX better to just return false for x<0 ? */
426  if (x < 0)
427  elog(ERROR, "negative bitmapset member not allowed");
428  if (a == NULL)
429  return false;
430  wordnum = WORDNUM(x);
431  bitnum = BITNUM(x);
432  if (wordnum >= a->nwords)
433  return false;
434  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
435  return true;
436  return false;
437 }
438 
439 /*
440  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
441  */
442 bool
443 bms_overlap(const Bitmapset *a, const Bitmapset *b)
444 {
445  int shortlen;
446  int i;
447 
448  /* Handle cases where either input is NULL */
449  if (a == NULL || b == NULL)
450  return false;
451  /* Check words in common */
452  shortlen = Min(a->nwords, b->nwords);
453  for (i = 0; i < shortlen; i++)
454  {
455  if ((a->words[i] & b->words[i]) != 0)
456  return true;
457  }
458  return false;
459 }
460 
461 /*
462  * bms_overlap_list - does a set overlap an integer list?
463  */
464 bool
465 bms_overlap_list(const Bitmapset *a, const List *b)
466 {
467  ListCell *lc;
468  int wordnum,
469  bitnum;
470 
471  if (a == NULL || b == NIL)
472  return false;
473 
474  foreach(lc, b)
475  {
476  int x = lfirst_int(lc);
477 
478  if (x < 0)
479  elog(ERROR, "negative bitmapset member not allowed");
480  wordnum = WORDNUM(x);
481  bitnum = BITNUM(x);
482  if (wordnum < a->nwords)
483  if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
484  return true;
485  }
486 
487  return false;
488 }
489 
490 /*
491  * bms_nonempty_difference - do sets have a nonempty difference?
492  */
493 bool
495 {
496  int shortlen;
497  int i;
498 
499  /* Handle cases where either input is NULL */
500  if (a == NULL)
501  return false;
502  if (b == NULL)
503  return !bms_is_empty(a);
504  /* Check words in common */
505  shortlen = Min(a->nwords, b->nwords);
506  for (i = 0; i < shortlen; i++)
507  {
508  if ((a->words[i] & ~b->words[i]) != 0)
509  return true;
510  }
511  /* Check extra words in a */
512  for (; i < a->nwords; i++)
513  {
514  if (a->words[i] != 0)
515  return true;
516  }
517  return false;
518 }
519 
520 /*
521  * bms_singleton_member - return the sole integer member of set
522  *
523  * Raises error if |a| is not 1.
524  */
525 int
527 {
528  int result = -1;
529  int nwords;
530  int wordnum;
531 
532  if (a == NULL)
533  elog(ERROR, "bitmapset is empty");
534  nwords = a->nwords;
535  for (wordnum = 0; wordnum < nwords; wordnum++)
536  {
537  bitmapword w = a->words[wordnum];
538 
539  if (w != 0)
540  {
541  if (result >= 0 || HAS_MULTIPLE_ONES(w))
542  elog(ERROR, "bitmapset has multiple members");
543  result = wordnum * BITS_PER_BITMAPWORD;
544  while ((w & 255) == 0)
545  {
546  w >>= 8;
547  result += 8;
548  }
549  result += rightmost_one_pos[w & 255];
550  }
551  }
552  if (result < 0)
553  elog(ERROR, "bitmapset is empty");
554  return result;
555 }
556 
557 /*
558  * bms_get_singleton_member
559  *
560  * Test whether the given set is a singleton.
561  * If so, set *member to the value of its sole member, and return TRUE.
562  * If not, return FALSE, without changing *member.
563  *
564  * This is more convenient and faster than calling bms_membership() and then
565  * bms_singleton_member(), if we don't care about distinguishing empty sets
566  * from multiple-member sets.
567  */
568 bool
569 bms_get_singleton_member(const Bitmapset *a, int *member)
570 {
571  int result = -1;
572  int nwords;
573  int wordnum;
574 
575  if (a == NULL)
576  return false;
577  nwords = a->nwords;
578  for (wordnum = 0; wordnum < nwords; wordnum++)
579  {
580  bitmapword w = a->words[wordnum];
581 
582  if (w != 0)
583  {
584  if (result >= 0 || HAS_MULTIPLE_ONES(w))
585  return false;
586  result = wordnum * BITS_PER_BITMAPWORD;
587  while ((w & 255) == 0)
588  {
589  w >>= 8;
590  result += 8;
591  }
592  result += rightmost_one_pos[w & 255];
593  }
594  }
595  if (result < 0)
596  return false;
597  *member = result;
598  return true;
599 }
600 
601 /*
602  * bms_num_members - count members of set
603  */
604 int
606 {
607  int result = 0;
608  int nwords;
609  int wordnum;
610 
611  if (a == NULL)
612  return 0;
613  nwords = a->nwords;
614  for (wordnum = 0; wordnum < nwords; wordnum++)
615  {
616  bitmapword w = a->words[wordnum];
617 
618  /* we assume here that bitmapword is an unsigned type */
619  while (w != 0)
620  {
621  result += number_of_ones[w & 255];
622  w >>= 8;
623  }
624  }
625  return result;
626 }
627 
628 /*
629  * bms_membership - does a set have zero, one, or multiple members?
630  *
631  * This is faster than making an exact count with bms_num_members().
632  */
635 {
636  BMS_Membership result = BMS_EMPTY_SET;
637  int nwords;
638  int wordnum;
639 
640  if (a == NULL)
641  return BMS_EMPTY_SET;
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 != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
650  return BMS_MULTIPLE;
651  result = BMS_SINGLETON;
652  }
653  }
654  return result;
655 }
656 
657 /*
658  * bms_is_empty - is a set empty?
659  *
660  * This is even faster than bms_membership().
661  */
662 bool
664 {
665  int nwords;
666  int wordnum;
667 
668  if (a == NULL)
669  return true;
670  nwords = a->nwords;
671  for (wordnum = 0; wordnum < nwords; wordnum++)
672  {
673  bitmapword w = a->words[wordnum];
674 
675  if (w != 0)
676  return false;
677  }
678  return true;
679 }
680 
681 
682 /*
683  * These operations all "recycle" their non-const inputs, ie, either
684  * return the modified input or pfree it if it can't hold the result.
685  *
686  * These should generally be used in the style
687  *
688  * foo = bms_add_member(foo, x);
689  */
690 
691 
692 /*
693  * bms_add_member - add a specified member to set
694  *
695  * Input set is modified or recycled!
696  */
697 Bitmapset *
699 {
700  int wordnum,
701  bitnum;
702 
703  if (x < 0)
704  elog(ERROR, "negative bitmapset member not allowed");
705  if (a == NULL)
706  return bms_make_singleton(x);
707  wordnum = WORDNUM(x);
708  bitnum = BITNUM(x);
709 
710  /* enlarge the set if necessary */
711  if (wordnum >= a->nwords)
712  {
713  int oldnwords = a->nwords;
714  int i;
715 
716  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
717  a->nwords = wordnum + 1;
718  /* zero out the enlarged portion */
719  for (i = oldnwords; i < a->nwords; i++)
720  a->words[i] = 0;
721  }
722 
723  a->words[wordnum] |= ((bitmapword) 1 << bitnum);
724  return a;
725 }
726 
727 /*
728  * bms_del_member - remove a specified member from set
729  *
730  * No error if x is not currently a member of set
731  *
732  * Input set is modified in-place!
733  */
734 Bitmapset *
736 {
737  int wordnum,
738  bitnum;
739 
740  if (x < 0)
741  elog(ERROR, "negative bitmapset member not allowed");
742  if (a == NULL)
743  return NULL;
744  wordnum = WORDNUM(x);
745  bitnum = BITNUM(x);
746  if (wordnum < a->nwords)
747  a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
748  return a;
749 }
750 
751 /*
752  * bms_add_members - like bms_union, but left input is recycled
753  */
754 Bitmapset *
756 {
757  Bitmapset *result;
758  const Bitmapset *other;
759  int otherlen;
760  int i;
761 
762  /* Handle cases where either input is NULL */
763  if (a == NULL)
764  return bms_copy(b);
765  if (b == NULL)
766  return a;
767  /* Identify shorter and longer input; copy the longer one if needed */
768  if (a->nwords < b->nwords)
769  {
770  result = bms_copy(b);
771  other = a;
772  }
773  else
774  {
775  result = a;
776  other = b;
777  }
778  /* And union the shorter input into the result */
779  otherlen = other->nwords;
780  for (i = 0; i < otherlen; i++)
781  result->words[i] |= other->words[i];
782  if (result != a)
783  pfree(a);
784  return result;
785 }
786 
787 /*
788  * bms_int_members - like bms_intersect, but left input is recycled
789  */
790 Bitmapset *
792 {
793  int shortlen;
794  int i;
795 
796  /* Handle cases where either input is NULL */
797  if (a == NULL)
798  return NULL;
799  if (b == NULL)
800  {
801  pfree(a);
802  return NULL;
803  }
804  /* Intersect b into a; we need never copy */
805  shortlen = Min(a->nwords, b->nwords);
806  for (i = 0; i < shortlen; i++)
807  a->words[i] &= b->words[i];
808  for (; i < a->nwords; i++)
809  a->words[i] = 0;
810  return a;
811 }
812 
813 /*
814  * bms_del_members - like bms_difference, but left input is recycled
815  */
816 Bitmapset *
818 {
819  int shortlen;
820  int i;
821 
822  /* Handle cases where either input is NULL */
823  if (a == NULL)
824  return NULL;
825  if (b == NULL)
826  return a;
827  /* Remove b's bits from a; we need never copy */
828  shortlen = Min(a->nwords, b->nwords);
829  for (i = 0; i < shortlen; i++)
830  a->words[i] &= ~b->words[i];
831  return a;
832 }
833 
834 /*
835  * bms_join - like bms_union, but *both* inputs are recycled
836  */
837 Bitmapset *
839 {
840  Bitmapset *result;
841  Bitmapset *other;
842  int otherlen;
843  int i;
844 
845  /* Handle cases where either input is NULL */
846  if (a == NULL)
847  return b;
848  if (b == NULL)
849  return a;
850  /* Identify shorter and longer input; use longer one as result */
851  if (a->nwords < b->nwords)
852  {
853  result = b;
854  other = a;
855  }
856  else
857  {
858  result = a;
859  other = b;
860  }
861  /* And union the shorter input into the result */
862  otherlen = other->nwords;
863  for (i = 0; i < otherlen; i++)
864  result->words[i] |= other->words[i];
865  if (other != result) /* pure paranoia */
866  pfree(other);
867  return result;
868 }
869 
870 /*
871  * bms_first_member - find and remove first member of a set
872  *
873  * Returns -1 if set is empty. NB: set is destructively modified!
874  *
875  * This is intended as support for iterating through the members of a set.
876  * The typical pattern is
877  *
878  * while ((x = bms_first_member(inputset)) >= 0)
879  * process member x;
880  *
881  * CAUTION: this destroys the content of "inputset". If the set must
882  * not be modified, use bms_next_member instead.
883  */
884 int
886 {
887  int nwords;
888  int wordnum;
889 
890  if (a == NULL)
891  return -1;
892  nwords = a->nwords;
893  for (wordnum = 0; wordnum < nwords; wordnum++)
894  {
895  bitmapword w = a->words[wordnum];
896 
897  if (w != 0)
898  {
899  int result;
900 
901  w = RIGHTMOST_ONE(w);
902  a->words[wordnum] &= ~w;
903 
904  result = wordnum * BITS_PER_BITMAPWORD;
905  while ((w & 255) == 0)
906  {
907  w >>= 8;
908  result += 8;
909  }
910  result += rightmost_one_pos[w & 255];
911  return result;
912  }
913  }
914  return -1;
915 }
916 
917 /*
918  * bms_next_member - find next member of a set
919  *
920  * Returns smallest member greater than "prevbit", or -2 if there is none.
921  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
922  *
923  * This is intended as support for iterating through the members of a set.
924  * The typical pattern is
925  *
926  * x = -1;
927  * while ((x = bms_next_member(inputset, x)) >= 0)
928  * process member x;
929  *
930  * Notice that when there are no more members, we return -2, not -1 as you
931  * might expect. The rationale for that is to allow distinguishing the
932  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
933  * It makes no difference in simple loop usage, but complex iteration logic
934  * might need such an ability.
935  */
936 int
937 bms_next_member(const Bitmapset *a, int prevbit)
938 {
939  int nwords;
940  int wordnum;
941  bitmapword mask;
942 
943  if (a == NULL)
944  return -2;
945  nwords = a->nwords;
946  prevbit++;
947  mask = (~(bitmapword) 0) << BITNUM(prevbit);
948  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
949  {
950  bitmapword w = a->words[wordnum];
951 
952  /* ignore bits before prevbit */
953  w &= mask;
954 
955  if (w != 0)
956  {
957  int result;
958 
959  result = wordnum * BITS_PER_BITMAPWORD;
960  while ((w & 255) == 0)
961  {
962  w >>= 8;
963  result += 8;
964  }
965  result += rightmost_one_pos[w & 255];
966  return result;
967  }
968 
969  /* in subsequent words, consider all bits */
970  mask = (~(bitmapword) 0);
971  }
972  return -2;
973 }
974 
975 /*
976  * bms_hash_value - compute a hash key for a Bitmapset
977  *
978  * Note: we must ensure that any two bitmapsets that are bms_equal() will
979  * hash to the same value; in practice this means that trailing all-zero
980  * words must not affect the result. Hence we strip those before applying
981  * hash_any().
982  */
983 uint32
985 {
986  int lastword;
987 
988  if (a == NULL)
989  return 0; /* All empty sets hash to 0 */
990  for (lastword = a->nwords; --lastword >= 0;)
991  {
992  if (a->words[lastword] != 0)
993  break;
994  }
995  if (lastword < 0)
996  return 0; /* All empty sets hash to 0 */
997  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
998  (lastword + 1) * sizeof(bitmapword)));
999 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
#define NIL
Definition: pg_list.h:69
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:885
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
#define WORDNUM(x)
Definition: bitmapset.c:27
#define Min(x, y)
Definition: c.h:812
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:937
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
unsigned char uint8
Definition: c.h:256
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:569
#define HAS_MULTIPLE_ONES(x)
Definition: bitmapset.c:52
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:33
#define BITNUM(x)
Definition: bitmapset.c:28
uint32 bitmapword
Definition: bitmapset.h:34
#define BITMAPSET_SIZE(nwords)
Definition: bitmapset.c:30
void pfree(void *pointer)
Definition: mcxt.c:949
BMS_Membership
Definition: bitmapset.h:54
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:107
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
static const uint8 rightmost_one_pos[256]
Definition: bitmapset.c:68
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:984
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:605
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:179
bitmapword words[FLEXIBLE_ARRAY_MEMBER]
Definition: bitmapset.h:40
unsigned int uint32
Definition: c.h:258
bool bms_overlap_list(const Bitmapset *a, const List *b)
Definition: bitmapset.c:465
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
#define RIGHTMOST_ONE(x)
Definition: bitmapset.c:50
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:634
void * palloc0(Size size)
Definition: mcxt.c:877
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:526
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:252
static const uint8 number_of_ones[256]
Definition: bitmapset.c:87
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:345
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:428
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:218
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:698
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:962
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:817
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
void * palloc(Size size)
Definition: mcxt.c:848
int i
#define elog
Definition: elog.h:219
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:791
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:735
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:420
BMS_Comparison
Definition: bitmapset.h:45
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:131
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494