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-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_add_range
789  * Add members in the range of 'lower' to 'upper' to the set.
790  *
791  * Note this could also be done by calling bms_add_member in a loop, however,
792  * using this function will be faster when the range is large as we work at
793  * the bitmapword level rather than at bit level.
794  */
795 Bitmapset *
797 {
798  int lwordnum,
799  lbitnum,
800  uwordnum,
801  ushiftbits,
802  wordnum;
803 
804  if (lower < 0 || upper < 0)
805  elog(ERROR, "negative bitmapset member not allowed");
806  if (lower > upper)
807  elog(ERROR, "lower range must not be above upper range");
808  uwordnum = WORDNUM(upper);
809 
810  if (a == NULL)
811  {
812  a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
813  a->nwords = uwordnum + 1;
814  }
815 
816  /* ensure we have enough words to store the upper bit */
817  else if (uwordnum >= a->nwords)
818  {
819  int oldnwords = a->nwords;
820  int i;
821 
822  a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
823  a->nwords = uwordnum + 1;
824  /* zero out the enlarged portion */
825  for (i = oldnwords; i < a->nwords; i++)
826  a->words[i] = 0;
827  }
828 
829  wordnum = lwordnum = WORDNUM(lower);
830 
831  lbitnum = BITNUM(lower);
832  ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
833 
834  /*
835  * Special case when lwordnum is the same as uwordnum we must perform the
836  * upper and lower masking on the word.
837  */
838  if (lwordnum == uwordnum)
839  {
840  a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
841  & (~(bitmapword) 0) >> ushiftbits;
842  }
843  else
844  {
845  /* turn on lbitnum and all bits left of it */
846  a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
847 
848  /* turn on all bits for any intermediate words */
849  while (wordnum < uwordnum)
850  a->words[wordnum++] = ~(bitmapword) 0;
851 
852  /* turn on upper's bit and all bits right of it. */
853  a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
854  }
855 
856  return a;
857 }
858 
859 /*
860  * bms_int_members - like bms_intersect, but left input is recycled
861  */
862 Bitmapset *
864 {
865  int shortlen;
866  int i;
867 
868  /* Handle cases where either input is NULL */
869  if (a == NULL)
870  return NULL;
871  if (b == NULL)
872  {
873  pfree(a);
874  return NULL;
875  }
876  /* Intersect b into a; we need never copy */
877  shortlen = Min(a->nwords, b->nwords);
878  for (i = 0; i < shortlen; i++)
879  a->words[i] &= b->words[i];
880  for (; i < a->nwords; i++)
881  a->words[i] = 0;
882  return a;
883 }
884 
885 /*
886  * bms_del_members - like bms_difference, but left input is recycled
887  */
888 Bitmapset *
890 {
891  int shortlen;
892  int i;
893 
894  /* Handle cases where either input is NULL */
895  if (a == NULL)
896  return NULL;
897  if (b == NULL)
898  return a;
899  /* Remove b's bits from a; we need never copy */
900  shortlen = Min(a->nwords, b->nwords);
901  for (i = 0; i < shortlen; i++)
902  a->words[i] &= ~b->words[i];
903  return a;
904 }
905 
906 /*
907  * bms_join - like bms_union, but *both* inputs are recycled
908  */
909 Bitmapset *
911 {
912  Bitmapset *result;
913  Bitmapset *other;
914  int otherlen;
915  int i;
916 
917  /* Handle cases where either input is NULL */
918  if (a == NULL)
919  return b;
920  if (b == NULL)
921  return a;
922  /* Identify shorter and longer input; use longer one as result */
923  if (a->nwords < b->nwords)
924  {
925  result = b;
926  other = a;
927  }
928  else
929  {
930  result = a;
931  other = b;
932  }
933  /* And union the shorter input into the result */
934  otherlen = other->nwords;
935  for (i = 0; i < otherlen; i++)
936  result->words[i] |= other->words[i];
937  if (other != result) /* pure paranoia */
938  pfree(other);
939  return result;
940 }
941 
942 /*
943  * bms_first_member - find and remove first member of a set
944  *
945  * Returns -1 if set is empty. NB: set is destructively modified!
946  *
947  * This is intended as support for iterating through the members of a set.
948  * The typical pattern is
949  *
950  * while ((x = bms_first_member(inputset)) >= 0)
951  * process member x;
952  *
953  * CAUTION: this destroys the content of "inputset". If the set must
954  * not be modified, use bms_next_member instead.
955  */
956 int
958 {
959  int nwords;
960  int wordnum;
961 
962  if (a == NULL)
963  return -1;
964  nwords = a->nwords;
965  for (wordnum = 0; wordnum < nwords; wordnum++)
966  {
967  bitmapword w = a->words[wordnum];
968 
969  if (w != 0)
970  {
971  int result;
972 
973  w = RIGHTMOST_ONE(w);
974  a->words[wordnum] &= ~w;
975 
976  result = wordnum * BITS_PER_BITMAPWORD;
977  while ((w & 255) == 0)
978  {
979  w >>= 8;
980  result += 8;
981  }
982  result += rightmost_one_pos[w & 255];
983  return result;
984  }
985  }
986  return -1;
987 }
988 
989 /*
990  * bms_next_member - find next member of a set
991  *
992  * Returns smallest member greater than "prevbit", or -2 if there is none.
993  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
994  *
995  * This is intended as support for iterating through the members of a set.
996  * The typical pattern is
997  *
998  * x = -1;
999  * while ((x = bms_next_member(inputset, x)) >= 0)
1000  * process member x;
1001  *
1002  * Notice that when there are no more members, we return -2, not -1 as you
1003  * might expect. The rationale for that is to allow distinguishing the
1004  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
1005  * It makes no difference in simple loop usage, but complex iteration logic
1006  * might need such an ability.
1007  */
1008 int
1009 bms_next_member(const Bitmapset *a, int prevbit)
1010 {
1011  int nwords;
1012  int wordnum;
1013  bitmapword mask;
1014 
1015  if (a == NULL)
1016  return -2;
1017  nwords = a->nwords;
1018  prevbit++;
1019  mask = (~(bitmapword) 0) << BITNUM(prevbit);
1020  for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
1021  {
1022  bitmapword w = a->words[wordnum];
1023 
1024  /* ignore bits before prevbit */
1025  w &= mask;
1026 
1027  if (w != 0)
1028  {
1029  int result;
1030 
1031  result = wordnum * BITS_PER_BITMAPWORD;
1032  while ((w & 255) == 0)
1033  {
1034  w >>= 8;
1035  result += 8;
1036  }
1037  result += rightmost_one_pos[w & 255];
1038  return result;
1039  }
1040 
1041  /* in subsequent words, consider all bits */
1042  mask = (~(bitmapword) 0);
1043  }
1044  return -2;
1045 }
1046 
1047 /*
1048  * bms_hash_value - compute a hash key for a Bitmapset
1049  *
1050  * Note: we must ensure that any two bitmapsets that are bms_equal() will
1051  * hash to the same value; in practice this means that trailing all-zero
1052  * words must not affect the result. Hence we strip those before applying
1053  * hash_any().
1054  */
1055 uint32
1057 {
1058  int lastword;
1059 
1060  if (a == NULL)
1061  return 0; /* All empty sets hash to 0 */
1062  for (lastword = a->nwords; --lastword >= 0;)
1063  {
1064  if (a->words[lastword] != 0)
1065  break;
1066  }
1067  if (lastword < 0)
1068  return 0; /* All empty sets hash to 0 */
1069  return DatumGetUInt32(hash_any((const unsigned char *) a->words,
1070  (lastword + 1) * sizeof(bitmapword)));
1071 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
#define NIL
Definition: pg_list.h:69
int bms_first_member(Bitmapset *a)
Definition: bitmapset.c:957
int nwords
Definition: bitmapset.h:39
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:111
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
#define WORDNUM(x)
Definition: bitmapset.c:27
#define Min(x, y)
Definition: c.h:802
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1009
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
unsigned char uint8
Definition: c.h:294
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
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
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
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:796
#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:910
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:1056
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:296
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:889
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:863
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