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