Annotation of embedaddon/quagga/lib/hash.c, revision 1.1.1.2
1.1 misho 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:
1.1.1.2 ! misho 34: assert ((size & (size-1)) == 0);
1.1 misho 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;
1.1.1.2 ! misho 39: hash->no_expand = 0;
1.1 misho 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: {
1.1.1.2 ! misho 52: return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp);
1.1 misho 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:
1.1.1.2 ! misho 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:
1.1 misho 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;
1.1.1.2 ! misho 119: unsigned int len;
1.1 misho 120: struct hash_backet *backet;
121:
122: key = (*hash->hash_key) (data);
1.1.1.2 ! misho 123: index = key & (hash->size - 1);
! 124: len = 0;
1.1 misho 125:
1.1.1.2 ! misho 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: }
1.1 misho 132:
133: if (alloc_func)
134: {
135: newdata = (*alloc_func) (data);
136: if (newdata == NULL)
137: return NULL;
138:
1.1.1.2 ! misho 139: if (len > HASH_THRESHOLD && !hash->no_expand)
! 140: {
! 141: hash_expand (hash);
! 142: index = key & (hash->size - 1);
! 143: }
! 144:
1.1 misho 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);
1.1.1.2 ! misho 187: index = key & (hash->size - 1);
1.1 misho 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