Lines Matching full:hash
96 static void *util_data_allocate_node(struct util_hash_data *hash) in util_data_allocate_node() argument
98 return malloc(hash->nodeSize); in util_data_allocate_node()
107 util_hash_create_node(struct util_hash *hash, in util_hash_create_node() argument
111 struct util_node *node = util_data_allocate_node(hash->data.d); in util_hash_create_node()
121 ++hash->data.d->size; in util_hash_create_node()
125 static void util_data_rehash(struct util_hash_data *hash, int hint) in util_data_rehash() argument
131 hash->userNumBits = (short)hint; in util_data_rehash()
132 while (primeForNumBits(hint) < (hash->size >> 1)) in util_data_rehash()
138 if (hash->numBits != hint) { in util_data_rehash()
139 struct util_node *e = (struct util_node *)(hash); in util_data_rehash()
140 struct util_node **oldBuckets = hash->buckets; in util_data_rehash()
141 int oldNumBuckets = hash->numBuckets; in util_data_rehash()
144 hash->numBits = (short)hint; in util_data_rehash()
145 hash->numBuckets = primeForNumBits(hint); in util_data_rehash()
146 hash->buckets = malloc(sizeof(struct util_node*) * hash->numBuckets); in util_data_rehash()
147 for (i = 0; i < hash->numBuckets; ++i) in util_data_rehash()
148 hash->buckets[i] = e; in util_data_rehash()
162 beforeFirstNode = &hash->buckets[h % hash->numBuckets]; in util_data_rehash()
174 static void util_data_might_grow(struct util_hash_data *hash) in util_data_might_grow() argument
176 if (hash->size >= hash->numBuckets) in util_data_might_grow()
177 util_data_rehash(hash, hash->numBits + 1); in util_data_might_grow()
180 static void util_data_has_shrunk(struct util_hash_data *hash) in util_data_has_shrunk() argument
182 if (hash->size <= (hash->numBuckets >> 3) && in util_data_has_shrunk()
183 hash->numBits > hash->userNumBits) { in util_data_has_shrunk()
184 int max = MAX(hash->numBits-2, hash->userNumBits); in util_data_has_shrunk()
185 util_data_rehash(hash, max); in util_data_has_shrunk()
189 static struct util_node *util_data_first_node(struct util_hash_data *hash) in util_data_first_node() argument
191 struct util_node *e = (struct util_node *)(hash); in util_data_first_node()
192 struct util_node **bucket = hash->buckets; in util_data_first_node()
193 int n = hash->numBuckets; in util_data_first_node()
202 static struct util_node **util_hash_find_node(struct util_hash *hash, unsigned akey) in util_hash_find_node() argument
206 if (hash->data.d->numBuckets) { in util_hash_find_node()
207 node = (struct util_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); in util_hash_find_node()
208 assert(*node == hash->data.e || (*node)->next); in util_hash_find_node()
209 while (*node != hash->data.e && (*node)->key != akey) in util_hash_find_node()
212 node = (struct util_node **)((const struct util_node * const *)(&hash->data.e)); in util_hash_find_node()
218 util_hash_insert(struct util_hash *hash, unsigned key, void *data) in util_hash_insert() argument
220 util_data_might_grow(hash->data.d); in util_hash_insert()
223 struct util_node **nextNode = util_hash_find_node(hash, key); in util_hash_insert()
224 struct util_node *node = util_hash_create_node(hash, key, data, nextNode); in util_hash_insert()
226 struct util_hash_iter null_iter = {hash, 0}; in util_hash_insert()
231 struct util_hash_iter iter = {hash, node}; in util_hash_insert()
239 struct util_hash *hash = malloc(sizeof(struct util_hash)); in util_hash_create() local
240 if (!hash) in util_hash_create()
243 hash->data.d = malloc(sizeof(struct util_hash_data)); in util_hash_create()
244 if (!hash->data.d) { in util_hash_create()
245 free(hash); in util_hash_create()
249 hash->data.d->fakeNext = 0; in util_hash_create()
250 hash->data.d->buckets = 0; in util_hash_create()
251 hash->data.d->size = 0; in util_hash_create()
252 hash->data.d->nodeSize = sizeof(struct util_node); in util_hash_create()
253 hash->data.d->userNumBits = (short)MinNumBits; in util_hash_create()
254 hash->data.d->numBits = 0; in util_hash_create()
255 hash->data.d->numBuckets = 0; in util_hash_create()
257 return hash; in util_hash_create()
260 drm_private void util_hash_delete(struct util_hash *hash) in util_hash_delete() argument
262 struct util_node *e_for_x = (struct util_node *)(hash->data.d); in util_hash_delete()
263 struct util_node **bucket = (struct util_node **)(hash->data.d->buckets); in util_hash_delete()
264 int n = hash->data.d->numBuckets; in util_hash_delete()
273 free(hash->data.d->buckets); in util_hash_delete()
274 free(hash->data.d); in util_hash_delete()
275 free(hash); in util_hash_delete()
279 util_hash_find(struct util_hash *hash, unsigned key) in util_hash_find() argument
281 struct util_node **nextNode = util_hash_find_node(hash, key); in util_hash_find()
282 struct util_hash_iter iter = {hash, *nextNode}; in util_hash_find()
288 if (!iter.node || iter.hash->data.e == iter.node) in util_hash_iter_key()
295 if (!iter.node || iter.hash->data.e == iter.node) in util_hash_iter_data()
333 struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)}; in util_hash_iter_next()
339 if (!iter.node || iter.node == iter.hash->data.e) in util_hash_iter_is_null()
344 drm_private void *util_hash_take(struct util_hash *hash, unsigned akey) in util_hash_take() argument
346 struct util_node **node = util_hash_find_node(hash, akey); in util_hash_take()
347 if (*node != hash->data.e) { in util_hash_take()
352 --hash->data.d->size; in util_hash_take()
353 util_data_has_shrunk(hash->data.d); in util_hash_take()
359 drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash) in util_hash_first_node() argument
361 struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)}; in util_hash_first_node()
366 util_hash_erase(struct util_hash *hash, struct util_hash_iter iter) in util_hash_erase() argument
372 if (node == hash->data.e) in util_hash_erase()
376 node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); in util_hash_erase()
381 --hash->data.d->size; in util_hash_erase()