LCOV - code coverage report
Current view: top level - src/backend/nodes - bitmapset.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 359 429 83.7 %
Date: 2021-12-09 03:08:47 Functions: 33 33 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-2021, PostgreSQL Global Development Group
      15             :  *
      16             :  * IDENTIFICATION
      17             :  *    src/backend/nodes/bitmapset.c
      18             :  *
      19             :  *-------------------------------------------------------------------------
      20             :  */
      21             : #include "postgres.h"
      22             : 
      23             : #include "common/hashfn.h"
      24             : #include "nodes/bitmapset.h"
      25             : #include "nodes/pg_list.h"
      26             : #include "port/pg_bitutils.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    20207458 : bms_copy(const Bitmapset *a)
      75             : {
      76             :     Bitmapset  *result;
      77             :     size_t      size;
      78             : 
      79    20207458 :     if (a == NULL)
      80    12200358 :         return NULL;
      81     8007100 :     size = BITMAPSET_SIZE(a->nwords);
      82     8007100 :     result = (Bitmapset *) palloc(size);
      83     8007100 :     memcpy(result, a, size);
      84     8007100 :     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     6598638 : 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     6598638 :     if (a == NULL)
     104             :     {
     105     4409402 :         if (b == NULL)
     106     4395192 :             return true;
     107       14210 :         return bms_is_empty(b);
     108             :     }
     109     2189236 :     else if (b == NULL)
     110        7766 :         return bms_is_empty(a);
     111             :     /* Identify shorter and longer input */
     112     2181470 :     if (a->nwords <= b->nwords)
     113             :     {
     114     2181470 :         shorter = a;
     115     2181470 :         longer = b;
     116             :     }
     117             :     else
     118             :     {
     119           0 :         shorter = b;
     120           0 :         longer = a;
     121             :     }
     122             :     /* And process */
     123     2181470 :     shortlen = shorter->nwords;
     124     3181236 :     for (i = 0; i < shortlen; i++)
     125             :     {
     126     2181742 :         if (shorter->words[i] != longer->words[i])
     127     1181976 :             return false;
     128             :     }
     129      999494 :     longlen = longer->nwords;
     130      999494 :     for (; i < longlen; i++)
     131             :     {
     132           0 :         if (longer->words[i] != 0)
     133           0 :             return false;
     134             :     }
     135      999494 :     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       12626 : 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       12626 :     if (a == NULL)
     154           0 :         return bms_is_empty(b) ? 0 : -1;
     155       12626 :     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       12626 :     shortlen = Min(a->nwords, b->nwords);
     159       12626 :     for (i = shortlen; i < a->nwords; i++)
     160             :     {
     161           0 :         if (a->words[i] != 0)
     162           0 :             return +1;
     163             :     }
     164       12626 :     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       12626 :     i = shortlen;
     171       12626 :     while (--i >= 0)
     172             :     {
     173       12626 :         bitmapword  aw = a->words[i];
     174       12626 :         bitmapword  bw = b->words[i];
     175             : 
     176       12626 :         if (aw != bw)
     177       12626 :             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     7527994 : bms_make_singleton(int x)
     187             : {
     188             :     Bitmapset  *result;
     189             :     int         wordnum,
     190             :                 bitnum;
     191             : 
     192     7527994 :     if (x < 0)
     193           0 :         elog(ERROR, "negative bitmapset member not allowed");
     194     7527994 :     wordnum = WORDNUM(x);
     195     7527994 :     bitnum = BITNUM(x);
     196     7527994 :     result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
     197     7527994 :     result->nwords = wordnum + 1;
     198     7527994 :     result->words[wordnum] = ((bitmapword) 1 << bitnum);
     199     7527994 :     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    12751320 : bms_free(Bitmapset *a)
     209             : {
     210    12751320 :     if (a)
     211     5680930 :         pfree(a);
     212    12751320 : }
     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     3144528 : 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     3144528 :     if (a == NULL)
     234     1798564 :         return bms_copy(b);
     235     1345964 :     if (b == NULL)
     236      639366 :         return bms_copy(a);
     237             :     /* Identify shorter and longer input; copy the longer one */
     238      706598 :     if (a->nwords <= b->nwords)
     239             :     {
     240      706598 :         result = bms_copy(b);
     241      706598 :         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      706598 :     otherlen = other->nwords;
     250     1413196 :     for (i = 0; i < otherlen; i++)
     251      706598 :         result->words[i] |= other->words[i];
     252      706598 :     return result;
     253             : }
     254             : 
     255             : /*
     256             :  * bms_intersect - set intersection
     257             :  */
     258             : Bitmapset *
     259     1146640 : 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     1146640 :     if (a == NULL || b == NULL)
     268      554076 :         return NULL;
     269             :     /* Identify shorter and longer input; copy the shorter one */
     270      592564 :     if (a->nwords <= b->nwords)
     271             :     {
     272      592564 :         result = bms_copy(a);
     273      592564 :         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      592564 :     resultlen = result->nwords;
     282     1185128 :     for (i = 0; i < resultlen; i++)
     283      592564 :         result->words[i] &= other->words[i];
     284      592564 :     return result;
     285             : }
     286             : 
     287             : /*
     288             :  * bms_difference - set difference (ie, A without members of B)
     289             :  */
     290             : Bitmapset *
     291       54838 : 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       54838 :     if (a == NULL)
     299         342 :         return NULL;
     300       54496 :     if (b == NULL)
     301           0 :         return bms_copy(a);
     302             :     /* Copy the left input */
     303       54496 :     result = bms_copy(a);
     304             :     /* And remove b's bits from result */
     305       54496 :     shortlen = Min(a->nwords, b->nwords);
     306      108992 :     for (i = 0; i < shortlen; i++)
     307       54496 :         result->words[i] &= ~b->words[i];
     308       54496 :     return result;
     309             : }
     310             : 
     311             : /*
     312             :  * bms_is_subset - is A a subset of B?
     313             :  */
     314             : bool
     315     7958146 : 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     7958146 :     if (a == NULL)
     323      616058 :         return true;            /* empty set is a subset of anything */
     324     7342088 :     if (b == NULL)
     325      204950 :         return bms_is_empty(a);
     326             :     /* Check common words */
     327     7137138 :     shortlen = Min(a->nwords, b->nwords);
     328    11390840 :     for (i = 0; i < shortlen; i++)
     329             :     {
     330     7137138 :         if ((a->words[i] & ~b->words[i]) != 0)
     331     2883436 :             return false;
     332             :     }
     333             :     /* Check extra words */
     334     4253702 :     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     4253702 :     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     1027296 : 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     1027296 :     if (a == NULL)
     361             :     {
     362      871960 :         if (b == NULL)
     363      851324 :             return BMS_EQUAL;
     364       20636 :         return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
     365             :     }
     366      155336 :     if (b == NULL)
     367       75364 :         return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
     368             :     /* Check common words */
     369       79972 :     result = BMS_EQUAL;         /* status so far */
     370       79972 :     shortlen = Min(a->nwords, b->nwords);
     371      140672 :     for (i = 0; i < shortlen; i++)
     372             :     {
     373       79972 :         bitmapword  aword = a->words[i];
     374       79972 :         bitmapword  bword = b->words[i];
     375             : 
     376       79972 :         if ((aword & ~bword) != 0)
     377             :         {
     378             :             /* a is not a subset of b */
     379       20786 :             if (result == BMS_SUBSET1)
     380           0 :                 return BMS_DIFFERENT;
     381       20786 :             result = BMS_SUBSET2;
     382             :         }
     383       79972 :         if ((bword & ~aword) != 0)
     384             :         {
     385             :             /* b is not a subset of a */
     386       20932 :             if (result == BMS_SUBSET2)
     387       19272 :                 return BMS_DIFFERENT;
     388        1660 :             result = BMS_SUBSET1;
     389             :         }
     390             :     }
     391             :     /* Check extra words */
     392       60700 :     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       60700 :     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       60700 :     return result;
     421             : }
     422             : 
     423             : /*
     424             :  * bms_is_member - is X a member of A?
     425             :  */
     426             : bool
     427    10055524 : 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    10055524 :     if (x < 0)
     434           0 :         elog(ERROR, "negative bitmapset member not allowed");
     435    10055524 :     if (a == NULL)
     436     6570280 :         return false;
     437     3485244 :     wordnum = WORDNUM(x);
     438     3485244 :     bitnum = BITNUM(x);
     439     3485244 :     if (wordnum >= a->nwords)
     440         176 :         return false;
     441     3485068 :     if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     442     1860304 :         return true;
     443     1624764 :     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        2720 : bms_member_index(Bitmapset *a, int x)
     454             : {
     455             :     int         i;
     456             :     int         bitnum;
     457             :     int         wordnum;
     458        2720 :     int         result = 0;
     459             :     bitmapword  mask;
     460             : 
     461             :     /* return -1 if not a member of the bitmap */
     462        2720 :     if (!bms_is_member(x, a))
     463           0 :         return -1;
     464             : 
     465        2720 :     wordnum = WORDNUM(x);
     466        2720 :     bitnum = BITNUM(x);
     467             : 
     468             :     /* count bits in preceding words */
     469        2720 :     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        2720 :     mask = ((bitmapword) 1 << bitnum) - 1;
     485        2720 :     result += bmw_popcount(a->words[wordnum] & mask);
     486             : 
     487        2720 :     return result;
     488             : }
     489             : 
     490             : /*
     491             :  * bms_overlap - do sets overlap (ie, have a nonempty intersection)?
     492             :  */
     493             : bool
     494     6489526 : 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     6489526 :     if (a == NULL || b == NULL)
     501     3115196 :         return false;
     502             :     /* Check words in common */
     503     3374330 :     shortlen = Min(a->nwords, b->nwords);
     504     4604652 :     for (i = 0; i < shortlen; i++)
     505             :     {
     506     3374330 :         if ((a->words[i] & b->words[i]) != 0)
     507     2144008 :             return true;
     508             :     }
     509     1230322 :     return false;
     510             : }
     511             : 
     512             : /*
     513             :  * bms_overlap_list - does a set overlap an integer list?
     514             :  */
     515             : bool
     516         872 : bms_overlap_list(const Bitmapset *a, const List *b)
     517             : {
     518             :     ListCell   *lc;
     519             :     int         wordnum,
     520             :                 bitnum;
     521             : 
     522         872 :     if (a == NULL || b == NIL)
     523         780 :         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             :  * i.e., are any members set in 'a' that are not also set in 'b'.
     545             :  */
     546             : bool
     547      949784 : bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
     548             : {
     549             :     int         shortlen;
     550             :     int         i;
     551             : 
     552             :     /* Handle cases where either input is NULL */
     553      949784 :     if (a == NULL)
     554          48 :         return false;
     555      949736 :     if (b == NULL)
     556           0 :         return !bms_is_empty(a);
     557             :     /* Check words in common */
     558      949736 :     shortlen = Min(a->nwords, b->nwords);
     559     1392518 :     for (i = 0; i < shortlen; i++)
     560             :     {
     561      949736 :         if ((a->words[i] & ~b->words[i]) != 0)
     562      506954 :             return true;
     563             :     }
     564             :     /* Check extra words in a */
     565      442782 :     for (; i < a->nwords; i++)
     566             :     {
     567           0 :         if (a->words[i] != 0)
     568           0 :             return true;
     569             :     }
     570      442782 :     return false;
     571             : }
     572             : 
     573             : /*
     574             :  * bms_singleton_member - return the sole integer member of set
     575             :  *
     576             :  * Raises error if |a| is not 1.
     577             :  */
     578             : int
     579      258854 : bms_singleton_member(const Bitmapset *a)
     580             : {
     581      258854 :     int         result = -1;
     582             :     int         nwords;
     583             :     int         wordnum;
     584             : 
     585      258854 :     if (a == NULL)
     586           0 :         elog(ERROR, "bitmapset is empty");
     587      258854 :     nwords = a->nwords;
     588      517708 :     for (wordnum = 0; wordnum < nwords; wordnum++)
     589             :     {
     590      258854 :         bitmapword  w = a->words[wordnum];
     591             : 
     592      258854 :         if (w != 0)
     593             :         {
     594      258854 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     595           0 :                 elog(ERROR, "bitmapset has multiple members");
     596      258854 :             result = wordnum * BITS_PER_BITMAPWORD;
     597      258854 :             result += bmw_rightmost_one_pos(w);
     598             :         }
     599             :     }
     600      258854 :     if (result < 0)
     601           0 :         elog(ERROR, "bitmapset is empty");
     602      258854 :     return result;
     603             : }
     604             : 
     605             : /*
     606             :  * bms_get_singleton_member
     607             :  *
     608             :  * Test whether the given set is a singleton.
     609             :  * If so, set *member to the value of its sole member, and return true.
     610             :  * If not, return false, without changing *member.
     611             :  *
     612             :  * This is more convenient and faster than calling bms_membership() and then
     613             :  * bms_singleton_member(), if we don't care about distinguishing empty sets
     614             :  * from multiple-member sets.
     615             :  */
     616             : bool
     617      659038 : bms_get_singleton_member(const Bitmapset *a, int *member)
     618             : {
     619      659038 :     int         result = -1;
     620             :     int         nwords;
     621             :     int         wordnum;
     622             : 
     623      659038 :     if (a == NULL)
     624          16 :         return false;
     625      659022 :     nwords = a->nwords;
     626     1152684 :     for (wordnum = 0; wordnum < nwords; wordnum++)
     627             :     {
     628      659022 :         bitmapword  w = a->words[wordnum];
     629             : 
     630      659022 :         if (w != 0)
     631             :         {
     632      659022 :             if (result >= 0 || HAS_MULTIPLE_ONES(w))
     633      165360 :                 return false;
     634      493662 :             result = wordnum * BITS_PER_BITMAPWORD;
     635      493662 :             result += bmw_rightmost_one_pos(w);
     636             :         }
     637             :     }
     638      493662 :     if (result < 0)
     639           0 :         return false;
     640      493662 :     *member = result;
     641      493662 :     return true;
     642             : }
     643             : 
     644             : /*
     645             :  * bms_num_members - count members of set
     646             :  */
     647             : int
     648      537536 : bms_num_members(const Bitmapset *a)
     649             : {
     650      537536 :     int         result = 0;
     651             :     int         nwords;
     652             :     int         wordnum;
     653             : 
     654      537536 :     if (a == NULL)
     655       78100 :         return 0;
     656      459436 :     nwords = a->nwords;
     657      918872 :     for (wordnum = 0; wordnum < nwords; wordnum++)
     658             :     {
     659      459436 :         bitmapword  w = a->words[wordnum];
     660             : 
     661             :         /* No need to count the bits in a zero word */
     662      459436 :         if (w != 0)
     663      459436 :             result += bmw_popcount(w);
     664             :     }
     665      459436 :     return result;
     666             : }
     667             : 
     668             : /*
     669             :  * bms_membership - does a set have zero, one, or multiple members?
     670             :  *
     671             :  * This is faster than making an exact count with bms_num_members().
     672             :  */
     673             : BMS_Membership
     674     2461854 : bms_membership(const Bitmapset *a)
     675             : {
     676     2461854 :     BMS_Membership result = BMS_EMPTY_SET;
     677             :     int         nwords;
     678             :     int         wordnum;
     679             : 
     680     2461854 :     if (a == NULL)
     681      223832 :         return BMS_EMPTY_SET;
     682     2238022 :     nwords = a->nwords;
     683     3861732 :     for (wordnum = 0; wordnum < nwords; wordnum++)
     684             :     {
     685     2238022 :         bitmapword  w = a->words[wordnum];
     686             : 
     687     2238022 :         if (w != 0)
     688             :         {
     689     2238022 :             if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
     690      614312 :                 return BMS_MULTIPLE;
     691     1623710 :             result = BMS_SINGLETON;
     692             :         }
     693             :     }
     694     1623710 :     return result;
     695             : }
     696             : 
     697             : /*
     698             :  * bms_is_empty - is a set empty?
     699             :  *
     700             :  * This is even faster than bms_membership().
     701             :  */
     702             : bool
     703     9682006 : bms_is_empty(const Bitmapset *a)
     704             : {
     705             :     int         nwords;
     706             :     int         wordnum;
     707             : 
     708     9682006 :     if (a == NULL)
     709     6138402 :         return true;
     710     3543604 :     nwords = a->nwords;
     711     4151322 :     for (wordnum = 0; wordnum < nwords; wordnum++)
     712             :     {
     713     3543676 :         bitmapword  w = a->words[wordnum];
     714             : 
     715     3543676 :         if (w != 0)
     716     2935958 :             return false;
     717             :     }
     718      607646 :     return true;
     719             : }
     720             : 
     721             : 
     722             : /*
     723             :  * These operations all "recycle" their non-const inputs, ie, either
     724             :  * return the modified input or pfree it if it can't hold the result.
     725             :  *
     726             :  * These should generally be used in the style
     727             :  *
     728             :  *      foo = bms_add_member(foo, x);
     729             :  */
     730             : 
     731             : 
     732             : /*
     733             :  * bms_add_member - add a specified member to set
     734             :  *
     735             :  * Input set is modified or recycled!
     736             :  */
     737             : Bitmapset *
     738    12038268 : bms_add_member(Bitmapset *a, int x)
     739             : {
     740             :     int         wordnum,
     741             :                 bitnum;
     742             : 
     743    12038268 :     if (x < 0)
     744           0 :         elog(ERROR, "negative bitmapset member not allowed");
     745    12038268 :     if (a == NULL)
     746     6244352 :         return bms_make_singleton(x);
     747     5793916 :     wordnum = WORDNUM(x);
     748     5793916 :     bitnum = BITNUM(x);
     749             : 
     750             :     /* enlarge the set if necessary */
     751     5793916 :     if (wordnum >= a->nwords)
     752             :     {
     753         112 :         int         oldnwords = a->nwords;
     754             :         int         i;
     755             : 
     756         112 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
     757         112 :         a->nwords = wordnum + 1;
     758             :         /* zero out the enlarged portion */
     759         672 :         for (i = oldnwords; i < a->nwords; i++)
     760         560 :             a->words[i] = 0;
     761             :     }
     762             : 
     763     5793916 :     a->words[wordnum] |= ((bitmapword) 1 << bitnum);
     764     5793916 :     return a;
     765             : }
     766             : 
     767             : /*
     768             :  * bms_del_member - remove a specified member from set
     769             :  *
     770             :  * No error if x is not currently a member of set
     771             :  *
     772             :  * Input set is modified in-place!
     773             :  */
     774             : Bitmapset *
     775     1000670 : bms_del_member(Bitmapset *a, int x)
     776             : {
     777             :     int         wordnum,
     778             :                 bitnum;
     779             : 
     780     1000670 :     if (x < 0)
     781           0 :         elog(ERROR, "negative bitmapset member not allowed");
     782     1000670 :     if (a == NULL)
     783      533714 :         return NULL;
     784      466956 :     wordnum = WORDNUM(x);
     785      466956 :     bitnum = BITNUM(x);
     786      466956 :     if (wordnum < a->nwords)
     787      466956 :         a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
     788      466956 :     return a;
     789             : }
     790             : 
     791             : /*
     792             :  * bms_add_members - like bms_union, but left input is recycled
     793             :  */
     794             : Bitmapset *
     795     5751684 : bms_add_members(Bitmapset *a, const Bitmapset *b)
     796             : {
     797             :     Bitmapset  *result;
     798             :     const Bitmapset *other;
     799             :     int         otherlen;
     800             :     int         i;
     801             : 
     802             :     /* Handle cases where either input is NULL */
     803     5751684 :     if (a == NULL)
     804     3500434 :         return bms_copy(b);
     805     2251250 :     if (b == NULL)
     806      888514 :         return a;
     807             :     /* Identify shorter and longer input; copy the longer one if needed */
     808     1362736 :     if (a->nwords < b->nwords)
     809             :     {
     810           0 :         result = bms_copy(b);
     811           0 :         other = a;
     812             :     }
     813             :     else
     814             :     {
     815     1362736 :         result = a;
     816     1362736 :         other = b;
     817             :     }
     818             :     /* And union the shorter input into the result */
     819     1362736 :     otherlen = other->nwords;
     820     2725472 :     for (i = 0; i < otherlen; i++)
     821     1362736 :         result->words[i] |= other->words[i];
     822     1362736 :     if (result != a)
     823           0 :         pfree(a);
     824     1362736 :     return result;
     825             : }
     826             : 
     827             : /*
     828             :  * bms_add_range
     829             :  *      Add members in the range of 'lower' to 'upper' to the set.
     830             :  *
     831             :  * Note this could also be done by calling bms_add_member in a loop, however,
     832             :  * using this function will be faster when the range is large as we work at
     833             :  * the bitmapword level rather than at bit level.
     834             :  */
     835             : Bitmapset *
     836       16290 : bms_add_range(Bitmapset *a, int lower, int upper)
     837             : {
     838             :     int         lwordnum,
     839             :                 lbitnum,
     840             :                 uwordnum,
     841             :                 ushiftbits,
     842             :                 wordnum;
     843             : 
     844             :     /* do nothing if nothing is called for, without further checking */
     845       16290 :     if (upper < lower)
     846          16 :         return a;
     847             : 
     848       16274 :     if (lower < 0)
     849           0 :         elog(ERROR, "negative bitmapset member not allowed");
     850       16274 :     uwordnum = WORDNUM(upper);
     851             : 
     852       16274 :     if (a == NULL)
     853             :     {
     854       16274 :         a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1));
     855       16274 :         a->nwords = uwordnum + 1;
     856             :     }
     857           0 :     else if (uwordnum >= a->nwords)
     858             :     {
     859           0 :         int         oldnwords = a->nwords;
     860             :         int         i;
     861             : 
     862             :         /* ensure we have enough words to store the upper bit */
     863           0 :         a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
     864           0 :         a->nwords = uwordnum + 1;
     865             :         /* zero out the enlarged portion */
     866           0 :         for (i = oldnwords; i < a->nwords; i++)
     867           0 :             a->words[i] = 0;
     868             :     }
     869             : 
     870       16274 :     wordnum = lwordnum = WORDNUM(lower);
     871             : 
     872       16274 :     lbitnum = BITNUM(lower);
     873       16274 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
     874             : 
     875             :     /*
     876             :      * Special case when lwordnum is the same as uwordnum we must perform the
     877             :      * upper and lower masking on the word.
     878             :      */
     879       16274 :     if (lwordnum == uwordnum)
     880             :     {
     881       16274 :         a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
     882       16274 :             & (~(bitmapword) 0) >> ushiftbits;
     883             :     }
     884             :     else
     885             :     {
     886             :         /* turn on lbitnum and all bits left of it */
     887           0 :         a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1);
     888             : 
     889             :         /* turn on all bits for any intermediate words */
     890           0 :         while (wordnum < uwordnum)
     891           0 :             a->words[wordnum++] = ~(bitmapword) 0;
     892             : 
     893             :         /* turn on upper's bit and all bits right of it. */
     894           0 :         a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
     895             :     }
     896             : 
     897       16274 :     return a;
     898             : }
     899             : 
     900             : /*
     901             :  * bms_int_members - like bms_intersect, but left input is recycled
     902             :  */
     903             : Bitmapset *
     904      379968 : bms_int_members(Bitmapset *a, const Bitmapset *b)
     905             : {
     906             :     int         shortlen;
     907             :     int         i;
     908             : 
     909             :     /* Handle cases where either input is NULL */
     910      379968 :     if (a == NULL)
     911       77710 :         return NULL;
     912      302258 :     if (b == NULL)
     913             :     {
     914        1822 :         pfree(a);
     915        1822 :         return NULL;
     916             :     }
     917             :     /* Intersect b into a; we need never copy */
     918      300436 :     shortlen = Min(a->nwords, b->nwords);
     919      600872 :     for (i = 0; i < shortlen; i++)
     920      300436 :         a->words[i] &= b->words[i];
     921      300436 :     for (; i < a->nwords; i++)
     922           0 :         a->words[i] = 0;
     923      300436 :     return a;
     924             : }
     925             : 
     926             : /*
     927             :  * bms_del_members - like bms_difference, but left input is recycled
     928             :  */
     929             : Bitmapset *
     930     1359146 : bms_del_members(Bitmapset *a, const Bitmapset *b)
     931             : {
     932             :     int         shortlen;
     933             :     int         i;
     934             : 
     935             :     /* Handle cases where either input is NULL */
     936     1359146 :     if (a == NULL)
     937      366528 :         return NULL;
     938      992618 :     if (b == NULL)
     939      561922 :         return a;
     940             :     /* Remove b's bits from a; we need never copy */
     941      430696 :     shortlen = Min(a->nwords, b->nwords);
     942      861392 :     for (i = 0; i < shortlen; i++)
     943      430696 :         a->words[i] &= ~b->words[i];
     944      430696 :     return a;
     945             : }
     946             : 
     947             : /*
     948             :  * bms_join - like bms_union, but *both* inputs are recycled
     949             :  */
     950             : Bitmapset *
     951      860786 : bms_join(Bitmapset *a, Bitmapset *b)
     952             : {
     953             :     Bitmapset  *result;
     954             :     Bitmapset  *other;
     955             :     int         otherlen;
     956             :     int         i;
     957             : 
     958             :     /* Handle cases where either input is NULL */
     959      860786 :     if (a == NULL)
     960      479378 :         return b;
     961      381408 :     if (b == NULL)
     962       35084 :         return a;
     963             :     /* Identify shorter and longer input; use longer one as result */
     964      346324 :     if (a->nwords < b->nwords)
     965             :     {
     966           0 :         result = b;
     967           0 :         other = a;
     968             :     }
     969             :     else
     970             :     {
     971      346324 :         result = a;
     972      346324 :         other = b;
     973             :     }
     974             :     /* And union the shorter input into the result */
     975      346324 :     otherlen = other->nwords;
     976      692648 :     for (i = 0; i < otherlen; i++)
     977      346324 :         result->words[i] |= other->words[i];
     978      346324 :     if (other != result)        /* pure paranoia */
     979      346324 :         pfree(other);
     980      346324 :     return result;
     981             : }
     982             : 
     983             : /*
     984             :  * bms_first_member - find and remove first member of a set
     985             :  *
     986             :  * Returns -1 if set is empty.  NB: set is destructively modified!
     987             :  *
     988             :  * This is intended as support for iterating through the members of a set.
     989             :  * The typical pattern is
     990             :  *
     991             :  *          while ((x = bms_first_member(inputset)) >= 0)
     992             :  *              process member x;
     993             :  *
     994             :  * CAUTION: this destroys the content of "inputset".  If the set must
     995             :  * not be modified, use bms_next_member instead.
     996             :  */
     997             : int
     998     2398652 : bms_first_member(Bitmapset *a)
     999             : {
    1000             :     int         nwords;
    1001             :     int         wordnum;
    1002             : 
    1003     2398652 :     if (a == NULL)
    1004       52198 :         return -1;
    1005     2346454 :     nwords = a->nwords;
    1006     2897456 :     for (wordnum = 0; wordnum < nwords; wordnum++)
    1007             :     {
    1008     2346454 :         bitmapword  w = a->words[wordnum];
    1009             : 
    1010     2346454 :         if (w != 0)
    1011             :         {
    1012             :             int         result;
    1013             : 
    1014     1795452 :             w = RIGHTMOST_ONE(w);
    1015     1795452 :             a->words[wordnum] &= ~w;
    1016             : 
    1017     1795452 :             result = wordnum * BITS_PER_BITMAPWORD;
    1018     1795452 :             result += bmw_rightmost_one_pos(w);
    1019     1795452 :             return result;
    1020             :         }
    1021             :     }
    1022      551002 :     return -1;
    1023             : }
    1024             : 
    1025             : /*
    1026             :  * bms_next_member - find next member of a set
    1027             :  *
    1028             :  * Returns smallest member greater than "prevbit", or -2 if there is none.
    1029             :  * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
    1030             :  *
    1031             :  * This is intended as support for iterating through the members of a set.
    1032             :  * The typical pattern is
    1033             :  *
    1034             :  *          x = -1;
    1035             :  *          while ((x = bms_next_member(inputset, x)) >= 0)
    1036             :  *              process member x;
    1037             :  *
    1038             :  * Notice that when there are no more members, we return -2, not -1 as you
    1039             :  * might expect.  The rationale for that is to allow distinguishing the
    1040             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1041             :  * It makes no difference in simple loop usage, but complex iteration logic
    1042             :  * might need such an ability.
    1043             :  */
    1044             : int
    1045    16028040 : bms_next_member(const Bitmapset *a, int prevbit)
    1046             : {
    1047             :     int         nwords;
    1048             :     int         wordnum;
    1049             :     bitmapword  mask;
    1050             : 
    1051    16028040 :     if (a == NULL)
    1052     6658522 :         return -2;
    1053     9369518 :     nwords = a->nwords;
    1054     9369518 :     prevbit++;
    1055     9369518 :     mask = (~(bitmapword) 0) << BITNUM(prevbit);
    1056    12348630 :     for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
    1057             :     {
    1058     9369790 :         bitmapword  w = a->words[wordnum];
    1059             : 
    1060             :         /* ignore bits before prevbit */
    1061     9369790 :         w &= mask;
    1062             : 
    1063     9369790 :         if (w != 0)
    1064             :         {
    1065             :             int         result;
    1066             : 
    1067     6390678 :             result = wordnum * BITS_PER_BITMAPWORD;
    1068     6390678 :             result += bmw_rightmost_one_pos(w);
    1069     6390678 :             return result;
    1070             :         }
    1071             : 
    1072             :         /* in subsequent words, consider all bits */
    1073     2979112 :         mask = (~(bitmapword) 0);
    1074             :     }
    1075     2978840 :     return -2;
    1076             : }
    1077             : 
    1078             : /*
    1079             :  * bms_prev_member - find prev member of a set
    1080             :  *
    1081             :  * Returns largest member less than "prevbit", or -2 if there is none.
    1082             :  * "prevbit" must NOT be more than one above the highest possible bit that can
    1083             :  * be set at the Bitmapset at its current size.
    1084             :  *
    1085             :  * To ease finding the highest set bit for the initial loop, the special
    1086             :  * prevbit value of -1 can be passed to have the function find the highest
    1087             :  * valued member in the set.
    1088             :  *
    1089             :  * This is intended as support for iterating through the members of a set in
    1090             :  * reverse.  The typical pattern is
    1091             :  *
    1092             :  *          x = -1;
    1093             :  *          while ((x = bms_prev_member(inputset, x)) >= 0)
    1094             :  *              process member x;
    1095             :  *
    1096             :  * Notice that when there are no more members, we return -2, not -1 as you
    1097             :  * might expect.  The rationale for that is to allow distinguishing the
    1098             :  * loop-not-started state (x == -1) from the loop-completed state (x == -2).
    1099             :  * It makes no difference in simple loop usage, but complex iteration logic
    1100             :  * might need such an ability.
    1101             :  */
    1102             : 
    1103             : int
    1104          12 : bms_prev_member(const Bitmapset *a, int prevbit)
    1105             : {
    1106             :     int         wordnum;
    1107             :     int         ushiftbits;
    1108             :     bitmapword  mask;
    1109             : 
    1110             :     /*
    1111             :      * If set is NULL or if there are no more bits to the right then we've
    1112             :      * nothing to do.
    1113             :      */
    1114          12 :     if (a == NULL || prevbit == 0)
    1115           0 :         return -2;
    1116             : 
    1117             :     /* transform -1 to the highest possible bit we could have set */
    1118          12 :     if (prevbit == -1)
    1119           0 :         prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
    1120             :     else
    1121          12 :         prevbit--;
    1122             : 
    1123          12 :     ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
    1124          12 :     mask = (~(bitmapword) 0) >> ushiftbits;
    1125          16 :     for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
    1126             :     {
    1127          12 :         bitmapword  w = a->words[wordnum];
    1128             : 
    1129             :         /* mask out bits left of prevbit */
    1130          12 :         w &= mask;
    1131             : 
    1132          12 :         if (w != 0)
    1133             :         {
    1134             :             int         result;
    1135             : 
    1136           8 :             result = wordnum * BITS_PER_BITMAPWORD;
    1137           8 :             result += bmw_leftmost_one_pos(w);
    1138           8 :             return result;
    1139             :         }
    1140             : 
    1141             :         /* in subsequent words, consider all bits */
    1142           4 :         mask = (~(bitmapword) 0);
    1143             :     }
    1144           4 :     return -2;
    1145             : }
    1146             : 
    1147             : /*
    1148             :  * bms_hash_value - compute a hash key for a Bitmapset
    1149             :  *
    1150             :  * Note: we must ensure that any two bitmapsets that are bms_equal() will
    1151             :  * hash to the same value; in practice this means that trailing all-zero
    1152             :  * words must not affect the result.  Hence we strip those before applying
    1153             :  * hash_any().
    1154             :  */
    1155             : uint32
    1156        3232 : bms_hash_value(const Bitmapset *a)
    1157             : {
    1158             :     int         lastword;
    1159             : 
    1160        3232 :     if (a == NULL)
    1161           0 :         return 0;               /* All empty sets hash to 0 */
    1162        3232 :     for (lastword = a->nwords; --lastword >= 0;)
    1163             :     {
    1164        3232 :         if (a->words[lastword] != 0)
    1165        3232 :             break;
    1166             :     }
    1167        3232 :     if (lastword < 0)
    1168           0 :         return 0;               /* All empty sets hash to 0 */
    1169        3232 :     return DatumGetUInt32(hash_any((const unsigned char *) a->words,
    1170             :                                    (lastword + 1) * sizeof(bitmapword)));
    1171             : }
    1172             : 
    1173             : /*
    1174             :  * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets
    1175             :  *
    1176             :  * Note: don't forget to specify bitmap_match as the match function!
    1177             :  */
    1178             : uint32
    1179        3232 : bitmap_hash(const void *key, Size keysize)
    1180             : {
    1181             :     Assert(keysize == sizeof(Bitmapset *));
    1182        3232 :     return bms_hash_value(*((const Bitmapset *const *) key));
    1183             : }
    1184             : 
    1185             : /*
    1186             :  * bitmap_match - match function to use with bitmap_hash
    1187             :  */
    1188             : int
    1189        2052 : bitmap_match(const void *key1, const void *key2, Size keysize)
    1190             : {
    1191             :     Assert(keysize == sizeof(Bitmapset *));
    1192        2052 :     return !bms_equal(*((const Bitmapset *const *) key1),
    1193             :                       *((const Bitmapset *const *) key2));
    1194             : }

Generated by: LCOV version 1.14