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

Generated by: LCOV version 1.13