/* Copyright (C) 2005 David Decotigny This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program 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 General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include #include #include #include #include "hash.h" #define SOS_HASH_NAME_MAXLEN 32 /** * @file hash.c * * A hash table is simply a table of lists: each list hash a "bucket * index". Each list contains the element for which the hash of the * key is equal to the bucket index (modulo the number of buckets). */ /** * Structure of one list of elements */ struct bucket { sos_count_t nb_elems; struct sos_hash_linkage * list; }; /** * The table of buckets, ie the hash itself */ struct sos_hash_table { char name[SOS_HASH_NAME_MAXLEN]; /** Hash function */ sos_hash_func_t * key_hasher; /** Key comparison function */ sos_hash_key_eq_func_t * key_iseq; /** Memory-offset of the key in the element structure */ sos_uoffset_t offset_h_key; /** Memory-offset of the hash linkage in the element structure */ sos_uoffset_t offset_h_linkage; /** Number of buckets in this hash table */ sos_count_t nbuckets; /** Number of elements currently in the hash */ sos_count_t nb_elems; struct bucket bucket[0]; }; /** From the address of the given element, access to its hash_linkage structrure */ #define h_linkage_of_elt(h,elt) \ ( (struct sos_hash_linkage*) \ ( ((unsigned long)(elt)) + (h)->offset_h_linkage) ) /** From the address of the given element, access to its pointer to the key */ #define h_keyptr_of_elt(h,elt) \ ( (void*) \ ( ((unsigned long)(elt)) + (h)->offset_h_key) ) /** From the given hash linkage structure address, retrieve the address of the surronding element */ #define elt_for_h_linkage(h,linkage) \ ( (void*) \ ( ((unsigned long)(linkage)) - (h)->offset_h_linkage) ) struct sos_hash_table * _sos_hash_create_FULL(const char *name, sos_hash_func_t *key_hasher, sos_hash_key_eq_func_t *key_iseq, sos_count_t nbuckets, sos_uoffset_t offset_h_key, sos_uoffset_t offset_h_linkage) { struct sos_hash_table * h; h = (struct sos_hash_table*) sos_kmalloc(sizeof(struct sos_hash_table) + nbuckets*sizeof(struct bucket), 0); memset(h, 0x0, sizeof(struct sos_hash_table) + nbuckets*sizeof(struct bucket)); h->key_hasher = key_hasher; h->key_iseq = key_iseq; h->offset_h_linkage = offset_h_linkage; h->offset_h_key = offset_h_key; h->nbuckets = nbuckets; strzcpy(h->name, name, SOS_HASH_NAME_MAXLEN); return h; } sos_count_t sos_hash_get_nb_elts(const struct sos_hash_table * h) { return h->nb_elems; } sos_ret_t sos_hash_dispose(struct sos_hash_table *h) { unsigned int i; for (i = 0 ; i < h->nbuckets ; i++) { struct sos_hash_linkage * elt; list_collapse_named(h->bucket[i].list, elt, h_prev, h_next) { elt->h_prev = elt->h_next = NULL; } } return sos_kfree((sos_vaddr_t)h); } sos_ret_t sos_hash_insert(struct sos_hash_table *h, void *elt_with_key) { struct sos_hash_linkage * h_elt; sos_uoffset_t bucket; h_elt = h_linkage_of_elt(h, elt_with_key); if (h_elt->h_prev || h_elt->h_next) return -SOS_EBUSY; if (h->key_hasher) bucket = h->key_hasher(h_keyptr_of_elt(h, elt_with_key)) % h->nbuckets; else { /* The key is assumed to be an integer */ unsigned long * keyval = h_keyptr_of_elt(h, elt_with_key); bucket = *keyval % h->nbuckets; } list_add_head_named(h->bucket[bucket].list, h_elt, h_prev, h_next); h->bucket[bucket].nb_elems ++; h->nb_elems ++; return SOS_OK; } void * sos_hash_lookup(struct sos_hash_table *h, const void * ptr_key) { struct sos_hash_linkage * h_elt; sos_uoffset_t bucket; int nb; if (h->key_hasher) bucket = h->key_hasher(ptr_key) % h->nbuckets; else { /* The key is assumed to be an integer */ const unsigned long * keyval = ptr_key; bucket = *keyval % h->nbuckets; } list_foreach_forward_named(h->bucket[bucket].list, h_elt, nb, h_prev, h_next) { void * elt = elt_for_h_linkage(h, h_elt); void * elt_ptr_key = h_keyptr_of_elt(h, elt); if (ptr_key == elt_ptr_key) return elt; if (! h->key_iseq) continue; if (h->key_iseq(ptr_key, elt_ptr_key)) return elt; } return NULL; } sos_ret_t sos_hash_remove(struct sos_hash_table *h, void * elt) { struct sos_hash_linkage * h_elt; sos_uoffset_t bucket; h_elt = h_linkage_of_elt(h, elt); SOS_ASSERT_FATAL(h_elt->h_prev && h_elt->h_next); if (h->key_hasher) bucket = h->key_hasher(h_keyptr_of_elt(h, elt)) % h->nbuckets; else { unsigned long * keyval = h_keyptr_of_elt(h, elt); bucket = *keyval % h->nbuckets; } list_delete_named(h->bucket[bucket].list, h_elt, h_prev, h_next); h->bucket[bucket].nb_elems --; h->nb_elems --; return SOS_OK; } sos_bool_t sos_hash_walk(const struct sos_hash_table *h, sos_hash_map_func_t * iter_func, void * custom_data) { unsigned int i; for (i = 0 ; i < h->nbuckets ; i++) { sos_count_t nelts; struct sos_hash_linkage * elt; list_foreach_forward_named(h->bucket[i].list, elt, nelts, h_prev, h_next) { if (! iter_func(custom_data, elt_for_h_linkage(h, elt))) return FALSE; } } return TRUE; } unsigned long sos_hash_ui64(const void * ptr_key) { const sos_ui64_t * keyval = ptr_key; return ((*keyval) * 302954987) & 0xffffffff; } sos_bool_t sos_hash_key_eq_ui64(const void * ptr_key1, const void * ptr_key2) { const sos_ui64_t * keyval1 = ptr_key1; const sos_ui64_t * keyval2 = ptr_key2; return (*keyval1 == *keyval2); }