]>
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 | ||
27 | /* Allocate a new hash. */ | |
28 | struct hash * | |
8cc4198f | 29 | hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), |
ffe11cfb | 30 | int (*hash_cmp) (const void *, const void *)) |
718e3744 | 31 | { |
32 | struct hash *hash; | |
33 | ||
34 | hash = XMALLOC (MTYPE_HASH, sizeof (struct hash)); | |
393deb9b | 35 | hash->index = XCALLOC (MTYPE_HASH_INDEX, |
718e3744 | 36 | sizeof (struct hash_backet *) * size); |
718e3744 | 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 * | |
8cc4198f | 47 | hash_create (unsigned int (*hash_key) (void *), |
ffe11cfb | 48 | int (*hash_cmp) (const void *, const void *)) |
718e3744 | 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 * | |
8cc4198f | 66 | hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *)) |
718e3744 | 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 | ||
6392aa83 SH |
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 | ||
718e3744 | 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 | { | |
8c328f11 | 154 | unsigned int i; |
718e3744 | 155 | struct hash_backet *hb; |
630e4807 | 156 | struct hash_backet *hbnext; |
718e3744 | 157 | |
158 | for (i = 0; i < hash->size; i++) | |
630e4807 | 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 | } | |
718e3744 | 167 | } |
168 | ||
169 | /* Clean up hash. */ | |
170 | void | |
171 | hash_clean (struct hash *hash, void (*free_func) (void *)) | |
172 | { | |
8c328f11 | 173 | unsigned int i; |
718e3744 | 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 | } |