granicus.if.org Git - postgresql/blob - src/backend/nodes/bitmapset.c

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