LCOV - code coverage report
Current view: top level - src/backend/nodes - bitmapset.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 371 433 85.7 %
Date: 2023-11-29 04:11:06 Functions: 31 31 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             :  *
      20             :  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
      21             :  *
      22             :  * IDENTIFICATION
      23             :  *    src/backend/nodes/bitmapset.c
      24             :  *
      25             :  *-------------------------------------------------------------------------
      26             :  */
      27             : #include "postgres.h"
      28             : 
      29             : #include "common/hashfn.h"
      30             : #include "nodes/bitmapset.h"
      31             : #include "nodes/pg_list.h"
      32             : #include "port/pg_bitutils.h"
      33             : 
      34             : 
      35             : #define WORDNUM(x)  ((x) / BITS_PER_BITMAPWORD)
      36             : #define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
      37             : 
      38             : #define BITMAPSET_SIZE(nwords)  \
      39             :     (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword))
      40             : 
      41             : /*----------
      42             :  * This is a well-known cute trick for isolating the rightmost one-bit
      43             :  * in a word.  It assumes two's complement arithmetic.  Consider any
      44             :  * nonzero value, and focus attention on the rightmost one.  The value is
      45             :  * then something like
      46             :  *              xxxxxx10000
      47             :  * where x's are unspecified bits.  The two's complement negative is formed
      48             :  * by inverting all the bits and adding one.  Inversion gives
      49             :  *              yyyyyy01111
      50             :  * where each y is the inverse of the corresponding x.  Incrementing gives
      51             :  *              yyyyyy10000
      52             :  * and then ANDing with the original value gives
      53             :  *              00000010000
      54             :  * This works for all cases except original value = zero, where of course
      55             :  * we get zero.
      56             :  *----------
      57             :  */
      58             : #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x)))
      59             : 
      60             : #define HAS_MULTIPLE_ONES(x)    ((bitmapword) RIGHTMOST_ONE(x) != (x))
      61             : 
      62             : /* Select appropriate bit-twiddling functions for bitmap word size */
      63             : #if BITS_PER_BITMAPWORD == 32
      64             : #define bmw_leftmost_one_pos(w)     pg_leftmost_one_pos32(w)
      65             : #define bmw_rightmost_one_pos(w)    pg_rightmost_one_pos32(w)
      66             : #define bmw_popcount(w)             pg_popcount32(w)
      67             : #elif BITS_PER_BITMAPWORD == 64
      68             : #define bmw_leftmost_one_pos(w)     pg_leftmost_one_pos64(w)
      69             : #define bmw_rightmost_one_pos(w)    pg_rightmost_one_pos64(w)
      70             : #define bmw_popcount(w)             pg_popcount64(w)
      71             : #else
      72             : #error "invalid BITS_PER_BITMAPWORD"
      73             : #endif
      74             : 
      75             : 
      76             : /*
      77             :  * bms_copy - make a palloc'd copy of a bitmapset
      78             :  */
      79             : Bitmapset *
      80    38455036 : bms_copy(const Bitmapset *a)
      81             : {
      82             :     Bitmapset  *result;
      83             :     size_t      size;
      84             : 
      85    38455036 :     if (a == NULL)
      86    24995858 :         return NULL;
      87    13459178 :     size = BITMAPSET_SIZE(a->nwords);
      88    13459178 :     result = (Bitmapset *) palloc(size);
      89    13459178 :     memcpy(result, a, size);
      90    13459178 :     return result;
      91             : }
      92             : 
      93             : /*
      94             :  * bms_equal - are two bitmapsets equal? or both NULL?
      95             :  */
      96             : bool
      97    18886934 : bms_equal(const Bitmapset *a, const Bitmapset *b)
      98             : {
      99             :     int         i;
     100             : 
     101             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     102             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     103             : 
     104             :     /* Handle cases where either input is NULL */
     105    18886934 :     if (a == NULL)
     106             :     {
     107    12931588 :         if (b == NULL)
     108    12861288 :             return true;
     109       70300 :         return false;
     110             :     }
     111     5955346 :     else if (b == NULL)
     112       20738 :         return false;
     113             : 
     114             :     /* can't be equal if the word counts don't match */
     115     5934608 :     if (a->nwords != b->nwords)
     116           0 :         return false;
     117             : 
     118             :     /* check each word matches */
     119     5934608 :     i = 0;
     120             :     do
     121             :     {
     122     5935016 :         if (a->words[i] != b->words[i])
     123     2228432 :             return false;
     124     3706584 :     } while (++i < a->nwords);
     125             : 
     126     3706176 :     return true;
     127             : }
     128             : 
     129             : /*
     130             :  * bms_compare - qsort-style comparator for bitmapsets
     131             :  *
     132             :  * This guarantees to report values as equal iff bms_equal would say they are
     133             :  * equal.  Otherwise, the highest-numbered bit that is set in one value but
     134             :  * not the other determines the result.  (This rule means that, for example,
     135             :  * {6} is greater than {5}, which seems plausible.)
     136             :  */
     137             : int
     138       19958 : bms_compare(const Bitmapset *a, const Bitmapset *b)
     139             : {
     140             :     int         i;
     141             : 
     142             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     143             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     144             : 
     145             :     /* Handle cases where either input is NULL */
     146       19958 :     if (a == NULL)
     147           0 :         return (b == NULL) ? 0 : -1;
     148       19958 :     else if (b == NULL)
     149           0 :         return +1;
     150             : 
     151             :     /* the set with the most words must be greater */
     152       19958 :     if (a->nwords != b->nwords)
     153           0 :         return (a->nwords > b->nwords) ? +1 : -1;
     154             : 
     155       19958 :     i = a->nwords - 1;
     156             :     do
     157             :     {
     158       19958 :         bitmapword  aw = a->words[i];
     159       19958 :         bitmapword  bw = b->words[i];
     160             : 
     161       19958 :         if (aw != bw)
     162       19958 :             return (aw > bw) ? +1 : -1;
     163           0 :     } while (--i >= 0);
     164           0 :     return 0;
     165             : }
     166             : 
     167             : /*
     168             :  * bms_make_singleton - build a bitmapset containing a single member
     169             :  */
     170             : Bitmapset *
     171    11693138 : bms_make_singleton(int x)
     172             : {
     173             :     Bitmapset  *result;
     174             :     int         wordnum,
     175             :                 bitnum;
     176             : 
     177    11693138 :     if (x < 0)
     178           0 :         elog(ERROR, "negative bitmapset member not allowed");
     179    11693138 :     wordnum = WORDNUM(x);
     180    11693138 :     bitnum = BITNUM(x);
     181    11693138 :     result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
     182    11693138 :     result->type = T_Bitmapset;
     183    11693138 :     result->nwords = wordnum + 1;
     184    11693138 :     result->words[wordnum] = ((bitmapword) 1 << bitnum);
     185    11693138 :     return result;
     186             : }
     187             : 
     188             : /*
     189             :  * bms_free - free a bitmapset
     190             :  *
     191             :  * Same as pfree except for allowing NULL input
     192             :  */
     193             : void
     194    14917576 : bms_free(Bitmapset *a)
     195             : {
     196    14917576 :     if (a)
     197     6509996 :         pfree(a);
     198    14917576 : }
     199             : 
     200             : 
     201             : /*
     202             :  * These operations all make a freshly palloc'd result,
     203             :  * leaving their inputs untouched
     204             :  */
     205             : 
     206             : 
     207             : /*
     208             :  * bms_union - set union
     209             :  */
     210             : Bitmapset *
     211     6353136 : bms_union(const Bitmapset *a, const Bitmapset *b)
     212             : {
     213             :     Bitmapset  *result;
     214             :     const Bitmapset *other;
     215             :     int         otherlen;
     216             :     int         i;
     217             : 
     218             :     /* Handle cases where either input is NULL */
     219     6353136 :     if (a == NULL)
     220     4056130 :         return bms_copy(b);
     221     2297006 :     if (b == NULL)
     222     1030252 :         return bms_copy(a);
     223             :     /* Identify shorter and longer input; copy the longer one */
     224     1266754 :     if (a->nwords <= b->nwords)
     225             :     {
     226     1266754 :         result = bms_copy(b);
     227     1266754 :         other = a;
     228             :     }
     229             :     else
     230             :     {
     231           0 :         result = bms_copy(a);
     232           0 :         other = b;
     233             :     }
     234             :     /* And union the shorter input into the result */
     235     1266754 :     otherlen = other->nwords;
     236     1266754 :     i = 0;
     237             :     do
     238             :     {
     239     1266754 :         result->words[i] |= other->words[i];
     240     1266754 :     } while (++i < otherlen);
     241     1266754 :     return result;
     242             : }
     243             : 
     244             : /*
     245             :  * bms_intersect - set intersection
     246             :  */
     247             : Bitmapset *
     248      836152 : bms_intersect(const Bitmapset *a, const Bitmapset *b)
     249             : {
     250             :     Bitmapset  *result;
     251             :     const Bitmapset *other;
     252             :     int         lastnonzero;
     253             :     int         resultlen;
     254             :     int         i;
     255             : 
     256             :     /* Handle cases where either input is NULL */
     257      836152 :     if (a == NULL || b == NULL)
     258      170870 :         return NULL;
     259             :     /* Identify shorter and longer input; copy the shorter one */
     260      665282 :     if (a->nwords <= b->nwords)
     261             :     {
     262      665282 :         result = bms_copy(a);
     263      665282 :         other = b;
     264             :     }
     265             :     else
     266             :     {
     267           0 :         result = bms_copy(b);
     268           0 :         other = a;
     269             :     }
     270             :     /* And intersect the longer input with the result */
     271      665282 :     resultlen = result->nwords;
     272      665282 :     lastnonzero = -1;
     273      665282 :     i = 0;
     274             :     do
     275             :     {
     276      665282 :         result->words[i] &= other->words[i];
     277             : 
     278      665282 :         if (result->words[i] != 0)
     279      657788 :             lastnonzero = i;
     280      665282 :     } while (++i < resultlen);
     281             :     /* If we computed an empty result, we must return NULL */
     282      665282 :     if (lastnonzero == -1)
     283             :     {
     284        7494 :         pfree(result);
     285        7494 :         return NULL;
     286             :     }
     287             : 
     288             :     /* get rid of trailing zero words */
     289      657788 :     result->nwords = lastnonzero + 1;
     290      657788 :     return result;
     291             : }
     292             : 
     293             : /*
     294             :  * bms_difference - set difference (ie, A without members of B)
     295             :  */
     296             : Bitmapset *
     297      677042 : bms_difference(const Bitmapset *a, const Bitmapset *b)
     298             : {
     299             :     Bitmapset  *result;
     300             :     int         i;
     301             : 
     302             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     303             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     304             : 
     305             :     /* Handle cases where either input is NULL */
     306      677042 :     if (a == NULL)
     307       10878 :         return NULL;
     308      666164 :     if (b == NULL)
     309      429136 :         return bms_copy(a);
     310             : 
     311             :     /*
     312             :      * In Postgres' usage, an empty result is a very common case, so it's
     313             :      * worth optimizing for that by testing bms_nonempty_difference().  This
     314             :      * saves us a palloc/pfree cycle compared to checking after-the-fact.
     315             :      */
     316      237028 :     if (!bms_nonempty_difference(a, b))
     317       88444 :         return NULL;
     318             : 
     319             :     /* Copy the left input */
     320      148584 :     result = bms_copy(a);
     321             : 
     322             :     /* And remove b's bits from result */
     323      148584 :     if (result->nwords > b->nwords)
     324             :     {
     325             :         /*
     326             :          * We'll never need to remove trailing zero words when 'a' has more
     327             :          * words than 'b' as the additional words must be non-zero.
     328             :          */
     329           0 :         i = 0;
     330             :         do
     331             :         {
     332           0 :             result->words[i] &= ~b->words[i];
     333           0 :         } while (++i < b->nwords);
     334             :     }
     335             :     else
     336             :     {
     337      148584 :         int         lastnonzero = -1;
     338             : 
     339             :         /* we may need to remove trailing zero words from the result. */
     340      148584 :         i = 0;
     341             :         do
     342             :         {
     343      148584 :             result->words[i] &= ~b->words[i];
     344             : 
     345             :             /* remember the last non-zero word */
     346      148584 :             if (result->words[i] != 0)
     347      148584 :                 lastnonzero = i;
     348      148584 :         } while (++i < result->nwords);
     349             : 
     350             :         /* trim off trailing zero words */
     351      148584 :         result->nwords = lastnonzero + 1;
     352             :     }
     353             :     Assert(result->nwords != 0);
     354             : 
     355             :     /* Need not check for empty result, since we handled that case above */
     356      148584 :     return result;
     357             : }
     358             : 
     359             : /*
     360             :  * bms_is_subset - is A a subset of B?
     361             :  */
     362             : bool
     363    14780514 : bms_is_subset(const Bitmapset *a, const Bitmapset *b)
     364             : {
     365             :     int         i;
     366             : 
     367             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     368             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     369             : 
     370             :     /* Handle cases where either input is NULL */
     371    14780514 :     if (a == NULL)
     372     1503664 :         return true;            /* empty set is a subset of anything */
     373    13276850 :     if (b == NULL)
     374      306606 :         return false;
     375             : 
     376             :     /* 'a' can't be a subset of 'b' if it contains more words */
     377    12970244 :     if (a->nwords > b->nwords)
     378           0 :         return false;
     379             : 
     380             :     /* Check all 'a' members are set in 'b' */
     381    12970244 :     i = 0;
     382             :     do
     383             :     {
     384    12970244 :         if ((a->words[i] & ~b->words[i]) != 0)
     385     5136612 :             return false;
     386     7833632 :     } while (++i < a->nwords);
     387     7833632 :     return true;
     388             : }
     389             : 
     390             : /*
     391             :  * bms_subset_compare - compare A and B for equality/subset relationships
     392             :  *
     393             :  * This is more efficient than testing bms_is_subset in both directions.
     394             :  */
     395             : BMS_Comparison
     396     1806240 : bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
     397             : {
     398             :     BMS_Comparison result;
     399             :     int         shortlen;
     400             :     int         i;
     401             : 
     402             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     403             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     404             : 
     405             :     /* Handle cases where either input is NULL */
     406     1806240 :     if (a == NULL)
     407             :     {
     408     1526522 :         if (b == NULL)
     409     1461294 :             return BMS_EQUAL;
     410       65228 :         return BMS_SUBSET1;
     411             :     }
     412      279718 :     if (b == NULL)
     413      134252 :         return BMS_SUBSET2;
     414             :     /* Check common words */
     415      145466 :     result = BMS_EQUAL;         /* status so far */
     416      145466 :     shortlen = Min(a->nwords, b->nwords);
     417      145466 :     i = 0;
     418             :     do
     419             :     {
     420      145466 :         bitmapword  aword = a->words[i];
     421      145466 :         bitmapword  bword = b->words[i];
     422             : 
     423      145466 :         if ((aword & ~bword) != 0)
     424             :         {
     425             :             /* a is not a subset of b */
     426       32844 :             if (result == BMS_SUBSET1)
     427           0 :                 return BMS_DIFFERENT;
     428       32844 :             result = BMS_SUBSET2;
     429             :         }
     430      145466 :         if ((bword & ~aword) != 0)
     431             :         {
     432             :             /* b is not a subset of a */
     433       33018 :             if (result == BMS_SUBSET2)
     434       30592 :                 return BMS_DIFFERENT;
     435        2426 :             result = BMS_SUBSET1;
     436             :         }
     437      114874 :     } while (++i < shortlen);
     438             :     /* Check extra words */
     439      114874 :     if (a->nwords > b->nwords)
     440             :     {
     441             :         /* if a has more words then a is not a subset of b */
     442           0 :         if (result == BMS_SUBSET1)
     443           0 :             return BMS_DIFFERENT;
     444           0 :         return BMS_SUBSET2;
     445             :     }
     446      114874 :     else if (a->nwords < b->nwords)
     447             :     {
     448             :         /* if b has more words then b is not a subset of a */
     449           0 :         if (result == BMS_SUBSET2)
     450           0 :             return BMS_DIFFERENT;
     451           0 :         return BMS_SUBSET1;
     452             :     }
     453      114874 :     return result;
     454             : }
     455             : 
     456             : /*
     457             :  * bms_is_member - is X a member of A?
     458             :  */
     459             : bool
     460    11175306 : bms_is_member(int x, const Bitmapset *a)
     461             : {
     462             :     int         wordnum,
     463             :                 bitnum;
     464             : 
     465             :     /* XXX better to just return false for x<0 ? */
     466    11175306 :     if (x < 0)
     467           0 :         elog(ERROR, "negative bitmapset member not allowed");
     468    11175306 :     if (a == NULL)
     469     6655766 :         return false;
     470     4519540 :     wordnum = WORDNUM(x);
     471     4519540 :     bitnum = BITNUM(x);
     472     4519540 :     if (wordnum >= a->nwords)
     473         226 :         return false;
     474     4519314 :     if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     475     3046196 :         return true;
     476     1473118 :     return false;
     477             : }
     478             : 
     479             : /*
     480             :  * bms_member_index
     481             :  *      determine 0-based index of member x in the bitmap
     482             :  *
     483             :  * Returns (-1) when x is not a member.
     484             :  */
     485             : int
     486        4110 : bms_member_index(Bitmapset *a, int x)
     487             : {
     488             :     int         i;
     489             :     int         bitnum;
     490             :     int         wordnum;
     491        4110 :     int         result = 0;
     492             :     bitmapword  mask;
     493             : 
     494             :     /* return -1 if not a member of the bitmap */
     495        4110 :     if (!bms_is_member(x, a))
     496           0 :         return -1;
     497             : 
     498        4110 :     wordnum = WORDNUM(x);
     499        4110 :     bitnum = BITNUM(x);
     500             : 
     501             :     /* count bits in preceding words */
     502        4110 :     for (i = 0; i < wordnum; i++)
     503             :     {
     504           0 :         bitmapword  w = a->words[i];
     505             : 
     506             :         /* No need to count the bits in a zero word */
     507           0 :         if (w != 0)
     508           0 :             result += bmw_popcount(w);
     509             :     }
     510             : 
     511             :     /*
     512             :      * Now add bits of the last word, but only those before the item. We can
     513             :      * do that by applying a mask and then using popcount again. To get
     514             :      * 0-based index, we want to count only preceding bits, not the item
     515             :      * itself, so we subtract 1.
     516             :      */
     517        4110 :     mask = ((bitmapword) 1 << bitnum) - 1;
     518        4110 :     result += bmw_popcount(a->words[wordnum] & mask);
     519             : 
     520        4110 :     return result;
     521             : }
     522             : 
     523             : /*
     524             :  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
     525             :  */
     526             : bool
     527     9819294 : bms_overlap(const Bitmapset *a, const Bitmapset *b)
     528             : {
     529             :     int         shortlen;
     530             :     int         i;
     531             : 
     532             :     /* Handle cases where either input is NULL */
     533     9819294 :     if (a == NULL || b == NULL)
     534     3786136 :         return false;
     535             :     /* Check words in common */
     536     6033158 :     shortlen = Min(a->nwords, b->nwords);
     537     6033158 :     i = 0;
     538             :     do
     539             :     {
     540     6033158 :         if ((a->words[i] & b->words[i]) != 0)
     541     3889952 :             return true;
     542     2143206 :     } while (++i < shortlen);
     543     2143206 :     return false;
     544             : }
     545             : 
     546             : /*
     547             :  * bms_overlap_list - does a set overlap an integer list?
     548             :  */
     549             : bool
     550        1306 : bms_overlap_list(const Bitmapset *a, const List *b)
     551             : {
     552             :     ListCell   *lc;
     553             :     int         wordnum,
     554             :                 bitnum;
     555             : 
     556        1306 :     if (a == NULL || b == NIL)
     557        1168 :         return false;
     558             : 
     559         258 :     foreach(lc, b)
     560             :     {
     561         198 :         int         x = lfirst_int(lc);
     562             : 
     563         198 :         if (x < 0)
     564           0 :             elog(ERROR, "negative bitmapset member not allowed");
     565         198 :         wordnum = WORDNUM(x);
     566         198 :         bitnum = BITNUM(x);
     567         198 :         if (wordnum < a->nwords)
     568         198 :             if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     569          78 :                 return true;
     570             :     }
     571             : 
     572          60 :     return false;
     573             : }
     574             : 
     575             : /*
     576             :  * bms_nonempty_difference - do sets have a nonempty difference?
     577             :  *
     578             :  * i.e., are any members set in 'a' that are not also set in 'b'.
     579             :  */
     580             : bool
     581     1877928 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
     582             : {
     583             :     int         i;
     584             : 
     585             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     586             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     587             : 
     588             :     /* Handle cases where either input is NULL */
     589     1877928 :     if (a == NULL)
     590          72 :         return false;
     591     1877856 :     if (b == NULL)
     592           0 :         return true;
     593             :     /* if 'a' has more words then it must contain additional members */
     594     1877856 :     if (a->nwords > b->nwords)
     595           0 :         return true;
     596             :     /* Check all 'a' members are set in 'b' */
     597     1877856 :     i = 0;
     598             :     do
     599             :     {
     600     1877856 :         if ((a->words[i] & ~b->words[i]) != 0)
     601     1085204 :             return true;
     602      792652 :     } while (++i < a->nwords);
     603      792652 :     return false;
     604             : }
     605             : 
     606             : /*
     607             :  * bms_singleton_member - return the sole integer member of set
     608             :  *
     609             :  * Raises error if |a| is not 1.
     610             :  */
     611             : int
     612       14822 : bms_singleton_member(const Bitmapset *a)
     613             : {
     614       14822 :     int         result = -1;
     615             :     int         nwords;
     616             :     int         wordnum;
     617             : 
     618       14822 :     if (a == NULL)
     619           0 :         elog(ERROR, "bitmapset is empty");
     620       14822 :     nwords = a->nwords;
     621       14822 :     wordnum = 0;
     622             :     do
     623             :     {
     624       14822 :         bitmapword  w = a->words[wordnum];
     625             : 
     626       14822 :         if (w != 0)
     627             :         {
     628       14822 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     629           0 :                 elog(ERROR, "bitmapset has multiple members");
     630       14822 :             result = wordnum * BITS_PER_BITMAPWORD;
     631       14822 :             result += bmw_rightmost_one_pos(w);
     632             :         }
     633       14822 :     } while (++wordnum < nwords);
     634             : 
     635             :     /* we don't expect non-NULL sets to be empty */
     636             :     Assert(result >= 0);
     637       14822 :     return result;
     638             : }
     639             : 
     640             : /*
     641             :  * bms_get_singleton_member
     642             :  *
     643             :  * Test whether the given set is a singleton.
     644             :  * If so, set *member to the value of its sole member, and return true.
     645             :  * If not, return false, without changing *member.
     646             :  *
     647             :  * This is more convenient and faster than calling bms_membership() and then
     648             :  * bms_singleton_member(), if we don't care about distinguishing empty sets
     649             :  * from multiple-member sets.
     650             :  */
     651             : bool
     652     1745826 : bms_get_singleton_member(const Bitmapset *a, int *member)
     653             : {
     654     1745826 :     int         result = -1;
     655             :     int         nwords;
     656             :     int         wordnum;
     657             : 
     658     1745826 :     if (a == NULL)
     659           0 :         return false;
     660     1745826 :     nwords = a->nwords;
     661     1745826 :     wordnum = 0;
     662             :     do
     663             :     {
     664     1745826 :         bitmapword  w = a->words[wordnum];
     665             : 
     666     1745826 :         if (w != 0)
     667             :         {
     668     1745826 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     669      298014 :                 return false;
     670     1447812 :             result = wordnum * BITS_PER_BITMAPWORD;
     671     1447812 :             result += bmw_rightmost_one_pos(w);
     672             :         }
     673     1447812 :     } while (++wordnum < nwords);
     674             : 
     675             :     /* we don't expect non-NULL sets to be empty */
     676             :     Assert(result >= 0);
     677     1447812 :     *member = result;
     678     1447812 :     return true;
     679             : }
     680             : 
     681             : /*
     682             :  * bms_num_members - count members of set
     683             :  */
     684             : int
     685     1517208 : bms_num_members(const Bitmapset *a)
     686             : {
     687     1517208 :     int         result = 0;
     688             :     int         nwords;
     689             :     int         wordnum;
     690             : 
     691     1517208 :     if (a == NULL)
     692      140756 :         return 0;
     693     1376452 :     nwords = a->nwords;
     694     1376452 :     wordnum = 0;
     695             :     do
     696             :     {
     697     1376452 :         bitmapword  w = a->words[wordnum];
     698             : 
     699             :         /* No need to count the bits in a zero word */
     700     1376452 :         if (w != 0)
     701     1376452 :             result += bmw_popcount(w);
     702     1376452 :     } while (++wordnum < nwords);
     703     1376452 :     return result;
     704             : }
     705             : 
     706             : /*
     707             :  * bms_membership - does a set have zero, one, or multiple members?
     708             :  *
     709             :  * This is faster than making an exact count with bms_num_members().
     710             :  */
     711             : BMS_Membership
     712      936542 : bms_membership(const Bitmapset *a)
     713             : {
     714      936542 :     BMS_Membership result = BMS_EMPTY_SET;
     715             :     int         nwords;
     716             :     int         wordnum;
     717             : 
     718      936542 :     if (a == NULL)
     719         464 :         return BMS_EMPTY_SET;
     720      936078 :     nwords = a->nwords;
     721      936078 :     wordnum = 0;
     722             :     do
     723             :     {
     724      936078 :         bitmapword  w = a->words[wordnum];
     725             : 
     726      936078 :         if (w != 0)
     727             :         {
     728      936078 :             if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
     729      297032 :                 return BMS_MULTIPLE;
     730      639046 :             result = BMS_SINGLETON;
     731             :         }
     732      639046 :     } while (++wordnum < nwords);
     733      639046 :     return result;
     734             : }
     735             : 
     736             : 
     737             : /*
     738             :  * These operations all "recycle" their non-const inputs, ie, either
     739             :  * return the modified input or pfree it if it can't hold the result.
     740             :  *
     741             :  * These should generally be used in the style
     742             :  *
     743             :  *      foo = bms_add_member(foo, x);
     744             :  */
     745             : 
     746             : 
     747             : /*
     748             :  * bms_add_member - add a specified member to set
     749             :  *
     750             :  * Input set is modified or recycled!
     751             :  */
     752             : Bitmapset *
     753    16525988 : bms_add_member(Bitmapset *a, int x)
     754             : {
     755             :     int         wordnum,
     756             :                 bitnum;
     757             : 
     758    16525988 :     if (x < 0)
     759           0 :         elog(ERROR, "negative bitmapset member not allowed");
     760    16525988 :     if (a == NULL)
     761     9903480 :         return bms_make_singleton(x);
     762     6622508 :     wordnum = WORDNUM(x);
     763     6622508 :     bitnum = BITNUM(x);
     764             : 
     765             :     /* enlarge the set if necessary */
     766     6622508 :     if (wordnum >= a->nwords)
     767             :     {
     768         204 :         int         oldnwords = a->nwords;
     769             :         int         i;
     770             : 
     771         204 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
     772         204 :         a->nwords = wordnum + 1;
     773             :         /* zero out the enlarged portion */
     774         204 :         i = oldnwords;
     775             :         do
     776             :         {
     777         876 :             a->words[i] = 0;
     778         876 :         } while (++i < a->nwords);
     779             :     }
     780             : 
     781     6622508 :     a->words[wordnum] |= ((bitmapword) 1 << bitnum);
     782     6622508 :     return a;
     783             : }
     784             : 
     785             : /*
     786             :  * bms_del_member - remove a specified member from set
     787             :  *
     788             :  * No error if x is not currently a member of set
     789             :  *
     790             :  * Input set is modified in-place!
     791             :  */
     792             : Bitmapset *
     793     2029236 : bms_del_member(Bitmapset *a, int x)
     794             : {
     795             :     int         wordnum,
     796             :                 bitnum;
     797             : 
     798     2029236 :     if (x < 0)
     799           0 :         elog(ERROR, "negative bitmapset member not allowed");
     800     2029236 :     if (a == NULL)
     801     1048860 :         return NULL;
     802      980376 :     wordnum = WORDNUM(x);
     803      980376 :     bitnum = BITNUM(x);
     804             : 
     805             :     /* member can't exist.  Return 'a' unmodified */
     806      980376 :     if (unlikely(wordnum >= a->nwords))
     807           0 :         return a;
     808             : 
     809      980376 :     a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
     810             : 
     811             :     /* when last word becomes empty, trim off all trailing empty words */
     812      980376 :     if (a->words[wordnum] == 0 && wordnum == a->nwords - 1)
     813             :     {
     814             :         /* find the last non-empty word and make that the new final word */
     815      456288 :         for (int i = wordnum - 1; i >= 0; i--)
     816             :         {
     817           0 :             if (a->words[i] != 0)
     818             :             {
     819           0 :                 a->nwords = i + 1;
     820           0 :                 return a;
     821             :             }
     822             :         }
     823             : 
     824             :         /* the set is now empty */
     825      456288 :         pfree(a);
     826      456288 :         return NULL;
     827             :     }
     828      524088 :     return a;
     829             : }
     830             : 
     831             : /*
     832             :  * bms_add_members - like bms_union, but left input is recycled
     833             :  */
     834             : Bitmapset *
     835    11134240 : bms_add_members(Bitmapset *a, const Bitmapset *b)
     836             : {
     837             :     Bitmapset  *result;
     838             :     const Bitmapset *other;
     839             :     int         otherlen;
     840             :     int         i;
     841             : 
     842             :     /* Handle cases where either input is NULL */
     843    11134240 :     if (a == NULL)
     844     5854040 :         return bms_copy(b);
     845     5280200 :     if (b == NULL)
     846     3340534 :         return a;
     847             :     /* Identify shorter and longer input; copy the longer one if needed */
     848     1939666 :     if (a->nwords < b->nwords)
     849             :     {
     850           0 :         result = bms_copy(b);
     851           0 :         other = a;
     852             :     }
     853             :     else
     854             :     {
     855     1939666 :         result = a;
     856     1939666 :         other = b;
     857             :     }
     858             :     /* And union the shorter input into the result */
     859     1939666 :     otherlen = other->nwords;
     860     1939666 :     i = 0;
     861             :     do
     862             :     {
     863     1939666 :         result->words[i] |= other->words[i];
     864     1939666 :     } while (++i < otherlen);
     865     1939666 :     if (result != a)
     866           0 :         pfree(a);
     867     1939666 :     return result;
     868             : }
     869             : 
     870             : /*
     871             :  * bms_add_range
     872             :  *      Add members in the range of 'lower' to 'upper' to the set.
     873             :  *
     874             :  * Note this could also be done by calling bms_add_member in a loop, however,
     875             :  * using this function will be faster when the range is large as we work at
     876             :  * the bitmapword level rather than at bit level.
     877             :  */
     878             : Bitmapset *
     879       25378 : bms_add_range(Bitmapset *a, int lower, int upper)
     880             : {
     881             :     int         lwordnum,
     882             :                 lbitnum,
     883             :                 uwordnum,
     884             :                 ushiftbits,
     885             :                 wordnum;
     886             : 
     887             :     /* do nothing if nothing is called for, without further checking */
     888       25378 :     if (upper < lower)
     889          28 :         return a;
     890             : 
     891       25350 :     if (lower < 0)
     892           0 :         elog(ERROR, "negative bitmapset member not allowed");
     893       25350 :     uwordnum = WORDNUM(upper);
     894             : 
     895       25350 :     if (a == NULL)
     896             :     {
     897       25350 :         a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
     898       25350 :         a->type = T_Bitmapset;
     899       25350 :         a->nwords = uwordnum + 1;
     900             :     }
     901           0 :     else if (uwordnum >= a->nwords)
     902             :     {
     903           0 :         int         oldnwords = a->nwords;
     904             :         int         i;
     905             : 
     906             :         /* ensure we have enough words to store the upper bit */
     907           0 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
     908           0 :         a->nwords = uwordnum + 1;
     909             :         /* zero out the enlarged portion */
     910           0 :         i = oldnwords;
     911             :         do
     912             :         {
     913           0 :             a->words[i] = 0;
     914           0 :         } while (++i < a->nwords);
     915             :     }
     916             : 
     917       25350 :     wordnum = lwordnum = WORDNUM(lower);
     918             : 
     919       25350 :     lbitnum = BITNUM(lower);
     920       25350 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
     921             : 
     922             :     /*
     923             :      * Special case when lwordnum is the same as uwordnum we must perform the
     924             :      * upper and lower masking on the word.
     925             :      */
     926       25350 :     if (lwordnum == uwordnum)
     927             :     {
     928       25350 :         a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
     929       25350 :             & (~(bitmapword) 0) >> ushiftbits;
     930             :     }
     931             :     else
     932             :     {
     933             :         /* turn on lbitnum and all bits left of it */
     934           0 :         a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
     935             : 
     936             :         /* turn on all bits for any intermediate words */
     937           0 :         while (wordnum < uwordnum)
     938           0 :             a->words[wordnum++] = ~(bitmapword) 0;
     939             : 
     940             :         /* turn on upper's bit and all bits right of it. */
     941           0 :         a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
     942             :     }
     943             : 
     944       25350 :     return a;
     945             : }
     946             : 
     947             : /*
     948             :  * bms_int_members - like bms_intersect, but left input is recycled
     949             :  */
     950             : Bitmapset *
     951      486090 : bms_int_members(Bitmapset *a, const Bitmapset *b)
     952             : {
     953             :     int         lastnonzero;
     954             :     int         shortlen;
     955             :     int         i;
     956             : 
     957             :     /* Handle cases where either input is NULL */
     958      486090 :     if (a == NULL)
     959       25158 :         return NULL;
     960      460932 :     if (b == NULL)
     961             :     {
     962        3818 :         pfree(a);
     963        3818 :         return NULL;
     964             :     }
     965             :     /* Intersect b into a; we need never copy */
     966      457114 :     shortlen = Min(a->nwords, b->nwords);
     967      457114 :     lastnonzero = -1;
     968      457114 :     i = 0;
     969             :     do
     970             :     {
     971      457114 :         a->words[i] &= b->words[i];
     972             : 
     973      457114 :         if (a->words[i] != 0)
     974      364724 :             lastnonzero = i;
     975      457114 :     } while (++i < shortlen);
     976             : 
     977             :     /* If we computed an empty result, we must return NULL */
     978      457114 :     if (lastnonzero == -1)
     979             :     {
     980       92390 :         pfree(a);
     981       92390 :         return NULL;
     982             :     }
     983             : 
     984             :     /* get rid of trailing zero words */
     985      364724 :     a->nwords = lastnonzero + 1;
     986      364724 :     return a;
     987             : }
     988             : 
     989             : /*
     990             :  * bms_del_members - like bms_difference, but left input is recycled
     991             :  */
     992             : Bitmapset *
     993     1619744 : bms_del_members(Bitmapset *a, const Bitmapset *b)
     994             : {
     995             :     int         i;
     996             : 
     997             :     Assert(a == NULL || a->words[a->nwords - 1] != 0);
     998             :     Assert(b == NULL || b->words[b->nwords - 1] != 0);
     999             : 
    1000             :     /* Handle cases where either input is NULL */
    1001     1619744 :     if (a == NULL)
    1002      714950 :         return NULL;
    1003      904794 :     if (b == NULL)
    1004      164040 :         return a;
    1005             :     /* Remove b's bits from a; we need never copy */
    1006      740754 :     if (a->nwords > b->nwords)
    1007             :     {
    1008             :         /*
    1009             :          * We'll never need to remove trailing zero words when 'a' has more
    1010             :          * words than 'b'.
    1011             :          */
    1012           0 :         i = 0;
    1013             :         do
    1014             :         {
    1015           0 :             a->words[i] &= ~b->words[i];
    1016           0 :         } while (++i < b->nwords);
    1017             :     }
    1018             :     else
    1019             :     {
    1020      740754 :         int         lastnonzero = -1;
    1021             : 
    1022             :         /* we may need to remove trailing zero words from the result. */
    1023      740754 :         i = 0;
    1024             :         do
    1025             :         {
    1026      740754 :             a->words[i] &= ~b->words[i];
    1027             : 
    1028             :             /* remember the last non-zero word */
    1029      740754 :             if (a->words[i] != 0)
    1030      138794 :                 lastnonzero = i;
    1031      740754 :         } while (++i < a->nwords);
    1032             : 
    1033             :         /* check if 'a' has become empty */
    1034      740754 :         if (lastnonzero == -1)
    1035             :         {
    1036      601960 :             pfree(a);
    1037      601960 :             return NULL;
    1038             :         }
    1039             : 
    1040             :         /* trim off any trailing zero words */
    1041      138794 :         a->nwords = lastnonzero + 1;
    1042             :     }
    1043             : 
    1044      138794 :     return a;
    1045             : }
    1046             : 
    1047             : /*
    1048             :  * bms_join - like bms_union, but *both* inputs are recycled
    1049             :  */
    1050             : Bitmapset *
    1051     1196850 : bms_join(Bitmapset *a, Bitmapset *b)
    1052             : {
    1053             :     Bitmapset  *result;
    1054             :     Bitmapset  *other;
    1055             :     int         otherlen;
    1056             :     int         i;
    1057             : 
    1058             :     /* Handle cases where either input is NULL */
    1059     1196850 :     if (a == NULL)
    1060      537392 :         return b;
    1061      659458 :     if (b == NULL)
    1062      135970 :         return a;
    1063             :     /* Identify shorter and longer input; use longer one as result */
    1064      523488 :     if (a->nwords < b->nwords)
    1065             :     {
    1066           0 :         result = b;
    1067           0 :         other = a;
    1068             :     }
    1069             :     else
    1070             :     {
    1071      523488 :         result = a;
    1072      523488 :         other = b;
    1073             :     }
    1074             :     /* And union the shorter input into the result */
    1075      523488 :     otherlen = other->nwords;
    1076      523488 :     i = 0;
    1077             :     do
    1078             :     {
    1079      523488 :         result->words[i] |= other->words[i];
    1080      523488 :     } while (++i < otherlen);
    1081      523488 :     if (other != result)        /* pure paranoia */
    1082      523488 :         pfree(other);
    1083      523488 :     return result;
    1084             : }
    1085             : 
    1086             : /*
    1087             :  * bms_next_member - find next member of a set
    1088             :  *
    1089             :  * Returns smallest member greater than "prevbit", or -2 if there is none.
    1090             :  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
    1091             :  *
    1092             :  * This is intended as support for iterating through the members of a set.
    1093             :  * The typical pattern is
    1094             :  *
    1095             :  *          x = -1;
    1096             :  *          while ((x = bms_next_member(inputset, x)) >= 0)
    1097             :  *              process member x;
    1098             :  *
    1099             :  * Notice that when there are no more members, we return -2, not -1 as you
    1100             :  * might expect.  The rationale for that is to allow distinguishing the
    1101             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1102             :  * It makes no difference in simple loop usage, but complex iteration logic
    1103             :  * might need such an ability.
    1104             :  */
    1105             : int
    1106    31377926 : bms_next_member(const Bitmapset *a, int prevbit)
    1107             : {
    1108             :     int         nwords;
    1109             :     int         wordnum;
    1110             :     bitmapword  mask;
    1111             : 
    1112    31377926 :     if (a == NULL)
    1113    13161692 :         return -2;
    1114    18216234 :     nwords = a->nwords;
    1115    18216234 :     prevbit++;
    1116    18216234 :     mask = (~(bitmapword) 0) << BITNUM(prevbit);
    1117    24250830 :     for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
    1118             :     {
    1119    18216642 :         bitmapword  w = a->words[wordnum];
    1120             : 
    1121             :         /* ignore bits before prevbit */
    1122    18216642 :         w &= mask;
    1123             : 
    1124    18216642 :         if (w != 0)
    1125             :         {
    1126             :             int         result;
    1127             : 
    1128    12182046 :             result = wordnum * BITS_PER_BITMAPWORD;
    1129    12182046 :             result += bmw_rightmost_one_pos(w);
    1130    12182046 :             return result;
    1131             :         }
    1132             : 
    1133             :         /* in subsequent words, consider all bits */
    1134     6034596 :         mask = (~(bitmapword) 0);
    1135             :     }
    1136     6034188 :     return -2;
    1137             : }
    1138             : 
    1139             : /*
    1140             :  * bms_prev_member - find prev member of a set
    1141             :  *
    1142             :  * Returns largest member less than "prevbit", or -2 if there is none.
    1143             :  * "prevbit" must NOT be more than one above the highest possible bit that can
    1144             :  * be set at the Bitmapset at its current size.
    1145             :  *
    1146             :  * To ease finding the highest set bit for the initial loop, the special
    1147             :  * prevbit value of -1 can be passed to have the function find the highest
    1148             :  * valued member in the set.
    1149             :  *
    1150             :  * This is intended as support for iterating through the members of a set in
    1151             :  * reverse.  The typical pattern is
    1152             :  *
    1153             :  *          x = -1;
    1154             :  *          while ((x = bms_prev_member(inputset, x)) >= 0)
    1155             :  *              process member x;
    1156             :  *
    1157             :  * Notice that when there are no more members, we return -2, not -1 as you
    1158             :  * might expect.  The rationale for that is to allow distinguishing the
    1159             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1160             :  * It makes no difference in simple loop usage, but complex iteration logic
    1161             :  * might need such an ability.
    1162             :  */
    1163             : 
    1164             : int
    1165          18 : bms_prev_member(const Bitmapset *a, int prevbit)
    1166             : {
    1167             :     int         wordnum;
    1168             :     int         ushiftbits;
    1169             :     bitmapword  mask;
    1170             : 
    1171             :     /*
    1172             :      * If set is NULL or if there are no more bits to the right then we've
    1173             :      * nothing to do.
    1174             :      */
    1175          18 :     if (a == NULL || prevbit == 0)
    1176           0 :         return -2;
    1177             : 
    1178             :     /* transform -1 to the highest possible bit we could have set */
    1179          18 :     if (prevbit == -1)
    1180           0 :         prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
    1181             :     else
    1182          18 :         prevbit--;
    1183             : 
    1184          18 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
    1185          18 :     mask = (~(bitmapword) 0) >> ushiftbits;
    1186          24 :     for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
    1187             :     {
    1188          18 :         bitmapword  w = a->words[wordnum];
    1189             : 
    1190             :         /* mask out bits left of prevbit */
    1191          18 :         w &= mask;
    1192             : 
    1193          18 :         if (w != 0)
    1194             :         {
    1195             :             int         result;
    1196             : 
    1197          12 :             result = wordnum * BITS_PER_BITMAPWORD;
    1198          12 :             result += bmw_leftmost_one_pos(w);
    1199          12 :             return result;
    1200             :         }
    1201             : 
    1202             :         /* in subsequent words, consider all bits */
    1203           6 :         mask = (~(bitmapword) 0);
    1204             :     }
    1205           6 :     return -2;
    1206             : }
    1207             : 
    1208             : /*
    1209             :  * bms_hash_value - compute a hash key for a Bitmapset
    1210             :  */
    1211             : uint32
    1212        5298 : bms_hash_value(const Bitmapset *a)
    1213             : {
    1214        5298 :     if (a == NULL)
    1215           0 :         return 0;               /* All empty sets hash to 0 */
    1216        5298 :     return DatumGetUInt32(hash_any((const unsigned char *) a->words,
    1217        5298 :                                    a->nwords * sizeof(bitmapword)));
    1218             : }
    1219             : 
    1220             : /*
    1221             :  * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
    1222             :  *
    1223             :  * Note: don't forget to specify bitmap_match as the match function!
    1224             :  */
    1225             : uint32
    1226        5298 : bitmap_hash(const void *key, Size keysize)
    1227             : {
    1228             :     Assert(keysize == sizeof(Bitmapset *));
    1229        5298 :     return bms_hash_value(*((const Bitmapset *const *) key));
    1230             : }
    1231             : 
    1232             : /*
    1233             :  * bitmap_match - match function to use with bitmap_hash
    1234             :  */
    1235             : int
    1236        3204 : bitmap_match(const void *key1, const void *key2, Size keysize)
    1237             : {
    1238             :     Assert(keysize == sizeof(Bitmapset *));
    1239        3204 :     return !bms_equal(*((const Bitmapset *const *) key1),
    1240             :                       *((const Bitmapset *const *) key2));
    1241             : }

Generated by: LCOV version 1.14