Mercurial > dovecot > original-hg > dovecot-1.2
view src/lib/hash.c @ 59:296c6dbf50a5 HEAD
Don't include system headers before lib.h, since config.h may change their
behaviour (64bit off_t)
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Wed, 28 Aug 2002 03:17:09 +0300 |
parents | e399e33d033d |
children | db6e288be0e9 |
line wrap: on
line source
/* GLIB - Library of useful routines for C programming * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public * License along with this library; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ /* * Modified by the GLib Team and others 1997-1999. See the AUTHORS * file for a list of people on the GLib Team. See the ChangeLog * files for a list of changes. These files are distributed with * GLib at ftp://ftp.gtk.org/pub/gtk/. */ /* several modifications Copyright (C) 2002 by Timo Sirainen */ #include "lib.h" #include "hash.h" #include "primes.h" #include <ctype.h> #define HASH_TABLE_MIN_SIZE 11 #define HASH_TABLE_MAX_SIZE 13845163 typedef struct _HashNode { void *key; void *value; int destroyed; struct _HashNode *next; } HashNode; struct _HashTable { Pool pool; unsigned int size; unsigned int nodes_count, nodes_destroyed; int frozen; HashNode **nodes; HashFunc hash_func; HashCompareFunc key_compare_func; }; static void hash_cleanup(HashTable *table); static int hash_resize(HashTable *table); static int foreach_stop; static unsigned int direct_hash(const void *p) { /* NOTE: may truncate the value, but that doesn't matter. */ return POINTER_TO_UINT(p); } static HashNode *hash_node_create(Pool pool, const void *key, const void *value) { HashNode *node; node = p_new(pool, HashNode, 1); node->key = (void *) key; node->value = (void *) value; return node; } static void hash_nodes_destroy(HashTable *table, HashNode *node) { HashNode *next; while (node != NULL) { next = node->next; p_free(table->pool, node); node = next; } } HashTable *hash_create(Pool pool, unsigned int initial_size, HashFunc hash_func, HashCompareFunc key_compare_func) { HashTable *table; i_assert(pool != NULL); table = p_new(pool, HashTable, 1); table->pool = pool; table->size = CLAMP(primes_closest(initial_size), HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); table->hash_func = hash_func != NULL ? hash_func : direct_hash; table->key_compare_func = key_compare_func; table->nodes = p_new(pool, HashNode *, table->size); return table; } void hash_destroy(HashTable *table) { unsigned int i; if (table == NULL) return; for (i = 0; i < table->size; i++) hash_nodes_destroy(table, table->nodes[i]); p_free(table->pool, table->nodes); p_free(table->pool, table); } void hash_clear(HashTable *table) { unsigned int i; i_assert(table != NULL); for (i = 0; i < table->size; i++) { hash_nodes_destroy(table, table->nodes[i]); table->nodes[i] = NULL; } } static inline HashNode ** hash_lookup_node(HashTable *table, const void *key) { HashNode **node; node = &table->nodes[table->hash_func(key) % table->size]; /* Hash table lookup needs to be fast. We therefore remove the extra conditional of testing whether to call the key_compare_func or not from the inner loop. */ if (table->key_compare_func) { while (*node != NULL) { if (!(*node)->destroyed && table->key_compare_func((*node)->key, key) == 0) break; node = &(*node)->next; } } else { while (*node != NULL && (*node)->key != key) node = &(*node)->next; } return node; } void *hash_lookup(HashTable *table, const void *key) { HashNode *node; i_assert(table != NULL); node = *hash_lookup_node(table, key); return node != NULL && !node->destroyed ? node->value : NULL; } int hash_lookup_full(HashTable *table, const void *lookup_key, void **orig_key, void **value) { HashNode *node; i_assert(table != NULL); node = *hash_lookup_node(table, lookup_key); if (node == NULL || node->destroyed) return FALSE; if (orig_key != NULL) *orig_key = node->key; if (value != NULL) *value = node->value; return TRUE; } static void hash_insert_full(HashTable *table, const void *key, const void *value, int replace_key) { HashNode **node; i_assert(table != NULL); node = hash_lookup_node(table, key); if (*node == NULL) { *node = hash_node_create(table->pool, key, value); table->nodes_count++; if (!table->frozen) hash_resize(table); } else { if (replace_key || (*node)->destroyed) { (*node)->key = (void *) key; (*node)->destroyed = FALSE; } (*node)->value = (void *) value; } } void hash_insert(HashTable *table, const void *key, const void *value) { hash_insert_full(table, key, value, TRUE); } void hash_update(HashTable *table, const void *key, const void *value) { hash_insert_full(table, key, value, FALSE); } void hash_remove(HashTable *table, const void *key) { HashNode **node, *old_node; i_assert(table != NULL); node = hash_lookup_node(table, key); if (*node != NULL && !(*node)->destroyed) { table->nodes_count--; if (table->frozen) { (*node)->destroyed = TRUE; table->nodes_destroyed++; } else { old_node = *node; *node = old_node->next; p_free(table->pool, old_node); hash_resize(table); } } } void hash_freeze(HashTable *table) { i_assert(table != NULL); table->frozen++; } void hash_thaw(HashTable *table) { i_assert(table != NULL); i_assert(table->frozen > 0); if (--table->frozen == 0) hash_cleanup(table); } void hash_foreach(HashTable *table, HashForeachFunc func, void *context) { HashNode *node; unsigned int i; i_assert(table != NULL); i_assert(func != NULL); hash_freeze(table); foreach_stop = FALSE; for (i = 0; i < table->size; i++) { for (node = table->nodes[i]; node; node = node->next) { if (!node->destroyed) { func(node->key, node->value, context); if (foreach_stop) { foreach_stop = FALSE; hash_thaw(table); return; } } } } hash_thaw(table); } void hash_foreach_stop(void) { foreach_stop = TRUE; } /* Returns the number of elements contained in the hash table. */ unsigned int hash_size(HashTable *table) { i_assert(table != NULL); return table->nodes_count; } static int hash_resize(HashTable *table) { HashFunc hash_func; HashNode *node, *next, **new_nodes; float nodes_per_list; unsigned int hash_val, new_size, i; nodes_per_list = (float) table->nodes_count / (float) table->size; if ((nodes_per_list > 0.3 || table->size <= HASH_TABLE_MIN_SIZE) && (nodes_per_list < 3.0 || table->size >= HASH_TABLE_MAX_SIZE)) return FALSE; new_size = CLAMP(primes_closest(table->nodes_count+1), HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); new_nodes = p_new(table->pool, HashNode *, new_size); hash_func = table->hash_func; for (i = 0; i < table->size; i++) { for (node = table->nodes[i]; node != NULL; node = next) { next = node->next; if (node->destroyed) { p_free(table->pool, node); } else { hash_val = hash_func(node->key) % new_size; node->next = new_nodes[hash_val]; new_nodes[hash_val] = node; } } } p_free(table->pool, table->nodes); table->nodes = new_nodes; table->size = new_size; table->nodes_destroyed = 0; return TRUE; } static void hash_cleanup(HashTable *table) { HashNode **node, **next, *old_node; unsigned int i; if (hash_resize(table)) return; if (table->nodes_destroyed == 0) return; /* find the destroyed nodes from hash table and remove them */ for (i = 0; i < table->size; i++) { for (node = &table->nodes[i]; *node != NULL; node = next) { next = &(*node)->next; if ((*node)->destroyed) { old_node = *node; *node = *next; p_free(table->pool, old_node); /* next points to free'd memory area now, fix it */ next = node; if (--table->nodes_destroyed == 0) return; } } } } /* 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; }