]>
Commit | Line | Data |
---|---|---|
718e3744 | 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 | ||
4a1ab8e4 DL |
27 | DEFINE_MTYPE( LIB, HASH, "Hash") |
28 | DEFINE_MTYPE( LIB, HASH_BACKET, "Hash Bucket") | |
29 | DEFINE_MTYPE_STATIC(LIB, HASH_INDEX, "Hash Index") | |
30 | ||
718e3744 | 31 | /* Allocate a new hash. */ |
32 | struct hash * | |
8cc4198f | 33 | hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), |
24873f0c | 34 | int (*hash_cmp) (const void *, const void *)) |
718e3744 | 35 | { |
36 | struct hash *hash; | |
37 | ||
90645f55 | 38 | assert ((size & (size-1)) == 0); |
718e3744 | 39 | hash = XMALLOC (MTYPE_HASH, sizeof (struct hash)); |
393deb9b | 40 | hash->index = XCALLOC (MTYPE_HASH_INDEX, |
718e3744 | 41 | sizeof (struct hash_backet *) * size); |
718e3744 | 42 | hash->size = size; |
6d729eea | 43 | hash->no_expand = 0; |
718e3744 | 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 * | |
8cc4198f | 53 | hash_create (unsigned int (*hash_key) (void *), |
ffe11cfb | 54 | int (*hash_cmp) (const void *, const void *)) |
718e3744 | 55 | { |
97c84db0 | 56 | return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp); |
718e3744 | 57 | } |
58 | ||
59 | /* Utility function for hash_get(). When this function is specified | |
60 | as alloc_func, return arugment as it is. This function is used for | |
61 | intern already allocated value. */ | |
62 | void * | |
63 | hash_alloc_intern (void *arg) | |
64 | { | |
65 | return arg; | |
66 | } | |
67 | ||
97c84db0 SH |
68 | /* Expand hash if the chain length exceeds the threshold. */ |
69 | static void hash_expand (struct hash *hash) | |
70 | { | |
71 | unsigned int i, new_size, losers; | |
72 | struct hash_backet *hb, *hbnext, **new_index; | |
73 | ||
74 | new_size = hash->size * 2; | |
75 | new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size); | |
76 | if (new_index == NULL) | |
77 | return; | |
78 | ||
79 | for (i = 0; i < hash->size; i++) | |
80 | for (hb = hash->index[i]; hb; hb = hbnext) | |
81 | { | |
82 | unsigned int h = hb->key & (new_size - 1); | |
83 | ||
84 | hbnext = hb->next; | |
85 | hb->next = new_index[h]; | |
86 | new_index[h] = hb; | |
87 | } | |
88 | ||
89 | /* Switch to new table */ | |
90 | XFREE(MTYPE_HASH_INDEX, hash->index); | |
91 | hash->size = new_size; | |
92 | hash->index = new_index; | |
93 | ||
94 | /* Ideally, new index should have chains half as long as the original. | |
95 | If expansion didn't help, then not worth expanding again, | |
96 | the problem is the hash function. */ | |
97 | losers = 0; | |
98 | for (i = 0; i < hash->size; i++) | |
99 | { | |
100 | unsigned int len = 0; | |
101 | for (hb = hash->index[i]; hb; hb = hb->next) | |
102 | { | |
103 | if (++len > HASH_THRESHOLD/2) | |
104 | ++losers; | |
105 | if (len >= HASH_THRESHOLD) | |
106 | hash->no_expand = 1; | |
107 | } | |
108 | } | |
109 | ||
110 | if (losers > hash->count / 2) | |
111 | hash->no_expand = 1; | |
112 | } | |
113 | ||
718e3744 | 114 | /* Lookup and return hash backet in hash. If there is no |
115 | corresponding hash backet and alloc_func is specified, create new | |
116 | hash backet. */ | |
117 | void * | |
8cc4198f | 118 | hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *)) |
718e3744 | 119 | { |
120 | unsigned int key; | |
121 | unsigned int index; | |
122 | void *newdata; | |
97c84db0 | 123 | unsigned int len; |
718e3744 | 124 | struct hash_backet *backet; |
125 | ||
126 | key = (*hash->hash_key) (data); | |
90645f55 | 127 | index = key & (hash->size - 1); |
97c84db0 | 128 | len = 0; |
718e3744 | 129 | |
97c84db0 SH |
130 | for (backet = hash->index[index]; backet != NULL; backet = backet->next) |
131 | { | |
132 | if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) | |
133 | return backet->data; | |
134 | ++len; | |
135 | } | |
718e3744 | 136 | |
137 | if (alloc_func) | |
138 | { | |
139 | newdata = (*alloc_func) (data); | |
140 | if (newdata == NULL) | |
141 | return NULL; | |
142 | ||
97c84db0 SH |
143 | if (len > HASH_THRESHOLD && !hash->no_expand) |
144 | { | |
145 | hash_expand (hash); | |
146 | index = key & (hash->size - 1); | |
147 | } | |
148 | ||
718e3744 | 149 | backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet)); |
150 | backet->data = newdata; | |
151 | backet->key = key; | |
152 | backet->next = hash->index[index]; | |
153 | hash->index[index] = backet; | |
154 | hash->count++; | |
155 | return backet->data; | |
156 | } | |
157 | return NULL; | |
158 | } | |
159 | ||
160 | /* Hash lookup. */ | |
161 | void * | |
162 | hash_lookup (struct hash *hash, void *data) | |
163 | { | |
164 | return hash_get (hash, data, NULL); | |
165 | } | |
166 | ||
6392aa83 SH |
167 | /* Simple Bernstein hash which is simple and fast for common case */ |
168 | unsigned int string_hash_make (const char *str) | |
169 | { | |
170 | unsigned int hash = 0; | |
171 | ||
172 | while (*str) | |
173 | hash = (hash * 33) ^ (unsigned int) *str++; | |
174 | ||
175 | return hash; | |
176 | } | |
177 | ||
718e3744 | 178 | /* This function release registered value from specified hash. When |
179 | release is successfully finished, return the data pointer in the | |
180 | hash backet. */ | |
181 | void * | |
182 | hash_release (struct hash *hash, void *data) | |
183 | { | |
184 | void *ret; | |
185 | unsigned int key; | |
186 | unsigned int index; | |
187 | struct hash_backet *backet; | |
188 | struct hash_backet *pp; | |
189 | ||
190 | key = (*hash->hash_key) (data); | |
90645f55 | 191 | index = key & (hash->size - 1); |
718e3744 | 192 | |
193 | for (backet = pp = hash->index[index]; backet; backet = backet->next) | |
194 | { | |
195 | if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) | |
196 | { | |
197 | if (backet == pp) | |
198 | hash->index[index] = backet->next; | |
199 | else | |
200 | pp->next = backet->next; | |
201 | ||
202 | ret = backet->data; | |
203 | XFREE (MTYPE_HASH_BACKET, backet); | |
204 | hash->count--; | |
205 | return ret; | |
206 | } | |
207 | pp = backet; | |
208 | } | |
209 | return NULL; | |
210 | } | |
211 | ||
212 | /* Iterator function for hash. */ | |
213 | void | |
214 | hash_iterate (struct hash *hash, | |
215 | void (*func) (struct hash_backet *, void *), void *arg) | |
216 | { | |
8c328f11 | 217 | unsigned int i; |
718e3744 | 218 | struct hash_backet *hb; |
630e4807 | 219 | struct hash_backet *hbnext; |
718e3744 | 220 | |
221 | for (i = 0; i < hash->size; i++) | |
630e4807 | 222 | for (hb = hash->index[i]; hb; hb = hbnext) |
223 | { | |
224 | /* get pointer to next hash backet here, in case (*func) | |
225 | * decides to delete hb by calling hash_release | |
226 | */ | |
227 | hbnext = hb->next; | |
228 | (*func) (hb, arg); | |
229 | } | |
718e3744 | 230 | } |
231 | ||
3f9c7369 DS |
232 | /* Iterator function for hash. */ |
233 | void | |
234 | hash_walk (struct hash *hash, | |
235 | int (*func) (struct hash_backet *, void *), void *arg) | |
236 | { | |
237 | unsigned int i; | |
238 | struct hash_backet *hb; | |
239 | struct hash_backet *hbnext; | |
240 | int ret = HASHWALK_CONTINUE; | |
241 | ||
242 | for (i = 0; i < hash->size; i++) | |
243 | { | |
244 | for (hb = hash->index[i]; hb; hb = hbnext) | |
245 | { | |
246 | /* get pointer to next hash backet here, in case (*func) | |
247 | * decides to delete hb by calling hash_release | |
248 | */ | |
249 | hbnext = hb->next; | |
250 | ret = (*func) (hb, arg); | |
251 | if (ret == HASHWALK_ABORT) | |
252 | return; | |
253 | } | |
254 | } | |
255 | } | |
256 | ||
718e3744 | 257 | /* Clean up hash. */ |
258 | void | |
259 | hash_clean (struct hash *hash, void (*free_func) (void *)) | |
260 | { | |
8c328f11 | 261 | unsigned int i; |
718e3744 | 262 | struct hash_backet *hb; |
263 | struct hash_backet *next; | |
264 | ||
265 | for (i = 0; i < hash->size; i++) | |
266 | { | |
267 | for (hb = hash->index[i]; hb; hb = next) | |
268 | { | |
269 | next = hb->next; | |
270 | ||
271 | if (free_func) | |
272 | (*free_func) (hb->data); | |
273 | ||
274 | XFREE (MTYPE_HASH_BACKET, hb); | |
275 | hash->count--; | |
276 | } | |
277 | hash->index[i] = NULL; | |
278 | } | |
279 | } | |
280 | ||
281 | /* Free hash memory. You may call hash_clean before call this | |
282 | function. */ | |
283 | void | |
284 | hash_free (struct hash *hash) | |
285 | { | |
286 | XFREE (MTYPE_HASH_INDEX, hash->index); | |
287 | XFREE (MTYPE_HASH, hash); | |
288 | } |