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 39 : #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 0 : SET_(private_full_last_word)( void ) {
216 0 : return fd_ulong_mask_lsb( SET_MAX - ((SET_(word_cnt)-1)<<6) );
217 0 : }
218 :
219 : /* Public APIs ********************************************************/
220 :
221 0 : FD_FN_CONST static inline ulong SET_(align) ( void ) { return alignof(ulong); }
222 12 : FD_FN_CONST static inline ulong SET_(footprint)( void ) { return 8UL*(ulong)SET_(word_cnt); }
223 :
224 : static inline void *
225 0 : 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 0 : return fd_memset( shmem, 0, SET_(footprint)() );
230 0 : }
231 :
232 0 : static inline SET_(t) * SET_(join) ( void * shset ) { return (SET_(t) *)shset; }
233 0 : static inline void * SET_(leave) ( SET_(t) * set ) { return (void *)set; }
234 0 : static inline void * SET_(delete)( void * shset ) { return shset; }
235 :
236 0 : 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 0 : SET_(valid)( SET_(t) const * set ) {
240 0 : if( FD_UNLIKELY( !set | !fd_ulong_is_aligned( (ulong)set, SET_(align)() ) ) ) return 0;
241 0 : return !(set[ SET_(word_cnt)-1 ] & ~SET_(private_full_last_word()));
242 0 : }
243 :
244 : FD_FN_CONST static inline int
245 : SET_(valid_idx)( SET_(t) const * set,
246 0 : ulong idx ) {
247 0 : (void)set;
248 0 : return idx<(ulong)SET_MAX;
249 0 : }
250 :
251 : FD_FN_PURE static inline ulong
252 13 : SET_(cnt)( SET_(t) const * set ) {
253 13 : ulong word_cnt = (ulong)SET_(word_cnt);
254 13 : ulong cnt = 0UL;
255 221 : for( ulong i=0UL; i<word_cnt; i++ ) cnt += (ulong)fd_ulong_popcnt( set[i] );
256 13 : return cnt;
257 13 : }
258 :
259 : FD_FN_PURE static inline int
260 0 : SET_(is_null)( SET_(t) const * set ) {
261 0 : ulong word_cnt = (ulong)SET_(word_cnt);
262 0 : for( ulong i=0UL; i<word_cnt; i++ ) if( set[i] ) return 0;
263 0 : return 1;
264 0 : }
265 :
266 : FD_FN_PURE static inline int
267 0 : SET_(is_full)( SET_(t) const * set ) {
268 0 : ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
269 0 : for( ulong i=0UL; i<word_cnt; i++ ) if( ~set[i] ) return 0;
270 0 : return set[word_cnt]==SET_(private_full_last_word());
271 0 : }
272 :
273 : FD_FN_PURE static inline ulong
274 14 : SET_(first)( SET_(t) const * set ) {
275 14 : ulong word_cnt = (ulong)SET_(word_cnt);
276 14 : for( ulong i=0UL; i<word_cnt; i++ ) {
277 14 : ulong w = set[i];
278 14 : if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w );
279 14 : }
280 0 : return ~0UL;
281 14 : }
282 :
283 : FD_FN_PURE static inline ulong
284 0 : SET_(last)( SET_(t) const * set ) {
285 0 : ulong word_cnt = (ulong)SET_(word_cnt);
286 0 : for( ulong i=word_cnt; i>0UL; i-- ) {
287 0 : ulong w = set[i-1];
288 0 : if( w ) return ((i-1)<<6) + (ulong)fd_ulong_find_msb( w );
289 0 : }
290 0 : return ~0UL;
291 0 : }
292 :
293 : __attribute__((warn_unused_result)) FD_FN_UNUSED static ulong /* Work around -Winline */
294 : SET_(iter_next)( SET_(t) * set,
295 0 : ulong j ) { /* We've considered all bits up to and including j */
296 0 : j++; /* Lowest bit we haven't considered */
297 0 : ulong word_cnt = (ulong)SET_(word_cnt);
298 0 : for( ulong i=(j>>6); i<word_cnt; i++ ) { /* For all words with bits we haven't considered */
299 0 : ulong w = set[i]; /* Get the bits we haven't considered for the current word */
300 0 : if( w ) { /* If any bits are set in this word */
301 0 : set[i] = fd_ulong_pop_lsb( w ); /* Clear the lsb */
302 0 : return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* And return the index */
303 0 : }
304 0 : }
305 0 : return ~0UL; /* No more bits to consider */
306 0 : }
307 0 : static inline ulong SET_(iter_init)( SET_(t) * set ) { return SET_(iter_next)( set, ~0UL ); }
308 0 : FD_FN_CONST static inline ulong SET_(iter_done)( ulong j ) { return !~j; }
309 :
310 : __attribute__((warn_unused_result)) FD_FN_PURE FD_FN_UNUSED static ulong /* Work around -Winline */
311 : SET_(const_iter_next)( SET_(t) const * set,
312 0 : ulong j ) { /* We've considered all bits up to and including j */
313 0 : j++; /* Lowest bit we haven't considered */
314 0 : ulong m = (1UL<<(j&63UL))-1UL; /* Bits in first word that have been considered */
315 0 : ulong word_cnt = (ulong)SET_(word_cnt);
316 0 : for( ulong i=(j>>6); i<word_cnt; i++ ) { /* For all words with bits we haven't considered */
317 0 : ulong w = set[i] & ~m; /* Get the bits we haven't considered for the current word */
318 0 : if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* If any bit is set in this word, return its index */
319 0 : m = 0UL; /* Otherwise, continue to next word (haven't considered any bits) */
320 0 : }
321 0 : return ~0UL; /* No more bits to consider */
322 0 : }
323 0 : FD_FN_PURE static inline ulong SET_(const_iter_init)( SET_(t) const * set ) { return SET_(const_iter_next)( set, ~0UL ); }
324 0 : 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 24 : 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 24 : set[ idx >> 6 ] |= 1UL << (idx & 63UL);
333 24 : return set;
334 24 : }
335 :
336 : static inline SET_(t) *
337 : SET_(remove)( SET_(t) * set,
338 0 : 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 0 : set[ idx >> 6 ] &= ~(1UL << (idx & 63UL));
343 0 : return set;
344 0 : }
345 :
346 : static inline SET_(t) *
347 : SET_(insert_if)( SET_(t) * set,
348 : int c,
349 0 : 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 0 : set[ idx >> 6 ] |= ((ulong)!!c) << (idx & 63UL);
354 0 : return set;
355 0 : }
356 :
357 : static inline SET_(t) *
358 : SET_(remove_if)( SET_(t) * set,
359 : int c,
360 0 : 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 0 : set[ idx >> 6 ] &= ~(((ulong)!!c) << (idx & 63UL));
365 0 : return set;
366 0 : }
367 :
368 : FD_FN_PURE static inline int
369 : SET_(test)( SET_(t) const * set,
370 12 : 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 12 : return (int)((set[ idx >> 6 ] >> (idx & 63UL)) & 1UL);
375 12 : }
376 :
377 : FD_FN_PURE static inline int
378 : SET_(eq)( SET_(t) const * x,
379 0 : SET_(t) const * y ) {
380 0 : ulong word_cnt = (ulong)SET_(word_cnt);
381 0 : for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=y[i] ) return 0;
382 0 : return 1;
383 0 : }
384 :
385 : FD_FN_PURE static inline int
386 : SET_(subset)( SET_(t) const * x,
387 0 : SET_(t) const * y ) {
388 0 : ulong word_cnt = (ulong)SET_(word_cnt);
389 0 : for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=(y[i] & x[i]) ) return 0;
390 0 : return 1;
391 0 : }
392 :
393 : static inline SET_(t) *
394 0 : SET_(null)( SET_(t) * z ) {
395 0 : ulong word_cnt = (ulong)SET_(word_cnt);
396 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = 0UL;
397 0 : return z;
398 0 : }
399 :
400 : static inline SET_(t) *
401 0 : SET_(full)( SET_(t) * z ) {
402 0 : ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
403 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = ~0UL;
404 0 : z[word_cnt] = SET_(private_full_last_word)();
405 0 : return z;
406 0 : }
407 :
408 : static inline SET_(t) *
409 : SET_(full_if)( SET_(t) * z,
410 0 : int c ) {
411 0 : ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
412 0 : ulong word = ((ulong)!c)-1UL;
413 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = word;
414 0 : z[word_cnt] = word & SET_(private_full_last_word)();
415 0 : return z;
416 0 : }
417 :
418 : static inline SET_(t) *
419 : SET_(ele)( SET_(t) * z,
420 0 : ulong idx ) {
421 0 : return SET_(insert)( SET_(null)( z ), idx );
422 0 : }
423 :
424 : static inline SET_(t) *
425 : SET_(ele_if)( SET_(t) * z,
426 : int c,
427 0 : ulong idx ) {
428 0 : return SET_(insert_if)( SET_(null)( z ), c, idx );
429 0 : }
430 :
431 : static inline SET_(t) *
432 : SET_(copy)( SET_(t) * z,
433 0 : SET_(t) const * x ) {
434 0 : ulong word_cnt = (ulong)SET_(word_cnt);
435 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i];
436 0 : return z;
437 0 : }
438 :
439 : static inline SET_(t) *
440 : SET_(complement)( SET_(t) * z,
441 0 : SET_(t) const * x ) {
442 0 : ulong word_cnt = ((ulong)SET_(word_cnt))-1UL;
443 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = ~x[i];
444 0 : z[word_cnt] = (~x[word_cnt]) & SET_(private_full_last_word)();
445 0 : return z;
446 0 : }
447 :
448 : static inline SET_(t) *
449 : SET_(union)( SET_(t) * z,
450 : SET_(t) const * x,
451 0 : SET_(t) const * y ) {
452 0 : ulong word_cnt = (ulong)SET_(word_cnt);
453 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] | y[i];
454 0 : return z;
455 0 : }
456 :
457 : static inline SET_(t) *
458 : SET_(intersect)( SET_(t) * z,
459 : SET_(t) const * x,
460 0 : SET_(t) const * y ) {
461 0 : ulong word_cnt = (ulong)SET_(word_cnt);
462 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & y[i];
463 0 : return z;
464 0 : }
465 :
466 : static inline SET_(t) *
467 : SET_(subtract)( SET_(t) * z,
468 : SET_(t) const * x,
469 0 : SET_(t) const * y ) {
470 0 : ulong word_cnt = (ulong)SET_(word_cnt);
471 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & ~y[i];
472 0 : return z;
473 0 : }
474 :
475 : static inline SET_(t) *
476 : SET_(xor)( SET_(t) * z,
477 : SET_(t) const * x,
478 0 : SET_(t) const * y ) {
479 0 : ulong word_cnt = (ulong)SET_(word_cnt);
480 0 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] ^ y[i];
481 0 : return z;
482 0 : }
483 :
484 : static inline SET_(t) *
485 : SET_(if)( SET_(t) * z,
486 : int c,
487 : SET_(t) const * x,
488 0 : SET_(t) const * y ) {
489 0 : return SET_(copy)( z, c ? x : y );
490 0 : }
491 :
492 : static inline SET_(t) *
493 : SET_(range)( SET_(t) * set,
494 : ulong l,
495 0 : 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 0 : ulong word_idx = 0UL;
501 :
502 : /* Handle any complete leading zero words */
503 :
504 0 : 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 0 : ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
510 0 : 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 0 : 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 0 : ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
522 0 : if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] = ((1UL << ocnt)-1UL); /* opt large range */
523 :
524 : /* Handle any complete trailing zero words */
525 :
526 0 : for( ulong stop_idx=(ulong)SET_(word_cnt); word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
527 :
528 0 : return set;
529 0 : }
530 :
531 : static inline SET_(t) *
532 : SET_(insert_range)( SET_(t) * set,
533 : ulong l,
534 0 : 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 0 : 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 0 : ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
547 0 : 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 0 : 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 0 : ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
559 0 : if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] |= ((1UL << ocnt)-1UL); /* opt large range */
560 :
561 : /* Handle any complete trailing zero words */
562 :
563 0 : return set;
564 0 : }
565 :
566 : static inline SET_(t) *
567 : SET_(select_range)( SET_(t) * set,
568 : ulong l,
569 0 : 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 0 : ulong word_idx = 0UL;
575 :
576 : /* Handle any complete leading zero words */
577 :
578 0 : 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 0 : ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
584 0 : 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 0 : 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 0 : ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
596 0 : if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] &= ((1UL << ocnt)-1UL); /* opt large range */
597 :
598 : /* Handle any complete trailing zero words */
599 :
600 0 : for( ulong stop_idx=(ulong)SET_(word_cnt); word_idx<stop_idx; word_idx++ ) set[ word_idx ] = 0UL; /* FIXME: Consider memset? */
601 :
602 0 : return set;
603 0 : }
604 :
605 : static inline SET_(t) *
606 : SET_(remove_range)( SET_(t) * set,
607 : ulong l,
608 0 : 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 0 : 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 0 : ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
621 0 : 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 0 : 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 0 : ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
633 0 : if( FD_LIKELY( ocnt ) ) set[ word_idx++ ] &= ~((1UL << ocnt)-1UL); /* opt large range */
634 :
635 : /* Handle any complete trailing zero words */
636 :
637 0 : return set;
638 0 : }
639 :
640 : FD_FN_PURE static inline ulong
641 : SET_(range_cnt)( SET_(t) const * set,
642 : ulong l,
643 0 : 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 0 : ulong cnt = 0UL;
649 :
650 : /* Handle any complete leading zero words */
651 :
652 0 : 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 0 : ulong zcnt = l & 63UL; // == l - (word_idx<<6); /* In [0,63] */
658 0 : 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 0 : 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 0 : ulong ocnt = h - fd_ulong_min( word_idx<<6, h ); /* in [0,63] */
670 0 : 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 0 : return cnt;
675 0 : }
676 :
677 : FD_PROTOTYPES_END
678 :
679 : #undef SET_
680 :
681 : #undef SET_MAX
682 : #undef SET_NAME
|
