Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4358 | Serge | 1 | /************************************************************************** |
2 | * |
||
3 | * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas. |
||
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 TUNGSTEN GRAPHICS 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 | * Key lookup/associative container. |
||
30 | * |
||
31 | * Like Jose's util_hash_table, based on CSO cache code for now. |
||
32 | * |
||
33 | * Author: Brian Paul |
||
34 | */ |
||
35 | |||
36 | |||
37 | #include "pipe/p_compiler.h" |
||
38 | #include "util/u_debug.h" |
||
39 | |||
40 | #include "cso_cache/cso_hash.h" |
||
41 | |||
42 | #include "util/u_memory.h" |
||
43 | #include "util/u_keymap.h" |
||
44 | |||
45 | |||
46 | struct keymap |
||
47 | { |
||
48 | struct cso_hash *cso; |
||
49 | unsigned key_size; |
||
50 | unsigned max_entries; /* XXX not obeyed net */ |
||
51 | unsigned num_entries; |
||
52 | keymap_delete_func delete_func; |
||
53 | }; |
||
54 | |||
55 | |||
56 | struct keymap_item |
||
57 | { |
||
58 | void *key, *value; |
||
59 | }; |
||
60 | |||
61 | |||
62 | /** |
||
63 | * This the default key-delete function used when the client doesn't |
||
64 | * provide one. |
||
65 | */ |
||
66 | static void |
||
67 | default_delete_func(const struct keymap *map, |
||
68 | const void *key, void *data, void *user) |
||
69 | { |
||
70 | FREE((void*) data); |
||
71 | } |
||
72 | |||
73 | |||
74 | static INLINE struct keymap_item * |
||
75 | hash_table_item(struct cso_hash_iter iter) |
||
76 | { |
||
77 | return (struct keymap_item *) cso_hash_iter_data(iter); |
||
78 | } |
||
79 | |||
80 | |||
81 | /** |
||
82 | * Return 4-byte hash key for a block of bytes. |
||
83 | */ |
||
84 | static unsigned |
||
85 | hash(const void *key, unsigned keySize) |
||
86 | { |
||
87 | unsigned i, hash; |
||
88 | |||
89 | keySize /= 4; /* convert from bytes to uints */ |
||
90 | |||
91 | hash = 0; |
||
92 | for (i = 0; i < keySize; i++) { |
||
93 | hash ^= (i + 1) * ((const unsigned *) key)[i]; |
||
94 | } |
||
95 | |||
96 | /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/ |
||
97 | |||
98 | return hash; |
||
99 | } |
||
100 | |||
101 | |||
102 | /** |
||
103 | * Create a new map. |
||
104 | * \param keySize size of the keys in bytes |
||
105 | * \param maxEntries max number of entries to allow (~0 = infinity) |
||
106 | * \param deleteFunc optional callback to call when entries |
||
107 | * are deleted/replaced |
||
108 | */ |
||
109 | struct keymap * |
||
110 | util_new_keymap(unsigned keySize, unsigned maxEntries, |
||
111 | keymap_delete_func deleteFunc) |
||
112 | { |
||
113 | struct keymap *map = MALLOC_STRUCT(keymap); |
||
114 | if (!map) |
||
115 | return NULL; |
||
116 | |||
117 | map->cso = cso_hash_create(); |
||
118 | if (!map->cso) { |
||
119 | FREE(map); |
||
120 | return NULL; |
||
121 | } |
||
122 | |||
123 | map->max_entries = maxEntries; |
||
124 | map->num_entries = 0; |
||
125 | map->key_size = keySize; |
||
126 | map->delete_func = deleteFunc ? deleteFunc : default_delete_func; |
||
127 | |||
128 | return map; |
||
129 | } |
||
130 | |||
131 | |||
132 | /** |
||
133 | * Delete/free a keymap and all entries. The deleteFunc that was given at |
||
134 | * create time will be called for each entry. |
||
135 | * \param user user-provided pointer passed through to the delete callback |
||
136 | */ |
||
137 | void |
||
138 | util_delete_keymap(struct keymap *map, void *user) |
||
139 | { |
||
140 | util_keymap_remove_all(map, user); |
||
141 | cso_hash_delete(map->cso); |
||
142 | FREE(map); |
||
143 | } |
||
144 | |||
145 | |||
146 | static INLINE struct cso_hash_iter |
||
147 | hash_table_find_iter(const struct keymap *map, const void *key, |
||
148 | unsigned key_hash) |
||
149 | { |
||
150 | struct cso_hash_iter iter; |
||
151 | struct keymap_item *item; |
||
152 | |||
153 | iter = cso_hash_find(map->cso, key_hash); |
||
154 | while (!cso_hash_iter_is_null(iter)) { |
||
155 | item = (struct keymap_item *) cso_hash_iter_data(iter); |
||
156 | if (!memcmp(item->key, key, map->key_size)) |
||
157 | break; |
||
158 | iter = cso_hash_iter_next(iter); |
||
159 | } |
||
160 | |||
161 | return iter; |
||
162 | } |
||
163 | |||
164 | |||
165 | static INLINE struct keymap_item * |
||
166 | hash_table_find_item(const struct keymap *map, const void *key, |
||
167 | unsigned key_hash) |
||
168 | { |
||
169 | struct cso_hash_iter iter = hash_table_find_iter(map, key, key_hash); |
||
170 | if (cso_hash_iter_is_null(iter)) { |
||
171 | return NULL; |
||
172 | } |
||
173 | else { |
||
174 | return hash_table_item(iter); |
||
175 | } |
||
176 | } |
||
177 | |||
178 | |||
179 | /** |
||
180 | * Insert a new key + data pointer into the table. |
||
181 | * Note: we create a copy of the key, but not the data! |
||
182 | * If the key is already present in the table, replace the existing |
||
183 | * entry (calling the delete callback on the previous entry). |
||
184 | * If the maximum capacity of the map is reached an old entry |
||
185 | * will be deleted (the delete callback will be called). |
||
186 | */ |
||
187 | boolean |
||
188 | util_keymap_insert(struct keymap *map, const void *key, |
||
189 | const void *data, void *user) |
||
190 | { |
||
191 | unsigned key_hash; |
||
192 | struct keymap_item *item; |
||
193 | struct cso_hash_iter iter; |
||
194 | |||
195 | assert(map); |
||
196 | if (!map) |
||
197 | return FALSE; |
||
198 | |||
199 | key_hash = hash(key, map->key_size); |
||
200 | |||
201 | item = hash_table_find_item(map, key, key_hash); |
||
202 | if (item) { |
||
203 | /* call delete callback for old entry/item */ |
||
204 | map->delete_func(map, item->key, item->value, user); |
||
205 | item->value = (void *) data; |
||
206 | return TRUE; |
||
207 | } |
||
208 | |||
209 | item = MALLOC_STRUCT(keymap_item); |
||
210 | if (!item) |
||
211 | return FALSE; |
||
212 | |||
213 | item->key = mem_dup(key, map->key_size); |
||
214 | item->value = (void *) data; |
||
215 | |||
216 | iter = cso_hash_insert(map->cso, key_hash, item); |
||
217 | if (cso_hash_iter_is_null(iter)) { |
||
218 | FREE(item); |
||
219 | return FALSE; |
||
220 | } |
||
221 | |||
222 | map->num_entries++; |
||
223 | |||
224 | return TRUE; |
||
225 | } |
||
226 | |||
227 | |||
228 | /** |
||
229 | * Look up a key in the map and return the associated data pointer. |
||
230 | */ |
||
231 | const void * |
||
232 | util_keymap_lookup(const struct keymap *map, const void *key) |
||
233 | { |
||
234 | unsigned key_hash; |
||
235 | struct keymap_item *item; |
||
236 | |||
237 | assert(map); |
||
238 | if (!map) |
||
239 | return NULL; |
||
240 | |||
241 | key_hash = hash(key, map->key_size); |
||
242 | |||
243 | item = hash_table_find_item(map, key, key_hash); |
||
244 | if (!item) |
||
245 | return NULL; |
||
246 | |||
247 | return item->value; |
||
248 | } |
||
249 | |||
250 | |||
251 | /** |
||
252 | * Remove an entry from the map. |
||
253 | * The delete callback will be called if the given key/entry is found. |
||
254 | * \param user passed to the delete callback as the last param. |
||
255 | */ |
||
256 | void |
||
257 | util_keymap_remove(struct keymap *map, const void *key, void *user) |
||
258 | { |
||
259 | unsigned key_hash; |
||
260 | struct cso_hash_iter iter; |
||
261 | struct keymap_item *item; |
||
262 | |||
263 | assert(map); |
||
264 | if (!map) |
||
265 | return; |
||
266 | |||
267 | key_hash = hash(key, map->key_size); |
||
268 | |||
269 | iter = hash_table_find_iter(map, key, key_hash); |
||
270 | if (cso_hash_iter_is_null(iter)) |
||
271 | return; |
||
272 | |||
273 | item = hash_table_item(iter); |
||
274 | assert(item); |
||
275 | if (!item) |
||
276 | return; |
||
277 | map->delete_func(map, item->key, item->value, user); |
||
278 | FREE(item->key); |
||
279 | FREE(item); |
||
280 | |||
281 | map->num_entries--; |
||
282 | |||
283 | cso_hash_erase(map->cso, iter); |
||
284 | } |
||
285 | |||
286 | |||
287 | /** |
||
288 | * Remove all entries from the map, calling the delete callback for each. |
||
289 | * \param user passed to the delete callback as the last param. |
||
290 | */ |
||
291 | void |
||
292 | util_keymap_remove_all(struct keymap *map, void *user) |
||
293 | { |
||
294 | struct cso_hash_iter iter; |
||
295 | struct keymap_item *item; |
||
296 | |||
297 | assert(map); |
||
298 | if (!map) |
||
299 | return; |
||
300 | |||
301 | iter = cso_hash_first_node(map->cso); |
||
302 | while (!cso_hash_iter_is_null(iter)) { |
||
303 | item = (struct keymap_item *) |
||
304 | cso_hash_take(map->cso, cso_hash_iter_key(iter)); |
||
305 | map->delete_func(map, item->key, item->value, user); |
||
306 | FREE(item->key); |
||
307 | FREE(item); |
||
308 | iter = cso_hash_first_node(map->cso); |
||
309 | } |
||
310 | } |
||
311 | |||
312 | |||
313 | extern void |
||
314 | util_keymap_info(const struct keymap *map) |
||
315 | { |
||
316 | debug_printf("Keymap %p: %u of max %u entries\n", |
||
317 | (void *) map, map->num_entries, map->max_entries); |
||
318 | }> |