libkern/kxld/kxld_dict.c

70 static kern_return_t get_locate_index(const KXLDDict *dict, const void *key,
72 static kern_return_t get_insert_index(const KXLDDict *dict, const void *key,
74 static kern_return_t resize_dict(KXLDDict *dict);
79 kxld_dict_init(KXLDDict * dict, kxld_dict_hash hash, kxld_dict_cmp cmp,
86     check(dict);
99     rval = kxld_array_init(&dict->buckets, sizeof(DictEntry), num_buckets);
103     dict->hash = hash;
104     dict->cmp = cmp;
105     dict->num_entries = 0;
106     dict->resize_threshold = RESIZE_THRESHOLD(num_buckets);
117 kxld_dict_clear(KXLDDict *dict)
119     check(dict);
121     dict->hash = NULL;
122     dict->cmp = NULL;
123     dict->num_entries = 0;
124     dict->resize_threshold = 0;
125     kxld_array_clear(&dict->buckets);
126     kxld_array_clear(&dict->resize_buckets);
132 kxld_dict_iterator_init(KXLDDictIterator *iter, const KXLDDict *dict)
135     check(dict);
138     iter->dict = dict;
144 kxld_dict_deinit(KXLDDict *dict)
146     check(dict);
148     kxld_array_deinit(&dict->buckets);
149     kxld_array_deinit(&dict->resize_buckets);
155 kxld_dict_get_num_entries(const KXLDDict *dict)
157     check(dict);
159     return dict->num_entries;
165 kxld_dict_find(const KXLDDict *dict, const void *key)
171     check(dict);
174     rval = get_locate_index(dict, key, &idx);
177     entry = kxld_array_get_item(&dict->buckets, idx);
191 get_locate_index(const KXLDDict *dict, const void *key, u_int *_idx)
197     base = idx = dict->hash(dict, key);
200     entry = kxld_array_get_item(&dict->buckets, idx);
201     while (!dict->cmp(entry->key, key)) {
204         idx = (idx + 1) % dict->buckets.nitems;
207         entry = kxld_array_get_item(&dict->buckets, idx);
210     check(idx < dict->buckets.nitems);
222 kxld_dict_insert(KXLDDict *dict, const void *key, void *value)
228     check(dict);
236     while (dict->num_entries > dict->resize_threshold) {
237         rval = resize_dict(dict);
244     rval = get_insert_index(dict, key, &idx);
250     entry = kxld_array_get_item(&dict->buckets, idx);
252         dict->num_entries++;
269 resize_dict(KXLDDict *dict)
274     u_int nbuckets = (dict->buckets.nitems * 2 + 1);
277     check(dict);
280     rval = kxld_array_init(&dict->resize_buckets, sizeof(DictEntry), nbuckets);
284     tmparray = dict->buckets;
285     dict->buckets = dict->resize_buckets;
286     dict->resize_buckets = tmparray;
289     dict->num_entries = 0;
290     dict->resize_threshold = RESIZE_THRESHOLD(dict->buckets.nitems);
293     for (i = 0; i < dict->resize_buckets.nitems; ++i) {
294         entry = kxld_array_get_item(&dict->resize_buckets, i);
296             rval = kxld_dict_insert(dict, entry->key, entry->value);
302     kxld_array_clear(&dict->resize_buckets);
314 get_insert_index(const KXLDDict *dict, const void *key, u_int *r_index)
320     base = idx = dict->hash(dict, key);
325     entry = kxld_array_get_item(&dict->buckets, idx);
326     while (entry->state == USED && !dict->cmp(entry->key, key)) {
327         idx = (idx + 1) % dict->buckets.nitems;
329         entry = kxld_array_get_item(&dict->buckets, idx);
342 kxld_dict_remove(KXLDDict *dict, const void *key, void **value)
348     check(dict);
352     rval = get_locate_index(dict, key, &idx);
358     entry = kxld_array_get_item(&dict->buckets, idx);
367     dict->num_entries--;
386     for (; iter->idx < iter->dict->buckets.nitems; ++(iter->idx)) {
387         entry = kxld_array_get_item(&iter->dict->buckets, iter->idx);
411 kxld_dict_string_hash(const KXLDDict *dict, const void *_key)
417     check(dict);
425     return (hash_val % dict->buckets.nitems);
429 kxld_dict_uint32_hash(const KXLDDict *dict, const void *_key)
435     return (u_int) (key % dict->buckets.nitems);
439 kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *_key)
445     return (u_int) (key % dict->buckets.nitems);