Lines Matching refs:hash
97 static void *cso_data_allocate_node(struct cso_hash_data *hash)
99 return MALLOC(hash->nodeSize);
108 cso_hash_create_node(struct cso_hash *hash,
112 struct cso_node *node = cso_data_allocate_node(hash->data.d);
122 ++hash->data.d->size;
126 static void cso_data_rehash(struct cso_hash_data *hash, int hint)
132 hash->userNumBits = (short)hint;
133 while (primeForNumBits(hint) < (hash->size >> 1))
139 if (hash->numBits != hint) {
140 struct cso_node *e = (struct cso_node *)(hash);
141 struct cso_node **oldBuckets = hash->buckets;
142 int oldNumBuckets = hash->numBuckets;
145 hash->numBits = (short)hint;
146 hash->numBuckets = primeForNumBits(hint);
147 hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
148 for (i = 0; i < hash->numBuckets; ++i)
149 hash->buckets[i] = e;
163 beforeFirstNode = &hash->buckets[h % hash->numBuckets];
175 static void cso_data_might_grow(struct cso_hash_data *hash)
177 if (hash->size >= hash->numBuckets)
178 cso_data_rehash(hash, hash->numBits + 1);
181 static void cso_data_has_shrunk(struct cso_hash_data *hash)
183 if (hash->size <= (hash->numBuckets >> 3) &&
184 hash->numBits > hash->userNumBits) {
185 int max = MAX(hash->numBits-2, hash->userNumBits);
186 cso_data_rehash(hash, max);
190 static struct cso_node *cso_data_first_node(struct cso_hash_data *hash)
192 struct cso_node *e = (struct cso_node *)(hash);
193 struct cso_node **bucket = hash->buckets;
194 int n = hash->numBuckets;
203 static struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey)
207 if (hash->data.d->numBuckets) {
208 node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
209 assert(*node == hash->data.e || (*node)->next);
210 while (*node != hash->data.e && (*node)->key != akey)
213 node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
218 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
221 cso_data_might_grow(hash->data.d);
224 struct cso_node **nextNode = cso_hash_find_node(hash, key);
225 struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
227 struct cso_hash_iter null_iter = {hash, 0};
232 struct cso_hash_iter iter = {hash, node};
240 struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
241 if (!hash)
244 hash->data.d = MALLOC_STRUCT(cso_hash_data);
245 if (!hash->data.d) {
246 FREE(hash);
250 hash->data.d->fakeNext = 0;
251 hash->data.d->buckets = 0;
252 hash->data.d->size = 0;
253 hash->data.d->nodeSize = sizeof(struct cso_node);
254 hash->data.d->userNumBits = (short)MinNumBits;
255 hash->data.d->numBits = 0;
256 hash->data.d->numBuckets = 0;
258 return hash;
261 void cso_hash_delete(struct cso_hash *hash)
263 struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
264 struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
265 int n = hash->data.d->numBuckets;
274 FREE(hash->data.d->buckets);
275 FREE(hash->data.d);
276 FREE(hash);
279 struct cso_hash_iter cso_hash_find(struct cso_hash *hash,
282 struct cso_node **nextNode = cso_hash_find_node(hash, key);
283 struct cso_hash_iter iter = {hash, *nextNode};
289 if (!iter.node || iter.hash->data.e == iter.node)
296 if (!iter.node || iter.hash->data.e == iter.node)
371 struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
377 if (!iter.node || iter.node == iter.hash->data.e)
382 void * cso_hash_take(struct cso_hash *hash,
385 struct cso_node **node = cso_hash_find_node(hash, akey);
386 if (*node != hash->data.e) {
391 --hash->data.d->size;
392 cso_data_has_shrunk(hash->data.d);
400 struct cso_hash_iter prev = {iter.hash,
405 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
407 struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)};
411 int cso_hash_size(struct cso_hash *hash)
413 return hash->data.d->size;
416 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
422 if (node == hash->data.e)
426 node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
431 --hash->data.d->size;
435 boolean cso_hash_contains(struct cso_hash *hash, unsigned key)
437 struct cso_node **node = cso_hash_find_node(hash, key);
438 return (*node != hash->data.e);