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