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 1844435214 : #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 153705 : SET_(cnt)( SET_(t) const * set ) {
249 153705 : ulong word_cnt = (ulong)SET_(word_cnt);
250 153705 : ulong cnt = 0UL;
251 29364765 : for( ulong i=0UL; i<word_cnt; i++ ) cnt += (ulong)fd_ulong_popcnt( set[i] );
252 153705 : return cnt;
253 153705 : }
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 153084 : SET_(first)( SET_(t) const * set ) {
271 153084 : ulong word_cnt = (ulong)SET_(word_cnt);
272 10854183 : for( ulong i=0UL; i<word_cnt; i++ ) {
273 10817148 : ulong w = set[i];
274 10817148 : if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w );
275 10817148 : }
276 37035 : return ~0UL;
277 153084 : }
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
|
