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 *hash_create_size(unsigned int size,
  33                               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 =
  41                 XCALLOC(MTYPE_HASH_INDEX, 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 *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 *hash_alloc_intern(void *arg)
  62 {
  63         return arg;
  64 }
  65
  66 /* Expand hash if the chain length exceeds the threshold. */
  67 static void hash_expand(struct hash *hash)
  68 {
  69         unsigned int i, new_size, losers;
  70         struct hash_backet *hb, *hbnext, **new_index;
  71
  72         new_size = hash->size * 2;
  73         new_index = XCALLOC(MTYPE_HASH_INDEX,
  74                             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                         unsigned int h = hb->key & (new_size - 1);
  81
  82                         hbnext = hb->next;
  83                         hb->next = new_index[h];
  84                         new_index[h] = hb;
  85                 }
  86
  87         /* Switch to new table */
  88         XFREE(MTYPE_HASH_INDEX, hash->index);
  89         hash->size = new_size;
  90         hash->index = new_index;
  91
  92         /* Ideally, new index should have chains half as long as the original.
  93            If expansion didn't help, then not worth expanding again,
  94            the problem is the hash function. */
  95         losers = 0;
  96         for (i = 0; i < hash->size; i++) {
  97                 unsigned int len = 0;
  98                 for (hb = hash->index[i]; hb; hb = hb->next) {
  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 *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
 114 {
 115         unsigned int key;
 116         unsigned int index;
 117         void *newdata;
 118         unsigned int len;
 119         struct hash_backet *backet;
 120
 121         key = (*hash->hash_key)(data);
 122         index = key & (hash->size - 1);
 123         len = 0;
 124
 125         for (backet = hash->index[index]; backet != NULL;
 126              backet = backet->next) {
 127                 if (backet->key == key && (*hash->hash_cmp)(backet->data, data))
 128                         return backet->data;
 129                 ++len;
 130         }
 131
 132         if (alloc_func) {
 133                 newdata = (*alloc_func)(data);
 134                 if (newdata == NULL)
 135                         return NULL;
 136
 137                 if (len > HASH_THRESHOLD && !hash->no_expand) {
 138                         hash_expand(hash);
 139                         index = key & (hash->size - 1);
 140                 }
 141
 142                 backet = XMALLOC(MTYPE_HASH_BACKET, sizeof(struct hash_backet));
 143                 backet->data = newdata;
 144                 backet->key = key;
 145                 backet->next = hash->index[index];
 146                 hash->index[index] = backet;
 147                 hash->count++;
 148                 return backet->data;
 149         }
 150         return NULL;
 151 }
 152
 153 /* Hash lookup.  */
 154 void *hash_lookup(struct hash *hash, void *data)
 155 {
 156         return hash_get(hash, data, NULL);
 157 }
 158
 159 /* Simple Bernstein hash which is simple and fast for common case */
 160 unsigned int string_hash_make(const char *str)
 161 {
 162         unsigned int hash = 0;
 163
 164         while (*str)
 165                 hash = (hash * 33) ^ (unsigned int)*str++;
 166
 167         return hash;
 168 }
 169
 170 /* This function release registered value from specified hash.  When
 171    release is successfully finished, return the data pointer in the
 172    hash backet.  */
 173 void *hash_release(struct hash *hash, void *data)
 174 {
 175         void *ret;
 176         unsigned int key;
 177         unsigned int index;
 178         struct hash_backet *backet;
 179         struct hash_backet *pp;
 180
 181         key = (*hash->hash_key)(data);
 182         index = key & (hash->size - 1);
 183
 184         for (backet = pp = hash->index[index]; backet; backet = backet->next) {
 185                 if (backet->key == key
 186                     && (*hash->hash_cmp)(backet->data, data)) {
 187                         if (backet == pp)
 188                                 hash->index[index] = backet->next;
 189                         else
 190                                 pp->next = backet->next;
 191
 192                         ret = backet->data;
 193                         XFREE(MTYPE_HASH_BACKET, backet);
 194                         hash->count--;
 195                         return ret;
 196                 }
 197                 pp = backet;
 198         }
 199         return NULL;
 200 }
 201
 202 /* Iterator function for hash.  */
 203 void hash_iterate(struct hash *hash, void (*func)(struct hash_backet *, void *),
 204                   void *arg)
 205 {
 206         unsigned int i;
 207         struct hash_backet *hb;
 208         struct hash_backet *hbnext;
 209
 210         for (i = 0; i < hash->size; i++)
 211                 for (hb = hash->index[i]; hb; hb = hbnext) {
 212                         /* get pointer to next hash backet here, in case (*func)
 213                          * decides to delete hb by calling hash_release
 214                          */
 215                         hbnext = hb->next;
 216                         (*func)(hb, arg);
 217                 }
 218 }
 219
 220 /* Iterator function for hash.  */
 221 void hash_walk(struct hash *hash, int (*func)(struct hash_backet *, void *),
 222                void *arg)
 223 {
 224         unsigned int i;
 225         struct hash_backet *hb;
 226         struct hash_backet *hbnext;
 227         int ret = HASHWALK_CONTINUE;
 228
 229         for (i = 0; i < hash->size; i++) {
 230                 for (hb = hash->index[i]; hb; hb = hbnext) {
 231                         /* get pointer to next hash backet here, in case (*func)
 232                          * decides to delete hb by calling hash_release
 233                          */
 234                         hbnext = hb->next;
 235                         ret = (*func)(hb, arg);
 236                         if (ret == HASHWALK_ABORT)
 237                                 return;
 238                 }
 239         }
 240 }
 241
 242 /* Clean up hash.  */
 243 void hash_clean(struct hash *hash, void (*free_func)(void *))
 244 {
 245         unsigned int i;
 246         struct hash_backet *hb;
 247         struct hash_backet *next;
 248
 249         for (i = 0; i < hash->size; i++) {
 250                 for (hb = hash->index[i]; hb; hb = next) {
 251                         next = hb->next;
 252
 253                         if (free_func)
 254                                 (*free_func)(hb->data);
 255
 256                         XFREE(MTYPE_HASH_BACKET, hb);
 257                         hash->count--;
 258                 }
 259                 hash->index[i] = NULL;
 260         }
 261 }
 262
 263 /* Free hash memory.  You may call hash_clean before call this
 264    function.  */
 265 void hash_free(struct hash *hash)
 266 {
 267         XFREE(MTYPE_HASH_INDEX, hash->index);
 268         XFREE(MTYPE_HASH, hash);
 269 }