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 : With the exception of my_set_valid_idx and my_set_valid, all of these
161 : assume the inputs are value and will produce strictly valid outputs
162 : unless otherwise explicitly noted. */
163 :
164 : #include "../bits/fd_bits.h"
165 : #include <stddef.h>
166 :
167 : #ifndef SET_NAME
168 : #error "Define SET_NAME"
169 : #endif
170 :
171 : /* Implementation *****************************************************/
172 :
173 1844826921 : #define SET_(x) FD_EXPAND_THEN_CONCAT3(SET_NAME,_,x)
174 :
175 : typedef ulong SET_(t);
176 :
177 : struct SET_(private) {
178 : ulong max; /* In [1,ULONG_MAX-63] */
179 : ulong word_cnt;
180 : ulong full_last_word;
181 : SET_(t) set[1]; /* Actually word_cnt in size */
182 : };
183 :
184 : typedef struct SET_(private) SET_(private_t);
185 :
186 : FD_PROTOTYPES_BEGIN
187 :
188 : /* Private APIs *******************************************************/
189 :
190 : FD_STATIC_ASSERT( sizeof(SET_(t))==8UL, unexpected_set_word_type );
191 :
192 : /* private_word_cnt returns the number of words needed to store a set.
193 : Return is at least as max is at least 1 and no overflow in calc as
194 : max is at most ULONG_MAX-63. */
195 :
196 21084 : FD_FN_CONST static inline ulong SET_(private_word_cnt)( ulong max ) { return (max+63UL)>>6; }
197 :
198 : /* private_full_last_word returns the bit pattern a full set that
199 : can contain up to max elements has in the last word. */
200 :
201 : FD_FN_CONST static inline ulong
202 7212 : SET_(private_full_last_word)( ulong max ) {
203 7212 : return fd_ulong_mask_lsb( (int)(max - ((SET_(private_word_cnt)( max )-1UL)<<6)) );
204 7212 : }
205 :
206 : /* private_from_set return a pointer to the set_private given a pointer
207 : to the set. private_from_set_const also provided for
208 : const-correctness purposes. */
209 :
210 : FD_FN_CONST static inline SET_(private_t) *
211 919693791 : SET_(private_hdr_from_set)( SET_(t) * set ) {
212 919693791 : return (SET_(private_t) *)( (ulong)set - offsetof(SET_(private_t), set) );
213 919693791 : }
214 :
215 : FD_FN_CONST static inline SET_(private_t) const *
216 922703508 : SET_(private_hdr_from_set_const)( SET_(t) const * set ) {
217 922703508 : return (SET_(private_t) const *)( (ulong)set - offsetof(SET_(private_t), set) );
218 922703508 : }
219 :
220 : /* Public APIs ********************************************************/
221 :
222 0 : FD_FN_CONST static inline ulong SET_(align)( void ) { return alignof(SET_(private_t)); }
223 :
224 : FD_FN_CONST static inline ulong
225 13734 : SET_(footprint)( ulong max ) {
226 13734 : return sizeof(SET_(private_t))-sizeof(SET_(t)) + sizeof(SET_(t))*SET_(private_word_cnt)( max );
227 13734 : }
228 :
229 : FD_FN_UNUSED static void * /* Work around -Winline */
230 : SET_(new)( void * shmem,
231 7212 : ulong max ) {
232 7212 : SET_(private_t) * hdr = (SET_(private_t) *)shmem;
233 :
234 7212 : ulong word_cnt = SET_(private_word_cnt)( max );
235 :
236 7212 : hdr->max = max;
237 7212 : hdr->word_cnt = word_cnt;
238 7212 : hdr->full_last_word = SET_(private_full_last_word)( max );
239 :
240 7212 : SET_(t) * set = hdr->set; FD_COMPILER_FORGET( set );
241 7212 : fd_memset( set, 0, sizeof(SET_(t))*word_cnt );
242 :
243 7212 : return hdr;
244 7212 : }
245 :
246 : static inline SET_(t) *
247 8979 : SET_(join)( void * shset ) {
248 8979 : SET_(private_t) * hdr = (SET_(private_t) *)shset;
249 8979 : return hdr->set;
250 8979 : }
251 :
252 3594 : static inline void * SET_(leave) ( SET_(t) * set ) { return (void *)SET_(private_hdr_from_set)( set ); }
253 3594 : static inline void * SET_(delete)( void * shset ) { return shset; }
254 :
255 27 : FD_FN_PURE static inline ulong SET_(max)( SET_(t) * set ) { return SET_(private_hdr_from_set)( set )->max; }
256 :
257 : FD_FN_PURE static inline int
258 333315 : SET_(valid)( SET_(t) const * set ) {
259 333315 : if( FD_UNLIKELY( !set ) ) return 0;
260 333315 : SET_(private_t) const * hdr = SET_(private_hdr_from_set_const)( set );
261 333315 : if( FD_UNLIKELY( !hdr ) ) return 0;
262 333315 : return !(set[ hdr->word_cnt-1UL ] & ~hdr->full_last_word);
263 333315 : }
264 :
265 : FD_FN_PURE static inline int
266 : SET_(valid_idx)( SET_(t) const * set,
267 666630 : ulong idx ) {
268 666630 : return idx < SET_(private_hdr_from_set_const)( set )->max;
269 666630 : }
270 :
271 : FD_FN_PURE static inline ulong
272 148728 : SET_(cnt)( SET_(t) const * set ) {
273 148728 : ulong word_cnt = SET_(private_hdr_from_set_const)( set )->word_cnt;
274 148728 : ulong cnt = 0UL;
275 28966968 : for( ulong i=0UL; i<word_cnt; i++ ) cnt += (ulong)fd_ulong_popcnt( set[i] );
276 148728 : return cnt;
277 148728 : }
278 :
279 : FD_FN_PURE static inline int
280 296286 : SET_(is_null)( SET_(t) const * set ) {
281 296286 : ulong word_cnt = SET_(private_hdr_from_set_const)( set )->word_cnt;
282 39589563 : for( ulong i=0UL; i<word_cnt; i++ ) if( set[i] ) return 0;
283 185181 : return 1;
284 296286 : }
285 :
286 : FD_FN_PURE static inline int
287 148146 : SET_(is_full)( SET_(t) const * set ) {
288 148146 : SET_(private_t) const * hdr = SET_(private_hdr_from_set_const)( set );
289 148146 : ulong last_word = hdr->word_cnt - 1UL;
290 10813362 : for( ulong i=0UL; i<last_word; i++ ) if( ~set[i] ) return 0;
291 37212 : return set[last_word]==hdr->full_last_word;
292 148146 : }
293 :
294 : FD_FN_PURE static inline ulong
295 148140 : SET_(first)( SET_(t) const * set ) {
296 148140 : ulong word_cnt = SET_(private_hdr_from_set_const)( set )->word_cnt;
297 10849239 : for( ulong i=0UL; i<word_cnt; i++ ) {
298 10812204 : ulong w = set[i];
299 10812204 : if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w );
300 10812204 : }
301 37035 : return ~0UL;
302 148140 : }
303 :
304 : FD_FN_UNUSED static ulong /* Work around -Winline */
305 : SET_(iter_next)( SET_(t) * set,
306 914542290 : ulong j ) { /* We've considered all bits up to and including j */
307 914542290 : j++; /* Lowest bit we haven't considered */
308 914542290 : ulong word_cnt = SET_(private_hdr_from_set)( set )->word_cnt;
309 928911870 : for( ulong i=(j>>6); i<word_cnt; i++ ) { /* For all words with bits we haven't considered */
310 928763730 : ulong w = set[i]; /* Get the bits we haven't considered for the current word */
311 928763730 : if( w ) { /* If any bits are set in this word */
312 914394150 : set[i] = fd_ulong_pop_lsb( w ); /* Clear the lsb */
313 914394150 : return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* And return the index */
314 914394150 : }
315 928763730 : }
316 148140 : return ~0UL; /* No more bits to consider */
317 914542290 : }
318 148140 : static inline ulong SET_(iter_init)( SET_(t) * set ) { return SET_(iter_next)( set, ~0UL ); }
319 914542290 : FD_FN_CONST static inline ulong SET_(iter_done)( ulong j ) { return !~j; }
320 :
321 : FD_FN_PURE FD_FN_UNUSED static ulong /* Work around -Winline */
322 : SET_(const_iter_next)( SET_(t) const * set,
323 914703342 : ulong j ) { /* We've considered all bits up to and including j */
324 914703342 : j++; /* Lowest bit we haven't considered */
325 914703342 : ulong m = (1UL<<(j&63UL))-1UL; /* Bits in first word that have considered */
326 914703342 : ulong word_cnt = SET_(private_hdr_from_set_const)( set )->word_cnt;
327 929297535 : for( ulong i=(j>>6); i<word_cnt; i++ ) { /* For all words with bits we haven't considered */
328 929148807 : ulong w = set[i] & ~m; /* Get the bits we haven't considered for the current word */
329 929148807 : if( w ) return (i<<6) + (ulong)fd_ulong_find_lsb( w ); /* If any bit is set in this word, return its index */
330 14594193 : m = 0UL; /* Otherwise, continue to next word (haven't considered any bits) */
331 14594193 : }
332 148728 : return ~0UL; /* No more bits to consider */
333 914703342 : }
334 148728 : FD_FN_PURE static inline ulong SET_(const_iter_init)( SET_(t) const * set ) { return SET_(const_iter_next)( set, ~0UL ); }
335 914703342 : FD_FN_CONST static inline ulong SET_(const_iter_done)( ulong j ) { return !~j; }
336 :
337 : static inline SET_(t) *
338 : SET_(insert)( SET_(t) * set,
339 3841470 : ulong idx ) {
340 3841470 : set[ idx >> 6 ] |= 1UL << (idx & 63UL);
341 3841470 : return set;
342 3841470 : }
343 :
344 : static inline SET_(t) *
345 : SET_(remove)( SET_(t) * set,
346 185175 : ulong idx ) {
347 185175 : set[ idx >> 6 ] &= ~(1UL << (idx & 63UL));
348 185175 : return set;
349 185175 : }
350 :
351 : static inline SET_(t) *
352 : SET_(insert_if)( SET_(t) * set,
353 : int c,
354 370350 : ulong idx ) {
355 370350 : set[ idx >> 6 ] |= ((ulong)!!c) << (idx & 63UL);
356 370350 : return set;
357 370350 : }
358 :
359 : static inline SET_(t) *
360 : SET_(remove_if)( SET_(t) * set,
361 : int c,
362 296280 : ulong idx ) {
363 296280 : set[ idx >> 6 ] &= ~(((ulong)!!c) << (idx & 63UL));
364 296280 : return set;
365 296280 : }
366 :
367 : FD_FN_PURE static inline int
368 : SET_(test)( SET_(t) const * set,
369 425295 : ulong idx ) {
370 425295 : return (int)((set[ idx >> 6 ] >> (idx & 63UL)) & 1UL);
371 425295 : }
372 :
373 : FD_FN_PURE static inline int
374 : SET_(eq)( SET_(t) const * x,
375 5555256 : SET_(t) const * y ) {
376 5555256 : ulong word_cnt = SET_(private_hdr_from_set_const)( x )->word_cnt;
377 1006159980 : for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=y[i] ) return 0;
378 5110836 : return 1;
379 5555256 : }
380 :
381 : FD_FN_PURE static inline int
382 : SET_(subset)( SET_(t) const * x,
383 592560 : SET_(t) const * y ) {
384 592560 : ulong word_cnt = SET_(private_hdr_from_set_const)( x )->word_cnt;
385 75582387 : for( ulong i=0UL; i<word_cnt; i++ ) if( x[i]!=(y[i] & x[i]) ) return 0;
386 333315 : return 1;
387 592560 : }
388 :
389 : static inline SET_(t) *
390 111105 : SET_(null)( SET_(t) * z ) {
391 111105 : ulong word_cnt = SET_(private_hdr_from_set_const)( z )->word_cnt;
392 21554370 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = 0UL;
393 111105 : return z;
394 111105 : }
395 :
396 : static inline SET_(t) *
397 9 : SET_(full)( SET_(t) * z ) {
398 9 : SET_(private_t) * hdr = SET_(private_hdr_from_set)( z );
399 9 : ulong last_word = hdr->word_cnt - 1UL;
400 1737 : for( ulong i=0UL; i<last_word; i++ ) z[i] = ~0UL;
401 9 : z[last_word] = hdr->full_last_word;
402 9 : return z;
403 9 : }
404 :
405 : static inline SET_(t) *
406 : SET_(full_if)( SET_(t) * z,
407 6 : int c ) {
408 6 : SET_(private_t) * hdr = SET_(private_hdr_from_set)( z );
409 6 : ulong last_word = hdr->word_cnt - 1UL;
410 6 : ulong word = ((ulong)!c)-1UL;
411 1158 : for( ulong i=0UL; i<last_word; i++ ) z[i] = word;
412 6 : z[last_word] = word & hdr->full_last_word;
413 6 : return z;
414 6 : }
415 :
416 : static inline SET_(t) *
417 : SET_(ele)( SET_(t) * z,
418 37035 : ulong idx ) {
419 37035 : return SET_(insert)( SET_(null)( z ), idx );
420 37035 : }
421 :
422 : static inline SET_(t) *
423 : SET_(ele_if)( SET_(t) * z,
424 : int c,
425 74070 : ulong idx ) {
426 74070 : return SET_(insert_if)( SET_(null)( z ), c, idx );
427 74070 : }
428 :
429 : static inline SET_(t) *
430 : SET_(copy)( SET_(t) * z,
431 2518380 : SET_(t) const * x ) {
432 2518380 : ulong word_cnt = SET_(private_hdr_from_set)( z )->word_cnt;
433 488565720 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i];
434 2518380 : return z;
435 2518380 : }
436 :
437 : FD_FN_UNUSED static SET_(t) * /* Work around -Winline */
438 : SET_(complement)( SET_(t) * z,
439 185175 : SET_(t) const * x ) {
440 185175 : SET_(private_t) * hdr = SET_(private_hdr_from_set)( z );
441 185175 : ulong last_word = hdr->word_cnt - 1UL;
442 35738775 : for( ulong i=0UL; i<last_word; i++ ) z[i] = ~x[i];
443 185175 : z[last_word] = (~x[last_word]) & hdr->full_last_word;
444 185175 : return z;
445 185175 : }
446 :
447 : static inline SET_(t) *
448 : SET_(union)( SET_(t) * z,
449 : SET_(t) const * x,
450 629595 : SET_(t) const * y ) {
451 629595 : ulong word_cnt = SET_(private_hdr_from_set)( z )->word_cnt;
452 122141430 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] | y[i];
453 629595 : return z;
454 629595 : }
455 :
456 : static inline SET_(t) *
457 : SET_(intersect)( SET_(t) * z,
458 : SET_(t) const * x,
459 592560 : SET_(t) const * y ) {
460 592560 : ulong word_cnt = SET_(private_hdr_from_set)( z )->word_cnt;
461 114956640 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & y[i];
462 592560 : return z;
463 592560 : }
464 :
465 : static inline SET_(t) *
466 : SET_(subtract)( SET_(t) * z,
467 : SET_(t) const * x,
468 629595 : SET_(t) const * y ) {
469 629595 : ulong word_cnt = SET_(private_hdr_from_set)( z )->word_cnt;
470 122141430 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] & ~y[i];
471 629595 : return z;
472 629595 : }
473 :
474 : static inline SET_(t) *
475 : SET_(xor)( SET_(t) * z,
476 : SET_(t) const * x,
477 592560 : SET_(t) const * y ) {
478 592560 : ulong word_cnt = SET_(private_hdr_from_set)( z )->word_cnt;
479 114956640 : for( ulong i=0UL; i<word_cnt; i++ ) z[i] = x[i] ^ y[i];
480 592560 : return z;
481 592560 : }
482 :
483 : static inline SET_(t) *
484 : SET_(if)( SET_(t) * z,
485 : int c,
486 : SET_(t) const * x,
487 1185120 : SET_(t) const * y ) {
488 1185120 : return SET_(copy)( z, c ? x : y );
489 1185120 : }
490 :
491 : FD_PROTOTYPES_END
492 :
493 : #undef SET_
494 :
495 : #undef SET_NAME
496 :
|
