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 "util/u_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
;
200 key_hash
= hash(key
, map
->key_size
);
202 item
= hash_table_find_item(map
, key
, key_hash
);
204 /* call delete callback for old entry/item */
205 map
->delete_func(map
, item
->key
, item
->value
, user
);
206 item
->value
= (void *) data
;
210 item
= MALLOC_STRUCT(keymap_item
);
214 item
->key
= mem_dup(key
, map
->key_size
);
215 item
->value
= (void *) data
;
217 iter
= cso_hash_insert(map
->cso
, key_hash
, item
);
218 if (cso_hash_iter_is_null(iter
)) {
230 * Look up a key in the map and return the associated data pointer.
233 util_keymap_lookup(const struct keymap
*map
, const void *key
)
236 struct keymap_item
*item
;
242 key_hash
= hash(key
, map
->key_size
);
244 item
= hash_table_find_item(map
, key
, key_hash
);
253 * Remove an entry from the map.
254 * The delete callback will be called if the given key/entry is found.
255 * \param user passed to the delete callback as the last param.
258 util_keymap_remove(struct keymap
*map
, const void *key
, void *user
)
261 struct cso_hash_iter iter
;
262 struct keymap_item
*item
;
268 key_hash
= hash(key
, map
->key_size
);
270 iter
= hash_table_find_iter(map
, key
, key_hash
);
271 if (cso_hash_iter_is_null(iter
))
274 item
= hash_table_item(iter
);
278 map
->delete_func(map
, item
->key
, item
->value
, user
);
284 cso_hash_erase(map
->cso
, iter
);
289 * Remove all entries from the map, calling the delete callback for each.
290 * \param user passed to the delete callback as the last param.
293 util_keymap_remove_all(struct keymap
*map
, void *user
)
295 struct cso_hash_iter iter
;
296 struct keymap_item
*item
;
302 iter
= cso_hash_first_node(map
->cso
);
303 while (!cso_hash_iter_is_null(iter
)) {
304 item
= (struct keymap_item
*)
305 cso_hash_take(map
->cso
, cso_hash_iter_key(iter
));
306 map
->delete_func(map
, item
->key
, item
->value
, user
);
309 iter
= cso_hash_first_node(map
->cso
);
315 util_keymap_info(const struct keymap
*map
)
317 debug_printf("Keymap %p: %u of max %u entries\n",
318 (void *) map
, map
->num_entries
, map
->max_entries
);