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 } 319
