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 util_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 #ifdef HAVE_CONFIG_H
42 #include "config.h"
43 #endif
44
45 #include "util_hash_table.h"
46 #include "util_hash.h"
47
48 #include <stdlib.h>
49 #include <assert.h>
50
51 struct util_hash_table
52 {
53 struct util_hash *head;
54
55 /** Hash function */
56 unsigned (*make_hash)(void *key);
57
58 /** Compare two keys */
59 int (*compare)(void *key1, void *key2);
60 };
61
62 struct util_hash_table_item
63 {
64 void *key;
65 void *value;
66 };
67
68
69 static struct util_hash_table_item *
util_hash_table_item(struct util_hash_iter iter)70 util_hash_table_item(struct util_hash_iter iter)
71 {
72 return (struct util_hash_table_item *)util_hash_iter_data(iter);
73 }
74
75 drm_private struct util_hash_table *
util_hash_table_create(unsigned (* hash)(void * key),int (* compare)(void * key1,void * key2))76 util_hash_table_create(unsigned (*hash)(void *key),
77 int (*compare)(void *key1, void *key2))
78 {
79 struct util_hash_table *ht;
80
81 ht = malloc(sizeof(struct util_hash_table));
82 if(!ht)
83 return NULL;
84
85 ht->head = util_hash_create();
86 if(!ht->head) {
87 free(ht);
88 return NULL;
89 }
90
91 ht->make_hash = hash;
92 ht->compare = compare;
93
94 return ht;
95 }
96
97 static struct util_hash_iter
util_hash_table_find_iter(struct util_hash_table * ht,void * key,unsigned key_hash)98 util_hash_table_find_iter(struct util_hash_table *ht,
99 void *key, unsigned key_hash)
100 {
101 struct util_hash_iter iter;
102 struct util_hash_table_item *item;
103
104 iter = util_hash_find(ht->head, key_hash);
105 while (!util_hash_iter_is_null(iter)) {
106 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
107 if (!ht->compare(item->key, key))
108 break;
109 iter = util_hash_iter_next(iter);
110 }
111
112 return iter;
113 }
114
115 static struct util_hash_table_item *
util_hash_table_find_item(struct util_hash_table * ht,void * key,unsigned key_hash)116 util_hash_table_find_item(struct util_hash_table *ht,
117 void *key, unsigned key_hash)
118 {
119 struct util_hash_iter iter;
120 struct util_hash_table_item *item;
121
122 iter = util_hash_find(ht->head, key_hash);
123 while (!util_hash_iter_is_null(iter)) {
124 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
125 if (!ht->compare(item->key, key))
126 return item;
127 iter = util_hash_iter_next(iter);
128 }
129
130 return NULL;
131 }
132
133 drm_private void
util_hash_table_set(struct util_hash_table * ht,void * key,void * value)134 util_hash_table_set(struct util_hash_table *ht, void *key, void *value)
135 {
136 unsigned key_hash;
137 struct util_hash_table_item *item;
138 struct util_hash_iter iter;
139
140 assert(ht);
141 if (!ht)
142 return;
143
144 key_hash = ht->make_hash(key);
145
146 item = util_hash_table_find_item(ht, key, key_hash);
147 if(item) {
148 /* TODO: key/value destruction? */
149 item->value = value;
150 return;
151 }
152
153 item = malloc(sizeof(struct util_hash_table_item));
154 if(!item)
155 return;
156
157 item->key = key;
158 item->value = value;
159
160 iter = util_hash_insert(ht->head, key_hash, item);
161 if(util_hash_iter_is_null(iter)) {
162 free(item);
163 return;
164 }
165 }
166
util_hash_table_get(struct util_hash_table * ht,void * key)167 drm_private void *util_hash_table_get(struct util_hash_table *ht, void *key)
168 {
169 unsigned key_hash;
170 struct util_hash_table_item *item;
171
172 assert(ht);
173 if (!ht)
174 return NULL;
175
176 key_hash = ht->make_hash(key);
177
178 item = util_hash_table_find_item(ht, key, key_hash);
179 if(!item)
180 return NULL;
181
182 return item->value;
183 }
184
util_hash_table_remove(struct util_hash_table * ht,void * key)185 drm_private void util_hash_table_remove(struct util_hash_table *ht, void *key)
186 {
187 unsigned key_hash;
188 struct util_hash_iter iter;
189 struct util_hash_table_item *item;
190
191 assert(ht);
192 if (!ht)
193 return;
194
195 key_hash = ht->make_hash(key);
196
197 iter = util_hash_table_find_iter(ht, key, key_hash);
198 if(util_hash_iter_is_null(iter))
199 return;
200
201 item = util_hash_table_item(iter);
202 assert(item);
203 free(item);
204
205 util_hash_erase(ht->head, iter);
206 }
207
util_hash_table_clear(struct util_hash_table * ht)208 drm_private void util_hash_table_clear(struct util_hash_table *ht)
209 {
210 struct util_hash_iter iter;
211 struct util_hash_table_item *item;
212
213 assert(ht);
214 if (!ht)
215 return;
216
217 iter = util_hash_first_node(ht->head);
218 while (!util_hash_iter_is_null(iter)) {
219 item = (struct util_hash_table_item *)util_hash_take(ht->head, util_hash_iter_key(iter));
220 free(item);
221 iter = util_hash_first_node(ht->head);
222 }
223 }
224
util_hash_table_foreach(struct util_hash_table * ht,void (* callback)(void * key,void * value,void * data),void * data)225 drm_private void util_hash_table_foreach(struct util_hash_table *ht,
226 void (*callback)(void *key, void *value, void *data),
227 void *data)
228 {
229 struct util_hash_iter iter;
230 struct util_hash_table_item *item;
231
232 assert(ht);
233 if (!ht)
234 return;
235
236 iter = util_hash_first_node(ht->head);
237 while (!util_hash_iter_is_null(iter)) {
238 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
239 callback(item->key, item->value, data);
240 iter = util_hash_iter_next(iter);
241 }
242 }
243
util_hash_table_destroy(struct util_hash_table * ht)244 drm_private void util_hash_table_destroy(struct util_hash_table *ht)
245 {
246 struct util_hash_iter iter;
247 struct util_hash_table_item *item;
248
249 assert(ht);
250 if (!ht)
251 return;
252
253 iter = util_hash_first_node(ht->head);
254 while (!util_hash_iter_is_null(iter)) {
255 item = (struct util_hash_table_item *)util_hash_iter_data(iter);
256 free(item);
257 iter = util_hash_iter_next(iter);
258 }
259
260 util_hash_delete(ht->head);
261 free(ht);
262 }
263