/* 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;
   
   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_ret_t sos_hash_dispose(struct sos_hash_table *h)
 {
   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 ++;
 
   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 --;
 
   return SOS_OK;
 }
 
 
 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);
 }