Lines Matching defs:table
50 struct hash_table *table;
61 static bool hash_table_resize(struct hash_table *table, bool grow);
67 struct hash_table *table;
70 table = i_new(struct hash_table, 1);
71 table->node_pool = node_pool;
72 table->initial_size =
75 table->hash_cb = hash_cb;
76 table->key_compare_cb = key_compare_cb;
78 table->size = table->initial_size;
79 table->nodes = i_new(struct hash_node, table->size);
80 *table_r = table;
101 static void free_node(struct hash_table *table, struct hash_node *node)
103 if (!table->node_pool->alloconly_pool)
104 p_free(table->node_pool, node);
106 node->next = table->free_nodes;
107 table->free_nodes = node;
111 static void destroy_node_list(struct hash_table *table, struct hash_node *node)
117 p_free(table->node_pool, node);
122 static void hash_table_destroy_nodes(struct hash_table *table)
126 for (i = 0; i < table->size; i++) {
127 if (table->nodes[i].next != NULL)
128 destroy_node_list(table, table->nodes[i].next);
134 struct hash_table *table = *_table;
138 i_assert(table->frozen == 0);
140 if (!table->node_pool->alloconly_pool) {
141 hash_table_destroy_nodes(table);
142 destroy_node_list(table, table->free_nodes);
145 pool_unref(&table->node_pool);
146 i_free(table->nodes);
147 i_free(table);
150 void hash_table_clear(struct hash_table *table, bool free_nodes)
152 i_assert(table->frozen == 0);
154 if (!table->node_pool->alloconly_pool)
155 hash_table_destroy_nodes(table);
158 if (!table->node_pool->alloconly_pool)
159 destroy_node_list(table, table->free_nodes);
160 table->free_nodes = NULL;
163 memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
165 table->nodes_count = 0;
166 table->removed_count = 0;
170 hash_table_lookup_node(const struct hash_table *table,
175 node = &table->nodes[hash % table->size];
179 if (table->key_compare_cb(node->key, key) == 0)
188 void *hash_table_lookup(const struct hash_table *table, const void *key)
192 node = hash_table_lookup_node(table, key, table->hash_cb(key));
196 bool hash_table_lookup_full(const struct hash_table *table,
202 node = hash_table_lookup_node(table, lookup_key,
203 table->hash_cb(lookup_key));
213 hash_table_insert_node(struct hash_table *table, void *key, void *value,
224 hash = table->hash_cb(key);
226 if (check_existing && table->removed_count > 0) {
228 node = hash_table_lookup_node(table, key, hash);
239 node = &table->nodes[hash % table->size];
241 table->nodes_count++;
248 if (table->key_compare_cb(node->key, key) == 0) {
262 if (table->key_compare_cb(node->key, key) == 0) {
273 if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
274 /* resized table, try again */
275 hash_table_insert_node(table, key, value, HASH_TABLE_OP_RESIZE);
279 if (table->free_nodes == NULL)
280 node = p_new(table->node_pool, struct hash_node, 1);
282 node = table->free_nodes;
283 table->free_nodes = node->next;
292 table->nodes_count++;
295 void hash_table_insert(struct hash_table *table, void *key, void *value)
297 hash_table_insert_node(table, key, value, HASH_TABLE_OP_INSERT);
300 void hash_table_update(struct hash_table *table, void *key, void *value)
302 hash_table_insert_node(table, key, value, HASH_TABLE_OP_UPDATE);
306 hash_table_compress(struct hash_table *table, struct hash_node *root)
310 i_assert(table->frozen == 0);
318 free_node(table, next);
328 free_node(table, next);
332 static void hash_table_compress_removed(struct hash_table *table)
336 for (i = 0; i < table->size; i++)
337 hash_table_compress(table, &table->nodes[i]);
339 table->removed_count = 0;
342 bool hash_table_try_remove(struct hash_table *table, const void *key)
347 hash = table->hash_cb(key);
349 node = hash_table_lookup_node(table, key, hash);
354 table->nodes_count--;
356 if (table->frozen != 0)
357 table->removed_count++;
358 else if (!hash_table_resize(table, FALSE))
359 hash_table_compress(table, &table->nodes[hash % table->size]);
363 unsigned int hash_table_count(const struct hash_table *table)
365 return table->nodes_count;
368 struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table)
372 hash_table_freeze(table);
375 ctx->table = table;
376 ctx->next = &table->nodes[0];
387 if (++ctx->pos == ctx->table->size) {
391 node = &ctx->table->nodes[ctx->pos];
422 hash_table_thaw(ctx->table);
426 void hash_table_freeze(struct hash_table *table)
428 table->frozen++;
431 void hash_table_thaw(struct hash_table *table)
433 i_assert(table->frozen > 0);
435 if (--table->frozen > 0)
438 if (table->removed_count > 0) {
439 if (!hash_table_resize(table, FALSE))
440 hash_table_compress_removed(table);
444 static bool hash_table_resize(struct hash_table *table, bool grow)
450 i_assert(table->frozen == 0);
452 nodes_per_list = (float) table->nodes_count / (float) table->size;
456 next_size = I_MAX(primes_closest(table->nodes_count+1),
457 table->initial_size);
458 if (next_size == table->size)
461 if (grow && table->size >= next_size)
464 /* recreate primary table */
465 old_size = table->size;
466 old_nodes = table->nodes;
468 table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE);
469 table->nodes = i_new(struct hash_node, table->size);
471 table->nodes_count = 0;
472 table->removed_count = 0;
474 table->frozen++;
480 hash_table_insert_node(table, node->key,
488 hash_table_insert_node(table, node->key,
491 free_node(table, node);
495 table->frozen--;