71 #define THASH_FACTOR_CRITICAL 2 75 #define THASH_FACTOR_REALLOC 4 77 #define TRRFN(root, suffix) root ## _ ## suffix 78 #define TRFN(root, suffix) TRRFN(root, suffix) 79 #define TFN(suffix) TRFN(TNAME, suffix) 81 #define TTYPENAME TFN(t) 95 struct TFN(_entry) *entries;
110 int nentries = _nentries;
111 if ((nentries & (nentries - 1)) != 0) {
113 while (nentries < _nentries)
117 assert((nentries & (nentries-1)) == 0);
120 hash->entries = calloc(hash->
nentries,
sizeof(
struct TFN(_entry)));
146 memset(hash->entries, 0, hash->nentries *
sizeof(
struct TFN(_entry)));
157 int min_run = hash->size;
161 memset(runs, 0,
sizeof(runs));
163 for (
int entry_idx = 0; entry_idx < hash->nentries; entry_idx++) {
164 if (!hash->entries[entry_idx].valid)
168 while (hash->entries[(entry_idx+this_run) & (hash->nentries - 1)].valid)
170 if (this_run < runs_sz)
172 if (this_run < min_run)
174 if (this_run > max_run)
178 run2 += this_run*this_run;
182 double Ex1 = 1.0 * run1 / cnt;
183 double Ex2 = 1.0 * run2 / cnt;
186 #define str(s) strr(s) 187 printf(
"%s: size %8d, nentries: %8d, min %3d, max %3d, mean %6.3f, stddev %6.3f\n",
189 hash->size, hash->nentries, min_run, max_run, Ex1, sqrt(Ex2 - Ex1*Ex1));
194 uint32_t code = TKEYHASH(key);
195 uint32_t entry_idx = code & (hash->nentries - 1);
197 while (hash->entries[entry_idx].valid) {
198 if (TKEYEQUAL(key, &hash->entries[entry_idx].key)) {
199 *value = &hash->entries[entry_idx].value;
203 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
209 static inline int TFN(
get)(
TTYPENAME *hash, TKEYTYPE *key, TVALTYPE *value)
214 uint32_t code = TKEYHASH(key);
215 uint32_t entry_idx = code & (hash->nentries - 1);
217 while (hash->entries[entry_idx].valid) {
218 if (TKEYEQUAL(key, &hash->entries[entry_idx].key)) {
219 *value = hash->entries[entry_idx].value;
223 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
229 static inline int TFN(
put)(
TTYPENAME *hash, TKEYTYPE *key, TVALTYPE *value, TKEYTYPE *oldkey, TVALTYPE *oldvalue)
231 uint32_t code = TKEYHASH(key);
232 uint32_t entry_idx = code & (hash->nentries - 1);
234 while (hash->entries[entry_idx].valid) {
235 if (TKEYEQUAL(key, &hash->entries[entry_idx].key)) {
237 *oldkey = hash->entries[entry_idx].key;
239 *oldvalue = hash->entries[entry_idx].value;
240 hash->entries[entry_idx].key = *key;
241 hash->entries[entry_idx].value = *value;
245 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
248 hash->entries[entry_idx].valid = 1;
249 hash->entries[entry_idx].key = *key;
250 hash->entries[entry_idx].value = *value;
260 for (
int entry_idx = 0; entry_idx < hash->nentries; entry_idx++) {
261 if (hash->entries[entry_idx].valid) {
263 if (
TFN(
put)(newhash, &hash->entries[entry_idx].key, &hash->entries[entry_idx].value, NULL, NULL))
271 memcpy(hash, newhash,
sizeof(
TTYPENAME));
272 memcpy(newhash, &tmp,
sizeof(
TTYPENAME));
282 static inline int TFN(
remove)(
TTYPENAME *hash, TKEYTYPE *key, TKEYTYPE *oldkey, TVALTYPE *oldvalue)
284 uint32_t code = TKEYHASH(key);
285 uint32_t entry_idx = code & (hash->nentries - 1);
287 while (hash->entries[entry_idx].valid) {
288 if (TKEYEQUAL(key, &hash->entries[entry_idx].key)) {
291 *oldkey = hash->entries[entry_idx].key;
293 *oldvalue = hash->entries[entry_idx].value;
295 hash->entries[entry_idx].valid = 0;
299 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
300 while (hash->entries[entry_idx].valid) {
301 TKEYTYPE key = hash->entries[entry_idx].key;
302 TVALTYPE value = hash->entries[entry_idx].value;
303 hash->entries[entry_idx].valid = 0;
306 if (
TFN(
put)(hash, &key, &value, NULL, NULL)) {
310 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
316 entry_idx = (entry_idx + 1) & (hash->nentries - 1);
326 for (
int entry_idx = 0; entry_idx < hash->nentries; entry_idx++) {
327 if (hash->entries[entry_idx].valid) {
328 if (
TFN(
put)(newhash, &hash->entries[entry_idx].key, &hash->entries[entry_idx].value, NULL, NULL))
336 typedef struct TFN(iterator)
TFN(iterator_t);
346 iter->last_entry = -1;
354 if (iter->last_entry+1 >= hash->
nentries)
359 if (hash->entries[iter->last_entry].valid) {
361 *outkey = hash->entries[iter->last_entry].key;
363 *outval = hash->entries[iter->last_entry].value;
373 hash->entries[iter->last_entry].valid = 0;
376 int entry_idx = (iter->last_entry + 1) & (hash->
nentries - 1);
377 while (hash->entries[entry_idx].valid) {
378 TKEYTYPE key = hash->entries[entry_idx].key;
379 TVALTYPE value = hash->entries[entry_idx].value;
380 hash->entries[entry_idx].valid = 0;
383 if (
TFN(
put)(hash, &key, &value, NULL, NULL)) {
387 entry_idx = (entry_idx + 1) & (hash->
nentries - 1);
static void TFN() performance(TTYPENAME *hash)
static int TFN() put(TTYPENAME *hash, TKEYTYPE *key, TVALTYPE *value, TKEYTYPE *oldkey, TVALTYPE *oldvalue)
static TTYPENAME *TFN() create()
static int TFN() iterator_next(TFN(iterator_t)*iter, TKEYTYPE *outkey, TVALTYPE *outval)
static void TFN() destroy(TTYPENAME *hash)
static TTYPENAME *TFN() create_capacity(int capacity)
static int TFN() size(TTYPENAME *hash)
static int TFN() get_volatile(TTYPENAME *hash, TKEYTYPE *key, TVALTYPE **value)
static void TFN() iterator_init(TTYPENAME *hash, TFN(iterator_t)*iter)
static void TFN() iterator_remove(TFN(iterator_t)*iter)
#define THASH_FACTOR_REALLOC
#define THASH_FACTOR_CRITICAL
static void TFN() clear(TTYPENAME *hash)
static TTYPENAME *TFN() copy(TTYPENAME *hash)