]> git.sommitrealweird.co.uk Git - quagga-debian.git/blob - lib/hash.c
New upstream release and new maintainer
[quagga-debian.git] / 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 }