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