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
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include <zebra.h>
  23
  24 #include "hash.h"
  25 #include "memory.h"
  26
  27 /* Allocate a new hash.  */
  28 struct hash *
  29 hash_create_size (unsigned int size, unsigned int (*hash_key) (void *),
  30                                      int (*hash_cmp) (const void *, const void *))
  31 {
  32   struct hash *hash;
  33
  34   assert ((size & (size-1)) == 0);
  35   hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
  36   hash->index = XCALLOC (MTYPE_HASH_INDEX,
  37                          sizeof (struct hash_backet *) * size);
  38   hash->size = size;
  39   hash->no_expand = 0;
  40   hash->hash_key = hash_key;
  41   hash->hash_cmp = hash_cmp;
  42   hash->count = 0;
  43
  44   return hash;
  45 }
  46
  47 /* Allocate a new hash with default hash size.  */
  48 struct hash *
  49 hash_create (unsigned int (*hash_key) (void *),
  50              int (*hash_cmp) (const void *, const void *))
  51 {
  52   return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp);
  53 }
  54
  55 /* Utility function for hash_get().  When this function is specified
  56    as alloc_func, return arugment as it is.  This function is used for
  57    intern already allocated value.  */
  58 void *
  59 hash_alloc_intern (void *arg)
  60 {
  61   return arg;
  62 }
  63
  64 /* Expand hash if the chain length exceeds the threshold. */
  65 static void hash_expand (struct hash *hash)
  66 {
  67   unsigned int i, new_size, losers;
  68   struct hash_backet *hb, *hbnext, **new_index;
  69
  70   new_size = hash->size * 2;
  71   new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size);
  72   if (new_index == NULL)
  73     return;
  74
  75   for (i = 0; i < hash->size; i++)
  76     for (hb = hash->index[i]; hb; hb = hbnext)
  77       {
  78         unsigned int h = hb->key & (new_size - 1);
  79
  80         hbnext = hb->next;
  81         hb->next = new_index[h];
  82         new_index[h] = hb;
  83       }
  84
  85   /* Switch to new table */
  86   XFREE(MTYPE_HASH_INDEX, hash->index);
  87   hash->size = new_size;
  88   hash->index = new_index;
  89
  90   /* Ideally, new index should have chains half as long as the original.
  91      If expansion didn't help, then not worth expanding again,
  92      the problem is the hash function. */
  93   losers = 0;
  94   for (i = 0; i < hash->size; i++)
  95     {
  96       unsigned int len = 0;
  97       for (hb = hash->index[i]; hb; hb = hb->next)
  98         {
  99           if (++len > HASH_THRESHOLD/2)
 100             ++losers;
 101           if (len >= HASH_THRESHOLD)
 102             hash->no_expand = 1;
 103         }
 104     }
 105
 106   if (losers > hash->count / 2)
 107     hash->no_expand = 1;
 108 }
 109
 110 /* Lookup and return hash backet in hash.  If there is no
 111    corresponding hash backet and alloc_func is specified, create new
 112    hash backet.  */
 113 void *
 114 hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
 115 {
 116   unsigned int key;
 117   unsigned int index;
 118   void *newdata;
 119   unsigned int len;
 120   struct hash_backet *backet;
 121
 122   key = (*hash->hash_key) (data);
 123   index = key & (hash->size - 1);
 124   len = 0;
 125
 126   for (backet = hash->index[index]; backet != NULL; backet = backet->next)
 127     {
 128       if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
 129         return backet->data;
 130       ++len;
 131     }
 132
 133   if (alloc_func)
 134     {
 135       newdata = (*alloc_func) (data);
 136       if (newdata == NULL)
 137         return NULL;
 138
 139       if (len > HASH_THRESHOLD && !hash->no_expand)
 140         {
 141           hash_expand (hash);
 142           index = key & (hash->size - 1);
 143         }
 144
 145       backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
 146       backet->data = newdata;
 147       backet->key = key;
 148       backet->next = hash->index[index];
 149       hash->index[index] = backet;
 150       hash->count++;
 151       return backet->data;
 152     }
 153   return NULL;
 154 }
 155
 156 /* Hash lookup.  */
 157 void *
 158 hash_lookup (struct hash *hash, void *data)
 159 {
 160   return hash_get (hash, data, NULL);
 161 }
 162
 163 /* Simple Bernstein hash which is simple and fast for common case */
 164 unsigned int string_hash_make (const char *str)
 165 {
 166   unsigned int hash = 0;
 167
 168   while (*str)
 169     hash = (hash * 33) ^ (unsigned int) *str++;
 170
 171   return hash;
 172 }
 173
 174 /* This function release registered value from specified hash.  When
 175    release is successfully finished, return the data pointer in the
 176    hash backet.  */
 177 void *
 178 hash_release (struct hash *hash, void *data)
 179 {
 180   void *ret;
 181   unsigned int key;
 182   unsigned int index;
 183   struct hash_backet *backet;
 184   struct hash_backet *pp;
 185
 186   key = (*hash->hash_key) (data);
 187   index = key & (hash->size - 1);
 188
 189   for (backet = pp = hash->index[index]; backet; backet = backet->next)
 190     {
 191       if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
 192         {
 193           if (backet == pp)
 194             hash->index[index] = backet->next;
 195           else
 196             pp->next = backet->next;
 197
 198           ret = backet->data;
 199           XFREE (MTYPE_HASH_BACKET, backet);
 200           hash->count--;
 201           return ret;
 202         }
 203       pp = backet;
 204     }
 205   return NULL;
 206 }
 207
 208 /* Iterator function for hash.  */
 209 void
 210 hash_iterate (struct hash *hash,
 211               void (*func) (struct hash_backet *, void *), void *arg)
 212 {
 213   unsigned int i;
 214   struct hash_backet *hb;
 215   struct hash_backet *hbnext;
 216
 217   for (i = 0; i < hash->size; i++)
 218     for (hb = hash->index[i]; hb; hb = hbnext)
 219       {
 220         /* get pointer to next hash backet here, in case (*func)
 221          * decides to delete hb by calling hash_release
 222          */
 223         hbnext = hb->next;
 224         (*func) (hb, arg);
 225       }
 226 }
 227
 228 /* Clean up hash.  */
 229 void
 230 hash_clean (struct hash *hash, void (*free_func) (void *))
 231 {
 232   unsigned int i;
 233   struct hash_backet *hb;
 234   struct hash_backet *next;
 235
 236   for (i = 0; i < hash->size; i++)
 237     {
 238       for (hb = hash->index[i]; hb; hb = next)
 239         {
 240           next = hb->next;
 241
 242           if (free_func)
 243             (*free_func) (hb->data);
 244
 245           XFREE (MTYPE_HASH_BACKET, hb);
 246           hash->count--;
 247         }
 248       hash->index[i] = NULL;
 249     }
 250 }
 251
 252 /* Free hash memory.  You may call hash_clean before call this
 253    function.  */
 254 void
 255 hash_free (struct hash *hash)
 256 {
 257   XFREE (MTYPE_HASH_INDEX, hash->index);
 258   XFREE (MTYPE_HASH, hash);
 259 }