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, PostgreSQL Global Development Group
  15  *
  16  * IDENTIFICATION
  17  *        $Header: /cvsroot/pgsql/src/backend/nodes/bitmapset.c,v 1.2 2003/06/29 23:05:04 tgl Exp $
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21 #include "postgres.h"
  22
  23 #include "nodes/bitmapset.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         {
 147                 return bms_is_empty(a);
 148         }
 149         /* Identify shorter and longer input */
 150         if (a->nwords <= b->nwords)
 151         {
 152                 shorter = a;
 153                 longer = b;
 154         }
 155         else
 156         {
 157                 shorter = b;
 158                 longer = a;
 159         }
 160         /* And process */
 161         shortlen = shorter->nwords;
 162         for (i = 0; i < shortlen; i++)
 163         {
 164                 if (shorter->words[i] != longer->words[i])
 165                         return false;
 166         }
 167         longlen = longer->nwords;
 168         for (; i < longlen; i++)
 169         {
 170                 if (longer->words[i] != 0)
 171                         return false;
 172         }
 173         return true;
 174 }
 175
 176 /*
 177  * bms_make_singleton - build a bitmapset containing a single member
 178  */
 179 Bitmapset *
 180 bms_make_singleton(int x)
 181 {
 182         Bitmapset  *result;
 183         int                     wordnum,
 184                                 bitnum;
 185
 186         if (x < 0)
 187                 elog(ERROR, "bms_make_singleton: negative set member not allowed");
 188         wordnum = WORDNUM(x);
 189         bitnum = BITNUM(x);
 190         result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
 191         result->nwords = wordnum + 1;
 192         result->words[wordnum] = ((bitmapword) 1 << bitnum);
 193         return result;
 194 }
 195
 196 /*
 197  * bms_free - free a bitmapset
 198  *
 199  * Same as pfree except for allowing NULL input
 200  */
 201 void
 202 bms_free(Bitmapset *a)
 203 {
 204         if (a)
 205                 pfree(a);
 206 }
 207
 208
 209 /*
 210  * These operations all make a freshly palloc'd result,
 211  * leaving their inputs untouched
 212  */
 213
 214
 215 /*
 216  * bms_union - set union
 217  */
 218 Bitmapset *
 219 bms_union(const Bitmapset *a, const Bitmapset *b)
 220 {
 221         Bitmapset  *result;
 222         const Bitmapset *other;
 223         int                     otherlen;
 224         int                     i;
 225
 226         /* Handle cases where either input is NULL */
 227         if (a == NULL)
 228                 return bms_copy(b);
 229         if (b == NULL)
 230                 return bms_copy(a);
 231         /* Identify shorter and longer input; copy the longer one */
 232         if (a->nwords <= b->nwords)
 233         {
 234                 result = bms_copy(b);
 235                 other = a;
 236         }
 237         else
 238         {
 239                 result = bms_copy(a);
 240                 other = b;
 241         }
 242         /* And union the shorter input into the result */
 243         otherlen = other->nwords;
 244         for (i = 0; i < otherlen; i++)
 245         {
 246                 result->words[i] |= other->words[i];
 247         }
 248         return result;
 249 }
 250
 251 /*
 252  * bms_intersect - set intersection
 253  */
 254 Bitmapset *
 255 bms_intersect(const Bitmapset *a, const Bitmapset *b)
 256 {
 257         Bitmapset  *result;
 258         const Bitmapset *other;
 259         int                     resultlen;
 260         int                     i;
 261
 262         /* Handle cases where either input is NULL */
 263         if (a == NULL || b == NULL)
 264                 return NULL;
 265         /* Identify shorter and longer input; copy the shorter one */
 266         if (a->nwords <= b->nwords)
 267         {
 268                 result = bms_copy(a);
 269                 other = b;
 270         }
 271         else
 272         {
 273                 result = bms_copy(b);
 274                 other = a;
 275         }
 276         /* And intersect the longer input with the result */
 277         resultlen = result->nwords;
 278         for (i = 0; i < resultlen; i++)
 279         {
 280                 result->words[i] &= other->words[i];
 281         }
 282         return result;
 283 }
 284
 285 /*
 286  * bms_difference - set difference (ie, A without members of B)
 287  */
 288 Bitmapset *
 289 bms_difference(const Bitmapset *a, const Bitmapset *b)
 290 {
 291         Bitmapset  *result;
 292         int                     shortlen;
 293         int                     i;
 294
 295         /* Handle cases where either input is NULL */
 296         if (a == NULL)
 297                 return NULL;
 298         if (b == NULL)
 299                 return bms_copy(a);
 300         /* Copy the left input */
 301         result = bms_copy(a);
 302         /* And remove b's bits from result */
 303         shortlen = Min(a->nwords, b->nwords);
 304         for (i = 0; i < shortlen; i++)
 305         {
 306                 result->words[i] &= ~ b->words[i];
 307         }
 308         return result;
 309 }
 310
 311 /*
 312  * bms_is_subset - is A a subset of B?
 313  */
 314 bool
 315 bms_is_subset(const Bitmapset *a, const Bitmapset *b)
 316 {
 317         int                     shortlen;
 318         int                     longlen;
 319         int                     i;
 320
 321         /* Handle cases where either input is NULL */
 322         if (a == NULL)
 323                 return true;                    /* empty set is a subset of anything */
 324         if (b == NULL)
 325                 return bms_is_empty(a);
 326         /* Check common words */
 327         shortlen = Min(a->nwords, b->nwords);
 328         for (i = 0; i < shortlen; i++)
 329         {
 330                 if ((a->words[i] & ~ b->words[i]) != 0)
 331                         return false;
 332         }
 333         /* Check extra words */
 334         if (a->nwords > b->nwords)
 335         {
 336                 longlen = a->nwords;
 337                 for (; i < longlen; i++)
 338                 {
 339                         if (a->words[i] != 0)
 340                                 return false;
 341                 }
 342         }
 343         return true;
 344 }
 345
 346 /*
 347  * bms_is_member - is X a member of A?
 348  */
 349 bool
 350 bms_is_member(int x, const Bitmapset *a)
 351 {
 352         int                     wordnum,
 353                                 bitnum;
 354
 355         /* XXX better to just return false for x<0 ? */
 356         if (x < 0)
 357                 elog(ERROR, "bms_is_member: negative set member not allowed");
 358         if (a == NULL)
 359                 return false;
 360         wordnum = WORDNUM(x);
 361         bitnum = BITNUM(x);
 362         if (wordnum >= a->nwords)
 363                 return false;
 364         if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
 365                 return true;
 366         return false;
 367 }
 368
 369 /*
 370  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
 371  */
 372 bool
 373 bms_overlap(const Bitmapset *a, const Bitmapset *b)
 374 {
 375         int                     shortlen;
 376         int                     i;
 377
 378         /* Handle cases where either input is NULL */
 379         if (a == NULL || b == NULL)
 380                 return false;
 381         /* Check words in common */
 382         shortlen = Min(a->nwords, b->nwords);
 383         for (i = 0; i < shortlen; i++)
 384         {
 385                 if ((a->words[i] & b->words[i]) != 0)
 386                         return true;
 387         }
 388         return false;
 389 }
 390
 391 /*
 392  * bms_nonempty_difference - do sets have a nonempty difference?
 393  */
 394 bool
 395 bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 396 {
 397         int                     shortlen;
 398         int                     i;
 399
 400         /* Handle cases where either input is NULL */
 401         if (a == NULL)
 402                 return false;
 403         if (b == NULL)
 404                 return !bms_is_empty(a);
 405         /* Check words in common */
 406         shortlen = Min(a->nwords, b->nwords);
 407         for (i = 0; i < shortlen; i++)
 408         {
 409                 if ((a->words[i] & ~ b->words[i]) != 0)
 410                         return true;
 411         }
 412         /* Check extra words in a */
 413         for (; i < a->nwords; i++)
 414         {
 415                 if (a->words[i] != 0)
 416                         return true;
 417         }
 418         return false;
 419 }
 420
 421 /*
 422  * bms_singleton_member - return the sole integer member of set
 423  *
 424  * Raises error if |a| is not 1.
 425  */
 426 int
 427 bms_singleton_member(const Bitmapset *a)
 428 {
 429         int             result = -1;
 430         int             nwords;
 431         int             wordnum;
 432
 433         if (a == NULL)
 434                 elog(ERROR, "bms_singleton_member: set is empty");
 435         nwords = a->nwords;
 436         for (wordnum = 0; wordnum < nwords; wordnum++)
 437         {
 438                 bitmapword      w = a->words[wordnum];
 439
 440                 if (w != 0)
 441                 {
 442                         if (result >= 0 || HAS_MULTIPLE_ONES(w))
 443                                 elog(ERROR, "bms_singleton_member: set has multiple members");
 444                         result = wordnum * BITS_PER_BITMAPWORD;
 445                         while ((w & 255) == 0)
 446                         {
 447                                 w >>= 8;
 448                                 result += 8;
 449                         }
 450                         result += rightmost_one_pos[w & 255];
 451                 }
 452         }
 453         if (result < 0)
 454                 elog(ERROR, "bms_singleton_member: set is empty");
 455         return result;
 456 }
 457
 458 /*
 459  * bms_num_members - count members of set
 460  */
 461 int
 462 bms_num_members(const Bitmapset *a)
 463 {
 464         int             result = 0;
 465         int             nwords;
 466         int             wordnum;
 467
 468         if (a == NULL)
 469                 return 0;
 470         nwords = a->nwords;
 471         for (wordnum = 0; wordnum < nwords; wordnum++)
 472         {
 473                 bitmapword      w = a->words[wordnum];
 474
 475                 /* we assume here that bitmapword is an unsigned type */
 476                 while (w != 0)
 477                 {
 478                         result += number_of_ones[w & 255];
 479                         w >>= 8;
 480                 }
 481         }
 482         return result;
 483 }
 484
 485 /*
 486  * bms_membership - does a set have zero, one, or multiple members?
 487  *
 488  * This is faster than making an exact count with bms_num_members().
 489  */
 490 BMS_Membership
 491 bms_membership(const Bitmapset *a)
 492 {
 493         BMS_Membership result = BMS_EMPTY_SET;
 494         int             nwords;
 495         int             wordnum;
 496
 497         if (a == NULL)
 498                 return BMS_EMPTY_SET;
 499         nwords = a->nwords;
 500         for (wordnum = 0; wordnum < nwords; wordnum++)
 501         {
 502                 bitmapword      w = a->words[wordnum];
 503
 504                 if (w != 0)
 505                 {
 506                         if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
 507                                 return BMS_MULTIPLE;
 508                         result = BMS_SINGLETON;
 509                 }
 510         }
 511         return result;
 512 }
 513
 514 /*
 515  * bms_is_empty - is a set empty?
 516  *
 517  * This is even faster than bms_membership().
 518  */
 519 bool
 520 bms_is_empty(const Bitmapset *a)
 521 {
 522         int             nwords;
 523         int             wordnum;
 524
 525         if (a == NULL)
 526                 return true;
 527         nwords = a->nwords;
 528         for (wordnum = 0; wordnum < nwords; wordnum++)
 529         {
 530                 bitmapword      w = a->words[wordnum];
 531
 532                 if (w != 0)
 533                         return false;
 534         }
 535         return true;
 536 }
 537
 538
 539 /*
 540  * These operations all "recycle" their non-const inputs, ie, either
 541  * return the modified input or pfree it if it can't hold the result.
 542  *
 543  * These should generally be used in the style
 544  *
 545  *              foo = bms_add_member(foo, x);
 546  */
 547
 548
 549 /*
 550  * bms_add_member - add a specified member to set
 551  *
 552  * Input set is modified or recycled!
 553  */
 554 Bitmapset *
 555 bms_add_member(Bitmapset *a, int x)
 556 {
 557         int                     wordnum,
 558                                 bitnum;
 559
 560         if (x < 0)
 561                 elog(ERROR, "bms_add_member: negative set member not allowed");
 562         if (a == NULL)
 563                 return bms_make_singleton(x);
 564         wordnum = WORDNUM(x);
 565         bitnum = BITNUM(x);
 566         if (wordnum >= a->nwords)
 567         {
 568                 /* Slow path: make a larger set and union the input set into it */
 569                 Bitmapset  *result;
 570                 int                     nwords;
 571                 int                     i;
 572
 573                 result = bms_make_singleton(x);
 574                 nwords = a->nwords;
 575                 for (i = 0; i < nwords; i++)
 576                 {
 577                         result->words[i] |= a->words[i];
 578                 }
 579                 pfree(a);
 580                 return result;
 581         }
 582         /* Fast path: x fits in existing set */
 583         a->words[wordnum] |= ((bitmapword) 1 << bitnum);
 584         return a;
 585 }
 586
 587 /*
 588  * bms_del_member - remove a specified member from set
 589  *
 590  * No error if x is not currently a member of set
 591  *
 592  * Input set is modified in-place!
 593  */
 594 Bitmapset *
 595 bms_del_member(Bitmapset *a, int x)
 596 {
 597         int                     wordnum,
 598                                 bitnum;
 599
 600         if (x < 0)
 601                 elog(ERROR, "bms_del_member: negative set member not allowed");
 602         if (a == NULL)
 603                 return NULL;
 604         wordnum = WORDNUM(x);
 605         bitnum = BITNUM(x);
 606         if (wordnum < a->nwords)
 607         {
 608                 a->words[wordnum] &= ~ ((bitmapword) 1 << bitnum);
 609         }
 610         return a;
 611 }
 612
 613 /*
 614  * bms_add_members - like bms_union, but left input is recycled
 615  */
 616 Bitmapset *
 617 bms_add_members(Bitmapset *a, const Bitmapset *b)
 618 {
 619         Bitmapset  *result;
 620         const Bitmapset *other;
 621         int                     otherlen;
 622         int                     i;
 623
 624         /* Handle cases where either input is NULL */
 625         if (a == NULL)
 626                 return bms_copy(b);
 627         if (b == NULL)
 628                 return a;
 629         /* Identify shorter and longer input; copy the longer one if needed */
 630         if (a->nwords < b->nwords)
 631         {
 632                 result = bms_copy(b);
 633                 other = a;
 634         }
 635         else
 636         {
 637                 result = a;
 638                 other = b;
 639         }
 640         /* And union the shorter input into the result */
 641         otherlen = other->nwords;
 642         for (i = 0; i < otherlen; i++)
 643         {
 644                 result->words[i] |= other->words[i];
 645         }
 646         if (result != a)
 647                 pfree(a);
 648         return result;
 649 }
 650
 651 /*
 652  * bms_int_members - like bms_intersect, but left input is recycled
 653  */
 654 Bitmapset *
 655 bms_int_members(Bitmapset *a, const Bitmapset *b)
 656 {
 657         int                     shortlen;
 658         int                     i;
 659
 660         /* Handle cases where either input is NULL */
 661         if (a == NULL)
 662                 return NULL;
 663         if (b == NULL)
 664         {
 665                 pfree(a);
 666                 return NULL;
 667         }
 668         /* Intersect b into a; we need never copy */
 669         shortlen = Min(a->nwords, b->nwords);
 670         for (i = 0; i < shortlen; i++)
 671         {
 672                 a->words[i] &= b->words[i];
 673         }
 674         for (; i < a->nwords; i++)
 675         {
 676                 a->words[i] = 0;
 677         }
 678         return a;
 679 }
 680
 681 /*
 682  * bms_del_members - like bms_difference, but left input is recycled
 683  */
 684 Bitmapset *
 685 bms_del_members(Bitmapset *a, const Bitmapset *b)
 686 {
 687         int                     shortlen;
 688         int                     i;
 689
 690         /* Handle cases where either input is NULL */
 691         if (a == NULL)
 692                 return NULL;
 693         if (b == NULL)
 694                 return a;
 695         /* Remove b's bits from a; we need never copy */
 696         shortlen = Min(a->nwords, b->nwords);
 697         for (i = 0; i < shortlen; i++)
 698         {
 699                 a->words[i] &= ~ b->words[i];
 700         }
 701         return a;
 702 }
 703
 704 /*
 705  * bms_join - like bms_union, but *both* inputs are recycled
 706  */
 707 Bitmapset *
 708 bms_join(Bitmapset *a, Bitmapset *b)
 709 {
 710         Bitmapset  *result;
 711         Bitmapset  *other;
 712         int                     otherlen;
 713         int                     i;
 714
 715         /* Handle cases where either input is NULL */
 716         if (a == NULL)
 717                 return b;
 718         if (b == NULL)
 719                 return a;
 720         /* Identify shorter and longer input; use longer one as result */
 721         if (a->nwords < b->nwords)
 722         {
 723                 result = b;
 724                 other = a;
 725         }
 726         else
 727         {
 728                 result = a;
 729                 other = b;
 730         }
 731         /* And union the shorter input into the result */
 732         otherlen = other->nwords;
 733         for (i = 0; i < otherlen; i++)
 734         {
 735                 result->words[i] |= other->words[i];
 736         }
 737         if (other != result)            /* pure paranoia */
 738                 pfree(other);
 739         return result;
 740 }
 741
 742 /*----------
 743  * bms_first_member - find and remove first member of a set
 744  *
 745  * Returns -1 if set is empty.  NB: set is destructively modified!
 746  *
 747  * This is intended as support for iterating through the members of a set.
 748  * The typical pattern is
 749  *
 750  *                      tmpset = bms_copy(inputset);
 751  *                      while ((x = bms_first_member(tmpset)) >= 0)
 752  *                      {
 753  *                              process member x;
 754  *                      }
 755  *                      bms_free(tmpset);
 756  *----------
 757  */
 758 int
 759 bms_first_member(Bitmapset *a)
 760 {
 761         int             nwords;
 762         int             wordnum;
 763
 764         if (a == NULL)
 765                 return -1;
 766         nwords = a->nwords;
 767         for (wordnum = 0; wordnum < nwords; wordnum++)
 768         {
 769                 bitmapword      w = a->words[wordnum];
 770
 771                 if (w != 0)
 772                 {
 773                         int             result;
 774
 775                         w = RIGHTMOST_ONE(w);
 776                         a->words[wordnum] &= ~ w;
 777
 778                         result = wordnum * BITS_PER_BITMAPWORD;
 779                         while ((w & 255) == 0)
 780                         {
 781                                 w >>= 8;
 782                                 result += 8;
 783                         }
 784                         result += rightmost_one_pos[w & 255];
 785                         return result;
 786                 }
 787         }
 788         return -1;
 789 }