lib/hash.c

   1 /* Hash routine.
   2  * Copyright (C) 1998 Kunihiro Ishiguro
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published
   8  * by the Free Software Foundation; either version 2, or (at your
   9  * option) any later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "hash.h"
  24 #include "memory.h"
  25
  26 DEFINE_MTYPE(       LIB, HASH,        "Hash")
  27 DEFINE_MTYPE(       LIB, HASH_BACKET, "Hash Bucket")
  28 DEFINE_MTYPE_STATIC(LIB, HASH_INDEX,  "Hash Index")
  29
  30 /* Allocate a new hash.  */
  31 struct hash *
  32 hash_create_size (unsigned int size, unsigned int (*hash_key) (void *),
  33                   int (*hash_cmp) (const void *, const void *))
  34 {
  35   struct hash *hash;
  36
  37   assert ((size & (size-1)) == 0);
  38   hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
  39   hash->index = XCALLOC (MTYPE_HASH_INDEX,
  40                          sizeof (struct hash_backet *) * size);
  41   hash->size = size;
  42   hash->no_expand = 0;
  43   hash->hash_key = hash_key;
  44   hash->hash_cmp = hash_cmp;
  45   hash->count = 0;
  46
  47   return hash;
  48 }
  49
  50 /* Allocate a new hash with default hash size.  */
  51 struct hash *
  52 hash_create (unsigned int (*hash_key) (void *),
  53              int (*hash_cmp) (const void *, const void *))
  54 {
  55   return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp);
  56 }
  57
  58 /* Utility function for hash_get().  When this function is specified
  59    as alloc_func, return arugment as it is.  This function is used for
  60    intern already allocated value.  */
  61 void *
  62 hash_alloc_intern (void *arg)
  63 {
  64   return arg;
  65 }
  66
  67 /* Expand hash if the chain length exceeds the threshold. */
  68 static void hash_expand (struct hash *hash)
  69 {
  70   unsigned int i, new_size, losers;
  71   struct hash_backet *hb, *hbnext, **new_index;
  72
  73   new_size = hash->size * 2;
  74   new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size);
  75   if (new_index == NULL)
  76     return;
  77
  78   for (i = 0; i < hash->size; i++)
  79     for (hb = hash->index[i]; hb; hb = hbnext)
  80       {
  81         unsigned int h = hb->key & (new_size - 1);
  82
  83         hbnext = hb->next;
  84         hb->next = new_index[h];
  85         new_index[h] = hb;
  86       }
  87
  88   /* Switch to new table */
  89   XFREE(MTYPE_HASH_INDEX, hash->index);
  90   hash->size = new_size;
  91   hash->index = new_index;
  92
  93   /* Ideally, new index should have chains half as long as the original.
  94      If expansion didn't help, then not worth expanding again,
  95      the problem is the hash function. */
  96   losers = 0;
  97   for (i = 0; i < hash->size; i++)
  98     {
  99       unsigned int len = 0;
 100       for (hb = hash->index[i]; hb; hb = hb->next)
 101         {
 102           if (++len > HASH_THRESHOLD/2)
 103             ++losers;
 104           if (len >= HASH_THRESHOLD)
 105             hash->no_expand = 1;
 106         }
 107     }
 108
 109   if (losers > hash->count / 2)
 110     hash->no_expand = 1;
 111 }
 112
 113 /* Lookup and return hash backet in hash.  If there is no
 114    corresponding hash backet and alloc_func is specified, create new
 115    hash backet.  */
 116 void *
 117 hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
 118 {
 119   unsigned int key;
 120   unsigned int index;
 121   void *newdata;
 122   unsigned int len;
 123   struct hash_backet *backet;
 124
 125   key = (*hash->hash_key) (data);
 126   index = key & (hash->size - 1);
 127   len = 0;
 128
 129   for (backet = hash->index[index]; backet != NULL; backet = backet->next)
 130     {
 131       if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
 132         return backet->data;
 133       ++len;
 134     }
 135
 136   if (alloc_func)
 137     {
 138       newdata = (*alloc_func) (data);
 139       if (newdata == NULL)
 140         return NULL;
 141
 142       if (len > HASH_THRESHOLD && !hash->no_expand)
 143         {
 144           hash_expand (hash);
 145           index = key & (hash->size - 1);
 146         }
 147
 148       backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
 149       backet->data = newdata;
 150       backet->key = key;
 151       backet->next = hash->index[index];
 152       hash->index[index] = backet;
 153       hash->count++;
 154       return backet->data;
 155     }
 156   return NULL;
 157 }
 158
 159 /* Hash lookup.  */
 160 void *
 161 hash_lookup (struct hash *hash, void *data)
 162 {
 163   return hash_get (hash, data, NULL);
 164 }
 165
 166 /* Simple Bernstein hash which is simple and fast for common case */
 167 unsigned int string_hash_make (const char *str)
 168 {
 169   unsigned int hash = 0;
 170
 171   while (*str)
 172     hash = (hash * 33) ^ (unsigned int) *str++;
 173
 174   return hash;
 175 }
 176
 177 /* This function release registered value from specified hash.  When
 178    release is successfully finished, return the data pointer in the
 179    hash backet.  */
 180 void *
 181 hash_release (struct hash *hash, void *data)
 182 {
 183   void *ret;
 184   unsigned int key;
 185   unsigned int index;
 186   struct hash_backet *backet;
 187   struct hash_backet *pp;
 188
 189   key = (*hash->hash_key) (data);
 190   index = key & (hash->size - 1);
 191
 192   for (backet = pp = hash->index[index]; backet; backet = backet->next)
 193     {
 194       if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
 195         {
 196           if (backet == pp)
 197             hash->index[index] = backet->next;
 198           else
 199             pp->next = backet->next;
 200
 201           ret = backet->data;
 202           XFREE (MTYPE_HASH_BACKET, backet);
 203           hash->count--;
 204           return ret;
 205         }
 206       pp = backet;
 207     }
 208   return NULL;
 209 }
 210
 211 /* Iterator function for hash.  */
 212 void
 213 hash_iterate (struct hash *hash,
 214               void (*func) (struct hash_backet *, void *), void *arg)
 215 {
 216   unsigned int i;
 217   struct hash_backet *hb;
 218   struct hash_backet *hbnext;
 219
 220   for (i = 0; i < hash->size; i++)
 221     for (hb = hash->index[i]; hb; hb = hbnext)
 222       {
 223         /* get pointer to next hash backet here, in case (*func)
 224          * decides to delete hb by calling hash_release
 225          */
 226         hbnext = hb->next;
 227         (*func) (hb, arg);
 228       }
 229 }
 230
 231 /* Iterator function for hash.  */
 232 void
 233 hash_walk (struct hash *hash,
 234            int (*func) (struct hash_backet *, void *), void *arg)
 235 {
 236   unsigned int i;
 237   struct hash_backet *hb;
 238   struct hash_backet *hbnext;
 239   int ret = HASHWALK_CONTINUE;
 240
 241   for (i = 0; i < hash->size; i++)
 242     {
 243       for (hb = hash->index[i]; hb; hb = hbnext)
 244         {
 245           /* get pointer to next hash backet here, in case (*func)
 246            * decides to delete hb by calling hash_release
 247            */
 248           hbnext = hb->next;
 249           ret = (*func) (hb, arg);
 250           if (ret == HASHWALK_ABORT)
 251             return;
 252         }
 253     }
 254 }
 255
 256 /* Clean up hash.  */
 257 void
 258 hash_clean (struct hash *hash, void (*free_func) (void *))
 259 {
 260   unsigned int i;
 261   struct hash_backet *hb;
 262   struct hash_backet *next;
 263
 264   for (i = 0; i < hash->size; i++)
 265     {
 266       for (hb = hash->index[i]; hb; hb = next)
 267         {
 268           next = hb->next;
 269
 270           if (free_func)
 271             (*free_func) (hb->data);
 272
 273           XFREE (MTYPE_HASH_BACKET, hb);
 274           hash->count--;
 275         }
 276       hash->index[i] = NULL;
 277     }
 278 }
 279
 280 /* Free hash memory.  You may call hash_clean before call this
 281    function.  */
 282 void
 283 hash_free (struct hash *hash)
 284 {
 285   XFREE (MTYPE_HASH_INDEX, hash->index);
 286   XFREE (MTYPE_HASH, hash);
 287 }