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 }
17 : myset_t myset_ele_if ( int c, ulong i ); // return c ? { i } : {}
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 : myset_t myset_insert( myset_t x, ulong i ); // short for myset_union ( x, myset_ele( i ) )
66 : myset_t myset_remove( myset_t x, ulong i ); // short for myset_subtract( x, myset_ele( i ) )
67 :
68 : myset_t myset_insert_if( int c, myset_t x, ulong i ); // Fast implementation of "c ? myset_insert( x, i ) : x;"
69 : myset_t myset_remove_if( int c, myset_t x, ulong i ); // Fast implementation of "c ? myset_remove( x, i ) : y;"
70 :
71 : // With the exceptions of myidx_valid_idx and myset_valid, all
72 : // these assume their inputs are valid and produce valid well
73 : // defined outputs unless explicitly noted otherwise
74 :
75 : This is safe for multiple inclusion and other options exist for fine
76 : tuning described below. */
77 :
78 : #include "../bits/fd_bits.h"
79 :
80 : #ifndef SET_NAME
81 : #error "Define SET_NAME"
82 : #endif
83 :
84 : /* SET_TYPE is a type that behaves like a primitive integral type and
85 : is efficient to pass around by value. Defaults to ulong. */
86 :
87 : #ifndef SET_TYPE
88 : #define SET_TYPE ulong
89 : #endif
90 :
91 : /* SET_MAX is an integer expression that gives the maximum number of
92 : elements this set can hold. Should be [1,WIDTH_SET_TYPE]. Defaults
93 : to the number of bits in SET_TYPE. */
94 :
95 : #ifndef SET_MAX
96 : #define SET_MAX (8*(int)sizeof(SET_TYPE))
97 : #endif
98 :
99 : /* SET_IDX_T is the integral type used to index set elements. Defaults
100 : to ulong. */
101 :
102 : #ifndef SET_IDX_T
103 : #define SET_IDX_T ulong
104 : #endif
105 :
106 : /* Define SET_POPCNT, SET_FIND_LSB AND SET_POP_LSB to the most efficient
107 : way to compute the population count of a small set. Defaults to
108 : corresponding APIs for the SET_TYPE in fd_bits. */
109 :
110 : #ifndef SET_POPCNT
111 170948049 : #define SET_POPCNT FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_popcnt)
112 : #endif
113 :
114 : #ifndef SET_FIND_LSB
115 170971095 : #define SET_FIND_LSB FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_find_lsb)
116 : #endif
117 :
118 : #ifndef SET_POP_LSB
119 23814 : #define SET_POP_LSB FD_EXPAND_THEN_CONCAT3(fd_,SET_TYPE,_pop_lsb)
120 : #endif
121 :
122 : /* Implementation *****************************************************/
123 :
124 113754 : #define SET_(x)FD_EXPAND_THEN_CONCAT3(SET_NAME,_,x)
125 :
126 : enum {
127 : SET_(MAX) = (SET_MAX),
128 : SET_(PRIVATE_BIT_CNT) = 8*(int)sizeof(SET_TYPE),
129 : SET_(PRIVATE_ZP_CNT) = SET_(PRIVATE_BIT_CNT) - SET_(MAX)
130 : };
131 :
132 : FD_STATIC_ASSERT( 0<SET_(MAX) && SET_(MAX)<=SET_(PRIVATE_BIT_CNT), range );
133 : FD_STATIC_ASSERT( (ulong)SET_(PRIVATE_BIT_CNT)<=(1UL<<(8*sizeof(SET_IDX_T)-1)), range );
134 :
135 : typedef SET_TYPE SET_(t);
136 : typedef SET_TYPE SET_(iter_t);
137 :
138 : FD_PROTOTYPES_BEGIN
139 :
140 0 : FD_FN_CONST static inline SET_(t) SET_(null)( void ) { return (SET_(t))0; }
141 :
142 0 : FD_FN_CONST static inline SET_(t) SET_(full)( void ) { return (SET_(t))((((SET_(t))~((SET_(t))0))) >> SET_(PRIVATE_ZP_CNT)); }
143 :
144 : FD_FN_CONST static inline SET_(t)
145 6 : SET_(full_if)( int c ) {
146 6 : return (SET_(t))(((SET_(t))(((SET_(t))!c)-((SET_(t))1))) & SET_(full)());
147 6 : }
148 :
149 349479024 : FD_FN_CONST static inline SET_(t) SET_(ele) ( SET_IDX_T i ) { return (SET_(t))(((SET_(t)) 1) << i); }
150 3402 : FD_FN_CONST static inline SET_(t) SET_(ele_if)( int c, SET_IDX_T i ) { return (SET_(t))(((SET_(t))!!c) << i); }
151 :
152 0 : FD_FN_CONST static inline SET_IDX_T SET_(max) ( void ) { return (SET_IDX_T)SET_(MAX); }
153 170948049 : FD_FN_CONST static inline SET_IDX_T SET_(cnt) ( SET_(t) x ) { return (SET_IDX_T)SET_POPCNT(x); }
154 170947281 : FD_FN_CONST static inline SET_IDX_T SET_(first)( SET_(t) x ) { return (SET_IDX_T)SET_FIND_LSB(x); }
155 :
156 : /* Handles >=0 for negative types too */
157 378 : FD_FN_CONST static inline int SET_(valid_idx)( SET_IDX_T i ) { return ((ulong)(long)i)<((ulong)SET_(MAX)); }
158 :
159 1512 : FD_FN_CONST static inline int SET_(valid) ( SET_(t) x ) { return !(x & ~SET_(full)()); }
160 744828 : FD_FN_CONST static inline int SET_(is_null) ( SET_(t) x ) { return !x; }
161 51837 : FD_FN_CONST static inline int SET_(is_full) ( SET_(t) x ) { return x==SET_(full)(); }
162 21570693 : FD_FN_CONST static inline int SET_(test) ( SET_(t) x, SET_IDX_T i ) { return (int)((x>>i) & ((SET_(t))1)); }
163 27411 : FD_FN_CONST static inline int SET_(eq) ( SET_(t) x, SET_(t) y ) { return x==y; }
164 3024 : FD_FN_CONST static inline int SET_(subset) ( SET_(t) x, SET_(t) y ) { return x==(x & y); }
165 :
166 756 : FD_FN_CONST static inline SET_(t) SET_(copy) ( SET_(t) x ) { return x; }
167 756 : FD_FN_CONST static inline SET_(t) SET_(complement)( SET_(t) x ) { return x ^ SET_(full)(); }
168 :
169 3213 : FD_FN_CONST static inline SET_(t) SET_(union) ( SET_(t) x, SET_(t) y ) { return x | y; }
170 747276 : FD_FN_CONST static inline SET_(t) SET_(intersect)( SET_(t) x, SET_(t) y ) { return x & y; }
171 3213 : FD_FN_CONST static inline SET_(t) SET_(subtract) ( SET_(t) x, SET_(t) y ) { return (SET_(t))(x & ~y); }
172 3024 : FD_FN_CONST static inline SET_(t) SET_(xor) ( SET_(t) x, SET_(t) y ) { return x ^ y; }
173 :
174 6048 : FD_FN_CONST static inline SET_(t) SET_(if)( int c, SET_(t) t, SET_(t) f ) { return c ? t : f; }
175 :
176 756 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_init)( SET_(t) set ) { return set; }
177 24570 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_done)( SET_(iter_t) iter ) { return !iter; }
178 23814 : FD_FN_CONST static inline SET_(iter_t) SET_(iter_next)( SET_(iter_t) iter ) { return SET_POP_LSB( iter ); }
179 23814 : FD_FN_CONST static inline SET_IDX_T SET_(iter_idx) ( SET_(iter_t) iter ) { return (SET_IDX_T)SET_FIND_LSB( iter ); }
180 :
181 55296 : FD_FN_CONST static inline SET_(t) SET_(insert)( SET_(t) x, SET_IDX_T i ) { return x | SET_(ele)(i); }
182 945 : FD_FN_CONST static inline SET_(t) SET_(remove)( SET_(t) x, SET_IDX_T i ) { return (SET_(t))(x & ~SET_(ele)(i)); }
183 :
184 1512 : 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); }
185 1512 : FD_FN_CONST static inline SET_(t) SET_(remove_if)( int c, SET_(t) x, SET_IDX_T i ) { return (SET_(t))(x & ~SET_(ele_if)(c,i)); }
186 :
187 : FD_PROTOTYPES_END
188 :
189 : #undef SET_
190 :
191 : #undef SET_POP_LSB
192 : #undef SET_FIND_LSB
193 : #undef SET_POPCNT
194 : #undef SET_MAX
195 : #undef SET_TYPE
196 : #undef SET_NAME
197 :
|
