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