Line data Source code
1 : /* Declare a header-only API for fast manipulation of index sets where
2 : the set itself is represented in a primitive unsigned integer type.
3 : Example:
4 :
5 : #define SET_NAME myset
6 : #include "util/tmpl/fd_smallset.c"
7 :
8 : will declare the following in the compile unit:
9 :
10 : enum { myset_MAX = 64 }; // maximum number of elements in set (for use in compile time constructors)
11 :
12 : // Set constructors
13 : myset_t myset_null ( void ); // return {}
14 : myset_t myset_full ( void ); // return ~{}
15 : myset_t myset_full_if( int c ); // return c ? ~{} : {}
16 : myset_t myset_ele ( ulong i ); // return { i } // Assumes 0<=i<max
17 : myset_t myset_ele_if ( int c, ulong i ); // return c ? { i } : {} // Assumes 0<=i<max
18 :
19 : // Index operations
20 : ulong myset_max ( void ); // return the maximum number of elements that can be held by the set,
21 : // will be in (0,8*sizeof(myset_t)]
22 : ulong myset_cnt ( myset_t x ); // return the current number of elements in the set, will be in [0,myset_max()]
23 : ulong myset_first( myset_t x ); // return the index of the first element in the set, will be in [0,myset_max()),
24 : // U.B. if set is null
25 :
26 : // Boolean operations
27 : int myset_valid_idx( ulong i ); // returns 1 if i is a valid set index (i.e. idx < myset_max())
28 : int myset_valid ( myset_t x ); // returns 1 if x a valid set (i.e. no bits idx >= myset_max() are set)
29 : int myset_is_null ( myset_t x ); // returns 1 if x is the null set
30 : int myset_is_full ( myset_t x ); // returns 1 if x is the full set
31 : int myset_test ( myset_t x, ulong i ); // returns 1 if element i is in set x
32 : int myset_eq ( myset_t x, myset_t y ); // returns 1 if x and y are the same sets
33 : int myset_subset ( myset_t x, myset_t y ); // returns 1 if x is a subset of y
34 :
35 : // Unary operations
36 : myset_t myset_copy ( myset_t x ); // returns x
37 : myset_t myset_complement( myset_t x ); // returns ~x
38 :
39 : // Binary operations
40 : myset_t myset_union ( myset_t x, myset_t y ); // returns x u y
41 : myset_t myset_intersect( myset_t x, myset_t y ); // returns x n y
42 : myset_t myset_subtract ( myset_t x, myset_t y ); // returns x - y
43 : myset_t myset_xor ( myset_t x, myset_t y ); // returns (x u y) - (x n y)
44 :
45 : // Trinary operations
46 : myset_t myset_if( int c, myset_t t, myset_t f ); // returns c ? t : f
47 :
48 : // Iteration
49 : //
50 : // for( myset_iter_t iter=myset_iter_init(set); !myset_iter_done(iter); iter=myset_iter_next(iter) ) {
51 : // ulong idx = myset_iter_idx(iter);
52 : // ... process element idx of set here
53 : // ... do not touch iter
54 : // }
55 : //
56 : // will efficiently iterate over the elements of set in ascending
57 : // order.
58 :
59 : myset_iter_t myset_iter_init( myset_t set );
60 : myset_iter_t myset_iter_done( myset_iter_t iter );
61 : myset_iter_t myset_iter_next( myset_iter_t iter );
62 : ulong myset_iter_idx ( myset_iter_t iter );
63 :
64 : // Misc
65 :
66 : myset_t myset_insert( myset_t x, ulong i ); // short for myset_union ( x, myset_ele( i ) )
67 : myset_t myset_remove( myset_t x, ulong i ); // short for myset_subtract( x, myset_ele( i ) )
68 :
69 : myset_t myset_insert_if( int c, myset_t x, ulong i ); // Fast impl of "c ? myset_insert( x, i ) : x;"
70 : myset_t myset_remove_if( int c, myset_t x, ulong i ); // Fast impl of "c ? myset_remove( x, i ) : x;"
71 :
72 : // Range APIs do fast O(1) operations for a contiguous range within
73 : // a myset. Ranges are specified on the half-open interval [l,h).
74 : // These all assume 0<=l<=h<=max.
75 :
76 : myset_t myset_range( ulong l, ulong h ); // returns set containing elements [l,h).
77 :
78 : myset_t myset_insert_range( myset_t x, ulong l, ulong h ); // returns myset_union ( x, myset_range( l, h ) )
79 : myset_t myset_select_range( myset_t x, ulong l, ulong h ); // returns myset_intersect( x, myset_range( l, h ) )
80 : myset_t myset_remove_range( myset_t x, ulong l, ulong h ); // returns myset_subtract ( x, myset_range( l, h ) )
81 :
82 : ulong myset_range_cnt( myset_t x, ulong l, ulong h ); // returns myset_cnt( myset_select_range( x, l, h ) )
83 :
84 : // With the exceptions of myidx_valid_idx and myset_valid, all
85 : // these assume their inputs are valid and produce valid well
86 : // defined outputs unless explicitly noted otherwise
87 :
88 : This is safe for multiple inclusion and other options exist for fine
89 : tuning described below. */
90 :
91 : #include "../bits/fd_bits.h"
92 :
93 : #ifndef SET_NAME
94 : #error "Define SET_NAME"
95 : #endif
96 :
97 : /* SET_TYPE is a type that behaves like a primitive integral type and
98 : is efficient to pass around by value. Defaults to ulong. */
99 :
100 : #ifndef SET_TYPE
101 : #define SET_TYPE ulong
102 : #endif
103 :
104 : /* SET_MAX is an integer expression that gives the maximum number of
105 : elements this set can hold. Should be [1,WIDTH_SET_TYPE]. Defaults
106 : to the number of bits in SET_TYPE. */
107 :
108 : #ifndef SET_MAX
109 : #define SET_MAX (8*(int)sizeof(SET_TYPE))
110 : #endif
111 :
112 : /* SET_IDX_T is the integral type used to index set elements. Defaults
113 : to ulong. */
114 :
115 : #ifndef SET_IDX_T
116 : #define SET_IDX_T ulong
117 : #endif
118 :
119 : /* Define SET_POPCNT, SET_FIND_LSB AND SET_POP_LSB to the most efficient
120 : way to compute the population count of a small set. Defaults to
121 : corresponding APIs for the SET_TYPE in fd_bits. */
122 :
123 : #ifndef SET_POPCNT
124 26322145 : #define SET_POPCNT FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_popcnt)
125 : #endif
126 :
127 : #ifndef SET_FIND_LSB
128 26209214 : #define SET_FIND_LSB FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_find_lsb)
129 : #endif
130 :
131 : #ifndef SET_POP_LSB
132 23814 : #define SET_POP_LSB FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_pop_lsb)
133 : #endif
134 :
135 : #if FD_TMPL_USE_HANDHOLDING
136 : #include "../log/fd_log.h"
137 : #endif
138 :
139 : /* Implementation *****************************************************/
140 :
141 859596 : #define SET_(x)FD_EXPAND_THEN_CONCAT3(SET_NAME,_,x)
142 :
143 : enum {
144 : SET_(MAX) = (SET_MAX),
145 : SET_(PRIVATE_BIT_CNT) = 8*(int)sizeof(SET_TYPE),
146 : SET_(PRIVATE_ZP_CNT) = SET_(PRIVATE_BIT_CNT) - SET_(MAX),
147 : SET_(PRIVATE_IDX_MASK) = SET_(PRIVATE_BIT_CNT) - 1
148 : };
149 :
150 : FD_STATIC_ASSERT( 0<SET_(MAX) && SET_(MAX)<=SET_(PRIVATE_BIT_CNT), range );
151 : FD_STATIC_ASSERT( (ulong)SET_(PRIVATE_BIT_CNT)<=(1UL<<(8*sizeof(SET_IDX_T)-1)), range );
152 :
153 : typedef SET_TYPE SET_(t);
154 : typedef SET_TYPE SET_(iter_t);
155 :
156 : FD_PROTOTYPES_BEGIN
157 :
158 64176 : FD_FN_CONST static inline SET_(t) SET_(null)( void ) { return (SET_(t))0; }
159 :
160 54702 : FD_FN_CONST static inline SET_(t) SET_(full)( void ) { return (SET_(t))((((SET_(t))~((SET_(t))0))) >> SET_(PRIVATE_ZP_CNT)); }
161 :
162 : FD_FN_CONST static inline SET_(t)
163 6 : SET_(full_if)( int c ) {
164 6 : return (SET_(t))(((SET_(t))(((SET_(t))!c)-((SET_(t))1))) & SET_(full)());
165 6 : }
166 :
167 : /* Handles >=0 for negative types too */
168 378 : FD_FN_CONST static inline int SET_(valid_idx)( SET_IDX_T i ) { return ((ulong)(long)i)<((ulong)SET_(MAX)); }
169 :
170 : FD_FN_CONST static inline SET_(t)
171 60321112 : SET_(ele)( SET_IDX_T i ) {
172 : # if FD_TMPL_USE_HANDHOLDING
173 : if( FD_UNLIKELY( !SET_(valid_idx)( i ) ) ) FD_LOG_CRIT(( "invalid index" ));
174 : # endif
175 60321112 : return (SET_(t))(((SET_(t))1) << i);
176 60321112 : }
177 :
178 : FD_FN_CONST static inline SET_(t)
179 396522 : SET_(ele_if)( int c, SET_IDX_T i ) {
180 : # if FD_TMPL_USE_HANDHOLDING
181 : if( FD_UNLIKELY( !SET_(valid_idx)( i ) ) ) FD_LOG_CRIT(( "invalid index" ));
182 : # endif
183 396522 : return (SET_(t))(((SET_(t))!!c) << i);
184 396522 : }
185 :
186 3 : FD_FN_CONST static inline SET_IDX_T SET_(max) ( void ) { return (SET_IDX_T)SET_(MAX); }
187 26315905 : FD_FN_CONST static inline SET_IDX_T SET_(cnt) ( SET_(t) x ) { return (SET_IDX_T)SET_POPCNT(x); }
188 26185400 : FD_FN_CONST static inline SET_IDX_T SET_(first)( SET_(t) x ) { return (SET_IDX_T)SET_FIND_LSB(x); }
189 :
190 1512 : FD_FN_CONST static inline int SET_(valid) ( SET_(t) x ) { return !(x & (SET_(t))~SET_(full)()); }
191 750441 : FD_FN_CONST static inline int SET_(is_null) ( SET_(t) x ) { return !x; }
192 52230 : FD_FN_CONST static inline int SET_(is_full) ( SET_(t) x ) { return x==SET_(full)(); }
193 :
194 : FD_FN_CONST static inline int
195 21780213 : SET_(test) ( SET_(t) x, SET_IDX_T i ) {
196 : # if FD_TMPL_USE_HANDHOLDING
197 : if( FD_UNLIKELY( !SET_(valid_idx)( i ) ) ) FD_LOG_CRIT(( "invalid index" ));
198 : # endif
199 21780213 : return (int)((x>>i) & ((SET_(t))1));
200 21780213 : }
201 :
202 52560 : FD_FN_CONST static inline int SET_(eq) ( SET_(t) x, SET_(t) y ) { return x==y; }
203 3024 : FD_FN_CONST static inline int SET_(subset) ( SET_(t) x, SET_(t) y ) { return x==(x & y); }
204 :
205 756 : FD_FN_CONST static inline SET_(t) SET_(copy) ( SET_(t) x ) { return x; }
206 945 : FD_FN_CONST static inline SET_(t) SET_(complement)( SET_(t) x ) { return x ^ SET_(full)(); }
207 :
208 9453 : FD_FN_CONST static inline SET_(t) SET_(union) ( SET_(t) x, SET_(t) y ) { return x | y; }
209 758934 : FD_FN_CONST static inline SET_(t) SET_(intersect)( SET_(t) x, SET_(t) y ) { return x & y; }
210 9453 : FD_FN_CONST static inline SET_(t) SET_(subtract) ( SET_(t) x, SET_(t) y ) { return x & (SET_(t))~y; }
211 3024 : FD_FN_CONST static inline SET_(t) SET_(xor) ( SET_(t) x, SET_(t) y ) { return x ^ y; }
212 :
213 6048 : FD_FN_CONST static inline SET_(t) SET_(if)( int c, SET_(t) t, SET_(t) f ) { return c ? t : f; }
214 :
215 756 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_init)( SET_(t) set ) { return set; }
216 24570 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_done)( SET_(iter_t) iter ) { return !iter; }
217 23814 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_next)( SET_(iter_t) iter ) { return SET_POP_LSB( iter ); }
218 23814 : FD_FN_CONST static inline SET_IDX_T SET_(iter_idx) ( SET_(iter_t) iter ) { return (SET_IDX_T)SET_FIND_LSB( iter ); }
219 :
220 202971 : FD_FN_CONST static inline SET_(t) SET_(insert)( SET_(t) x, SET_IDX_T i ) { return x | SET_(ele)(i); }
221 945 : FD_FN_CONST static inline SET_(t) SET_(remove)( SET_(t) x, SET_IDX_T i ) { return x & (SET_(t))~SET_(ele)(i); }
222 :
223 394632 : FD_FN_CONST static inline SET_(t) SET_(insert_if)( int c, SET_(t) x, SET_IDX_T i ) { return x | SET_(ele_if)(c,i); }
224 1512 : FD_FN_CONST static inline SET_(t) SET_(remove_if)( int c, SET_(t) x, SET_IDX_T i ) { return x & (SET_(t))~SET_(ele_if)(c,i); }
225 :
226 31200 : FD_FN_CONST static inline SET_(t) SET_(range)( SET_IDX_T l, SET_IDX_T h ) {
227 : # if FD_TMPL_USE_HANDHOLDING
228 : /* Note: the 0<=l test is commented because compilers make babies cry
229 : with superfluous warnings when SET_IDX_T is an unsigned type. */
230 : if( FD_UNLIKELY( !( /*(((SET_(t))0)<=l) &*/ (l<=h) & (h<=SET_(max)()) ) ) ) FD_LOG_CRIT(( "invalid range" ));
231 : # endif
232 : /* Compute (2^h) - (2^l) == ones for bits [l,h), with no UB in the
233 : case where l and/or h == BIT_CNT */
234 31200 : return (SET_(t))( (((SET_(t))(h<=(SET_IDX_T)SET_(PRIVATE_IDX_MASK))) << (h & (SET_IDX_T)SET_(PRIVATE_IDX_MASK)))
235 31200 : - (((SET_(t))(l<=(SET_IDX_T)SET_(PRIVATE_IDX_MASK))) << (l & (SET_IDX_T)SET_(PRIVATE_IDX_MASK))) );
236 31200 : }
237 :
238 6240 : FD_FN_CONST static inline SET_(t) SET_(insert_range)( SET_(t) x, SET_IDX_T l, SET_IDX_T h ) {
239 6240 : return x | SET_(range)(l,h);
240 6240 : }
241 :
242 6240 : FD_FN_CONST static inline SET_(t) SET_(select_range)( SET_(t) x, SET_IDX_T l, SET_IDX_T h ) {
243 6240 : return x & SET_(range)(l,h);
244 6240 : }
245 :
246 6240 : FD_FN_CONST static inline SET_(t) SET_(remove_range)( SET_(t) x, SET_IDX_T l, SET_IDX_T h ) {
247 6240 : return x & (SET_(t))~SET_(range)(l,h);
248 6240 : }
249 :
250 6240 : FD_FN_CONST static inline SET_IDX_T SET_(range_cnt)( SET_(t) x, SET_IDX_T l, SET_IDX_T h ) {
251 6240 : return (SET_IDX_T)SET_POPCNT( x & SET_(range)(l,h) );
252 6240 : }
253 :
254 : FD_PROTOTYPES_END
255 :
256 : #undef SET_
257 :
258 : #undef SET_POP_LSB
259 : #undef SET_FIND_LSB
260 : #undef SET_POPCNT
261 : #undef SET_MAX
262 : #undef SET_TYPE
263 : #undef SET_NAME
|
