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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib