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