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: