sos-code-article10/sos/hash.c

272 lines
6.3 KiB
C
Raw Permalink Normal View History

2018-07-13 17:13:10 +02:00
/* 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);
}