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 u_hash_table, based on CSO cache code for now.
37 #include "pipe/p_compiler.h"
38 #include "pipe/p_debug.h"
39 #include "pipe/p_error.h"
41 #include "cso_cache/cso_hash.h"
43 #include "util/u_memory.h"
44 #include "util/u_keymap.h"
51 unsigned max_entries
; /* XXX not obeyed net */
53 keymap_delete_func delete_func
;
64 * This the default key-delete function used when the client doesn't
68 default_delete_func(const struct keymap
*map
,
69 const void *key
, void *data
, void *user
)
75 static INLINE
struct keymap_item
*
76 hash_table_item(struct cso_hash_iter iter
)
78 return (struct keymap_item
*) cso_hash_iter_data(iter
);
83 * Return 4-byte hash key for a block of bytes.
86 hash(const void *key
, unsigned keySize
)
90 keySize
/= 4; /* convert from bytes to uints */
93 for (i
= 0; i
< keySize
; i
++) {
94 hash
^= (i
+ 1) * ((const unsigned *) key
)[i
];
97 /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/
105 * \param keySize size of the keys in bytes
106 * \param maxEntries max number of entries to allow (~0 = infinity)
107 * \param deleteFunc optional callback to call when entries
108 * are deleted/replaced
111 util_new_keymap(unsigned keySize
, unsigned maxEntries
,
112 keymap_delete_func deleteFunc
)
114 struct keymap
*map
= MALLOC_STRUCT(keymap
);
118 map
->cso
= cso_hash_create();
124 map
->max_entries
= maxEntries
;
125 map
->num_entries
= 0;
126 map
->key_size
= keySize
;
127 map
->delete_func
= deleteFunc
? deleteFunc
: default_delete_func
;
134 * Delete/free a keymap and all entries. The deleteFunc that was given at
135 * create time will be called for each entry.
136 * \param user user-provided pointer passed through to the delete callback
139 util_delete_keymap(struct keymap
*map
, void *user
)
141 util_keymap_remove_all(map
, user
);
142 cso_hash_delete(map
->cso
);
147 static INLINE
struct cso_hash_iter
148 hash_table_find_iter(const struct keymap
*map
, const void *key
,
151 struct cso_hash_iter iter
;
152 struct keymap_item
*item
;
154 iter
= cso_hash_find(map
->cso
, key_hash
);
155 while (!cso_hash_iter_is_null(iter
)) {
156 item
= (struct keymap_item
*) cso_hash_iter_data(iter
);
157 if (!memcmp(item
->key
, key
, map
->key_size
))
159 iter
= cso_hash_iter_next(iter
);
166 static INLINE
struct keymap_item
*
167 hash_table_find_item(const struct keymap
*map
, const void *key
,
170 struct cso_hash_iter iter
= hash_table_find_iter(map
, key
, key_hash
);
171 if (cso_hash_iter_is_null(iter
)) {
175 return hash_table_item(iter
);
181 * Insert a new key + data pointer into the table.
182 * Note: we create a copy of the key, but not the data!
183 * If the key is already present in the table, replace the existing
184 * entry (calling the delete callback on the previous entry).
185 * If the maximum capacity of the map is reached an old entry
186 * will be deleted (the delete callback will be called).
189 util_keymap_insert(struct keymap
*map
, const void *key
,
190 const void *data
, void *user
)
193 struct keymap_item
*item
;
194 struct cso_hash_iter iter
;
198 key_hash
= hash(key
, map
->key_size
);
200 item
= hash_table_find_item(map
, key
, key_hash
);
202 /* call delete callback for old entry/item */
203 map
->delete_func(map
, item
->key
, item
->value
, user
);
204 item
->value
= (void *) data
;
208 item
= MALLOC_STRUCT(keymap_item
);
212 item
->key
= mem_dup(key
, map
->key_size
);
213 item
->value
= (void *) data
;
215 iter
= cso_hash_insert(map
->cso
, key_hash
, item
);
216 if (cso_hash_iter_is_null(iter
)) {
228 * Look up a key in the map and return the associated data pointer.
231 util_keymap_lookup(const struct keymap
*map
, const void *key
)
234 struct keymap_item
*item
;
238 key_hash
= hash(key
, map
->key_size
);
240 item
= hash_table_find_item(map
, key
, key_hash
);
249 * Remove an entry from the map.
250 * The delete callback will be called if the given key/entry is found.
251 * \param user passed to the delete callback as the last param.
254 util_keymap_remove(struct keymap
*map
, const void *key
, void *user
)
257 struct cso_hash_iter iter
;
258 struct keymap_item
*item
;
262 key_hash
= hash(key
, map
->key_size
);
264 iter
= hash_table_find_iter(map
, key
, key_hash
);
265 if (cso_hash_iter_is_null(iter
))
268 item
= hash_table_item(iter
);
270 map
->delete_func(map
, item
->key
, item
->value
, user
);
276 cso_hash_erase(map
->cso
, iter
);
281 * Remove all entries from the map, calling the delete callback for each.
282 * \param user passed to the delete callback as the last param.
285 util_keymap_remove_all(struct keymap
*map
, void *user
)
287 struct cso_hash_iter iter
;
288 struct keymap_item
*item
;
292 iter
= cso_hash_first_node(map
->cso
);
293 while (!cso_hash_iter_is_null(iter
)) {
294 item
= (struct keymap_item
*)
295 cso_hash_take(map
->cso
, cso_hash_iter_key(iter
));
296 map
->delete_func(map
, item
->key
, item
->value
, user
);
299 iter
= cso_hash_first_node(map
->cso
);
305 util_keymap_info(const struct keymap
*map
)
307 debug_printf("Keymap %p: %u of max %u entries\n",
308 (void *) map
, map
->num_entries
, map
->max_entries
);