272 lines
6.3 KiB
C
272 lines
6.3 KiB
C
/* 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 <sos/kmalloc.h>
|
|
#include <sos/klibc.h>
|
|
#include <sos/list.h>
|
|
#include <sos/assert.h>
|
|
|
|
#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);
|
|
}
|