Mercurial > dovecot > core-2.2
view src/lib/hash.c @ 1741:9df02b1533b3 HEAD
Removed most of the license comments from src/lib/*.c. It's just fine to
keep them in a single COPYING.MIT file. Changed a few other comments as well.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Wed, 27 Aug 2003 00:18:16 +0300 |
parents | 60646878858e |
children | 1e6ed8045f2b |
line wrap: on
line source
/* Copyright (c) 2002-2003 Timo Sirainen */ /* @UNSAFE: whole file */ #include "lib.h" #include "hash.h" #include "primes.h" #include <ctype.h> #define HASH_TABLE_MIN_SIZE 109 struct hash_node { struct hash_node *next; void *key; void *value; }; struct hash_table { pool_t table_pool, node_pool; int frozen; size_t initial_size, nodes_count, removed_count; size_t size; struct hash_node *nodes; struct hash_node *free_nodes; hash_callback_t *hash_cb; hash_cmp_callback_t *key_compare_cb; }; static int hash_resize(struct hash_table *table, int grow); static int foreach_stop; static int direct_cmp(const void *p1, const void *p2) { return p1 == p2 ? 0 : 1; } static unsigned int direct_hash(const void *p) { /* NOTE: may truncate the value, but that doesn't matter. */ return POINTER_CAST_TO(p, unsigned int); } struct hash_table * hash_create(pool_t table_pool, pool_t node_pool, size_t initial_size, hash_callback_t *hash_cb, hash_cmp_callback_t *key_compare_cb) { struct hash_table *table; initial_size = 0; table = p_new(table_pool, struct hash_table, 1); table->table_pool = table_pool; table->node_pool = node_pool; table->initial_size = I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE); table->hash_cb = hash_cb != NULL ? hash_cb : direct_hash; table->key_compare_cb = key_compare_cb == NULL ? direct_cmp : key_compare_cb; table->size = table->initial_size; table->nodes = p_new(table_pool, struct hash_node, table->size); return table; } static void free_node(struct hash_table *table, struct hash_node *node) { if (!table->node_pool->alloconly_pool) p_free(table->node_pool, node); else { node->next = table->free_nodes; table->free_nodes = node; } } static void destroy_node_list(struct hash_table *table, struct hash_node *node) { struct hash_node *next; while (node != NULL) { next = node->next; p_free(table->node_pool, node); node = next; } } static void hash_destroy_nodes(struct hash_table *table) { size_t i; for (i = 0; i < table->size; i++) { if (table->nodes[i].next != NULL) destroy_node_list(table, table->nodes[i].next); } } void hash_destroy(struct hash_table *table) { if (!table->node_pool->alloconly_pool) { hash_destroy_nodes(table); destroy_node_list(table, table->free_nodes); } p_free(table->table_pool, table->nodes); p_free(table->table_pool, table); } void hash_clear(struct hash_table *table, int free_nodes) { if (!table->node_pool->alloconly_pool) hash_destroy_nodes(table); if (free_nodes) { if (!table->node_pool->alloconly_pool) destroy_node_list(table, table->free_nodes); table->free_nodes = NULL; } memset(table->nodes, 0, sizeof(struct hash_node) * table->size); table->nodes_count = 0; table->removed_count = 0; } static struct hash_node * hash_lookup_node(struct hash_table *table, const void *key, unsigned int hash) { struct hash_node *node; node = &table->nodes[hash % table->size]; do { if (node->key != NULL) { if (table->key_compare_cb(node->key, key) == 0) return node; } node = node->next; } while (node != NULL); return NULL; } void *hash_lookup(struct hash_table *table, const void *key) { struct hash_node *node; node = hash_lookup_node(table, key, table->hash_cb(key)); return node != NULL ? node->value : NULL; } int hash_lookup_full(struct hash_table *table, const void *lookup_key, void **orig_key, void **value) { struct hash_node *node; node = hash_lookup_node(table, lookup_key, table->hash_cb(lookup_key)); if (node == NULL) return FALSE; if (orig_key != NULL) *orig_key = node->key; if (value != NULL) *value = node->value; return TRUE; } static struct hash_node * hash_insert_node(struct hash_table *table, void *key, void *value, int check_existing) { struct hash_node *node, *prev; unsigned int hash; i_assert(key != NULL); hash = table->hash_cb(key); if (check_existing && table->removed_count > 0) { /* there may be holes, have to check everything */ node = hash_lookup_node(table, key, hash); if (node != NULL) { node->value = value; return node; } check_existing = FALSE; } /* a) primary node */ node = &table->nodes[hash % table->size]; if (node->key == NULL) { table->nodes_count++; node->key = key; node->value = value; return node; } if (check_existing) { if (table->key_compare_cb(node->key, key) == 0) { node->value = value; return node; } } /* b) collisions list */ prev = node; node = node->next; while (node != NULL) { if (node->key == NULL) break; if (check_existing) { if (table->key_compare_cb(node->key, key) == 0) { node->value = value; return node; } } prev = node; node = node->next; } if (node == NULL) { if (table->frozen == 0 && hash_resize(table, TRUE)) { /* resized table, try again */ return hash_insert_node(table, key, value, FALSE); } if (table->free_nodes == NULL) node = p_new(table->node_pool, struct hash_node, 1); else { node = table->free_nodes; table->free_nodes = node->next; node->next = NULL; } prev->next = node; } node->key = key; node->value = value;; table->nodes_count++; return node; } void hash_insert(struct hash_table *table, void *key, void *value) { struct hash_node *node; node = hash_insert_node(table, key, value, TRUE); node->key = key; } void hash_update(struct hash_table *table, void *key, void *value) { (void)hash_insert_node(table, key, value, TRUE); } static void hash_compress(struct hash_table *table, struct hash_node *node) { struct hash_node *next; /* remove deleted nodes from the list */ while (node->next != NULL) { next = node->next; if (next->key == NULL) { node->next = next->next; free_node(table, next); } else { node = next; } } /* update root */ if (node->key == NULL && node->next != NULL) { next = node->next; memcpy(node, next, sizeof(*node)); free_node(table, next); } } static void hash_compress_removed(struct hash_table *table) { size_t i; for (i = 0; i < table->size; i++) hash_compress(table, &table->nodes[i]); table->removed_count = 0; } void hash_remove(struct hash_table *table, const void *key) { struct hash_node *node; unsigned int hash; hash = table->hash_cb(key); node = hash_lookup_node(table, key, hash); if (node == NULL) i_panic("key not found from hash"); node->key = NULL; table->nodes_count--; if (table->frozen != 0) table->removed_count++; else if (!hash_resize(table, FALSE)) hash_compress(table, &table->nodes[hash % table->size]); } size_t hash_size(struct hash_table *table) { return table->nodes_count; } void hash_foreach(struct hash_table *table, hash_foreach_callback_t *callback, void *context) { struct hash_node *node; size_t i; hash_freeze(table); foreach_stop = FALSE; for (i = 0; i < table->size; i++) { node = &table->nodes[i]; do { if (node->key != NULL) { callback(node->key, node->value, context); if (foreach_stop) { table->frozen--; return; } } node = node->next; } while (node != NULL); } hash_thaw(table); } void hash_foreach_stop(void) { foreach_stop = TRUE; } void hash_freeze(struct hash_table *table) { table->frozen++; } void hash_thaw(struct hash_table *table) { i_assert(table->frozen > 0); if (--table->frozen > 0) return; if (table->removed_count > 0) { if (!hash_resize(table, FALSE)) hash_compress_removed(table); } } static int hash_resize(struct hash_table *table, int grow) { struct hash_node *old_nodes, *node, *next; size_t next_size, old_size, i; float nodes_per_list; nodes_per_list = (float) table->nodes_count / (float) table->size; if (nodes_per_list > 0.3 && nodes_per_list < 2.0) return FALSE; next_size = I_MAX(primes_closest(table->nodes_count+1), table->initial_size); if (next_size == table->size) return FALSE; if (grow && table->size >= next_size) return FALSE; /* recreate primary table */ old_size = table->size; old_nodes = table->nodes; table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE); table->nodes = p_new(table->table_pool, struct hash_node, table->size); table->nodes_count = 0; table->removed_count = 0; table->frozen++; /* move the data */ for (i = 0; i < old_size; i++) { node = &old_nodes[i]; if (node->key != NULL) hash_insert_node(table, node->key, node->value, FALSE); for (node = node->next; node != NULL; node = next) { next = node->next; if (node->key != NULL) { hash_insert_node(table, node->key, node->value, FALSE); } free_node(table, node); } } table->frozen--; p_free(table->table_pool, old_nodes); return TRUE; } /* a char* hash function from ASU -- from glib */ unsigned int str_hash(const void *p) { const unsigned char *s = p; unsigned int g, h = 0; while (*s != '\0') { h = (h << 4) + *s; if ((g = h & 0xf0000000UL)) { h = h ^ (g >> 24); h = h ^ g; } s++; } return h; } /* a char* hash function from ASU -- from glib */ unsigned int strcase_hash(const void *p) { const unsigned char *s = p; unsigned int g, h = 0; while (*s != '\0') { h = (h << 4) + i_toupper(*s); if ((g = h & 0xf0000000UL)) { h = h ^ (g >> 24); h = h ^ g; } s++; } return h; }