Line data Source code
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 89 : 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 89 : assert ((size & (size-1)) == 0);
35 89 : hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
36 89 : hash->index = XCALLOC (MTYPE_HASH_INDEX,
37 : sizeof (struct hash_backet *) * size);
38 89 : hash->size = size;
39 89 : hash->no_expand = 0;
40 89 : hash->hash_key = hash_key;
41 89 : hash->hash_cmp = hash_cmp;
42 89 : hash->count = 0;
43 :
44 89 : return hash;
45 : }
46 :
47 : /* Allocate a new hash with default hash size. */
48 : struct hash *
49 88 : hash_create (unsigned int (*hash_key) (void *),
50 : int (*hash_cmp) (const void *, const void *))
51 : {
52 88 : 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 5 : hash_alloc_intern (void *arg)
60 : {
61 5 : return arg;
62 : }
63 :
64 : /* Expand hash if the chain length exceeds the threshold. */
65 0 : 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 0 : new_size = hash->size * 2;
71 0 : new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size);
72 0 : if (new_index == NULL)
73 0 : return;
74 :
75 0 : for (i = 0; i < hash->size; i++)
76 0 : for (hb = hash->index[i]; hb; hb = hbnext)
77 : {
78 0 : unsigned int h = hb->key & (new_size - 1);
79 :
80 0 : hbnext = hb->next;
81 0 : hb->next = new_index[h];
82 0 : new_index[h] = hb;
83 : }
84 :
85 : /* Switch to new table */
86 0 : XFREE(MTYPE_HASH_INDEX, hash->index);
87 0 : hash->size = new_size;
88 0 : 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 0 : losers = 0;
94 0 : for (i = 0; i < hash->size; i++)
95 : {
96 0 : unsigned int len = 0;
97 0 : for (hb = hash->index[i]; hb; hb = hb->next)
98 : {
99 0 : if (++len > HASH_THRESHOLD/2)
100 0 : ++losers;
101 0 : if (len >= HASH_THRESHOLD)
102 0 : hash->no_expand = 1;
103 : }
104 : }
105 :
106 0 : if (losers > hash->count / 2)
107 0 : 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 149078 : 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 149078 : key = (*hash->hash_key) (data);
123 149078 : index = key & (hash->size - 1);
124 149078 : len = 0;
125 :
126 198060 : for (backet = hash->index[index]; backet != NULL; backet = backet->next)
127 : {
128 196262 : if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
129 147280 : return backet->data;
130 48982 : ++len;
131 : }
132 :
133 1798 : if (alloc_func)
134 : {
135 1058 : newdata = (*alloc_func) (data);
136 1058 : if (newdata == NULL)
137 0 : return NULL;
138 :
139 1058 : if (len > HASH_THRESHOLD && !hash->no_expand)
140 : {
141 0 : hash_expand (hash);
142 0 : index = key & (hash->size - 1);
143 : }
144 :
145 1058 : backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
146 1058 : backet->data = newdata;
147 1058 : backet->key = key;
148 1058 : backet->next = hash->index[index];
149 1058 : hash->index[index] = backet;
150 1058 : hash->count++;
151 1058 : return backet->data;
152 : }
153 740 : return NULL;
154 : }
155 :
156 : /* Hash lookup. */
157 : void *
158 145984 : hash_lookup (struct hash *hash, void *data)
159 : {
160 145984 : return hash_get (hash, data, NULL);
161 : }
162 :
163 : /* Simple Bernstein hash which is simple and fast for common case */
164 0 : unsigned int string_hash_make (const char *str)
165 : {
166 0 : unsigned int hash = 0;
167 :
168 0 : while (*str)
169 0 : hash = (hash * 33) ^ (unsigned int) *str++;
170 :
171 0 : 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 459 : 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 459 : key = (*hash->hash_key) (data);
187 459 : index = key & (hash->size - 1);
188 :
189 530 : for (backet = pp = hash->index[index]; backet; backet = backet->next)
190 : {
191 530 : if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
192 : {
193 459 : if (backet == pp)
194 400 : hash->index[index] = backet->next;
195 : else
196 59 : pp->next = backet->next;
197 :
198 459 : ret = backet->data;
199 459 : XFREE (MTYPE_HASH_BACKET, backet);
200 459 : hash->count--;
201 459 : return ret;
202 : }
203 71 : pp = backet;
204 : }
205 0 : return NULL;
206 : }
207 :
208 : /* Iterator function for hash. */
209 : void
210 1000 : 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 257000 : for (i = 0; i < hash->size; i++)
218 401244 : 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 145244 : hbnext = hb->next;
224 145244 : (*func) (hb, arg);
225 : }
226 1000 : }
227 :
228 : /* Clean up hash. */
229 : void
230 2 : 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 514 : for (i = 0; i < hash->size; i++)
237 : {
238 793 : for (hb = hash->index[i]; hb; hb = next)
239 : {
240 281 : next = hb->next;
241 :
242 281 : if (free_func)
243 281 : (*free_func) (hb->data);
244 :
245 281 : XFREE (MTYPE_HASH_BACKET, hb);
246 281 : hash->count--;
247 : }
248 512 : hash->index[i] = NULL;
249 : }
250 2 : }
251 :
252 : /* Free hash memory. You may call hash_clean before call this
253 : function. */
254 : void
255 2 : hash_free (struct hash *hash)
256 : {
257 2 : XFREE (MTYPE_HASH_INDEX, hash->index);
258 2 : XFREE (MTYPE_HASH, hash);
259 2 : }
|
