LCOV - code coverage report
Current view: top level - util/tmpl - fd_set.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 209 209 100.0 %
Date: 2025-07-01 05:00:49 Functions: 87 10604 0.8 %

          Line data    Source code
       1             : /* Declare a bunch of functions for fast manipulation of index sets that
       2             :    can contain a large compile time bounded number of elements and that
       3             :    can be shared between processes.  The implementation is optimized for
       4             :    dense-ish sets with a largish maximum element contains (thousands+).
       5             :    Example:
       6             : 
       7             :      #define SET_NAME my_set
       8             :      #define SET_MAX  65536   ... Should be in [1,2^31-64]
       9             :      #include "util/tmpl/fd_set.c"
      10             : 
      11             :    Will implement and expose the following header only library in the
      12             :    local compilation unit:
      13             : 
      14             :      my_set_t // opaque handle type for the set
      15             : 
      16             :      // interprocess shared memory constructors / destructors
      17             :      // these obey the usual conventions
      18             : 
      19             :      ulong      my_set_align    ( void             ); // required byte alignment of a my_set_t
      20             :      ulong      my_set_footprint( void             ); // required byte footprint of a my_set_t
      21             :      void *     my_set_new      ( void     * shmem ); // format memory region into a my_set, my_set will be empty
      22             :                                                       // (caller not joined on return, mem has required align/footprint, etc)
      23             :      my_set_t * my_set_join     ( void     * shset ); // join a my_set_t (unlimited joins, etc)
      24             :      void *     my_set_leave    ( my_set_t *   set ); // leave a my_set_t (matched with join, etc)
      25             :      void *     my_set_delete   ( void     * shset ); // unformat memory (no active joins, etc)
      26             : 
      27             :      // it is also possible to do declaration based allocation via
      28             : 
      29             :      my_set_t set[ my_set_word_cnt ];
      30             : 
      31             :      // Returns 1 if set appears to be point to a valid set, 0 otherwise
      32             :      // (e.g. set is NULL, there's corruption in the set zero padding,
      33             :      // etc).
      34             : 
      35             :      int my_set_valid( my_set_t const * set )
      36             : 
      37             :      // Returns 1 if idx is a valid set element index (i.e. in [0,max)
      38             :      // (It is okay to pass NULL for set here as it is technically
      39             :      // ignored).
      40             : 
      41             :      int my_set_valid_idx( my_set_t const * set, ulong idx )
      42             : 
      43             :      // Return the maximum number of elements this set can contain.  Set
      44             :      // elements are indexed [0,max).  (It is okay to pass NULL for set
      45             :      // here as it is technically ignored.)
      46             : 
      47             :      ulong my_set_max( my_set_t const * set ); // Return positive
      48             : 
      49             :      // Return the current number of elements this set contains
      50             : 
      51             :      ulong my_set_cnt( my_set_t const * set ); // Return in [0,max]
      52             : 
      53             :      // Return 1 if set contains no elements and 0 if not
      54             : 
      55             :      int my_set_is_null( my_set_t const * set );
      56             : 
      57             :      // Return 1 if set contains all elements and 0 if not
      58             : 
      59             :      int my_set_is_full( my_set_t const * set );
      60             : 
      61             :      // Return the lowest indexed element in the set
      62             : 
      63             :      ulong my_set_first( my_set_t const * set ); // Return in [0,max) on success, >=max if empty set
      64             : 
      65             :      // Two pair of functions for writing efficient iterators over all
      66             :      // members of sparse sets.  The first pair is a destructive
      67             :      // iterator:
      68             :      //
      69             :      //   for( ulong idx=my_set_iter_init( set ); !my_set_iter_done( idx ); idx=my_set_iter_next( set, idx ) ) {
      70             :      //     ... idx is the next element of the set, will be in [0,max)
      71             :      //     ... set elements will be iterated over in increasing order
      72             :      //     ... do not modify set, modify idx; there are no elements
      73             :      //     ... in set before idx at this point
      74             :      //   }
      75             :      //   ... set will be empty at this point
      76             :      //
      77             :      // The second pair is a non-destructive iterator:
      78             :      //
      79             :      //   for( ulong idx=my_set_const_iter_init( set ); !my_set_const_iter_done( idx ); idx=my_set_const_iter_next( set, idx ) ) {
      80             :      //     ... idx is the next element of the set, will be in [0,max)
      81             :      //     ... set elements will be iterated over in increasing order
      82             :      //     ... do not modify set or modify idx; set is unchanged
      83             :      //     ... at this point
      84             :      //   }
      85             :      //   ... set is unchanged at this point
      86             :      //
      87             :      // The performance difference between the two styles are situation
      88             :      // dependent (depends on the sizes of the set, cache conditions,
      89             :      // distribution of elements in the set, etc) but not expected to be
      90             :      // large.  In general though, the above iterators are best for very
      91             :      // sparse sets.  For dense sets, the idiom:
      92             :      //
      93             :      //   ulong max = my_set_max( set );
      94             :      //   for( ulong idx=0UL; idx<max; idx++ ) {
      95             :      //     if( !my_set_test( set, idx ) ) continue;
      96             :      //     ... idx is the next element of the set, will be in [0,max)
      97             :      //     ... set elements will be iterated over in increasing order
      98             :      //     ... do not modify set or modify idx; set is unchanged
      99             :      //     ... at this point
     100             :      //   }
     101             :      //   ... set is unchanged at this point
     102             :      //
     103             :      // or is more predictable branchless speculative variant:
     104             :      //
     105             :      //   ulong max = my_set_max( set );
     106             :      //   for( ulong idx=0UL; idx<max; idx++ ) {
     107             :      //     ... speculate idx is in the set, will be in [0,max)
     108             :      //     ... set elements will be iterated over in increasing order
     109             :      //     ... do not modify set or modify idx; set is unchanged
     110             :      //     ... at this point
     111             :      //     ... commit speculation when my_set_test( set, idx ) is true
     112             :      //   }
     113             :      //   ... set is unchanged at this point
     114             :      //
     115             :      // might be preferable.
     116             : 
     117             :      ulong my_set_iter_init( my_set_t * set );
     118             :      int   my_set_iter_done( ulong idx );
     119             :      ulong my_set_iter_next( my_set_t * set, ulong idx );
     120             : 
     121             :      ulong my_set_const_iter_init( my_set_t const * set );
     122             :      int   my_set_const_iter_done( ulong idx );
     123             :      ulong my_set_const_iter_next( my_set_t const * set, ulong idx );
     124             : 
     125             :      // Insert/remove element idx to a set if not already present (no-op
     126             :      // otherwise).  Returns set.
     127             : 
     128             :      my_set_t * my_set_insert( my_set_t * set, ulong idx ); // in [0,max).
     129             :      my_set_t * my_set_remove( my_set_t * set, ulong idx ); // in [0,max).
     130             : 
     131             :      // Fast version of "c ? my_set_{insert,remove}( set, idx ) : set".
     132             : 
     133             :      my_set_t * my_set_insert_if( my_set_t * set, int c, ulong idx ); // in [0,max).
     134             :      my_set_t * my_set_remove_if( my_set_t * set, int c, ulong idx ); // in [0,max).
     135             : 
     136             :      // Return 1 if idx is in set and 0 otherwise
     137             : 
     138             :      int my_set_test( my_set_t const * set, ulong idx ); // in [0,max).
     139             : 
     140             :      // Returns 1 if x and y contain the same elements, 0 otherwise.  In
     141             :      // place is fine.
     142             : 
     143             :      int my_set_eq( my_set_t const * x, my_set_t const * y );
     144             : 
     145             :      // Returns 1 if x is a subset of y (including x==y), 0 otherwise.
     146             :      // In place is fine.
     147             : 
     148             :      int my_set_subset( my_set_t const * x, my_set_t const * y );
     149             : 
     150             :      // Operations that populate an output set.  All of these return z
     151             :      // and inplace operation is fine.
     152             : 
     153             :      my_set_t * my_set_null      ( my_set_t * z );                                                // z =  {}
     154             :      my_set_t * my_set_full      ( my_set_t * z );                                                // z = ~{}
     155             :      my_set_t * my_set_full_if   ( my_set_t * z, int c );                                         // z = c ? {idx} : {}
     156             :      my_set_t * my_set_ele       ( my_set_t * z, ulong idx );                                     // z = {idx}
     157             :      my_set_t * my_set_ele_if    ( my_set_t * z, int c, ulong idx );                              // z = c ? {idx} : {}
     158             :      my_set_t * my_set_copy      ( my_set_t * z, my_set_t const * x );                            // z = x
     159             :      my_set_t * my_set_complement( my_set_t * z, my_set_t const * x );                            // z = ~x
     160             :      my_set_t * my_set_union     ( my_set_t * z, my_set_t const * x, my_set_t const * y );        // z = x u y
     161             :      my_set_t * my_set_intersect ( my_set_t * z, my_set_t const * x, my_set_t const * y );        // z = x n y
     162             :      my_set_t * my_set_subtract  ( my_set_t * z, my_set_t const * x, my_set_t const * y );        // z = x - y
     163             :      my_set_t * my_set_xor       ( my_set_t * z, my_set_t const * x, my_set_t const * y );        // z = (x u y) - (x n y)
     164             :      my_set_t * my_set_if        ( my_set_t * z, int c, my_set_t const * x, my_set_t const * y ); // z = c ? x : y
     165             : 
     166             :      // Range APIs do fast operations for a contiguous range within a
     167             :      // my_set.  Ranges are specified on the half-open interval [l,h).
     168             :      // These all assume 0<=l<=h<=max.
     169             : 
     170             :      my_set_t * my_set_range( my_set_t * z, ulong l, ulong h );        // z = r where r is the set with elements [l,h), fast O(max)
     171             : 
     172             :      my_set_t * my_set_insert_range( my_set_t * z, ulong l, ulong h ); // z = z u r, fast O(h-l)
     173             :      my_set_t * my_set_select_range( my_set_t * z, ulong l, ulong h ); // z = z n r, fast O(max-(h-l))
     174             :      my_set_t * my_set_remove_range( my_set_t * z, ulong l, ulong h ); // z = z - r, fast O(h-l)
     175             : 
     176             :      ulong my_set_range_cnt( my_set_t const * x, ulong l, ulong h );   // returns cnt( z n r ), in [0,h-l], fast O(h-l)
     177             : 
     178             :    With the exception of my_set_valid_idx and my_set_valid, all of these
     179             :    assume the inputs are value and will produce strictly valid outputs
     180             :    unless otherwise explicitly noted. */
     181             : 
     182             : #include "../bits/fd_bits.h"
     183             : 
     184             : #ifndef SET_NAME
     185             : #error "Define SET_NAME"
     186             : #endif
     187             : 
     188             : #ifndef SET_MAX
     189             : #error "Define SET_MAX"
     190             : #endif
     191             : 
     192             : FD_STATIC_ASSERT( 1<=SET_MAX && SET_MAX<=2147483584 /* 2^31-64 */, invalid_set_max );
     193             : 
     194             : #if FD_TMPL_USE_HANDHOLDING
     195             : #include "../log/fd_log.h"
     196             : #endif
     197             : 
     198             : /* Implementation *****************************************************/
     199             : 
     200  1844435196 : #define SET_(x) FD_EXPAND_THEN_CONCAT3(SET_NAME,_,x)
     201             : 
     202             : typedef ulong SET_(t);
     203             : 
     204             : enum { SET_(word_cnt) = (((int)(SET_MAX))+63)>>6 };
     205             : 
     206             : FD_PROTOTYPES_BEGIN
     207             : 
     208             : /* Private APIs *******************************************************/
     209             : 
     210             : FD_FN_CONST static inline ulong
     211      555807 : SET_(private_full_last_word)( void ) {
     212      555807 :   return fd_ulong_mask_lsb( SET_MAX - ((SET_(word_cnt)-1)<<6) );
     213      555807 : }
     214             : 
     215             : /* Public APIs ********************************************************/
     216             : 
     217      333315 : FD_FN_CONST static inline ulong SET_(align)    ( void ) { return alignof(ulong); }
     218         801 : FD_FN_CONST static inline ulong SET_(footprint)( void ) { return 8UL*(ulong)SET_(word_cnt); }
     219             : 
     220             : static inline void *
     221         762 : SET_(new)( void * shmem ) {
     222             : # if FD_TMPL_USE_HANDHOLDING
     223             :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, SET_(align)() ) ) ) FD_LOG_CRIT(( "unaligned shmem" ));
     224             : # endif
     225         762 :   return fd_memset( shmem, 0, SET_(footprint)() );
     226         762 : }
     227             : 
     228         762 : static inline SET_(t) * SET_(join)  ( void *    shset ) { return (SET_(t) *)shset; }
     229         747 : static inline void    * SET_(leave) ( SET_(t) * set   ) { return (void *)set; }
     230         747 : static inline void    * SET_(delete)( void *    shset ) { return shset; }
     231             : 
     232           3 : FD_FN_CONST static inline ulong SET_(max)( SET_(t) const * set ) { (void)set; return (ulong)SET_MAX; }
     233             : 
     234             : FD_FN_PURE static inline int
     235      333315 : SET_(valid)( SET_(t) const * set ) {
     236      333315 :   if( FD_UNLIKELY( !set | !fd_ulong_is_aligned( (ulong)set, SET_(align)() ) ) ) return 0;
     237      333315 :   return !(set[ SET_(word_cnt)-1 ] & ~SET_(private_full_last_word()));
     238      333315 : }
     239             : 
     240             : FD_FN_CONST static inline int
     241             : SET_(valid_idx)( SET_(t) const * set,
     242       74070 :                  ulong           idx ) {
     243       74070 :   (void)set;
     244       74070 :   return idx<(ulong)SET_MAX;
     245       74070 : }
     246             : 
     247             : FD_FN_PURE static inline ulong
     248      153699 : SET_(cnt)( SET_(t) const * set ) {
     249      153699 :   ulong word_cnt = (ulong)SET_(word_cnt);
     250      153699 :   ulong cnt = 0UL;
     251    29364663 :   for( ulong i=0UL; i<word_cnt; i++ ) cnt += (ulong)fd_ulong_popcnt( set[i] );
     252      153699 :   return cnt;
     253      153699 : }
     254             : 
     255             : FD_FN_PURE static inline int
     256      296286 : SET_(is_null)( SET_(t) const * set ) {
     257      296286 :   ulong word_cnt = (ulong)SET_(word_cnt);
     258    39589563 :   for( ulong i=0UL; i<word_cnt; i++ ) if( set[i] ) return 0;
     259      185181 :   return 1;
     260      296286 : }
     261             : 
     262             : FD_FN_PURE static inline int
     263      148146 : SET_(is_full)( SET_(t) const * set ) {
     264      148146 :   ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
     265    10813362 :   for( ulong i=0UL; i<word_cnt; i++ ) if( ~set[i] ) return 0;
     266       37212 :   return set[word_cnt]==SET_(private_full_last_word());
     267      148146 : }
     268             : 
     269             : FD_FN_PURE static inline ulong
     270      153072 : SET_(first)( SET_(t) const * set ) {
     271      153072 :   ulong word_cnt = (ulong)SET_(word_cnt);
     272    10854171 :   for( ulong i=0UL; i<word_cnt; i++ ) {
     273    10817136 :     ulong w = set[i];
     274    10817136 :     if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w );
     275    10817136 :   }
     276       37035 :   return ~0UL;
     277      153072 : }
     278             : 
     279             : FD_FN_UNUSED static ulong /* Work around -Winline */
     280             : SET_(iter_next)( SET_(t) * set,
     281   914542569 :                  ulong     j ) {                     /* We've considered all bits up to and including j */
     282   914542569 :   j++;                                               /* Lowest bit we haven't considered */
     283   914542569 :   ulong word_cnt = (ulong)SET_(word_cnt);
     284   928917807 :   for( ulong i=(j>>6); i<word_cnt; i++ ) {           /* For all words with bits we haven't considered */
     285   928769661 :     ulong w = set[i];                                /* Get the bits we haven't considered for the current word */
     286   928769661 :     if( w ) {                                        /* If any bits are set in this word */
     287   914394423 :       set[i] = fd_ulong_pop_lsb( w );                /* Clear the lsb */
     288   914394423 :       return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* And return the index */
     289   914394423 :     }
     290   928769661 :   }
     291      148146 :   return ~0UL;                                       /* No more bits to consider */
     292   914542569 : }
     293      148230 : static inline ulong SET_(iter_init)( SET_(t) * set ) { return SET_(iter_next)( set, ~0UL ); }
     294   914542569 : FD_FN_CONST static inline ulong SET_(iter_done)( ulong j ) { return !~j; }
     295             : 
     296             : FD_FN_PURE FD_FN_UNUSED static ulong /* Work around -Winline */
     297             : SET_(const_iter_next)( SET_(t) const * set,
     298   914542290 :                        ulong           j ) {               /* We've considered all bits up to and including j */
     299   914542290 :   j++;                                                     /* Lowest bit we haven't considered */
     300   914542290 :   ulong m = (1UL<<(j&63UL))-1UL;                           /* Bits in first word that have been considered */
     301   914542290 :   ulong word_cnt = (ulong)SET_(word_cnt);
     302   928911870 :   for( ulong i=(j>>6); i<word_cnt; i++ ) {                 /* For all words with bits we haven't considered */
     303   928763730 :     ulong w = set[i] & ~m;                                 /* Get the bits we haven't considered for the current word */
     304   928763730 :     if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* If any bit is set in this word, return its index */
     305    14369580 :     m = 0UL;                                               /* Otherwise, continue to next word (haven't considered any bits) */
     306    14369580 :   }
     307      148140 :   return ~0UL;                                             /* No more bits to consider */
     308   914542290 : }
     309      148140 : FD_FN_PURE  static inline ulong SET_(const_iter_init)( SET_(t) const * set ) { return SET_(const_iter_next)( set, ~0UL ); }
     310   914542290 : FD_FN_CONST static inline ulong SET_(const_iter_done)( ulong j             ) { return !~j; }
     311             : 
     312             : static inline SET_(t) *
     313             : SET_(insert)( SET_(t) * set,
     314    12602634 :               ulong     idx ) {
     315             : # if FD_TMPL_USE_HANDHOLDING
     316             :   if( FD_UNLIKELY( idx>=(ulong)(SET_MAX) ) ) FD_LOG_CRIT(( "idx out of bounds" ));
     317             : # endif
     318    12602634 :   set[ idx >> 6 ] |= 1UL << (idx & 63UL);
     319    12602634 :   return set;
     320    12602634 : }
     321             : 
     322             : static inline SET_(t) *
     323             : SET_(remove)( SET_(t) * set,
     324      547179 :               ulong     idx ) {
     325             : # if FD_TMPL_USE_HANDHOLDING
     326             :   if( FD_UNLIKELY( idx>=(ulong)(SET_MAX) ) ) FD_LOG_CRIT(( "idx out of bounds" ));
     327             : # endif
     328      547179 :   set[ idx >> 6 ] &= ~(1UL << (idx & 63UL));
     329      547179 :   return set;
     330      547179 : }
     331             : 
     332             : static inline SET_(t) *
     333             : SET_(insert_if)( SET_(t) * set,
     334             :                  int       c,
     335    37423026 :                  ulong     idx ) {
     336             : # if FD_TMPL_USE_HANDHOLDING
     337             :   if( FD_UNLIKELY( idx>=(ulong)(SET_MAX) ) ) FD_LOG_CRIT(( "idx out of bounds" ));
     338             : # endif
     339    37423026 :   set[ idx >> 6 ] |= ((ulong)!!c) << (idx & 63UL);
     340    37423026 :   return set;
     341    37423026 : }
     342             : 
     343             : static inline SET_(t) *
     344             : SET_(remove_if)( SET_(t) * set,
     345             :                  int       c,
     346      296280 :                  ulong     idx ) {
     347             : # if FD_TMPL_USE_HANDHOLDING
     348             :   if( FD_UNLIKELY( idx>=(ulong)(SET_MAX) ) ) FD_LOG_CRIT(( "idx out of bounds" ));
     349             : # endif
     350      296280 :   set[ idx >> 6 ] &= ~(((ulong)!!c) << (idx & 63UL));
     351      296280 :   return set;
     352      296280 : }
     353             : 
     354             : FD_FN_PURE static inline int
     355             : SET_(test)( SET_(t) const * set,
     356      388920 :             ulong           idx ) {
     357             : # if FD_TMPL_USE_HANDHOLDING
     358             :   if( FD_UNLIKELY( idx>=(ulong)(SET_MAX) ) ) FD_LOG_CRIT(( "idx out of bounds" ));
     359             : # endif
     360      388920 :   return (int)((set[ idx >> 6 ] >> (idx & 63UL)) & 1UL);
     361      388920 : }
     362             : 
     363             : FD_FN_PURE static inline int
     364             : SET_(eq)( SET_(t) const * x,
     365     5567271 :           SET_(t) const * y ) {
     366     5567271 :   ulong word_cnt = (ulong)SET_(word_cnt);
     367  1008488187 :   for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=y[i] ) return 0;
     368     5122848 :   return 1;
     369     5567271 : }
     370             : 
     371             : FD_FN_PURE static inline int
     372             : SET_(subset)( SET_(t) const * x,
     373      592560 :               SET_(t) const * y ) {
     374      592560 :   ulong word_cnt = (ulong)SET_(word_cnt);
     375    75582387 :   for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=(y[i] & x[i]) ) return 0;
     376      333315 :   return 1;
     377      592560 : }
     378             : 
     379             : static inline SET_(t) *
     380      117132 : SET_(null)( SET_(t) * z ) {
     381      117132 :   ulong word_cnt = (ulong)SET_(word_cnt);
     382    22718829 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = 0UL;
     383      117132 :   return z;
     384      117132 : }
     385             : 
     386             : static inline SET_(t) *
     387          99 : SET_(full)( SET_(t) * z ) {
     388          99 :   ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
     389       58347 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = ~0UL;
     390          99 :   z[word_cnt] = SET_(private_full_last_word)();
     391          99 :   return z;
     392          99 : }
     393             : 
     394             : static inline SET_(t) *
     395             : SET_(full_if)( SET_(t) * z,
     396           6 :                int       c ) {
     397           6 :   ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
     398           6 :   ulong word     = ((ulong)!c)-1UL;
     399        1158 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = word;
     400           6 :   z[word_cnt] = word & SET_(private_full_last_word)();
     401           6 :   return z;
     402           6 : }
     403             : 
     404             : static inline SET_(t) *
     405             : SET_(ele)( SET_(t) * z,
     406       37035 :            ulong     idx ) {
     407       37035 :   return SET_(insert)( SET_(null)( z ), idx );
     408       37035 : }
     409             : 
     410             : static inline SET_(t) *
     411             : SET_(ele_if)( SET_(t) * z,
     412             :               int       c,
     413       74070 :               ulong     idx ) {
     414       74070 :   return SET_(insert_if)( SET_(null)( z ), c, idx );
     415       74070 : }
     416             : 
     417             : static inline SET_(t) *
     418             : SET_(copy)( SET_(t) *       z,
     419     2527380 :             SET_(t) const * x ) {
     420     2527380 :   ulong word_cnt = (ulong)SET_(word_cnt);
     421   490311720 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i];
     422     2527380 :   return z;
     423     2527380 : }
     424             : 
     425             : static inline SET_(t) *
     426             : SET_(complement)( SET_(t) *       z,
     427      185175 :                   SET_(t) const * x ) {
     428      185175 :   ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
     429    35738775 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = ~x[i];
     430      185175 :   z[word_cnt] = (~x[word_cnt]) & SET_(private_full_last_word)();
     431      185175 :   return z;
     432      185175 : }
     433             : 
     434             : static inline SET_(t) *
     435             : SET_(union)( SET_(t) *       z,
     436             :              SET_(t) const * x,
     437      632598 :              SET_(t) const * y ) {
     438      632598 :   ulong word_cnt = (ulong)SET_(word_cnt);
     439   122723481 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] | y[i];
     440      632598 :   return z;
     441      632598 : }
     442             : 
     443             : static inline SET_(t) *
     444             : SET_(intersect)( SET_(t) *       z,
     445             :                  SET_(t) const * x,
     446      595563 :                  SET_(t) const * y ) {
     447      595563 :   ulong word_cnt = (ulong)SET_(word_cnt);
     448   115538691 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & y[i];
     449      595563 :   return z;
     450      595563 : }
     451             : 
     452             : static inline SET_(t) *
     453             : SET_(subtract)( SET_(t) *       z,
     454             :                 SET_(t) const * x,
     455      632595 :                 SET_(t) const * y ) {
     456      632595 :   ulong word_cnt = (ulong)SET_(word_cnt);
     457   122723430 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & ~y[i];
     458      632595 :   return z;
     459      632595 : }
     460             : 
     461             : static inline SET_(t) *
     462             : SET_(xor)( SET_(t) *       z,
     463             :            SET_(t) const * x,
     464      592563 :            SET_(t) const * y ) {
     465      592563 :   ulong word_cnt = (ulong)SET_(word_cnt);
     466   114956691 :   for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] ^ y[i];
     467      592563 :   return z;
     468      592563 : }
     469             : 
     470             : static inline SET_(t) *
     471             : SET_(if)( SET_(t) *       z,
     472             :           int             c,
     473             :           SET_(t) const * x,
     474     1185120 :           SET_(t) const * y ) {
     475     1185120 :   return SET_(copy)( z, c ? x : y );
     476     1185120 : }
     477             : 
     478             : static inline SET_(t) *
     479             : SET_(range)( SET_(t) * set,
     480             :              ulong     l,
     481        3000 :              ulong     h ) {
     482             : # if FD_TMPL_USE_HANDHOLDING
     483             :   if( FD_UNLIKELY( !( (l<=h) & (h<=(ulong)(SET_MAX)) ) ) ) FD_LOG_CRIT(( "invalid range" ));
     484             : # endif
     485             : 
     486        3000 :   ulong word_idx = 0UL;
     487             : 
     488             :   /* Handle any complete leading zero words */
     489             : 
     490      190677 :   for( ulong stop_idx=l>>6; word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
     491             : 
     492             :   /* Handle any mixed leading word.  Note that it is possible the range
     493             :      also ends in this word. */
     494             : 
     495        3000 :   ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
     496        3000 :   if( FD_LIKELY( zcnt ) ) set[ word_idx++ ] = ((1UL << fd_ulong_min( 64UL-zcnt, h-l ))-1UL) << zcnt; /* opt large range */
     497             : 
     498             :   /* Handle any complete ones words.  Need to be careful as 64 word_idx
     499             :      might already be past h if the range ended in the mixed leading
     500             :      word. */
     501             : 
     502      193425 :   for( ulong stop_idx=h>>6; word_idx<stop_idx; word_idx++ ) set[ word_idx ] = ~0UL; /* FIXME: Consider memset? */
     503             : 
     504             :   /* Handle any mixed trailing word.  Like the above, 64 word_idx might
     505             :      already be past h at this point. */
     506             : 
     507        3000 :   ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
     508        3000 :   if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] = ((1UL << ocnt)-1UL); /* opt large range */
     509             : 
     510             :   /* Handle any complete trailing zero words */
     511             : 
     512      198015 :   for( ulong stop_idx=(ulong)SET_(word_cnt); word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
     513             : 
     514        3000 :   return set;
     515        3000 : }
     516             : 
     517             : static inline SET_(t) *
     518             : SET_(insert_range)( SET_(t) * set,
     519             :                     ulong     l,
     520        3000 :                     ulong     h ) {
     521             : # if FD_TMPL_USE_HANDHOLDING
     522             :   if( FD_UNLIKELY( !( (l<=h) & (h<=(ulong)(SET_MAX)) ) ) ) FD_LOG_CRIT(( "invalid range" ));
     523             : # endif
     524             : 
     525             :   /* Handle any complete leading zero words */
     526             : 
     527        3000 :   ulong word_idx = l>>6;
     528             : 
     529             :   /* Handle any mixed leading word.  Note that it is possible the range
     530             :      also ends in this word. */
     531             : 
     532        3000 :   ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
     533        3000 :   if( FD_LIKELY( zcnt ) ) set[ word_idx++ ] |= ((1UL << fd_ulong_min( 64UL-zcnt, h-l ))-1UL) << zcnt; /* opt large range */
     534             : 
     535             :   /* Handle any complete ones words.  Need to be careful as 64 word_idx
     536             :      might already be past h if the range ended in the mixed leading
     537             :      word. */
     538             : 
     539      193425 :   for( ulong stop_idx=h>>6; word_idx<stop_idx; word_idx++ ) set[ word_idx ] = ~0UL; /* FIXME: Consider memset? */
     540             : 
     541             :   /* Handle any mixed trailing word.  Like the above, 64 word_idx might
     542             :      already be past h at this point. */
     543             : 
     544        3000 :   ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
     545        3000 :   if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] |= ((1UL << ocnt)-1UL); /* opt large range */
     546             : 
     547             :   /* Handle any complete trailing zero words */
     548             : 
     549        3000 :   return set;
     550        3000 : }
     551             : 
     552             : static inline SET_(t) *
     553             : SET_(select_range)( SET_(t) * set,
     554             :                     ulong     l,
     555        3000 :                     ulong     h ) {
     556             : # if FD_TMPL_USE_HANDHOLDING
     557             :   if( FD_UNLIKELY( !( (l<=h) & (h<=(ulong)(SET_MAX)) ) ) ) FD_LOG_CRIT(( "invalid range" ));
     558             : # endif
     559             : 
     560        3000 :   ulong word_idx = 0UL;
     561             : 
     562             :   /* Handle any complete leading zero words */
     563             : 
     564      190677 :   for( ulong stop_idx=l>>6; word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
     565             : 
     566             :   /* Handle any mixed leading word.  Note that it is possible the range
     567             :      also ends in this word. */
     568             : 
     569        3000 :   ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
     570        3000 :   if( FD_LIKELY( zcnt ) ) set[ word_idx++ ] &= ((1UL << fd_ulong_min( 64UL-zcnt, h-l ))-1UL) << zcnt; /* opt large range */
     571             : 
     572             :   /* Handle any complete ones words.  Need to be careful as 64 word_idx
     573             :      might already be past h if the range ended in the mixed leading
     574             :      word. */
     575             : 
     576        3000 :   word_idx = fd_ulong_max( word_idx, h>>6 );
     577             : 
     578             :   /* Handle any mixed trailing word.  Like the above, 64 word_idx might
     579             :      already be past h at this point. */
     580             : 
     581        3000 :   ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
     582        3000 :   if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] &= ((1UL << ocnt)-1UL); /* opt large range */
     583             : 
     584             :   /* Handle any complete trailing zero words */
     585             : 
     586      198015 :   for( ulong stop_idx=(ulong)SET_(word_cnt); word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
     587             : 
     588        3000 :   return set;
     589        3000 : }
     590             : 
     591             : static inline SET_(t) *
     592             : SET_(remove_range)( SET_(t) * set,
     593             :                     ulong     l,
     594        3000 :                     ulong     h ) {
     595             : # if FD_TMPL_USE_HANDHOLDING
     596             :   if( FD_UNLIKELY( !( (l<=h) & (h<=(ulong)(SET_MAX)) ) ) ) FD_LOG_CRIT(( "invalid range" ));
     597             : # endif
     598             : 
     599             :   /* Handle any complete leading zero words */
     600             : 
     601        3000 :   ulong word_idx = l>>6;
     602             : 
     603             :   /* Handle any mixed leading word.  Note that it is possible the range
     604             :      also ends in this word. */
     605             : 
     606        3000 :   ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
     607        3000 :   if( FD_LIKELY( zcnt ) ) set[ word_idx++ ] &= ~(((1UL << fd_ulong_min( 64UL-zcnt, h-l ))-1UL) << zcnt); /* opt large range */
     608             : 
     609             :   /* Handle any complete ones words.  Need to be careful as 64 word_idx
     610             :      might already be past h if the range ended in the mixed leading
     611             :      word. */
     612             : 
     613      193425 :   for( ulong stop_idx=h>>6; word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
     614             : 
     615             :   /* Handle any mixed trailing word.  Like the above, 64 word_idx might
     616             :      already be past h at this point. */
     617             : 
     618        3000 :   ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
     619        3000 :   if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] &= ~((1UL << ocnt)-1UL); /* opt large range */
     620             : 
     621             :   /* Handle any complete trailing zero words */
     622             : 
     623        3000 :   return set;
     624        3000 : }
     625             : 
     626             : FD_FN_PURE static inline ulong
     627             : SET_(range_cnt)( SET_(t) const * set,
     628             :                  ulong           l,
     629        3000 :                  ulong           h ) {
     630             : # if FD_TMPL_USE_HANDHOLDING
     631             :   if( FD_UNLIKELY( !( (l<=h) & (h<=(ulong)(SET_MAX)) ) ) ) FD_LOG_CRIT(( "invalid range" ));
     632             : # endif
     633             : 
     634        3000 :   ulong cnt = 0UL;
     635             : 
     636             :   /* Handle any complete leading zero words */
     637             : 
     638        3000 :   ulong word_idx = l>>6;
     639             : 
     640             :   /* Handle any mixed leading word.  Note that it is possible the range
     641             :      also ends in this word. */
     642             : 
     643        3000 :   ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
     644        3000 :   if( FD_LIKELY( zcnt ) ) cnt += (ulong)fd_ulong_popcnt( set[ word_idx++ ] & (((1UL << fd_ulong_min( 64UL-zcnt, h-l ))-1UL) << zcnt) ); /* opt large range */
     645             : 
     646             :   /* Handle any complete ones words.  Need to be careful as 64 word_idx
     647             :      might already be past h if the range ended in the mixed leading
     648             :      word. */
     649             : 
     650      193425 :   for( ulong stop_idx=h>>6; word_idx<stop_idx; word_idx++ ) cnt += (ulong)fd_ulong_popcnt( set[ word_idx ] );
     651             : 
     652             :   /* Handle any mixed trailing word.  Like the above, 64 word_idx might
     653             :      already be past h at this point. */
     654             : 
     655        3000 :   ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
     656        3000 :   if( FD_LIKELY( ocnt ) ) cnt += (ulong)fd_ulong_popcnt( set[ word_idx++ ] & ((1UL << ocnt)-1UL) ); /* opt large range */
     657             : 
     658             :   /* Handle any complete trailing zero words */
     659             : 
     660        3000 :   return cnt;
     661        3000 : }
     662             : 
     663             : FD_PROTOTYPES_END
     664             : 
     665             : #undef SET_
     666             : 
     667             : #undef SET_MAX
     668             : #undef SET_NAME

Generated by: LCOV version 1.14