1/** 2 * \file hash.c 3 * Generic hash table. 4 * 5 * Used for display lists, texture objects, vertex/fragment programs, 6 * buffer objects, etc. The hash functions are thread-safe. 7 * 8 * \note key=0 is illegal. 9 * 10 * \author Brian Paul 11 */ 12 13/* 14 * Mesa 3-D graphics library 15 * 16 * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. 17 * 18 * Permission is hereby granted, free of charge, to any person obtaining a 19 * copy of this software and associated documentation files (the "Software"), 20 * to deal in the Software without restriction, including without limitation 21 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 22 * and/or sell copies of the Software, and to permit persons to whom the 23 * Software is furnished to do so, subject to the following conditions: 24 * 25 * The above copyright notice and this permission notice shall be included 26 * in all copies or substantial portions of the Software. 27 * 28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 29 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 31 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 32 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 33 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 34 * OTHER DEALINGS IN THE SOFTWARE. 35 */ 36 37#include "errors.h" 38#include "glheader.h" 39#include "hash.h" 40#include "util/hash_table.h" 41#include "util/u_memory.h" 42#include "util/u_idalloc.h" 43 44 45/** 46 * Create a new hash table. 47 * 48 * \return pointer to a new, empty hash table. 49 */ 50struct _mesa_HashTable * 51_mesa_NewHashTable(void) 52{ 53 struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); 54 55 if (table) { 56 table->ht = _mesa_hash_table_create(NULL, uint_key_hash, 57 uint_key_compare); 58 if (table->ht == NULL) { 59 free(table); 60 _mesa_error_no_memory(__func__); 61 return NULL; 62 } 63 64 _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE)); 65 simple_mtx_init(&table->Mutex, mtx_plain); 66 } 67 else { 68 _mesa_error_no_memory(__func__); 69 } 70 71 return table; 72} 73 74 75 76/** 77 * Delete a hash table. 78 * Frees each entry on the hash table and then the hash table structure itself. 79 * Note that the caller should have already traversed the table and deleted 80 * the objects in the table (i.e. We don't free the entries' data pointer). 81 * 82 * \param table the hash table to delete. 83 */ 84void 85_mesa_DeleteHashTable(struct _mesa_HashTable *table) 86{ 87 assert(table); 88 89 if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) { 90 _mesa_problem(NULL, "In _mesa_DeleteHashTable, found non-freed data"); 91 } 92 93 _mesa_hash_table_destroy(table->ht, NULL); 94 if (table->id_alloc) { 95 util_idalloc_fini(table->id_alloc); 96 free(table->id_alloc); 97 } 98 99 simple_mtx_destroy(&table->Mutex); 100 FREE(table); 101} 102 103static void init_name_reuse(struct _mesa_HashTable *table) 104{ 105 assert(_mesa_hash_table_num_entries(table->ht) == 0); 106 table->id_alloc = MALLOC_STRUCT(util_idalloc); 107 util_idalloc_init(table->id_alloc, 8); 108 ASSERTED GLuint reserve0 = util_idalloc_alloc(table->id_alloc); 109 assert (reserve0 == 0); 110} 111 112void 113_mesa_HashEnableNameReuse(struct _mesa_HashTable *table) 114{ 115 _mesa_HashLockMutex(table); 116 init_name_reuse(table); 117 _mesa_HashUnlockMutex(table); 118} 119 120/** 121 * Lookup an entry in the hash table, without locking. 122 * \sa _mesa_HashLookup 123 */ 124static inline void * 125_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) 126{ 127 const struct hash_entry *entry; 128 129 assert(table); 130 assert(key); 131 132 if (key == DELETED_KEY_VALUE) 133 return table->deleted_key_data; 134 135 entry = _mesa_hash_table_search_pre_hashed(table->ht, 136 uint_hash(key), 137 uint_key(key)); 138 if (!entry) 139 return NULL; 140 141 return entry->data; 142} 143 144 145/** 146 * Lookup an entry in the hash table. 147 * 148 * \param table the hash table. 149 * \param key the key. 150 * 151 * \return pointer to user's data or NULL if key not in table 152 */ 153void * 154_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) 155{ 156 void *res; 157 _mesa_HashLockMutex(table); 158 res = _mesa_HashLookup_unlocked(table, key); 159 _mesa_HashUnlockMutex(table); 160 return res; 161} 162 163 164/** 165 * Lookup an entry in the hash table without locking the mutex. 166 * 167 * The hash table mutex must be locked manually by calling 168 * _mesa_HashLockMutex() before calling this function. 169 * 170 * \param table the hash table. 171 * \param key the key. 172 * 173 * \return pointer to user's data or NULL if key not in table 174 */ 175void * 176_mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key) 177{ 178 return _mesa_HashLookup_unlocked(table, key); 179} 180 181 182static inline void 183_mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data) 184{ 185 uint32_t hash = uint_hash(key); 186 struct hash_entry *entry; 187 188 assert(table); 189 assert(key); 190 191 if (key > table->MaxKey) 192 table->MaxKey = key; 193 194 if (key == DELETED_KEY_VALUE) { 195 table->deleted_key_data = data; 196 } else { 197 entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key)); 198 if (entry) { 199 entry->data = data; 200 } else { 201 _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data); 202 } 203 } 204} 205 206 207/** 208 * Insert a key/pointer pair into the hash table without locking the mutex. 209 * If an entry with this key already exists we'll replace the existing entry. 210 * 211 * The hash table mutex must be locked manually by calling 212 * _mesa_HashLockMutex() before calling this function. 213 * 214 * \param table the hash table. 215 * \param key the key (not zero). 216 * \param data pointer to user data. 217 * \param isGenName true if the key has been generated by a HashFindFreeKey* function 218 */ 219void 220_mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data, 221 GLboolean isGenName) 222{ 223 _mesa_HashInsert_unlocked(table, key, data); 224 if (!isGenName && table->id_alloc) 225 util_idalloc_reserve(table->id_alloc, key); 226} 227 228 229/** 230 * Insert a key/pointer pair into the hash table. 231 * If an entry with this key already exists we'll replace the existing entry. 232 * 233 * \param table the hash table. 234 * \param key the key (not zero). 235 * \param data pointer to user data. 236 * \param isGenName true if the key has been generated by a HashFindFreeKey* function 237 */ 238void 239_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data, 240 GLboolean isGenName) 241{ 242 _mesa_HashLockMutex(table); 243 _mesa_HashInsert_unlocked(table, key, data); 244 if (!isGenName && table->id_alloc) 245 util_idalloc_reserve(table->id_alloc, key); 246 _mesa_HashUnlockMutex(table); 247} 248 249 250/** 251 * Remove an entry from the hash table. 252 * 253 * \param table the hash table. 254 * \param key key of entry to remove. 255 * 256 * While holding the hash table's lock, searches the entry with the matching 257 * key and unlinks it. 258 */ 259static inline void 260_mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key) 261{ 262 struct hash_entry *entry; 263 264 assert(table); 265 assert(key); 266 267 #ifndef NDEBUG 268 /* assert if _mesa_HashRemove illegally called from _mesa_HashDeleteAll 269 * callback function. Have to check this outside of mutex lock. 270 */ 271 assert(!table->InDeleteAll); 272 #endif 273 274 if (key == DELETED_KEY_VALUE) { 275 table->deleted_key_data = NULL; 276 } else { 277 entry = _mesa_hash_table_search_pre_hashed(table->ht, 278 uint_hash(key), 279 uint_key(key)); 280 _mesa_hash_table_remove(table->ht, entry); 281 } 282 283 if (table->id_alloc) 284 util_idalloc_free(table->id_alloc, key); 285} 286 287 288void 289_mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key) 290{ 291 _mesa_HashRemove_unlocked(table, key); 292} 293 294void 295_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 296{ 297 _mesa_HashLockMutex(table); 298 _mesa_HashRemove_unlocked(table, key); 299 _mesa_HashUnlockMutex(table); 300} 301 302/** 303 * Delete all entries in a hash table, but don't delete the table itself. 304 * Invoke the given callback function for each table entry. 305 * 306 * \param table the hash table to delete 307 * \param callback the callback function 308 * \param userData arbitrary pointer to pass along to the callback 309 * (this is typically a struct gl_context pointer) 310 */ 311void 312_mesa_HashDeleteAll(struct _mesa_HashTable *table, 313 void (*callback)(void *data, void *userData), 314 void *userData) 315{ 316 assert(callback); 317 _mesa_HashLockMutex(table); 318 #ifndef NDEBUG 319 table->InDeleteAll = GL_TRUE; 320 #endif 321 hash_table_foreach(table->ht, entry) { 322 callback(entry->data, userData); 323 _mesa_hash_table_remove(table->ht, entry); 324 } 325 if (table->deleted_key_data) { 326 callback(table->deleted_key_data, userData); 327 table->deleted_key_data = NULL; 328 } 329 if (table->id_alloc) { 330 util_idalloc_fini(table->id_alloc); 331 free(table->id_alloc); 332 init_name_reuse(table); 333 } 334 #ifndef NDEBUG 335 table->InDeleteAll = GL_FALSE; 336 #endif 337 table->MaxKey = 0; 338 _mesa_HashUnlockMutex(table); 339} 340 341 342/** 343 * Walk over all entries in a hash table, calling callback function for each. 344 * \param table the hash table to walk 345 * \param callback the callback function 346 * \param userData arbitrary pointer to pass along to the callback 347 * (this is typically a struct gl_context pointer) 348 */ 349static void 350hash_walk_unlocked(const struct _mesa_HashTable *table, 351 void (*callback)(void *data, void *userData), 352 void *userData) 353{ 354 assert(table); 355 assert(callback); 356 357 hash_table_foreach(table->ht, entry) { 358 callback(entry->data, userData); 359 } 360 if (table->deleted_key_data) 361 callback(table->deleted_key_data, userData); 362} 363 364 365void 366_mesa_HashWalk(const struct _mesa_HashTable *table, 367 void (*callback)(void *data, void *userData), 368 void *userData) 369{ 370 /* cast-away const */ 371 struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; 372 373 _mesa_HashLockMutex(table2); 374 hash_walk_unlocked(table, callback, userData); 375 _mesa_HashUnlockMutex(table2); 376} 377 378void 379_mesa_HashWalkLocked(const struct _mesa_HashTable *table, 380 void (*callback)(void *data, void *userData), 381 void *userData) 382{ 383 hash_walk_unlocked(table, callback, userData); 384} 385 386/** 387 * Dump contents of hash table for debugging. 388 * 389 * \param table the hash table. 390 */ 391void 392_mesa_HashPrint(const struct _mesa_HashTable *table) 393{ 394 if (table->deleted_key_data) 395 _mesa_debug(NULL, "%u %p\n", DELETED_KEY_VALUE, table->deleted_key_data); 396 397 hash_table_foreach(table->ht, entry) { 398 _mesa_debug(NULL, "%u %p\n", (unsigned)(uintptr_t) entry->key, 399 entry->data); 400 } 401} 402 403 404/** 405 * Find a block of adjacent unused hash keys. 406 * 407 * \param table the hash table. 408 * \param numKeys number of keys needed. 409 * 410 * \return Starting key of free block or 0 if failure. 411 * 412 * If there are enough free keys between the maximum key existing in the table 413 * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return 414 * the adjacent key. Otherwise do a full search for a free key block in the 415 * allowable key range. 416 */ 417GLuint 418_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) 419{ 420 const GLuint maxKey = ~((GLuint) 0) - 1; 421 if (table->id_alloc && numKeys == 1) { 422 return util_idalloc_alloc(table->id_alloc); 423 } else if (maxKey - numKeys > table->MaxKey) { 424 /* the quick solution */ 425 return table->MaxKey + 1; 426 } 427 else { 428 /* the slow solution */ 429 GLuint freeCount = 0; 430 GLuint freeStart = 1; 431 GLuint key; 432 for (key = 1; key != maxKey; key++) { 433 if (_mesa_HashLookup_unlocked(table, key)) { 434 /* darn, this key is already in use */ 435 freeCount = 0; 436 freeStart = key+1; 437 } 438 else { 439 /* this key not in use, check if we've found enough */ 440 freeCount++; 441 if (freeCount == numKeys) { 442 return freeStart; 443 } 444 } 445 } 446 /* cannot allocate a block of numKeys consecutive keys */ 447 return 0; 448 } 449} 450 451 452bool 453_mesa_HashFindFreeKeys(struct _mesa_HashTable *table, GLuint* keys, GLuint numKeys) 454{ 455 if (!table->id_alloc) { 456 GLuint first = _mesa_HashFindFreeKeyBlock(table, numKeys); 457 for (int i = 0; i < numKeys; i++) { 458 keys[i] = first + i; 459 } 460 return first != 0; 461 } 462 463 for (int i = 0; i < numKeys; i++) { 464 keys[i] = util_idalloc_alloc(table->id_alloc); 465 } 466 467 return true; 468} 469 470 471/** 472 * Return the number of entries in the hash table. 473 */ 474GLuint 475_mesa_HashNumEntries(const struct _mesa_HashTable *table) 476{ 477 GLuint count = 0; 478 479 if (table->deleted_key_data) 480 count++; 481 482 count += _mesa_hash_table_num_entries(table->ht); 483 484 return count; 485} 486