💾 Archived View for gmi.noulin.net › gitRepositories › set › file › set.h.gmi captured on 2023-01-29 at 13:15:34. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
set.h (11844B)
1
2 #include "libsheepyObject.h"
3
4 // TODO
5 // add and remove
6 // buckets with multiple keys
7
8 /**
9 * simple static set
10 *
11 * keys are assigned a unique index
12 * this data structure maps keys to indexes in an array of size count
13 *
14 * when there is a collision, a linear search is done until an empty bucket is found
15 *
16 * the simple static set can be used together with a bitset to filter keys efficiently
17 *
18 * HASHFUNC, ISEMPTY and CMPFUNC are functions defined before using sstaticSet* macros
19 *
20 * hashType HASHFUNC(key);
21 * returns the hash value for key
22 *
23 * bool ISEMPTY(keyInSet);
24 * returns true when the bucket don't have a key
25 *
26 * bool CMPFUNC(key1, key2);
27 * returns true when key1 is equal key2
28 */
29
30 /** type definition */
31 #define sstaticSetT(typeName, keyType, count)\
32 typedef struct { keyType set[count];} typeName;
33
34 /** clear set */
35 #define sstaticSetClear(name) memset((name)->set, 0, sizeof((name)->set));
36
37 /** get bucket at index */
38 #define sstaticSetAt(name, index) ((name)->set[index])
39
40 /**
41 * add key to set
42 *
43 * \return
44 * 1 key is added
45 * 0 key was already in set
46 * -1 set is full, can't add the key
47 */
48 #define sstaticSetAdd(name, key) ({\
49 var UNIQVAR(k) = key;\
50 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
51 size_t UNIQVAR(mhash) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
52 i8 UNIQVAR(r) = -1;\
53 if (ISEMPTY((name)->set[UNIQVAR(mhash)])) {\
54 /* save key in this bucket */\
55 /*logI("empty");*/\
56 (name)->set[UNIQVAR(mhash)] = UNIQVAR(k);\
57 UNIQVAR(r) = 1;\
58 }\
59 else {\
60 /* key already in set or collision */\
61 UNIQVAR(r) = 0;\
62 if (not CMPFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) {\
63 /* collision */\
64 /*logI("collision");*/\
65 circular(UNIQVAR(i), UNIQVAR(mhash), ARRAY_SIZE((name)->set)) {\
66 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
67 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
68 goto UNIQVAR(end);\
69 }\
70 if (ISEMPTY((name)->set[UNIQVAR(i)])) {\
71 /* use empty bucket for key */\
72 (name)->set[UNIQVAR(i)] = UNIQVAR(k);\
73 UNIQVAR(r) = 1;\
74 /*logI("found a bucket");*/\
75 goto UNIQVAR(end);\
76 }\
77 } /* circular */\
78 /* set is full, the key cannot be added */\
79 UNIQVAR(r) = -1;\
80 } /* if (not CPMFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) */\
81 }\
82 UNIQVAR(end):\
83 UNIQVAR(r);\
84 })
85
86 #define sstaticSetHas(name, key) ({\
87 var UNIQVAR(k) = key;\
88 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
89 size_t UNIQVAR(mhash) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
90 bool UNIQVAR(r) = true;\
91 if (not CMPFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) {\
92 /* collision */\
93 /*logI("collision");*/\
94 circular(UNIQVAR(i), UNIQVAR(mhash), ARRAY_SIZE((name)->set)) {\
95 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
96 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
97 /* found key in set */\
98 /*logI("already key");*/\
99 goto UNIQVAR(end);\
100 }\
101 if (ISEMPTY((name)->set[UNIQVAR(i)])) {\
102 /* key not found */\
103 /*logI("found a bucket");*/\
104 break;\
105 }\
106 } /* circular */\
107 UNIQVAR(r) = false;\
108 } /* if (not CPMFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) */\
109 UNIQVAR(end):\
110 UNIQVAR(r);\
111 })
112
113 /**
114 * get index for key
115 *
116 * \return
117 * index for key
118 * -1 not found
119 */
120 #define sstaticSetGet(name, key) ({\
121 var UNIQVAR(k) = key;\
122 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
123 ssize_t UNIQVAR(r) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
124 if (not CMPFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) {\
125 /* collision */\
126 /*logI("collision");*/\
127 circular(UNIQVAR(i), UNIQVAR(r), ARRAY_SIZE((name)->set)) {\
128 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
129 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
130 /* found key in set */\
131 /*logI("already key");*/\
132 UNIQVAR(r) = UNIQVAR(i);\
133 goto UNIQVAR(end);\
134 }\
135 if (ISEMPTY((name)->set[UNIQVAR(i)])) {\
136 /* key not found */\
137 /*logI("found a bucket");*/\
138 break;\
139 }\
140 } /* circular */\
141 UNIQVAR(r) = -1;\
142 } /* if (not CPMFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) */\
143 UNIQVAR(end):\
144 UNIQVAR(r);\
145 })
146
147 /**
148 * get index and add key
149 *
150 * \return
151 * index for key
152 * -1 set is full, can't add the key
153 */
154 #define sstaticSetGetNAdd(name, key) ({\
155 var UNIQVAR(k) = key;\
156 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
157 ssize_t UNIQVAR(r) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
158 if (ISEMPTY((name)->set[UNIQVAR(r)])) {\
159 /* save key in this bucket */\
160 /*logI("empty");*/\
161 (name)->set[UNIQVAR(r)] = UNIQVAR(k);\
162 }\
163 else {\
164 /* key already in set or collision */\
165 if (not CMPFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) {\
166 /* collision */\
167 /*logI("collision");*/\
168 circular(UNIQVAR(i), UNIQVAR(r), ARRAY_SIZE((name)->set)) {\
169 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
170 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
171 /* found key in set */\
172 UNIQVAR(r) = UNIQVAR(i);\
173 /*logI("already key");*/\
174 goto UNIQVAR(end);\
175 }\
176 if (ISEMPTY((name)->set[UNIQVAR(i)])) {\
177 /* use empty bucket for key */\
178 (name)->set[UNIQVAR(i)] = UNIQVAR(k);\
179 UNIQVAR(r) = UNIQVAR(i);\
180 /*logI("found a bucket");*/\
181 goto UNIQVAR(end);\
182 }\
183 } /* circular */\
184 UNIQVAR(r) = -1;\
185 } /* if (not CPMFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) */\
186 }\
187 UNIQVAR(end):\
188 UNIQVAR(r);\
189 })
190
191
192
193 /**
194 * another static set
195 *
196 * this set doesn't need ISFUNC, it keeps track of empty buckets
197 */
198
199 /** type definition */
200 #define astaticSetT(typeName, keyType, count)\
201 staticBitsetT(UNIQVAR(bits), u64, count);\
202 typedef struct { \
203 keyType set[count];\
204 UNIQVAR(bits) hasKey;\
205 } typeName;
206
207 /** clear set */
208 #define astaticSetClear(name) do{\
209 memset((name)->set, 0, sizeof((name)->set));\
210 staticBitsetClear(&(name)->hasKey);\
211 } while(0)
212
213 /** get bucket at index */
214 #define astaticSetAt(name, index) ((name)->set[index])
215
216 /** is bucket empty */
217 #define astaticSetIsBucketEmpty(name, index) !staticBitsetGet(&(name)->hasKey, index)
218
219 /**
220 * add key to set
221 *
222 * \return
223 * 1 key is added
224 * 0 key was already in set
225 * -1 set is full, can't add the key
226 */
227 #define astaticSetAdd(name, key) ({\
228 var UNIQVAR(k) = key;\
229 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
230 size_t UNIQVAR(mhash) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
231 i8 UNIQVAR(r) = -1;\
232 if (astaticSetIsBucketEmpty(name,UNIQVAR(mhash))) {\
233 /* save key in this bucket */\
234 /*logI("empty");*/\
235 (name)->set[UNIQVAR(mhash)] = UNIQVAR(k);\
236 UNIQVAR(r) = 1;\
237 staticBitset1(&(name)->hasKey, UNIQVAR(mhash));\
238 }\
239 else {\
240 /* key already in set or collision */\
241 UNIQVAR(r) = 0;\
242 if (not CMPFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) {\
243 /* collision */\
244 /*logI("collision");*/\
245 circular(UNIQVAR(i), UNIQVAR(mhash), ARRAY_SIZE((name)->set)) {\
246 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
247 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
248 goto UNIQVAR(end);\
249 }\
250 if (astaticSetIsBucketEmpty(name,UNIQVAR(i))) {\
251 /* use empty bucket for key */\
252 (name)->set[UNIQVAR(i)] = UNIQVAR(k);\
253 UNIQVAR(r) = 1;\
254 staticBitset1(&(name)->hasKey, UNIQVAR(i));\
255 /*logI("found a bucket");*/\
256 goto UNIQVAR(end);\
257 }\
258 } /* circular */\
259 /* set is full, the key cannot be added */\
260 UNIQVAR(r) = -1;\
261 } /* if (not CPMFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) */\
262 }\
263 UNIQVAR(end):\
264 UNIQVAR(r);\
265 })
266
267 #define astaticSetHas(name, key) ({\
268 var UNIQVAR(k) = key;\
269 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
270 size_t UNIQVAR(mhash) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
271 bool UNIQVAR(r) = true;\
272 if (not CMPFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) {\
273 /* collision */\
274 /*logI("collision");*/\
275 circular(UNIQVAR(i), UNIQVAR(mhash), ARRAY_SIZE((name)->set)) {\
276 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
277 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
278 /* found key in set */\
279 /*logI("already key");*/\
280 goto UNIQVAR(end);\
281 }\
282 if (astaticSetIsBucketEmpty(name,UNIQVAR(i))) {\
283 /* key not found */\
284 /*logI("found a bucket");*/\
285 break;\
286 }\
287 } /* circular */\
288 UNIQVAR(r) = false;\
289 } /* if (not CPMFUNC((name)->set[UNIQVAR(mhash)], UNIQVAR(k))) */\
290 UNIQVAR(end):\
291 UNIQVAR(r);\
292 })
293
294 /**
295 * get index for key
296 *
297 * \return
298 * index for key
299 * -1 not found
300 */
301 #define astaticSetGet(name, key) ({\
302 var UNIQVAR(k) = key;\
303 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
304 ssize_t UNIQVAR(r) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
305 if (not CMPFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) {\
306 /* collision */\
307 /*logI("collision");*/\
308 circular(UNIQVAR(i), UNIQVAR(r), ARRAY_SIZE((name)->set)) {\
309 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
310 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
311 /* found key in set */\
312 /*logI("already key");*/\
313 UNIQVAR(r) = UNIQVAR(i);\
314 goto UNIQVAR(end);\
315 }\
316 if (astaticSetIsBucketEmpty(name,UNIQVAR(i))) {\
317 /* key not found */\
318 /*logI("found a bucket");*/\
319 break;\
320 }\
321 } /* circular */\
322 UNIQVAR(r) = -1;\
323 } /* if (not CPMFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) */\
324 UNIQVAR(end):\
325 UNIQVAR(r);\
326 })
327
328 /**
329 * get index and add key
330 *
331 * \return
332 * index for key
333 * -1 set is full, can't add the key
334 */
335 #define astaticSetGetNAdd(name, key) ({\
336 var UNIQVAR(k) = key;\
337 var UNIQVAR(hash) = HASHFUNC(UNIQVAR(k));\
338 ssize_t UNIQVAR(r) = UNIQVAR(hash) % ARRAY_SIZE((name)->set);\
339 if (astaticSetIsBucketEmpty(name,UNIQVAR(r))) {\
340 /* save key in this bucket */\
341 /*logI("empty");*/\
342 (name)->set[UNIQVAR(r)] = UNIQVAR(k);\
343 staticBitset1(&(name)->hasKey, UNIQVAR(r));\
344 }\
345 else {\
346 /* key already in set or collision */\
347 if (not CMPFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) {\
348 /* collision */\
349 /*logI("collision");*/\
350 circular(UNIQVAR(i), UNIQVAR(r), ARRAY_SIZE((name)->set)) {\
351 /*logI("circ %zu %d", UNIQVAR(i), (name)->set[UNIQVAR(i)]);*/\
352 if (CMPFUNC((name)->set[UNIQVAR(i)], UNIQVAR(k))) {\
353 /* found key in set */\
354 UNIQVAR(r) = UNIQVAR(i);\
355 /*logI("already key");*/\
356 goto UNIQVAR(end);\
357 }\
358 if (astaticSetIsBucketEmpty(name,UNIQVAR(i))) {\
359 /* use empty bucket for key */\
360 (name)->set[UNIQVAR(i)] = UNIQVAR(k);\
361 UNIQVAR(r) = UNIQVAR(i);\
362 staticBitset1(&(name)->hasKey, UNIQVAR(i));\
363 /*logI("found a bucket");*/\
364 goto UNIQVAR(end);\
365 }\
366 } /* circular */\
367 UNIQVAR(r) = -1;\
368 } /* if (not CPMFUNC((name)->set[UNIQVAR(r)], UNIQVAR(k))) */\
369 }\
370 UNIQVAR(end):\
371 UNIQVAR(r);\
372 })
373
374 // vim: set expandtab ts=2 sw=2: