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