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   hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
  35   hash->index = XMALLOC (MTYPE_HASH_INDEX,
  36                          sizeof (struct hash_backet *) * size);
  37   memset (hash->index, 0, sizeof (struct hash_backet *) * size);
  38   hash->size = size;
  39   hash->hash_key = hash_key;
  40   hash->hash_cmp = hash_cmp;
  41   hash->count = 0;
  42
  43   return hash;
  44 }
  45
  46 /* Allocate a new hash with default hash size.  */
  47 struct hash *
  48 hash_create (unsigned int (*hash_key) (void *),
  49              int (*hash_cmp) (const void *, const void *))
  50 {
  51   return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
  52 }
  53
  54 /* Utility function for hash_get().  When this function is specified
  55    as alloc_func, return arugment as it is.  This function is used for
  56    intern already allocated value.  */
  57 void *
  58 hash_alloc_intern (void *arg)
  59 {
  60   return arg;
  61 }
  62
  63 /* Lookup and return hash backet in hash.  If there is no
  64    corresponding hash backet and alloc_func is specified, create new
  65    hash backet.  */
  66 void *
  67 hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
  68 {
  69   unsigned int key;
  70   unsigned int index;
  71   void *newdata;
  72   struct hash_backet *backet;
  73
  74   key = (*hash->hash_key) (data);
  75   index = key % hash->size;
  76
  77   for (backet = hash->index[index]; backet != NULL; backet = backet->next)
  78     if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
  79       return backet->data;
  80
  81   if (alloc_func)
  82     {
  83       newdata = (*alloc_func) (data);
  84       if (newdata == NULL)
  85         return NULL;
  86
  87       backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
  88       backet->data = newdata;
  89       backet->key = key;
  90       backet->next = hash->index[index];
  91       hash->index[index] = backet;
  92       hash->count++;
  93       return backet->data;
  94     }
  95   return NULL;
  96 }
  97
  98 /* Hash lookup.  */
  99 void *
 100 hash_lookup (struct hash *hash, void *data)
 101 {
 102   return hash_get (hash, data, NULL);
 103 }
 104
 105 /* This function release registered value from specified hash.  When
 106    release is successfully finished, return the data pointer in the
 107    hash backet.  */
 108 void *
 109 hash_release (struct hash *hash, void *data)
 110 {
 111   void *ret;
 112   unsigned int key;
 113   unsigned int index;
 114   struct hash_backet *backet;
 115   struct hash_backet *pp;
 116
 117   key = (*hash->hash_key) (data);
 118   index = key % hash->size;
 119
 120   for (backet = pp = hash->index[index]; backet; backet = backet->next)
 121     {
 122       if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
 123         {
 124           if (backet == pp)
 125             hash->index[index] = backet->next;
 126           else
 127             pp->next = backet->next;
 128
 129           ret = backet->data;
 130           XFREE (MTYPE_HASH_BACKET, backet);
 131           hash->count--;
 132           return ret;
 133         }
 134       pp = backet;
 135     }
 136   return NULL;
 137 }
 138
 139 /* Iterator function for hash.  */
 140 void
 141 hash_iterate (struct hash *hash,
 142               void (*func) (struct hash_backet *, void *), void *arg)
 143 {
 144   unsigned int i;
 145   struct hash_backet *hb;
 146   struct hash_backet *hbnext;
 147
 148   for (i = 0; i < hash->size; i++)
 149     for (hb = hash->index[i]; hb; hb = hbnext)
 150       {
 151         /* get pointer to next hash backet here, in case (*func)
 152          * decides to delete hb by calling hash_release
 153          */
 154         hbnext = hb->next;
 155         (*func) (hb, arg);
 156       }
 157 }
 158
 159 /* Clean up hash.  */
 160 void
 161 hash_clean (struct hash *hash, void (*free_func) (void *))
 162 {
 163   unsigned int i;
 164   struct hash_backet *hb;
 165   struct hash_backet *next;
 166
 167   for (i = 0; i < hash->size; i++)
 168     {
 169       for (hb = hash->index[i]; hb; hb = next)
 170         {
 171           next = hb->next;
 172
 173           if (free_func)
 174             (*free_func) (hb->data);
 175
 176           XFREE (MTYPE_HASH_BACKET, hb);
 177           hash->count--;
 178         }
 179       hash->index[i] = NULL;
 180     }
 181 }
 182
 183 /* Free hash memory.  You may call hash_clean before call this
 184    function.  */
 185 void
 186 hash_free (struct hash *hash)
 187 {
 188   XFREE (MTYPE_HASH_INDEX, hash->index);
 189   XFREE (MTYPE_HASH, hash);
 190 }