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