1 /**************************************************************************
2 *
3 * Copyright 2008 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28 /**
29 * @file
30 * General purpose hash table implementation.
31 *
32 * Just uses the cso_hash for now, but it might be better switch to a linear
33 * probing hash table implementation at some point -- as it is said they have
34 * better lookup and cache performance and it appears to be possible to write
35 * a lock-free implementation of such hash tables .
36 *
37 * @author José Fonseca <jfonseca@vmware.com>
38 */
39
40
41 #include "pipe/p_compiler.h"
42 #include "util/u_debug.h"
43
44 #include "cso_cache/cso_hash.h"
45
46 #include "util/u_memory.h"
47 #include "util/u_hash_table.h"
48
49
50 struct util_hash_table
51 {
52 struct cso_hash *cso;
53
54 /** Hash function */
55 unsigned (*hash)(void *key);
56
57 /** Compare two keys */
58 int (*compare)(void *key1, void *key2);
59
60 /** free value */
61 void (*destroy)(void *value);
62 };
63
64
65 struct util_hash_table_item
66 {
67 void *key;
68 void *value;
69 };
70
71
72 static inline struct util_hash_table_item *
util_hash_table_item(struct cso_hash_iter iter)73 util_hash_table_item(struct cso_hash_iter iter)
74 {
75 return (struct util_hash_table_item *)cso_hash_iter_data(iter);
76 }
77
78
79 struct util_hash_table *
util_hash_table_create(unsigned (* hash)(void * key),int (* compare)(void * key1,void * key2),void (* destroy)(void * value))80 util_hash_table_create(unsigned (*hash)(void *key),
81 int (*compare)(void *key1, void *key2),
82 void (*destroy)(void *value))
83 {
84 struct util_hash_table *ht;
85
86 ht = MALLOC_STRUCT(util_hash_table);
87 if(!ht)
88 return NULL;
89
90 ht->cso = cso_hash_create();
91 if(!ht->cso) {
92 FREE(ht);
93 return NULL;
94 }
95
96 ht->hash = hash;
97 ht->compare = compare;
98 ht->destroy = destroy;
99
100 return ht;
101 }
102
103
104 static inline struct cso_hash_iter
util_hash_table_find_iter(struct util_hash_table * ht,void * key,unsigned key_hash)105 util_hash_table_find_iter(struct util_hash_table *ht,
106 void *key,
107 unsigned key_hash)
108 {
109 struct cso_hash_iter iter;
110 struct util_hash_table_item *item;
111
112 iter = cso_hash_find(ht->cso, key_hash);
113 while (!cso_hash_iter_is_null(iter)) {
114 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
115 if (!ht->compare(item->key, key))
116 break;
117 iter = cso_hash_iter_next(iter);
118 }
119
120 return iter;
121 }
122
123
124 static inline struct util_hash_table_item *
util_hash_table_find_item(struct util_hash_table * ht,void * key,unsigned key_hash)125 util_hash_table_find_item(struct util_hash_table *ht,
126 void *key,
127 unsigned key_hash)
128 {
129 struct cso_hash_iter iter;
130 struct util_hash_table_item *item;
131
132 iter = cso_hash_find(ht->cso, key_hash);
133 while (!cso_hash_iter_is_null(iter)) {
134 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
135 if (!ht->compare(item->key, key))
136 return item;
137 iter = cso_hash_iter_next(iter);
138 }
139
140 return NULL;
141 }
142
143
144 enum pipe_error
util_hash_table_set(struct util_hash_table * ht,void * key,void * value)145 util_hash_table_set(struct util_hash_table *ht,
146 void *key,
147 void *value)
148 {
149 unsigned key_hash;
150 struct util_hash_table_item *item;
151 struct cso_hash_iter iter;
152
153 assert(ht);
154 if (!ht)
155 return PIPE_ERROR_BAD_INPUT;
156
157 key_hash = ht->hash(key);
158
159 item = util_hash_table_find_item(ht, key, key_hash);
160 if(item) {
161 ht->destroy(item->value);
162 item->value = value;
163 return PIPE_OK;
164 }
165
166 item = MALLOC_STRUCT(util_hash_table_item);
167 if(!item)
168 return PIPE_ERROR_OUT_OF_MEMORY;
169
170 item->key = key;
171 item->value = value;
172
173 iter = cso_hash_insert(ht->cso, key_hash, item);
174 if(cso_hash_iter_is_null(iter)) {
175 FREE(item);
176 return PIPE_ERROR_OUT_OF_MEMORY;
177 }
178
179 return PIPE_OK;
180 }
181
182
183 void *
util_hash_table_get(struct util_hash_table * ht,void * key)184 util_hash_table_get(struct util_hash_table *ht,
185 void *key)
186 {
187 unsigned key_hash;
188 struct util_hash_table_item *item;
189
190 assert(ht);
191 if (!ht)
192 return NULL;
193
194 key_hash = ht->hash(key);
195
196 item = util_hash_table_find_item(ht, key, key_hash);
197 if(!item)
198 return NULL;
199
200 return item->value;
201 }
202
203
204 void
util_hash_table_remove(struct util_hash_table * ht,void * key)205 util_hash_table_remove(struct util_hash_table *ht,
206 void *key)
207 {
208 unsigned key_hash;
209 struct cso_hash_iter iter;
210 struct util_hash_table_item *item;
211
212 assert(ht);
213 if (!ht)
214 return;
215
216 key_hash = ht->hash(key);
217
218 iter = util_hash_table_find_iter(ht, key, key_hash);
219 if(cso_hash_iter_is_null(iter))
220 return;
221
222 item = util_hash_table_item(iter);
223 assert(item);
224 ht->destroy(item->value);
225 FREE(item);
226
227 cso_hash_erase(ht->cso, iter);
228 }
229
230
231 void
util_hash_table_clear(struct util_hash_table * ht)232 util_hash_table_clear(struct util_hash_table *ht)
233 {
234 struct cso_hash_iter iter;
235 struct util_hash_table_item *item;
236
237 assert(ht);
238 if (!ht)
239 return;
240
241 iter = cso_hash_first_node(ht->cso);
242 while (!cso_hash_iter_is_null(iter)) {
243 item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
244 ht->destroy(item->value);
245 FREE(item);
246 iter = cso_hash_first_node(ht->cso);
247 }
248 }
249
250
251 enum pipe_error
util_hash_table_foreach(struct util_hash_table * ht,enum pipe_error (* callback)(void * key,void * value,void * data),void * data)252 util_hash_table_foreach(struct util_hash_table *ht,
253 enum pipe_error (*callback)
254 (void *key, void *value, void *data),
255 void *data)
256 {
257 struct cso_hash_iter iter;
258 struct util_hash_table_item *item;
259 enum pipe_error result;
260
261 assert(ht);
262 if (!ht)
263 return PIPE_ERROR_BAD_INPUT;
264
265 iter = cso_hash_first_node(ht->cso);
266 while (!cso_hash_iter_is_null(iter)) {
267 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
268 result = callback(item->key, item->value, data);
269 if(result != PIPE_OK)
270 return result;
271 iter = cso_hash_iter_next(iter);
272 }
273
274 return PIPE_OK;
275 }
276
277
278 void
util_hash_table_destroy(struct util_hash_table * ht)279 util_hash_table_destroy(struct util_hash_table *ht)
280 {
281 struct cso_hash_iter iter;
282 struct util_hash_table_item *item;
283
284 assert(ht);
285 if (!ht)
286 return;
287
288 iter = cso_hash_first_node(ht->cso);
289 while (!cso_hash_iter_is_null(iter)) {
290 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
291 ht->destroy(item->value);
292 FREE(item);
293 iter = cso_hash_iter_next(iter);
294 }
295
296 cso_hash_delete(ht->cso);
297
298 FREE(ht);
299 }
300