1 /**************************************************************************
3 * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
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:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
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.
26 **************************************************************************/
29 * Key lookup/associative container.
31 * Like Jose's util_hash_table, based on CSO cache code for now.
37 #include "pipe/p_compiler.h"
38 #include "util/u_debug.h"
40 #include "cso_cache/cso_hash.h"
42 #include "util/u_memory.h"
43 #include "util/u_keymap.h"
50 unsigned max_entries; /* XXX not obeyed net */
52 keymap_delete_func delete_func;
63 * This the default key-delete function used when the client doesn't
67 default_delete_func(const struct keymap *map,
68 const void *key, void *data, void *user)
74 static INLINE struct keymap_item *
75 hash_table_item(struct cso_hash_iter iter)
77 return (struct keymap_item *) cso_hash_iter_data(iter);
82 * Return 4-byte hash key for a block of bytes.
85 hash(const void *key, unsigned keySize)
89 keySize /= 4; /* convert from bytes to uints */
92 for (i = 0; i < keySize; i++) {
93 hash ^= (i + 1) * ((const unsigned *) key)[i];
96 /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/
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
110 util_new_keymap(unsigned keySize, unsigned maxEntries,
111 keymap_delete_func deleteFunc)
113 struct keymap *map = MALLOC_STRUCT(keymap);
117 map->cso = cso_hash_create();
123 map->max_entries = maxEntries;
124 map->num_entries = 0;
125 map->key_size = keySize;
126 map->delete_func = deleteFunc ? deleteFunc : default_delete_func;
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
138 util_delete_keymap(struct keymap *map, void *user)
140 util_keymap_remove_all(map, user);
141 cso_hash_delete(map->cso);
146 static INLINE struct cso_hash_iter
147 hash_table_find_iter(const struct keymap *map, const void *key,
150 struct cso_hash_iter iter;
151 struct keymap_item *item;
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))
158 iter = cso_hash_iter_next(iter);
165 static INLINE struct keymap_item *
166 hash_table_find_item(const struct keymap *map, const void *key,
169 struct cso_hash_iter iter = hash_table_find_iter(map, key, key_hash);
170 if (cso_hash_iter_is_null(iter)) {
174 return hash_table_item(iter);
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).
188 util_keymap_insert(struct keymap *map, const void *key,
189 const void *data, void *user)
192 struct keymap_item *item;
193 struct cso_hash_iter iter;
199 key_hash = hash(key, map->key_size);
201 item = hash_table_find_item(map, key, key_hash);
203 /* call delete callback for old entry/item */
204 map->delete_func(map, item->key, item->value, user);
205 item->value = (void *) data;
209 item = MALLOC_STRUCT(keymap_item);
213 item->key = mem_dup(key, map->key_size);
214 item->value = (void *) data;
216 iter = cso_hash_insert(map->cso, key_hash, item);
217 if (cso_hash_iter_is_null(iter)) {
229 * Look up a key in the map and return the associated data pointer.
232 util_keymap_lookup(const struct keymap *map, const void *key)
235 struct keymap_item *item;
241 key_hash = hash(key, map->key_size);
243 item = hash_table_find_item(map, key, key_hash);
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.
257 util_keymap_remove(struct keymap *map, const void *key, void *user)
260 struct cso_hash_iter iter;
261 struct keymap_item *item;
267 key_hash = hash(key, map->key_size);
269 iter = hash_table_find_iter(map, key, key_hash);
270 if (cso_hash_iter_is_null(iter))
273 item = hash_table_item(iter);
277 map->delete_func(map, item->key, item->value, user);
283 cso_hash_erase(map->cso, iter);
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.
292 util_keymap_remove_all(struct keymap *map, void *user)
294 struct cso_hash_iter iter;
295 struct keymap_item *item;
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);
308 iter = cso_hash_first_node(map->cso);
314 util_keymap_info(const struct keymap *map)
316 debug_printf("Keymap %p: %u of max %u entries\n",
317 (void *) map, map->num_entries, map->max_entries);