Lines Matching refs:dict
32 bitp(struct dict *dict, size_t n) in bitp() argument
34 return VECT_ELEMENT(&dict->status, struct status_bits, n); in bitp()
38 dict_init(struct dict *dict, in dict_init() argument
47 vect_init(&dict->keys, key_size); in dict_init()
48 vect_init(&dict->values, value_size); in dict_init()
49 VECT_INIT(&dict->status, struct status_bits); in dict_init()
50 dict->size = 0; in dict_init()
52 dict->hash1 = hash1; in dict_init()
53 dict->hash2 = hash2; in dict_init()
54 dict->eq = eq; in dict_init()
58 struct dict *target;
98 dict_clone(struct dict *target, const struct dict *source, in dict_clone()
113 if (dict_each((struct dict *)source, NULL, in dict_clone()
122 dict_size(const struct dict *dict) in dict_size() argument
124 return dict->size; in dict_size()
128 dict_empty(const struct dict *dict) in dict_empty() argument
130 return dict->size == 0; in dict_empty()
151 dict_destroy(struct dict *dict, in dict_destroy() argument
163 dict_each(dict, NULL, destroy_cb, &destroy_data); in dict_destroy()
166 vect_destroy(&dict->keys, NULL, NULL); in dict_destroy()
167 vect_destroy(&dict->values, NULL, NULL); in dict_destroy()
168 vect_destroy(&dict->status, NULL, NULL); in dict_destroy()
184 n(struct dict *dict) in n() argument
186 return vect_size(&dict->keys); in n()
190 hash2(struct dict *dict))(size_t) in hash2() argument
192 if (dict->hash2 != NULL) in hash2()
193 return dict->hash2; in hash2()
194 else if (n(dict) < 100) in hash2()
201 getkey(struct dict *dict, size_t pos) in getkey() argument
203 return ((unsigned char *)dict->keys.data) in getkey()
204 + dict->keys.elt_size * pos; in getkey()
208 getvalue(struct dict *dict, size_t pos) in getvalue() argument
210 return ((unsigned char *)dict->values.data) in getvalue()
211 + dict->values.elt_size * pos; in getvalue()
215 find_slot(struct dict *dict, const void *key, in find_slot() argument
218 assert(n(dict) > 0); in find_slot()
219 size_t pos = dict->hash1(key) % n(dict); in find_slot()
221 size_t d = hash2(dict)(pos); in find_slot()
228 for (; bitp(dict, pos)->taken || bitp(dict, pos)->erased; in find_slot()
229 pos = (pos + d) % n(dict)) { in find_slot()
230 if (pos0 == (size_t)-1 && bitp(dict, pos)->erased) in find_slot()
235 if (++i > dict->size) { in find_slot()
241 if (bitp(dict, pos)->taken in find_slot()
242 && dict->eq(getkey(dict, pos), key)) { in find_slot()
254 *should_rehash = i > 10 && i > n(dict) / 10; in find_slot()
271 rehash(struct dict *dict, size_t nn) in rehash() argument
273 assert(nn != n(dict)); in rehash()
276 struct dict tmp; in rehash()
277 dict_init(&tmp, dict->keys.elt_size, dict->values.elt_size, in rehash()
278 dict->hash1, dict->eq, dict->hash2); in rehash()
300 if (dict_each(dict, NULL, rehash_move, &tmp) != NULL) in rehash()
305 struct dict tmp2 = *dict; in rehash()
306 *dict = tmp; in rehash()
366 dict_insert(struct dict *dict, void *key, void *value) in dict_insert() argument
368 if (n(dict) == 0 || dict->size > 0.7 * n(dict)) in dict_insert()
370 if (rehash(dict, larger_size(n(dict))) < 0) in dict_insert()
375 size_t slot_n = find_slot(dict, key, &found, &should_rehash, NULL); in dict_insert()
380 assert(!bitp(dict, slot_n)->taken); in dict_insert()
385 if (should_rehash && dict->size > 0.3 * n(dict)) in dict_insert()
388 memmove(getkey(dict, slot_n), key, dict->keys.elt_size); in dict_insert()
389 memmove(getvalue(dict, slot_n), value, dict->values.elt_size); in dict_insert()
391 bitp(dict, slot_n)->taken = 1; in dict_insert()
392 bitp(dict, slot_n)->erased = 0; in dict_insert()
393 ++dict->size; in dict_insert()
399 dict_find(struct dict *dict, const void *key) in dict_find() argument
401 if (dict->size == 0) in dict_find()
403 assert(n(dict) > 0); in dict_find()
406 size_t slot_n = find_slot(dict, key, &found, NULL, NULL); in dict_find()
408 return getvalue(dict, slot_n); in dict_find()
414 dict_erase(struct dict *dict, const void *key, in dict_erase() argument
421 size_t slot_n = find_slot(dict, key, &found, NULL, &i); in dict_erase()
426 dtor_key(getkey(dict, slot_n), data); in dict_erase()
428 dtor_value(getvalue(dict, slot_n), data); in dict_erase()
430 bitp(dict, slot_n)->taken = 0; in dict_erase()
431 bitp(dict, slot_n)->erased = 1; in dict_erase()
432 --dict->size; in dict_erase()
434 if (dict->size < 0.3 * n(dict)) { in dict_erase()
435 size_t smaller = smaller_size(n(dict)); in dict_erase()
436 if (smaller != n(dict)) in dict_erase()
438 rehash(dict, smaller); in dict_erase()
445 dict_each(struct dict *dict, void *start_after, in dict_each() argument
450 i = ((start_after - dict->keys.data) / dict->keys.elt_size) + 1; in dict_each()
454 for (; i < dict->keys.size; ++i) in dict_each()
455 if (bitp(dict, i)->taken && !bitp(dict, i)->erased) { in dict_each()
456 void *key = getkey(dict, i); in dict_each()
457 if (cb(key, getvalue(dict, i), data) != CBS_CONT) in dict_each()
523 verify(struct dict *di, size_t len, char *seen) in verify()
544 struct dict di; in test1()
561 struct dict d2; in test1()
589 struct dict d2; in test_erase()
601 struct dict copy; in test_erase()