Lines Matching refs:hash
100 static void *util_data_allocate_node(struct util_hash_data *hash) in util_data_allocate_node() argument
102 return malloc(hash->nodeSize); in util_data_allocate_node()
111 util_hash_create_node(struct util_hash *hash, in util_hash_create_node() argument
115 struct util_node *node = util_data_allocate_node(hash->data.d); in util_hash_create_node()
125 ++hash->data.d->size; in util_hash_create_node()
129 static void util_data_rehash(struct util_hash_data *hash, int hint) in util_data_rehash() argument
135 hash->userNumBits = (short)hint; in util_data_rehash()
136 while (primeForNumBits(hint) < (hash->size >> 1)) in util_data_rehash()
142 if (hash->numBits != hint) { in util_data_rehash()
143 struct util_node *e = (struct util_node *)(hash); in util_data_rehash()
144 struct util_node **oldBuckets = hash->buckets; in util_data_rehash()
145 int oldNumBuckets = hash->numBuckets; in util_data_rehash()
148 hash->numBits = (short)hint; in util_data_rehash()
149 hash->numBuckets = primeForNumBits(hint); in util_data_rehash()
150 hash->buckets = malloc(sizeof(struct util_node*) * hash->numBuckets); in util_data_rehash()
151 for (i = 0; i < hash->numBuckets; ++i) in util_data_rehash()
152 hash->buckets[i] = e; in util_data_rehash()
166 beforeFirstNode = &hash->buckets[h % hash->numBuckets]; in util_data_rehash()
178 static void util_data_might_grow(struct util_hash_data *hash) in util_data_might_grow() argument
180 if (hash->size >= hash->numBuckets) in util_data_might_grow()
181 util_data_rehash(hash, hash->numBits + 1); in util_data_might_grow()
184 static void util_data_has_shrunk(struct util_hash_data *hash) in util_data_has_shrunk() argument
186 if (hash->size <= (hash->numBuckets >> 3) && in util_data_has_shrunk()
187 hash->numBits > hash->userNumBits) { in util_data_has_shrunk()
188 int max = MAX(hash->numBits-2, hash->userNumBits); in util_data_has_shrunk()
189 util_data_rehash(hash, max); in util_data_has_shrunk()
193 static struct util_node *util_data_first_node(struct util_hash_data *hash) in util_data_first_node() argument
195 struct util_node *e = (struct util_node *)(hash); in util_data_first_node()
196 struct util_node **bucket = hash->buckets; in util_data_first_node()
197 int n = hash->numBuckets; in util_data_first_node()
206 static struct util_node **util_hash_find_node(struct util_hash *hash, unsigned akey) in util_hash_find_node() argument
210 if (hash->data.d->numBuckets) { in util_hash_find_node()
211 node = (struct util_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); in util_hash_find_node()
212 assert(*node == hash->data.e || (*node)->next); in util_hash_find_node()
213 while (*node != hash->data.e && (*node)->key != akey) in util_hash_find_node()
216 node = (struct util_node **)((const struct util_node * const *)(&hash->data.e)); in util_hash_find_node()
222 util_hash_insert(struct util_hash *hash, unsigned key, void *data) in util_hash_insert() argument
224 util_data_might_grow(hash->data.d); in util_hash_insert()
227 struct util_node **nextNode = util_hash_find_node(hash, key); in util_hash_insert()
228 struct util_node *node = util_hash_create_node(hash, key, data, nextNode); in util_hash_insert()
230 struct util_hash_iter null_iter = {hash, 0}; in util_hash_insert()
235 struct util_hash_iter iter = {hash, node}; in util_hash_insert()
243 struct util_hash *hash = malloc(sizeof(struct util_hash)); in util_hash_create() local
244 if (!hash) in util_hash_create()
247 hash->data.d = malloc(sizeof(struct util_hash_data)); in util_hash_create()
248 if (!hash->data.d) { in util_hash_create()
249 free(hash); in util_hash_create()
253 hash->data.d->fakeNext = 0; in util_hash_create()
254 hash->data.d->buckets = 0; in util_hash_create()
255 hash->data.d->size = 0; in util_hash_create()
256 hash->data.d->nodeSize = sizeof(struct util_node); in util_hash_create()
257 hash->data.d->userNumBits = (short)MinNumBits; in util_hash_create()
258 hash->data.d->numBits = 0; in util_hash_create()
259 hash->data.d->numBuckets = 0; in util_hash_create()
261 return hash; in util_hash_create()
264 drm_private void util_hash_delete(struct util_hash *hash) in util_hash_delete() argument
266 struct util_node *e_for_x = (struct util_node *)(hash->data.d); in util_hash_delete()
267 struct util_node **bucket = (struct util_node **)(hash->data.d->buckets); in util_hash_delete()
268 int n = hash->data.d->numBuckets; in util_hash_delete()
277 free(hash->data.d->buckets); in util_hash_delete()
278 free(hash->data.d); in util_hash_delete()
279 free(hash); in util_hash_delete()
283 util_hash_find(struct util_hash *hash, unsigned key) in util_hash_find() argument
285 struct util_node **nextNode = util_hash_find_node(hash, key); in util_hash_find()
286 struct util_hash_iter iter = {hash, *nextNode}; in util_hash_find()
292 if (!iter.node || iter.hash->data.e == iter.node) in util_hash_iter_key()
299 if (!iter.node || iter.hash->data.e == iter.node) in util_hash_iter_data()
337 struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)}; in util_hash_iter_next()
343 if (!iter.node || iter.node == iter.hash->data.e) in util_hash_iter_is_null()
348 drm_private void *util_hash_take(struct util_hash *hash, unsigned akey) in util_hash_take() argument
350 struct util_node **node = util_hash_find_node(hash, akey); in util_hash_take()
351 if (*node != hash->data.e) { in util_hash_take()
356 --hash->data.d->size; in util_hash_take()
357 util_data_has_shrunk(hash->data.d); in util_hash_take()
363 drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash) in util_hash_first_node() argument
365 struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)}; in util_hash_first_node()
370 util_hash_erase(struct util_hash *hash, struct util_hash_iter iter) in util_hash_erase() argument
376 if (node == hash->data.e) in util_hash_erase()
380 node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); in util_hash_erase()
385 --hash->data.d->size; in util_hash_erase()