Annotation of embedaddon/quagga/lib/hash.c, revision 1.1.1.1
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:
34: hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
35: hash->index = XCALLOC (MTYPE_HASH_INDEX,
36: sizeof (struct hash_backet *) * size);
37: hash->size = size;
38: hash->hash_key = hash_key;
39: hash->hash_cmp = hash_cmp;
40: hash->count = 0;
41:
42: return hash;
43: }
44:
45: /* Allocate a new hash with default hash size. */
46: struct hash *
47: hash_create (unsigned int (*hash_key) (void *),
48: int (*hash_cmp) (const void *, const void *))
49: {
50: return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
51: }
52:
53: /* Utility function for hash_get(). When this function is specified
54: as alloc_func, return arugment as it is. This function is used for
55: intern already allocated value. */
56: void *
57: hash_alloc_intern (void *arg)
58: {
59: return arg;
60: }
61:
62: /* Lookup and return hash backet in hash. If there is no
63: corresponding hash backet and alloc_func is specified, create new
64: hash backet. */
65: void *
66: hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
67: {
68: unsigned int key;
69: unsigned int index;
70: void *newdata;
71: struct hash_backet *backet;
72:
73: key = (*hash->hash_key) (data);
74: index = key % hash->size;
75:
76: for (backet = hash->index[index]; backet != NULL; backet = backet->next)
77: if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
78: return backet->data;
79:
80: if (alloc_func)
81: {
82: newdata = (*alloc_func) (data);
83: if (newdata == NULL)
84: return NULL;
85:
86: backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
87: backet->data = newdata;
88: backet->key = key;
89: backet->next = hash->index[index];
90: hash->index[index] = backet;
91: hash->count++;
92: return backet->data;
93: }
94: return NULL;
95: }
96:
97: /* Hash lookup. */
98: void *
99: hash_lookup (struct hash *hash, void *data)
100: {
101: return hash_get (hash, data, NULL);
102: }
103:
104: /* Simple Bernstein hash which is simple and fast for common case */
105: unsigned int string_hash_make (const char *str)
106: {
107: unsigned int hash = 0;
108:
109: while (*str)
110: hash = (hash * 33) ^ (unsigned int) *str++;
111:
112: return hash;
113: }
114:
115: /* This function release registered value from specified hash. When
116: release is successfully finished, return the data pointer in the
117: hash backet. */
118: void *
119: hash_release (struct hash *hash, void *data)
120: {
121: void *ret;
122: unsigned int key;
123: unsigned int index;
124: struct hash_backet *backet;
125: struct hash_backet *pp;
126:
127: key = (*hash->hash_key) (data);
128: index = key % hash->size;
129:
130: for (backet = pp = hash->index[index]; backet; backet = backet->next)
131: {
132: if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
133: {
134: if (backet == pp)
135: hash->index[index] = backet->next;
136: else
137: pp->next = backet->next;
138:
139: ret = backet->data;
140: XFREE (MTYPE_HASH_BACKET, backet);
141: hash->count--;
142: return ret;
143: }
144: pp = backet;
145: }
146: return NULL;
147: }
148:
149: /* Iterator function for hash. */
150: void
151: hash_iterate (struct hash *hash,
152: void (*func) (struct hash_backet *, void *), void *arg)
153: {
154: unsigned int i;
155: struct hash_backet *hb;
156: struct hash_backet *hbnext;
157:
158: for (i = 0; i < hash->size; i++)
159: for (hb = hash->index[i]; hb; hb = hbnext)
160: {
161: /* get pointer to next hash backet here, in case (*func)
162: * decides to delete hb by calling hash_release
163: */
164: hbnext = hb->next;
165: (*func) (hb, arg);
166: }
167: }
168:
169: /* Clean up hash. */
170: void
171: hash_clean (struct hash *hash, void (*free_func) (void *))
172: {
173: unsigned int i;
174: struct hash_backet *hb;
175: struct hash_backet *next;
176:
177: for (i = 0; i < hash->size; i++)
178: {
179: for (hb = hash->index[i]; hb; hb = next)
180: {
181: next = hb->next;
182:
183: if (free_func)
184: (*free_func) (hb->data);
185:
186: XFREE (MTYPE_HASH_BACKET, hb);
187: hash->count--;
188: }
189: hash->index[i] = NULL;
190: }
191: }
192:
193: /* Free hash memory. You may call hash_clean before call this
194: function. */
195: void
196: hash_free (struct hash *hash)
197: {
198: XFREE (MTYPE_HASH_INDEX, hash->index);
199: XFREE (MTYPE_HASH, hash);
200: }
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