LCOV - code coverage report
Current view: top level - src/backend/nodes - bitmapset.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 380 446 85.2 %
Date: 2024-10-10 04:14:55 Functions: 32 32 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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, we always represent a set with
       9             :  * the minimum possible number of words, i.e, there are never any trailing
      10             :  * zero words.  Enforcing this requires that an empty set is represented as
      11             :  * NULL.  Because an empty Bitmapset is represented as NULL, a non-NULL
      12             :  * Bitmapset always has at least 1 Bitmapword.  We can exploit this fact to
      13             :  * speed up various loops over the Bitmapset's words array by using "do while"
      14             :  * loops instead of "for" loops.  This means the code does not waste time
      15             :  * checking the loop condition before the first iteration.  For Bitmapsets
      16             :  * containing only a single word (likely the majority of them) this halves the
      17             :  * number of loop condition checks.
      18             :  *
      19             :  * Callers must ensure that the set returned by functions in this file which
      20             :  * adjust the members of an existing set is assigned to all pointers pointing
      21             :  * to that existing set.  No guarantees are made that we'll ever modify the
      22             :  * existing set in-place and return it.
      23             :  *
      24             :  * To help find bugs caused by callers failing to record the return value of
      25             :  * the function which manipulates an existing set, we support building with
      26             :  * REALLOCATE_BITMAPSETS.  This results in the set being reallocated each time
      27             :  * the set is altered and the existing being pfreed.  This is useful as if any
      28             :  * references still exist to the old set, we're more likely to notice as
      29             :  * any users of the old set will be accessing pfree'd memory.  This option is
      30             :  * only intended to be used for debugging.
      31             :  *
      32             :  * Copyright (c) 2003-2024, PostgreSQL Global Development Group
      33             :  *
      34             :  * IDENTIFICATION
      35             :  *    src/backend/nodes/bitmapset.c
      36             :  *
      37             :  *-------------------------------------------------------------------------
      38             :  */
      39             : #include "postgres.h"
      40             : 
      41             : #include "common/hashfn.h"
      42             : #include "nodes/bitmapset.h"
      43             : #include "nodes/pg_list.h"
      44             : #include "port/pg_bitutils.h"
      45             : 
      46             : 
      47             : #define WORDNUM(x)  ((x) / BITS_PER_BITMAPWORD)
      48             : #define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
      49             : 
      50             : #define BITMAPSET_SIZE(nwords)  \
      51             :     (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
      52             : 
      53             : /*----------
      54             :  * This is a well-known cute trick for isolating the rightmost one-bit
      55             :  * in a word.  It assumes two's complement arithmetic.  Consider any
      56             :  * nonzero value, and focus attention on the rightmost one.  The value is
      57             :  * then something like
      58             :  *              xxxxxx10000
      59             :  * where x's are unspecified bits.  The two's complement negative is formed
      60             :  * by inverting all the bits and adding one.  Inversion gives
      61             :  *              yyyyyy01111
      62             :  * where each y is the inverse of the corresponding x.  Incrementing gives
      63             :  *              yyyyyy10000
      64             :  * and then ANDing with the original value gives
      65             :  *              00000010000
      66             :  * This works for all cases except original value = zero, where of course
      67             :  * we get zero.
      68             :  *----------
      69             :  */
      70             : #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
      71             : 
      72             : #define HAS_MULTIPLE_ONES(x)    ((bitmapword) RIGHTMOST_ONE(x) != (x))
      73             : 
      74             : #ifdef USE_ASSERT_CHECKING
      75             : /*
      76             :  * bms_is_valid_set - for cassert builds to check for valid sets
      77             :  */
      78             : static bool
      79             : bms_is_valid_set(const Bitmapset *a)
      80             : {
      81             :     /* NULL is the correct representation of an empty set */
      82             :     if (a == NULL)
      83             :         return true;
      84             : 
      85             :     /* check the node tag is set correctly.  pfree'd pointer, maybe? */
      86             :     if (!IsA(a, Bitmapset))
      87             :         return false;
      88             : 
      89             :     /* trailing zero words are not allowed */
      90             :     if (a->words[a->nwords - 1] == 0)
      91             :         return false;
      92             : 
      93             :     return true;
      94             : }
      95             : #endif
      96             : 
      97             : #ifdef REALLOCATE_BITMAPSETS
      98             : /*
      99             :  * bms_copy_and_free
     100             :  *      Only required in REALLOCATE_BITMAPSETS builds.  Provide a simple way
     101             :  *      to return a freshly allocated set and pfree the original.
     102             :  *
     103             :  * Note: callers which accept multiple sets must be careful when calling this
     104             :  * function to clone one parameter as other parameters may point to the same
     105             :  * set.  A good option is to call this just before returning the resulting
     106             :  * set.
     107             :  */
     108             : static Bitmapset *
     109             : bms_copy_and_free(Bitmapset *a)
     110             : {
     111             :     Bitmapset  *c = bms_copy(a);
     112             : 
     113             :     bms_free(a);
     114             :     return c;
     115             : }
     116             : #endif
     117             : 
     118             : /*
     119             :  * bms_copy - make a palloc'd copy of a bitmapset
     120             :  */
     121             : Bitmapset *
     122    40588082 : bms_copy(const Bitmapset *a)
     123             : {
     124             :     Bitmapset  *result;
     125             :     size_t      size;
     126             : 
     127             :     Assert(bms_is_valid_set(a));
     128             : 
     129    40588082 :     if (a == NULL)
     130    26824622 :         return NULL;
     131             : 
     132    13763460 :     size = BITMAPSET_SIZE(a->nwords);
     133    13763460 :     result = (Bitmapset *) palloc(size);
     134    13763460 :     memcpy(result, a, size);
     135    13763460 :     return result;
     136             : }
     137             : 
     138             : /*
     139             :  * bms_equal - are two bitmapsets equal? or both NULL?
     140             :  */
     141             : bool
     142    19616292 : bms_equal(const Bitmapset *a, const Bitmapset *b)
     143             : {
     144             :     int         i;
     145             : 
     146             :     Assert(bms_is_valid_set(a));
     147             :     Assert(bms_is_valid_set(b));
     148             : 
     149             :     /* Handle cases where either input is NULL */
     150    19616292 :     if (a == NULL)
     151             :     {
     152    13798104 :         if (b == NULL)
     153    13748456 :             return true;
     154       49648 :         return false;
     155             :     }
     156     5818188 :     else if (b == NULL)
     157       30790 :         return false;
     158             : 
     159             :     /* can't be equal if the word counts don't match */
     160     5787398 :     if (a->nwords != b->nwords)
     161           0 :         return false;
     162             : 
     163             :     /* check each word matches */
     164     5787398 :     i = 0;
     165             :     do
     166             :     {
     167     5787806 :         if (a->words[i] != b->words[i])
     168     2502328 :             return false;
     169     3285478 :     } while (++i < a->nwords);
     170             : 
     171     3285070 :     return true;
     172             : }
     173             : 
     174             : /*
     175             :  * bms_compare - qsort-style comparator for bitmapsets
     176             :  *
     177             :  * This guarantees to report values as equal iff bms_equal would say they are
     178             :  * equal.  Otherwise, the highest-numbered bit that is set in one value but
     179             :  * not the other determines the result.  (This rule means that, for example,
     180             :  * {6} is greater than {5}, which seems plausible.)
     181             :  */
     182             : int
     183       20568 : bms_compare(const Bitmapset *a, const Bitmapset *b)
     184             : {
     185             :     int         i;
     186             : 
     187             :     Assert(bms_is_valid_set(a));
     188             :     Assert(bms_is_valid_set(b));
     189             : 
     190             :     /* Handle cases where either input is NULL */
     191       20568 :     if (a == NULL)
     192           0 :         return (b == NULL) ? 0 : -1;
     193       20568 :     else if (b == NULL)
     194           0 :         return +1;
     195             : 
     196             :     /* the set with the most words must be greater */
     197       20568 :     if (a->nwords != b->nwords)
     198           0 :         return (a->nwords > b->nwords) ? +1 : -1;
     199             : 
     200       20568 :     i = a->nwords - 1;
     201             :     do
     202             :     {
     203       20568 :         bitmapword  aw = a->words[i];
     204       20568 :         bitmapword  bw = b->words[i];
     205             : 
     206       20568 :         if (aw != bw)
     207       20568 :             return (aw > bw) ? +1 : -1;
     208           0 :     } while (--i >= 0);
     209           0 :     return 0;
     210             : }
     211             : 
     212             : /*
     213             :  * bms_make_singleton - build a bitmapset containing a single member
     214             :  */
     215             : Bitmapset *
     216    12597186 : bms_make_singleton(int x)
     217             : {
     218             :     Bitmapset  *result;
     219             :     int         wordnum,
     220             :                 bitnum;
     221             : 
     222    12597186 :     if (x < 0)
     223           0 :         elog(ERROR, "negative bitmapset member not allowed");
     224    12597186 :     wordnum = WORDNUM(x);
     225    12597186 :     bitnum = BITNUM(x);
     226    12597186 :     result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
     227    12597186 :     result->type = T_Bitmapset;
     228    12597186 :     result->nwords = wordnum + 1;
     229    12597186 :     result->words[wordnum] = ((bitmapword) 1 << bitnum);
     230    12597186 :     return result;
     231             : }
     232             : 
     233             : /*
     234             :  * bms_free - free a bitmapset
     235             :  *
     236             :  * Same as pfree except for allowing NULL input
     237             :  */
     238             : void
     239    16490178 : bms_free(Bitmapset *a)
     240             : {
     241    16490178 :     if (a)
     242     7159422 :         pfree(a);
     243    16490178 : }
     244             : 
     245             : 
     246             : /*
     247             :  * bms_union - create and return a new set containing all members from both
     248             :  * input sets.  Both inputs are left unmodified.
     249             :  */
     250             : Bitmapset *
     251     6510000 : bms_union(const Bitmapset *a, const Bitmapset *b)
     252             : {
     253             :     Bitmapset  *result;
     254             :     const Bitmapset *other;
     255             :     int         otherlen;
     256             :     int         i;
     257             : 
     258             :     Assert(bms_is_valid_set(a));
     259             :     Assert(bms_is_valid_set(b));
     260             : 
     261             :     /* Handle cases where either input is NULL */
     262     6510000 :     if (a == NULL)
     263     4078356 :         return bms_copy(b);
     264     2431644 :     if (b == NULL)
     265     1096290 :         return bms_copy(a);
     266             :     /* Identify shorter and longer input; copy the longer one */
     267     1335354 :     if (a->nwords <= b->nwords)
     268             :     {
     269     1335354 :         result = bms_copy(b);
     270     1335354 :         other = a;
     271             :     }
     272             :     else
     273             :     {
     274           0 :         result = bms_copy(a);
     275           0 :         other = b;
     276             :     }
     277             :     /* And union the shorter input into the result */
     278     1335354 :     otherlen = other->nwords;
     279     1335354 :     i = 0;
     280             :     do
     281             :     {
     282     1335354 :         result->words[i] |= other->words[i];
     283     1335354 :     } while (++i < otherlen);
     284     1335354 :     return result;
     285             : }
     286             : 
     287             : /*
     288             :  * bms_intersect - create and return a new set containing members which both
     289             :  * input sets have in common.  Both inputs are left unmodified.
     290             :  */
     291             : Bitmapset *
     292      919376 : bms_intersect(const Bitmapset *a, const Bitmapset *b)
     293             : {
     294             :     Bitmapset  *result;
     295             :     const Bitmapset *other;
     296             :     int         lastnonzero;
     297             :     int         resultlen;
     298             :     int         i;
     299             : 
     300             :     Assert(bms_is_valid_set(a));
     301             :     Assert(bms_is_valid_set(b));
     302             : 
     303             :     /* Handle cases where either input is NULL */
     304      919376 :     if (a == NULL || b == NULL)
     305      178386 :         return NULL;
     306             : 
     307             :     /* Identify shorter and longer input; copy the shorter one */
     308      740990 :     if (a->nwords <= b->nwords)
     309             :     {
     310      740990 :         result = bms_copy(a);
     311      740990 :         other = b;
     312             :     }
     313             :     else
     314             :     {
     315           0 :         result = bms_copy(b);
     316           0 :         other = a;
     317             :     }
     318             :     /* And intersect the longer input with the result */
     319      740990 :     resultlen = result->nwords;
     320      740990 :     lastnonzero = -1;
     321      740990 :     i = 0;
     322             :     do
     323             :     {
     324      740990 :         result->words[i] &= other->words[i];
     325             : 
     326      740990 :         if (result->words[i] != 0)
     327      733908 :             lastnonzero = i;
     328      740990 :     } while (++i < resultlen);
     329             :     /* If we computed an empty result, we must return NULL */
     330      740990 :     if (lastnonzero == -1)
     331             :     {
     332        7082 :         pfree(result);
     333        7082 :         return NULL;
     334             :     }
     335             : 
     336             :     /* get rid of trailing zero words */
     337      733908 :     result->nwords = lastnonzero + 1;
     338      733908 :     return result;
     339             : }
     340             : 
     341             : /*
     342             :  * bms_difference - create and return a new set containing all the members of
     343             :  * 'a' without the members of 'b'.
     344             :  */
     345             : Bitmapset *
     346      717790 : bms_difference(const Bitmapset *a, const Bitmapset *b)
     347             : {
     348             :     Bitmapset  *result;
     349             :     int         i;
     350             : 
     351             :     Assert(bms_is_valid_set(a));
     352             :     Assert(bms_is_valid_set(b));
     353             : 
     354             :     /* Handle cases where either input is NULL */
     355      717790 :     if (a == NULL)
     356       11188 :         return NULL;
     357      706602 :     if (b == NULL)
     358      448136 :         return bms_copy(a);
     359             : 
     360             :     /*
     361             :      * In Postgres' usage, an empty result is a very common case, so it's
     362             :      * worth optimizing for that by testing bms_nonempty_difference().  This
     363             :      * saves us a palloc/pfree cycle compared to checking after-the-fact.
     364             :      */
     365      258466 :     if (!bms_nonempty_difference(a, b))
     366       95914 :         return NULL;
     367             : 
     368             :     /* Copy the left input */
     369      162552 :     result = bms_copy(a);
     370             : 
     371             :     /* And remove b's bits from result */
     372      162552 :     if (result->nwords > b->nwords)
     373             :     {
     374             :         /*
     375             :          * We'll never need to remove trailing zero words when 'a' has more
     376             :          * words than 'b' as the additional words must be non-zero.
     377             :          */
     378           0 :         i = 0;
     379             :         do
     380             :         {
     381           0 :             result->words[i] &= ~b->words[i];
     382           0 :         } while (++i < b->nwords);
     383             :     }
     384             :     else
     385             :     {
     386      162552 :         int         lastnonzero = -1;
     387             : 
     388             :         /* we may need to remove trailing zero words from the result. */
     389      162552 :         i = 0;
     390             :         do
     391             :         {
     392      162552 :             result->words[i] &= ~b->words[i];
     393             : 
     394             :             /* remember the last non-zero word */
     395      162552 :             if (result->words[i] != 0)
     396      162552 :                 lastnonzero = i;
     397      162552 :         } while (++i < result->nwords);
     398             : 
     399             :         /* trim off trailing zero words */
     400      162552 :         result->nwords = lastnonzero + 1;
     401             :     }
     402             :     Assert(result->nwords != 0);
     403             : 
     404             :     /* Need not check for empty result, since we handled that case above */
     405      162552 :     return result;
     406             : }
     407             : 
     408             : /*
     409             :  * bms_is_subset - is A a subset of B?
     410             :  */
     411             : bool
     412    15551022 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
     413             : {
     414             :     int         i;
     415             : 
     416             :     Assert(bms_is_valid_set(a));
     417             :     Assert(bms_is_valid_set(b));
     418             : 
     419             :     /* Handle cases where either input is NULL */
     420    15551022 :     if (a == NULL)
     421     1455312 :         return true;            /* empty set is a subset of anything */
     422    14095710 :     if (b == NULL)
     423      382940 :         return false;
     424             : 
     425             :     /* 'a' can't be a subset of 'b' if it contains more words */
     426    13712770 :     if (a->nwords > b->nwords)
     427           0 :         return false;
     428             : 
     429             :     /* Check all 'a' members are set in 'b' */
     430    13712770 :     i = 0;
     431             :     do
     432             :     {
     433    13712770 :         if ((a->words[i] & ~b->words[i]) != 0)
     434     5435036 :             return false;
     435     8277734 :     } while (++i < a->nwords);
     436     8277734 :     return true;
     437             : }
     438             : 
     439             : /*
     440             :  * bms_subset_compare - compare A and B for equality/subset relationships
     441             :  *
     442             :  * This is more efficient than testing bms_is_subset in both directions.
     443             :  */
     444             : BMS_Comparison
     445     1967698 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
     446             : {
     447             :     BMS_Comparison result;
     448             :     int         shortlen;
     449             :     int         i;
     450             : 
     451             :     Assert(bms_is_valid_set(a));
     452             :     Assert(bms_is_valid_set(b));
     453             : 
     454             :     /* Handle cases where either input is NULL */
     455     1967698 :     if (a == NULL)
     456             :     {
     457     1665212 :         if (b == NULL)
     458     1609392 :             return BMS_EQUAL;
     459       55820 :         return BMS_SUBSET1;
     460             :     }
     461      302486 :     if (b == NULL)
     462      143974 :         return BMS_SUBSET2;
     463             : 
     464             :     /* Check common words */
     465      158512 :     result = BMS_EQUAL;         /* status so far */
     466      158512 :     shortlen = Min(a->nwords, b->nwords);
     467      158512 :     i = 0;
     468             :     do
     469             :     {
     470      158512 :         bitmapword  aword = a->words[i];
     471      158512 :         bitmapword  bword = b->words[i];
     472             : 
     473      158512 :         if ((aword & ~bword) != 0)
     474             :         {
     475             :             /* a is not a subset of b */
     476       37470 :             if (result == BMS_SUBSET1)
     477           0 :                 return BMS_DIFFERENT;
     478       37470 :             result = BMS_SUBSET2;
     479             :         }
     480      158512 :         if ((bword & ~aword) != 0)
     481             :         {
     482             :             /* b is not a subset of a */
     483       37400 :             if (result == BMS_SUBSET2)
     484       34888 :                 return BMS_DIFFERENT;
     485        2512 :             result = BMS_SUBSET1;
     486             :         }
     487      123624 :     } while (++i < shortlen);
     488             :     /* Check extra words */
     489      123624 :     if (a->nwords > b->nwords)
     490             :     {
     491             :         /* if a has more words then a is not a subset of b */
     492           0 :         if (result == BMS_SUBSET1)
     493           0 :             return BMS_DIFFERENT;
     494           0 :         return BMS_SUBSET2;
     495             :     }
     496      123624 :     else if (a->nwords < b->nwords)
     497             :     {
     498             :         /* if b has more words then b is not a subset of a */
     499           0 :         if (result == BMS_SUBSET2)
     500           0 :             return BMS_DIFFERENT;
     501           0 :         return BMS_SUBSET1;
     502             :     }
     503      123624 :     return result;
     504             : }
     505             : 
     506             : /*
     507             :  * bms_is_member - is X a member of A?
     508             :  */
     509             : bool
     510    11259080 : bms_is_member(int x, const Bitmapset *a)
     511             : {
     512             :     int         wordnum,
     513             :                 bitnum;
     514             : 
     515             :     Assert(bms_is_valid_set(a));
     516             : 
     517             :     /* XXX better to just return false for x<0 ? */
     518    11259080 :     if (x < 0)
     519           0 :         elog(ERROR, "negative bitmapset member not allowed");
     520    11259080 :     if (a == NULL)
     521     6699262 :         return false;
     522             : 
     523     4559818 :     wordnum = WORDNUM(x);
     524     4559818 :     bitnum = BITNUM(x);
     525     4559818 :     if (wordnum >= a->nwords)
     526         226 :         return false;
     527     4559592 :     if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     528     3108786 :         return true;
     529     1450806 :     return false;
     530             : }
     531             : 
     532             : /*
     533             :  * bms_member_index
     534             :  *      determine 0-based index of member x in the bitmap
     535             :  *
     536             :  * Returns (-1) when x is not a member.
     537             :  */
     538             : int
     539        4038 : bms_member_index(Bitmapset *a, int x)
     540             : {
     541             :     int         i;
     542             :     int         bitnum;
     543             :     int         wordnum;
     544        4038 :     int         result = 0;
     545             :     bitmapword  mask;
     546             : 
     547             :     Assert(bms_is_valid_set(a));
     548             : 
     549             :     /* return -1 if not a member of the bitmap */
     550        4038 :     if (!bms_is_member(x, a))
     551           0 :         return -1;
     552             : 
     553        4038 :     wordnum = WORDNUM(x);
     554        4038 :     bitnum = BITNUM(x);
     555             : 
     556             :     /* count bits in preceding words */
     557        4038 :     for (i = 0; i < wordnum; i++)
     558             :     {
     559           0 :         bitmapword  w = a->words[i];
     560             : 
     561             :         /* No need to count the bits in a zero word */
     562           0 :         if (w != 0)
     563           0 :             result += bmw_popcount(w);
     564             :     }
     565             : 
     566             :     /*
     567             :      * Now add bits of the last word, but only those before the item. We can
     568             :      * do that by applying a mask and then using popcount again. To get
     569             :      * 0-based index, we want to count only preceding bits, not the item
     570             :      * itself, so we subtract 1.
     571             :      */
     572        4038 :     mask = ((bitmapword) 1 << bitnum) - 1;
     573        4038 :     result += bmw_popcount(a->words[wordnum] & mask);
     574             : 
     575        4038 :     return result;
     576             : }
     577             : 
     578             : /*
     579             :  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
     580             :  */
     581             : bool
     582    10823502 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
     583             : {
     584             :     int         shortlen;
     585             :     int         i;
     586             : 
     587             :     Assert(bms_is_valid_set(a));
     588             :     Assert(bms_is_valid_set(b));
     589             : 
     590             :     /* Handle cases where either input is NULL */
     591    10823502 :     if (a == NULL || b == NULL)
     592     4523986 :         return false;
     593             :     /* Check words in common */
     594     6299516 :     shortlen = Min(a->nwords, b->nwords);
     595     6299516 :     i = 0;
     596             :     do
     597             :     {
     598     6299516 :         if ((a->words[i] & b->words[i]) != 0)
     599     4092844 :             return true;
     600     2206672 :     } while (++i < shortlen);
     601     2206672 :     return false;
     602             : }
     603             : 
     604             : /*
     605             :  * bms_overlap_list - does a set overlap an integer list?
     606             :  */
     607             : bool
     608        1450 : bms_overlap_list(const Bitmapset *a, const List *b)
     609             : {
     610             :     ListCell   *lc;
     611             :     int         wordnum,
     612             :                 bitnum;
     613             : 
     614             :     Assert(bms_is_valid_set(a));
     615             : 
     616        1450 :     if (a == NULL || b == NIL)
     617        1312 :         return false;
     618             : 
     619         258 :     foreach(lc, b)
     620             :     {
     621         198 :         int         x = lfirst_int(lc);
     622             : 
     623         198 :         if (x < 0)
     624           0 :             elog(ERROR, "negative bitmapset member not allowed");
     625         198 :         wordnum = WORDNUM(x);
     626         198 :         bitnum = BITNUM(x);
     627         198 :         if (wordnum < a->nwords)
     628         198 :             if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     629          78 :                 return true;
     630             :     }
     631             : 
     632          60 :     return false;
     633             : }
     634             : 
     635             : /*
     636             :  * bms_nonempty_difference - do sets have a nonempty difference?
     637             :  *
     638             :  * i.e., are any members set in 'a' that are not also set in 'b'.
     639             :  */
     640             : bool
     641     2045262 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
     642             : {
     643             :     int         i;
     644             : 
     645             :     Assert(bms_is_valid_set(a));
     646             :     Assert(bms_is_valid_set(b));
     647             : 
     648             :     /* Handle cases where either input is NULL */
     649     2045262 :     if (a == NULL)
     650        4716 :         return false;
     651     2040546 :     if (b == NULL)
     652           0 :         return true;
     653             :     /* if 'a' has more words then it must contain additional members */
     654     2040546 :     if (a->nwords > b->nwords)
     655           0 :         return true;
     656             :     /* Check all 'a' members are set in 'b' */
     657     2040546 :     i = 0;
     658             :     do
     659             :     {
     660     2040546 :         if ((a->words[i] & ~b->words[i]) != 0)
     661     1159728 :             return true;
     662      880818 :     } while (++i < a->nwords);
     663      880818 :     return false;
     664             : }
     665             : 
     666             : /*
     667             :  * bms_singleton_member - return the sole integer member of set
     668             :  *
     669             :  * Raises error if |a| is not 1.
     670             :  */
     671             : int
     672       12008 : bms_singleton_member(const Bitmapset *a)
     673             : {
     674       12008 :     int         result = -1;
     675             :     int         nwords;
     676             :     int         wordnum;
     677             : 
     678             :     Assert(bms_is_valid_set(a));
     679             : 
     680       12008 :     if (a == NULL)
     681           0 :         elog(ERROR, "bitmapset is empty");
     682             : 
     683       12008 :     nwords = a->nwords;
     684       12008 :     wordnum = 0;
     685             :     do
     686             :     {
     687       12008 :         bitmapword  w = a->words[wordnum];
     688             : 
     689       12008 :         if (w != 0)
     690             :         {
     691       12008 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     692           0 :                 elog(ERROR, "bitmapset has multiple members");
     693       12008 :             result = wordnum * BITS_PER_BITMAPWORD;
     694       12008 :             result += bmw_rightmost_one_pos(w);
     695             :         }
     696       12008 :     } while (++wordnum < nwords);
     697             : 
     698             :     /* we don't expect non-NULL sets to be empty */
     699             :     Assert(result >= 0);
     700       12008 :     return result;
     701             : }
     702             : 
     703             : /*
     704             :  * bms_get_singleton_member
     705             :  *
     706             :  * Test whether the given set is a singleton.
     707             :  * If so, set *member to the value of its sole member, and return true.
     708             :  * If not, return false, without changing *member.
     709             :  *
     710             :  * This is more convenient and faster than calling bms_membership() and then
     711             :  * bms_singleton_member(), if we don't care about distinguishing empty sets
     712             :  * from multiple-member sets.
     713             :  */
     714             : bool
     715     1891166 : bms_get_singleton_member(const Bitmapset *a, int *member)
     716             : {
     717     1891166 :     int         result = -1;
     718             :     int         nwords;
     719             :     int         wordnum;
     720             : 
     721             :     Assert(bms_is_valid_set(a));
     722             : 
     723     1891166 :     if (a == NULL)
     724           0 :         return false;
     725             : 
     726     1891166 :     nwords = a->nwords;
     727     1891166 :     wordnum = 0;
     728             :     do
     729             :     {
     730     1891166 :         bitmapword  w = a->words[wordnum];
     731             : 
     732     1891166 :         if (w != 0)
     733             :         {
     734     1891166 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     735      330360 :                 return false;
     736     1560806 :             result = wordnum * BITS_PER_BITMAPWORD;
     737     1560806 :             result += bmw_rightmost_one_pos(w);
     738             :         }
     739     1560806 :     } while (++wordnum < nwords);
     740             : 
     741             :     /* we don't expect non-NULL sets to be empty */
     742             :     Assert(result >= 0);
     743     1560806 :     *member = result;
     744     1560806 :     return true;
     745             : }
     746             : 
     747             : /*
     748             :  * bms_num_members - count members of set
     749             :  */
     750             : int
     751     1676146 : bms_num_members(const Bitmapset *a)
     752             : {
     753     1676146 :     int         result = 0;
     754             :     int         nwords;
     755             :     int         wordnum;
     756             : 
     757             :     Assert(bms_is_valid_set(a));
     758             : 
     759     1676146 :     if (a == NULL)
     760      136072 :         return 0;
     761             : 
     762     1540074 :     nwords = a->nwords;
     763     1540074 :     wordnum = 0;
     764             :     do
     765             :     {
     766     1540074 :         bitmapword  w = a->words[wordnum];
     767             : 
     768             :         /* No need to count the bits in a zero word */
     769     1540074 :         if (w != 0)
     770     1540074 :             result += bmw_popcount(w);
     771     1540074 :     } while (++wordnum < nwords);
     772     1540074 :     return result;
     773             : }
     774             : 
     775             : /*
     776             :  * bms_membership - does a set have zero, one, or multiple members?
     777             :  *
     778             :  * This is faster than making an exact count with bms_num_members().
     779             :  */
     780             : BMS_Membership
     781      873814 : bms_membership(const Bitmapset *a)
     782             : {
     783      873814 :     BMS_Membership result = BMS_EMPTY_SET;
     784             :     int         nwords;
     785             :     int         wordnum;
     786             : 
     787             :     Assert(bms_is_valid_set(a));
     788             : 
     789      873814 :     if (a == NULL)
     790         518 :         return BMS_EMPTY_SET;
     791             : 
     792      873296 :     nwords = a->nwords;
     793      873296 :     wordnum = 0;
     794             :     do
     795             :     {
     796      873296 :         bitmapword  w = a->words[wordnum];
     797             : 
     798      873296 :         if (w != 0)
     799             :         {
     800      873296 :             if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
     801      217962 :                 return BMS_MULTIPLE;
     802      655334 :             result = BMS_SINGLETON;
     803             :         }
     804      655334 :     } while (++wordnum < nwords);
     805      655334 :     return result;
     806             : }
     807             : 
     808             : 
     809             : /*
     810             :  * bms_add_member - add a specified member to set
     811             :  *
     812             :  * 'a' is recycled when possible.
     813             :  */
     814             : Bitmapset *
     815    20674938 : bms_add_member(Bitmapset *a, int x)
     816             : {
     817             :     int         wordnum,
     818             :                 bitnum;
     819             : 
     820             :     Assert(bms_is_valid_set(a));
     821             : 
     822    20674938 :     if (x < 0)
     823           0 :         elog(ERROR, "negative bitmapset member not allowed");
     824    20674938 :     if (a == NULL)
     825    10617384 :         return bms_make_singleton(x);
     826             : 
     827    10057554 :     wordnum = WORDNUM(x);
     828    10057554 :     bitnum = BITNUM(x);
     829             : 
     830             :     /* enlarge the set if necessary */
     831    10057554 :     if (wordnum >= a->nwords)
     832             :     {
     833         204 :         int         oldnwords = a->nwords;
     834             :         int         i;
     835             : 
     836         204 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
     837         204 :         a->nwords = wordnum + 1;
     838             :         /* zero out the enlarged portion */
     839         204 :         i = oldnwords;
     840             :         do
     841             :         {
     842         876 :             a->words[i] = 0;
     843         876 :         } while (++i < a->nwords);
     844             :     }
     845             : 
     846    10057554 :     a->words[wordnum] |= ((bitmapword) 1 << bitnum);
     847             : 
     848             : #ifdef REALLOCATE_BITMAPSETS
     849             : 
     850             :     /*
     851             :      * There's no guarantee that the repalloc returned a new pointer, so copy
     852             :      * and free unconditionally here.
     853             :      */
     854             :     a = bms_copy_and_free(a);
     855             : #endif
     856             : 
     857    10057554 :     return a;
     858             : }
     859             : 
     860             : /*
     861             :  * bms_del_member - remove a specified member from set
     862             :  *
     863             :  * No error if x is not currently a member of set
     864             :  *
     865             :  * 'a' is recycled when possible.
     866             :  */
     867             : Bitmapset *
     868     1278230 : bms_del_member(Bitmapset *a, int x)
     869             : {
     870             :     int         wordnum,
     871             :                 bitnum;
     872             : 
     873             :     Assert(bms_is_valid_set(a));
     874             : 
     875     1278230 :     if (x < 0)
     876           0 :         elog(ERROR, "negative bitmapset member not allowed");
     877     1278230 :     if (a == NULL)
     878      539676 :         return NULL;
     879             : 
     880      738554 :     wordnum = WORDNUM(x);
     881      738554 :     bitnum = BITNUM(x);
     882             : 
     883             : #ifdef REALLOCATE_BITMAPSETS
     884             :     a = bms_copy_and_free(a);
     885             : #endif
     886             : 
     887             :     /* member can't exist.  Return 'a' unmodified */
     888      738554 :     if (unlikely(wordnum >= a->nwords))
     889           0 :         return a;
     890             : 
     891      738554 :     a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
     892             : 
     893             :     /* when last word becomes empty, trim off all trailing empty words */
     894      738554 :     if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
     895             :     {
     896             :         /* find the last non-empty word and make that the new final word */
     897      397338 :         for (int i = wordnum - 1; i >= 0; i--)
     898             :         {
     899           0 :             if (a->words[i] != 0)
     900             :             {
     901           0 :                 a->nwords = i + 1;
     902           0 :                 return a;
     903             :             }
     904             :         }
     905             : 
     906             :         /* the set is now empty */
     907      397338 :         pfree(a);
     908      397338 :         return NULL;
     909             :     }
     910      341216 :     return a;
     911             : }
     912             : 
     913             : /*
     914             :  * bms_add_members - like bms_union, but left input is recycled when possible
     915             :  */
     916             : Bitmapset *
     917    11933628 : bms_add_members(Bitmapset *a, const Bitmapset *b)
     918             : {
     919             :     Bitmapset  *result;
     920             :     const Bitmapset *other;
     921             :     int         otherlen;
     922             :     int         i;
     923             : 
     924             :     Assert(bms_is_valid_set(a));
     925             :     Assert(bms_is_valid_set(b));
     926             : 
     927             :     /* Handle cases where either input is NULL */
     928    11933628 :     if (a == NULL)
     929     6321532 :         return bms_copy(b);
     930     5612096 :     if (b == NULL)
     931             :     {
     932             : #ifdef REALLOCATE_BITMAPSETS
     933             :         a = bms_copy_and_free(a);
     934             : #endif
     935             : 
     936     3566052 :         return a;
     937             :     }
     938             :     /* Identify shorter and longer input; copy the longer one if needed */
     939     2046044 :     if (a->nwords < b->nwords)
     940             :     {
     941           0 :         result = bms_copy(b);
     942           0 :         other = a;
     943             :     }
     944             :     else
     945             :     {
     946     2046044 :         result = a;
     947     2046044 :         other = b;
     948             :     }
     949             :     /* And union the shorter input into the result */
     950     2046044 :     otherlen = other->nwords;
     951     2046044 :     i = 0;
     952             :     do
     953             :     {
     954     2046044 :         result->words[i] |= other->words[i];
     955     2046044 :     } while (++i < otherlen);
     956     2046044 :     if (result != a)
     957           0 :         pfree(a);
     958             : #ifdef REALLOCATE_BITMAPSETS
     959             :     else
     960             :         result = bms_copy_and_free(result);
     961             : #endif
     962             : 
     963     2046044 :     return result;
     964             : }
     965             : 
     966             : /*
     967             :  * bms_replace_members
     968             :  *      Remove all existing members from 'a' and repopulate the set with members
     969             :  *      from 'b', recycling 'a', when possible.
     970             :  */
     971             : Bitmapset *
     972       12900 : bms_replace_members(Bitmapset *a, const Bitmapset *b)
     973             : {
     974             :     int         i;
     975             : 
     976             :     Assert(bms_is_valid_set(a));
     977             :     Assert(bms_is_valid_set(b));
     978             : 
     979       12900 :     if (a == NULL)
     980           0 :         return bms_copy(b);
     981       12900 :     if (b == NULL)
     982             :     {
     983           0 :         pfree(a);
     984           0 :         return NULL;
     985             :     }
     986             : 
     987       12900 :     if (a->nwords < b->nwords)
     988           0 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords));
     989             : 
     990       12900 :     i = 0;
     991             :     do
     992             :     {
     993       12900 :         a->words[i] = b->words[i];
     994       12900 :     } while (++i < b->nwords);
     995             : 
     996       12900 :     a->nwords = b->nwords;
     997             : 
     998             : #ifdef REALLOCATE_BITMAPSETS
     999             : 
    1000             :     /*
    1001             :      * There's no guarantee that the repalloc returned a new pointer, so copy
    1002             :      * and free unconditionally here.
    1003             :      */
    1004             :     a = bms_copy_and_free(a);
    1005             : #endif
    1006             : 
    1007       12900 :     return a;
    1008             : }
    1009             : 
    1010             : /*
    1011             :  * bms_add_range
    1012             :  *      Add members in the range of 'lower' to 'upper' to the set.
    1013             :  *
    1014             :  * Note this could also be done by calling bms_add_member in a loop, however,
    1015             :  * using this function will be faster when the range is large as we work at
    1016             :  * the bitmapword level rather than at bit level.
    1017             :  */
    1018             : Bitmapset *
    1019       35526 : bms_add_range(Bitmapset *a, int lower, int upper)
    1020             : {
    1021             :     int         lwordnum,
    1022             :                 lbitnum,
    1023             :                 uwordnum,
    1024             :                 ushiftbits,
    1025             :                 wordnum;
    1026             : 
    1027             :     Assert(bms_is_valid_set(a));
    1028             : 
    1029             :     /* do nothing if nothing is called for, without further checking */
    1030       35526 :     if (upper < lower)
    1031             :     {
    1032             : #ifdef REALLOCATE_BITMAPSETS
    1033             :         a = bms_copy_and_free(a);
    1034             : #endif
    1035             : 
    1036          28 :         return a;
    1037             :     }
    1038             : 
    1039       35498 :     if (lower < 0)
    1040           0 :         elog(ERROR, "negative bitmapset member not allowed");
    1041       35498 :     uwordnum = WORDNUM(upper);
    1042             : 
    1043       35498 :     if (a == NULL)
    1044             :     {
    1045       35498 :         a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
    1046       35498 :         a->type = T_Bitmapset;
    1047       35498 :         a->nwords = uwordnum + 1;
    1048             :     }
    1049           0 :     else if (uwordnum >= a->nwords)
    1050             :     {
    1051           0 :         int         oldnwords = a->nwords;
    1052             :         int         i;
    1053             : 
    1054             :         /* ensure we have enough words to store the upper bit */
    1055           0 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
    1056           0 :         a->nwords = uwordnum + 1;
    1057             :         /* zero out the enlarged portion */
    1058           0 :         i = oldnwords;
    1059             :         do
    1060             :         {
    1061           0 :             a->words[i] = 0;
    1062           0 :         } while (++i < a->nwords);
    1063             :     }
    1064             : 
    1065       35498 :     wordnum = lwordnum = WORDNUM(lower);
    1066             : 
    1067       35498 :     lbitnum = BITNUM(lower);
    1068       35498 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
    1069             : 
    1070             :     /*
    1071             :      * Special case when lwordnum is the same as uwordnum we must perform the
    1072             :      * upper and lower masking on the word.
    1073             :      */
    1074       35498 :     if (lwordnum == uwordnum)
    1075             :     {
    1076       35498 :         a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
    1077       35498 :             & (~(bitmapword) 0) >> ushiftbits;
    1078             :     }
    1079             :     else
    1080             :     {
    1081             :         /* turn on lbitnum and all bits left of it */
    1082           0 :         a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
    1083             : 
    1084             :         /* turn on all bits for any intermediate words */
    1085           0 :         while (wordnum < uwordnum)
    1086           0 :             a->words[wordnum++] = ~(bitmapword) 0;
    1087             : 
    1088             :         /* turn on upper's bit and all bits right of it. */
    1089           0 :         a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
    1090             :     }
    1091             : 
    1092             : #ifdef REALLOCATE_BITMAPSETS
    1093             : 
    1094             :     /*
    1095             :      * There's no guarantee that the repalloc returned a new pointer, so copy
    1096             :      * and free unconditionally here.
    1097             :      */
    1098             :     a = bms_copy_and_free(a);
    1099             : #endif
    1100             : 
    1101       35498 :     return a;
    1102             : }
    1103             : 
    1104             : /*
    1105             :  * bms_int_members - like bms_intersect, but left input is recycled when
    1106             :  * possible
    1107             :  */
    1108             : Bitmapset *
    1109      527806 : bms_int_members(Bitmapset *a, const Bitmapset *b)
    1110             : {
    1111             :     int         lastnonzero;
    1112             :     int         shortlen;
    1113             :     int         i;
    1114             : 
    1115             :     Assert(bms_is_valid_set(a));
    1116             :     Assert(bms_is_valid_set(b));
    1117             : 
    1118             :     /* Handle cases where either input is NULL */
    1119      527806 :     if (a == NULL)
    1120       25480 :         return NULL;
    1121      502326 :     if (b == NULL)
    1122             :     {
    1123        3994 :         pfree(a);
    1124        3994 :         return NULL;
    1125             :     }
    1126             : 
    1127             :     /* Intersect b into a; we need never copy */
    1128      498332 :     shortlen = Min(a->nwords, b->nwords);
    1129      498332 :     lastnonzero = -1;
    1130      498332 :     i = 0;
    1131             :     do
    1132             :     {
    1133      498332 :         a->words[i] &= b->words[i];
    1134             : 
    1135      498332 :         if (a->words[i] != 0)
    1136      406422 :             lastnonzero = i;
    1137      498332 :     } while (++i < shortlen);
    1138             : 
    1139             :     /* If we computed an empty result, we must return NULL */
    1140      498332 :     if (lastnonzero == -1)
    1141             :     {
    1142       91910 :         pfree(a);
    1143       91910 :         return NULL;
    1144             :     }
    1145             : 
    1146             :     /* get rid of trailing zero words */
    1147      406422 :     a->nwords = lastnonzero + 1;
    1148             : 
    1149             : #ifdef REALLOCATE_BITMAPSETS
    1150             :     a = bms_copy_and_free(a);
    1151             : #endif
    1152             : 
    1153      406422 :     return a;
    1154             : }
    1155             : 
    1156             : /*
    1157             :  * bms_del_members - delete members in 'a' that are set in 'b'.  'a' is
    1158             :  * recycled when possible.
    1159             :  */
    1160             : Bitmapset *
    1161     1756878 : bms_del_members(Bitmapset *a, const Bitmapset *b)
    1162             : {
    1163             :     int         i;
    1164             : 
    1165             :     Assert(bms_is_valid_set(a));
    1166             :     Assert(bms_is_valid_set(b));
    1167             : 
    1168             :     /* Handle cases where either input is NULL */
    1169     1756878 :     if (a == NULL)
    1170      778806 :         return NULL;
    1171      978072 :     if (b == NULL)
    1172             :     {
    1173             : #ifdef REALLOCATE_BITMAPSETS
    1174             :         a = bms_copy_and_free(a);
    1175             : #endif
    1176             : 
    1177      163132 :         return a;
    1178             :     }
    1179             : 
    1180             :     /* Remove b's bits from a; we need never copy */
    1181      814940 :     if (a->nwords > b->nwords)
    1182             :     {
    1183             :         /*
    1184             :          * We'll never need to remove trailing zero words when 'a' has more
    1185             :          * words than 'b'.
    1186             :          */
    1187           0 :         i = 0;
    1188             :         do
    1189             :         {
    1190           0 :             a->words[i] &= ~b->words[i];
    1191           0 :         } while (++i < b->nwords);
    1192             :     }
    1193             :     else
    1194             :     {
    1195      814940 :         int         lastnonzero = -1;
    1196             : 
    1197             :         /* we may need to remove trailing zero words from the result. */
    1198      814940 :         i = 0;
    1199             :         do
    1200             :         {
    1201      814940 :             a->words[i] &= ~b->words[i];
    1202             : 
    1203             :             /* remember the last non-zero word */
    1204      814940 :             if (a->words[i] != 0)
    1205      154922 :                 lastnonzero = i;
    1206      814940 :         } while (++i < a->nwords);
    1207             : 
    1208             :         /* check if 'a' has become empty */
    1209      814940 :         if (lastnonzero == -1)
    1210             :         {
    1211      660018 :             pfree(a);
    1212      660018 :             return NULL;
    1213             :         }
    1214             : 
    1215             :         /* trim off any trailing zero words */
    1216      154922 :         a->nwords = lastnonzero + 1;
    1217             :     }
    1218             : 
    1219             : #ifdef REALLOCATE_BITMAPSETS
    1220             :     a = bms_copy_and_free(a);
    1221             : #endif
    1222             : 
    1223      154922 :     return a;
    1224             : }
    1225             : 
    1226             : /*
    1227             :  * bms_join - like bms_union, but *either* input *may* be recycled
    1228             :  */
    1229             : Bitmapset *
    1230     1302588 : bms_join(Bitmapset *a, Bitmapset *b)
    1231             : {
    1232             :     Bitmapset  *result;
    1233             :     Bitmapset  *other;
    1234             :     int         otherlen;
    1235             :     int         i;
    1236             : 
    1237             :     Assert(bms_is_valid_set(a));
    1238             :     Assert(bms_is_valid_set(b));
    1239             : 
    1240             :     /* Handle cases where either input is NULL */
    1241     1302588 :     if (a == NULL)
    1242             :     {
    1243             : #ifdef REALLOCATE_BITMAPSETS
    1244             :         b = bms_copy_and_free(b);
    1245             : #endif
    1246             : 
    1247      565602 :         return b;
    1248             :     }
    1249      736986 :     if (b == NULL)
    1250             :     {
    1251             : #ifdef REALLOCATE_BITMAPSETS
    1252             :         a = bms_copy_and_free(a);
    1253             : #endif
    1254             : 
    1255      154032 :         return a;
    1256             :     }
    1257             : 
    1258             :     /* Identify shorter and longer input; use longer one as result */
    1259      582954 :     if (a->nwords < b->nwords)
    1260             :     {
    1261           0 :         result = b;
    1262           0 :         other = a;
    1263             :     }
    1264             :     else
    1265             :     {
    1266      582954 :         result = a;
    1267      582954 :         other = b;
    1268             :     }
    1269             :     /* And union the shorter input into the result */
    1270      582954 :     otherlen = other->nwords;
    1271      582954 :     i = 0;
    1272             :     do
    1273             :     {
    1274      582954 :         result->words[i] |= other->words[i];
    1275      582954 :     } while (++i < otherlen);
    1276      582954 :     if (other != result)        /* pure paranoia */
    1277      582954 :         pfree(other);
    1278             : 
    1279             : #ifdef REALLOCATE_BITMAPSETS
    1280             :     result = bms_copy_and_free(result);
    1281             : #endif
    1282             : 
    1283      582954 :     return result;
    1284             : }
    1285             : 
    1286             : /*
    1287             :  * bms_next_member - find next member of a set
    1288             :  *
    1289             :  * Returns smallest member greater than "prevbit", or -2 if there is none.
    1290             :  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
    1291             :  *
    1292             :  * This is intended as support for iterating through the members of a set.
    1293             :  * The typical pattern is
    1294             :  *
    1295             :  *          x = -1;
    1296             :  *          while ((x = bms_next_member(inputset, x)) >= 0)
    1297             :  *              process member x;
    1298             :  *
    1299             :  * Notice that when there are no more members, we return -2, not -1 as you
    1300             :  * might expect.  The rationale for that is to allow distinguishing the
    1301             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1302             :  * It makes no difference in simple loop usage, but complex iteration logic
    1303             :  * might need such an ability.
    1304             :  */
    1305             : int
    1306    32373784 : bms_next_member(const Bitmapset *a, int prevbit)
    1307             : {
    1308             :     int         nwords;
    1309             :     int         wordnum;
    1310             :     bitmapword  mask;
    1311             : 
    1312             :     Assert(bms_is_valid_set(a));
    1313             : 
    1314    32373784 :     if (a == NULL)
    1315    13854644 :         return -2;
    1316    18519140 :     nwords = a->nwords;
    1317    18519140 :     prevbit++;
    1318    18519140 :     mask = (~(bitmapword) 0) << BITNUM(prevbit);
    1319    24489270 :     for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
    1320             :     {
    1321    18519548 :         bitmapword  w = a->words[wordnum];
    1322             : 
    1323             :         /* ignore bits before prevbit */
    1324    18519548 :         w &= mask;
    1325             : 
    1326    18519548 :         if (w != 0)
    1327             :         {
    1328             :             int         result;
    1329             : 
    1330    12549418 :             result = wordnum * BITS_PER_BITMAPWORD;
    1331    12549418 :             result += bmw_rightmost_one_pos(w);
    1332    12549418 :             return result;
    1333             :         }
    1334             : 
    1335             :         /* in subsequent words, consider all bits */
    1336     5970130 :         mask = (~(bitmapword) 0);
    1337             :     }
    1338     5969722 :     return -2;
    1339             : }
    1340             : 
    1341             : /*
    1342             :  * bms_prev_member - find prev member of a set
    1343             :  *
    1344             :  * Returns largest member less than "prevbit", or -2 if there is none.
    1345             :  * "prevbit" must NOT be more than one above the highest possible bit that can
    1346             :  * be set at the Bitmapset at its current size.
    1347             :  *
    1348             :  * To ease finding the highest set bit for the initial loop, the special
    1349             :  * prevbit value of -1 can be passed to have the function find the highest
    1350             :  * valued member in the set.
    1351             :  *
    1352             :  * This is intended as support for iterating through the members of a set in
    1353             :  * reverse.  The typical pattern is
    1354             :  *
    1355             :  *          x = -1;
    1356             :  *          while ((x = bms_prev_member(inputset, x)) >= 0)
    1357             :  *              process member x;
    1358             :  *
    1359             :  * Notice that when there are no more members, we return -2, not -1 as you
    1360             :  * might expect.  The rationale for that is to allow distinguishing the
    1361             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1362             :  * It makes no difference in simple loop usage, but complex iteration logic
    1363             :  * might need such an ability.
    1364             :  */
    1365             : 
    1366             : int
    1367          18 : bms_prev_member(const Bitmapset *a, int prevbit)
    1368             : {
    1369             :     int         wordnum;
    1370             :     int         ushiftbits;
    1371             :     bitmapword  mask;
    1372             : 
    1373             :     Assert(bms_is_valid_set(a));
    1374             : 
    1375             :     /*
    1376             :      * If set is NULL or if there are no more bits to the right then we've
    1377             :      * nothing to do.
    1378             :      */
    1379          18 :     if (a == NULL || prevbit == 0)
    1380           0 :         return -2;
    1381             : 
    1382             :     /* transform -1 to the highest possible bit we could have set */
    1383          18 :     if (prevbit == -1)
    1384           0 :         prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
    1385             :     else
    1386          18 :         prevbit--;
    1387             : 
    1388          18 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
    1389          18 :     mask = (~(bitmapword) 0) >> ushiftbits;
    1390          24 :     for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
    1391             :     {
    1392          18 :         bitmapword  w = a->words[wordnum];
    1393             : 
    1394             :         /* mask out bits left of prevbit */
    1395          18 :         w &= mask;
    1396             : 
    1397          18 :         if (w != 0)
    1398             :         {
    1399             :             int         result;
    1400             : 
    1401          12 :             result = wordnum * BITS_PER_BITMAPWORD;
    1402          12 :             result += bmw_leftmost_one_pos(w);
    1403          12 :             return result;
    1404             :         }
    1405             : 
    1406             :         /* in subsequent words, consider all bits */
    1407           6 :         mask = (~(bitmapword) 0);
    1408             :     }
    1409           6 :     return -2;
    1410             : }
    1411             : 
    1412             : /*
    1413             :  * bms_hash_value - compute a hash key for a Bitmapset
    1414             :  */
    1415             : uint32
    1416        5298 : bms_hash_value(const Bitmapset *a)
    1417             : {
    1418             :     Assert(bms_is_valid_set(a));
    1419             : 
    1420        5298 :     if (a == NULL)
    1421           0 :         return 0;               /* All empty sets hash to 0 */
    1422        5298 :     return DatumGetUInt32(hash_any((const unsigned char *) a->words,
    1423        5298 :                                    a->nwords * sizeof(bitmapword)));
    1424             : }
    1425             : 
    1426             : /*
    1427             :  * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
    1428             :  *
    1429             :  * Note: don't forget to specify bitmap_match as the match function!
    1430             :  */
    1431             : uint32
    1432        5298 : bitmap_hash(const void *key, Size keysize)
    1433             : {
    1434             :     Assert(keysize == sizeof(Bitmapset *));
    1435        5298 :     return bms_hash_value(*((const Bitmapset *const *) key));
    1436             : }
    1437             : 
    1438             : /*
    1439             :  * bitmap_match - match function to use with bitmap_hash
    1440             :  */
    1441             : int
    1442        3204 : bitmap_match(const void *key1, const void *key2, Size keysize)
    1443             : {
    1444             :     Assert(keysize == sizeof(Bitmapset *));
    1445        3204 :     return !bms_equal(*((const Bitmapset *const *) key1),
    1446             :                       *((const Bitmapset *const *) key2));
    1447             : }

Generated by: LCOV version 1.14