sos-code-article10/sos/hash.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);
}