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