Lines Matching defs:htable
54 static unsigned int ares__htable_generate_seed(ares__htable_t *htable)
62 seed |= (unsigned int)((size_t)htable & 0xFFFFFFFF);
93 void ares__htable_destroy(ares__htable_t *htable)
95 if (htable == NULL) {
98 ares__htable_buckets_destroy(htable->buckets, htable->size, ARES_TRUE);
99 ares_free(htable);
107 ares__htable_t *htable = NULL;
114 htable = ares_malloc_zero(sizeof(*htable));
115 if (htable == NULL) {
119 htable->hash = hash_func;
120 htable->bucket_key = bucket_key;
121 htable->bucket_free = bucket_free;
122 htable->key_eq = key_eq;
123 htable->seed = ares__htable_generate_seed(htable);
124 htable->size = ARES__HTABLE_MIN_BUCKETS;
125 htable->buckets = ares_malloc_zero(sizeof(*htable->buckets) * htable->size);
127 if (htable->buckets == NULL) {
131 return htable;
134 ares__htable_destroy(htable);
138 const void **ares__htable_all_buckets(const ares__htable_t *htable, size_t *num)
144 if (htable == NULL || num == NULL) {
150 out = ares_malloc_zero(sizeof(*out) * htable->num_keys);
155 for (i = 0; i < htable->size; i++) {
157 for (node = ares__llist_node_first(htable->buckets[i]); node != NULL;
174 static ares__llist_node_t *ares__htable_find(const ares__htable_t *htable,
179 for (node = ares__llist_node_first(htable->buckets[idx]); node != NULL;
181 if (htable->key_eq(key, htable->bucket_key(ares__llist_node_val(node)))) {
189 static ares_bool_t ares__htable_expand(ares__htable_t *htable)
192 unsigned int old_size = htable->size;
203 htable->size <<= 1;
208 buckets = ares_malloc_zero(sizeof(*buckets) * htable->size);
215 prealloc_llist_len = htable->num_collisions;
224 prealloc_llist[i] = ares__llist_create(htable->bucket_free);
231 htable->num_collisions = 0;
236 if (htable->buckets[i] == NULL) {
243 if (ares__llist_len(htable->buckets[i]) == 1) {
244 const void *val = ares__llist_first_val(htable->buckets[i]);
245 size_t idx = HASH_IDX(htable, htable->bucket_key(val));
249 buckets[idx] = htable->buckets[i];
250 htable->buckets[i] = NULL;
256 while ((node = ares__llist_node_first(htable->buckets[i])) != NULL) {
258 size_t idx = HASH_IDX(htable, htable->bucket_key(val));
262 if (buckets[idx] == NULL && ares__llist_len(htable->buckets[i]) == 1) {
264 buckets[idx] = htable->buckets[i];
265 htable->buckets[i] = NULL;
279 htable->num_collisions++;
286 if (htable->buckets[i] != NULL) {
287 ares__llist_destroy(htable->buckets[i]);
288 htable->buckets[i] = NULL;
294 ares_free(htable->buckets);
295 htable->buckets = buckets;
305 /* On failure, we need to restore the htable size */
307 htable->size = old_size;
313 ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket)
319 if (htable == NULL || bucket == NULL) {
324 key = htable->bucket_key(bucket);
325 idx = HASH_IDX(htable, key);
328 node = ares__htable_find(htable, idx, key);
336 if (htable->num_keys + 1 >
337 (htable->size * ARES__HTABLE_EXPAND_PERCENT) / 100) {
338 if (!ares__htable_expand(htable)) {
342 idx = HASH_IDX(htable, key);
346 if (htable->buckets[idx] == NULL) {
347 htable->buckets[idx] = ares__llist_create(htable->bucket_free);
348 if (htable->buckets[idx] == NULL) {
353 node = ares__llist_insert_first(htable->buckets[idx], bucket);
359 if (ares__llist_len(htable->buckets[idx]) > 1) {
360 htable->num_collisions++;
363 htable->num_keys++;
368 void *ares__htable_get(const ares__htable_t *htable, const void *key)
372 if (htable == NULL || key == NULL) {
376 idx = HASH_IDX(htable, key);
378 return ares__llist_node_val(ares__htable_find(htable, idx, key));
381 ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key)
386 if (htable == NULL || key == NULL) {
390 idx = HASH_IDX(htable, key);
391 node = ares__htable_find(htable, idx, key);
396 htable->num_keys--;
400 htable->num_collisions--;
407 size_t ares__htable_num_keys(const ares__htable_t *htable)
409 if (htable == NULL) {
412 return htable->num_keys;