hash.c revision f63623779a44c677d8731cbd706a02a615e03b0f
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 * Version: 6.5.1 16 * 17 * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. 18 * 19 * Permission is hereby granted, free of charge, to any person obtaining a 20 * copy of this software and associated documentation files (the "Software"), 21 * to deal in the Software without restriction, including without limitation 22 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 23 * and/or sell copies of the Software, and to permit persons to whom the 24 * Software is furnished to do so, subject to the following conditions: 25 * 26 * The above copyright notice and this permission notice shall be included 27 * in all copies or substantial portions of the Software. 28 * 29 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 30 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 31 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 32 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 33 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 34 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 35 */ 36 37 38#include "glheader.h" 39#include "imports.h" 40#include "glthread.h" 41#include "hash.h" 42 43 44#define TABLE_SIZE 1023 /**< Size of lookup table/array */ 45 46#define HASH_FUNC(K) ((K) % TABLE_SIZE) 47 48 49/** 50 * An entry in the hash table. 51 */ 52struct HashEntry { 53 GLuint Key; /**< the entry's key */ 54 void *Data; /**< the entry's data */ 55 struct HashEntry *Next; /**< pointer to next entry */ 56}; 57 58 59/** 60 * The hash table data structure. 61 */ 62struct _mesa_HashTable { 63 struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */ 64 GLuint MaxKey; /**< highest key inserted so far */ 65 _glthread_Mutex Mutex; /**< mutual exclusion lock */ 66 GLboolean InDeleteAll; /**< Debug check */ 67}; 68 69 70 71/** 72 * Create a new hash table. 73 * 74 * \return pointer to a new, empty hash table. 75 */ 76struct _mesa_HashTable * 77_mesa_NewHashTable(void) 78{ 79 struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); 80 if (table) { 81 _glthread_INIT_MUTEX(table->Mutex); 82 } 83 return table; 84} 85 86 87 88/** 89 * Delete a hash table. 90 * Frees each entry on the hash table and then the hash table structure itself. 91 * Note that the caller should have already traversed the table and deleted 92 * the objects in the table (i.e. We don't free the entries' data pointer). 93 * 94 * \param table the hash table to delete. 95 */ 96void 97_mesa_DeleteHashTable(struct _mesa_HashTable *table) 98{ 99 GLuint pos; 100 assert(table); 101 for (pos = 0; pos < TABLE_SIZE; pos++) { 102 struct HashEntry *entry = table->Table[pos]; 103 while (entry) { 104 struct HashEntry *next = entry->Next; 105 if (entry->Data) { 106 _mesa_problem(NULL, 107 "In _mesa_DeleteHashTable, found non-freed data"); 108 } 109 _mesa_free(entry); 110 entry = next; 111 } 112 } 113 _glthread_DESTROY_MUTEX(table->Mutex); 114 _mesa_free(table); 115} 116 117 118 119/** 120 * Lookup an entry in the hash table. 121 * 122 * \param table the hash table. 123 * \param key the key. 124 * 125 * \return pointer to user's data or NULL if key not in table 126 */ 127void * 128_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key) 129{ 130 GLuint pos; 131 const struct HashEntry *entry; 132 133 assert(table); 134 assert(key); 135 136 pos = HASH_FUNC(key); 137 entry = table->Table[pos]; 138 while (entry) { 139 if (entry->Key == key) { 140 return entry->Data; 141 } 142 entry = entry->Next; 143 } 144 return NULL; 145} 146 147 148 149/** 150 * Insert a key/pointer pair into the hash table. 151 * If an entry with this key already exists we'll replace the existing entry. 152 * 153 * \param table the hash table. 154 * \param key the key (not zero). 155 * \param data pointer to user data. 156 */ 157void 158_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) 159{ 160 /* search for existing entry with this key */ 161 GLuint pos; 162 struct HashEntry *entry; 163 164 assert(table); 165 assert(key); 166 167 _glthread_LOCK_MUTEX(table->Mutex); 168 169 if (key > table->MaxKey) 170 table->MaxKey = key; 171 172 pos = HASH_FUNC(key); 173 174 /* check if replacing an existing entry with same key */ 175 for (entry = table->Table[pos]; entry; entry = entry->Next) { 176 if (entry->Key == key) { 177 /* replace entry's data */ 178 if (entry->Data) { 179 _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert"); 180 } 181 entry->Data = data; 182 _glthread_UNLOCK_MUTEX(table->Mutex); 183 return; 184 } 185 } 186 187 /* alloc and insert new table entry */ 188 entry = MALLOC_STRUCT(HashEntry); 189 entry->Key = key; 190 entry->Data = data; 191 entry->Next = table->Table[pos]; 192 table->Table[pos] = entry; 193 194 _glthread_UNLOCK_MUTEX(table->Mutex); 195} 196 197 198 199/** 200 * Remove an entry from the hash table. 201 * 202 * \param table the hash table. 203 * \param key key of entry to remove. 204 * 205 * While holding the hash table's lock, searches the entry with the matching 206 * key and unlinks it. 207 */ 208void 209_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 210{ 211 GLuint pos; 212 struct HashEntry *entry, *prev; 213 214 assert(table); 215 assert(key); 216 217 /* have to check this outside of mutex lock */ 218 if (table->InDeleteAll) { 219 _mesa_problem(NULL, "_mesa_HashRemove illegally called from " 220 "_mesa_HashDeleteAll callback function"); 221 return; 222 } 223 224 _glthread_LOCK_MUTEX(table->Mutex); 225 226 pos = HASH_FUNC(key); 227 prev = NULL; 228 entry = table->Table[pos]; 229 while (entry) { 230 if (entry->Key == key) { 231 /* found it! */ 232 if (prev) { 233 prev->Next = entry->Next; 234 } 235 else { 236 table->Table[pos] = entry->Next; 237 } 238 _mesa_free(entry); 239 _glthread_UNLOCK_MUTEX(table->Mutex); 240 return; 241 } 242 prev = entry; 243 entry = entry->Next; 244 } 245 246 _glthread_UNLOCK_MUTEX(table->Mutex); 247} 248 249 250 251/** 252 * Delete all entries in a hash table, but don't delete the table itself. 253 * Invoke the given callback function for each table entry. 254 * 255 * \param table the hash table to delete 256 * \param callback the callback function 257 * \param userData arbitrary pointer to pass along to the callback 258 * (this is typically a GLcontext pointer) 259 */ 260void 261_mesa_HashDeleteAll(struct _mesa_HashTable *table, 262 void (*callback)(GLuint key, void *data, void *userData), 263 void *userData) 264{ 265 GLuint pos; 266 ASSERT(table); 267 ASSERT(callback); 268 _glthread_LOCK_MUTEX(table->Mutex); 269 table->InDeleteAll = GL_TRUE; 270 for (pos = 0; pos < TABLE_SIZE; pos++) { 271 struct HashEntry *entry, *next; 272 for (entry = table->Table[pos]; entry; entry = next) { 273 callback(entry->Key, entry->Data, userData); 274 next = entry->Next; 275 _mesa_free(entry); 276 } 277 table->Table[pos] = NULL; 278 } 279 table->InDeleteAll = GL_FALSE; 280 _glthread_UNLOCK_MUTEX(table->Mutex); 281} 282 283 284/** 285 * Walk over all entries in a hash table, calling callback function for each. 286 * \param table the hash table to walk 287 * \param callback the callback function 288 * \param userData arbitrary pointer to pass along to the callback 289 * (this is typically a GLcontext pointer) 290 */ 291void 292_mesa_HashWalk(const struct _mesa_HashTable *table, 293 void (*callback)(GLuint key, void *data, void *userData), 294 void *userData) 295{ 296 /* cast-away const */ 297 struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; 298 GLuint pos; 299 ASSERT(table); 300 ASSERT(callback); 301 _glthread_UNLOCK_MUTEX(table2->Mutex); 302 for (pos = 0; pos < TABLE_SIZE; pos++) { 303 struct HashEntry *entry; 304 for (entry = table->Table[pos]; entry; entry = entry->Next) { 305 callback(entry->Key, entry->Data, userData); 306 } 307 } 308 _glthread_UNLOCK_MUTEX(table2->Mutex); 309} 310 311 312/** 313 * Return the key of the "first" entry in the hash table. 314 * While holding the lock, walks through all table positions until finding 315 * the first entry of the first non-empty one. 316 * 317 * \param table the hash table 318 * \return key for the "first" entry in the hash table. 319 */ 320GLuint 321_mesa_HashFirstEntry(struct _mesa_HashTable *table) 322{ 323 GLuint pos; 324 assert(table); 325 _glthread_LOCK_MUTEX(table->Mutex); 326 for (pos = 0; pos < TABLE_SIZE; pos++) { 327 if (table->Table[pos]) { 328 _glthread_UNLOCK_MUTEX(table->Mutex); 329 return table->Table[pos]->Key; 330 } 331 } 332 _glthread_UNLOCK_MUTEX(table->Mutex); 333 return 0; 334} 335 336 337/** 338 * Given a hash table key, return the next key. This is used to walk 339 * over all entries in the table. Note that the keys returned during 340 * walking won't be in any particular order. 341 * \return next hash key or 0 if end of table. 342 */ 343GLuint 344_mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key) 345{ 346 const struct HashEntry *entry; 347 GLuint pos; 348 349 assert(table); 350 assert(key); 351 352 /* Find the entry with given key */ 353 pos = HASH_FUNC(key); 354 for (entry = table->Table[pos]; entry ; entry = entry->Next) { 355 if (entry->Key == key) { 356 break; 357 } 358 } 359 360 if (!entry) { 361 /* the given key was not found, so we can't find the next entry */ 362 return 0; 363 } 364 365 if (entry->Next) { 366 /* return next in linked list */ 367 return entry->Next->Key; 368 } 369 else { 370 /* look for next non-empty table slot */ 371 pos++; 372 while (pos < TABLE_SIZE) { 373 if (table->Table[pos]) { 374 return table->Table[pos]->Key; 375 } 376 pos++; 377 } 378 return 0; 379 } 380} 381 382 383/** 384 * Dump contents of hash table for debugging. 385 * 386 * \param table the hash table. 387 */ 388void 389_mesa_HashPrint(const struct _mesa_HashTable *table) 390{ 391 GLuint pos; 392 assert(table); 393 for (pos = 0; pos < TABLE_SIZE; pos++) { 394 const struct HashEntry *entry = table->Table[pos]; 395 while (entry) { 396 _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data); 397 entry = entry->Next; 398 } 399 } 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); 421 _glthread_LOCK_MUTEX(table->Mutex); 422 if (maxKey - numKeys > table->MaxKey) { 423 /* the quick solution */ 424 _glthread_UNLOCK_MUTEX(table->Mutex); 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(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 _glthread_UNLOCK_MUTEX(table->Mutex); 443 return freeStart; 444 } 445 } 446 } 447 /* cannot allocate a block of numKeys consecutive keys */ 448 _glthread_UNLOCK_MUTEX(table->Mutex); 449 return 0; 450 } 451} 452 453 454#if 0 /* debug only */ 455 456/** 457 * Test walking over all the entries in a hash table. 458 */ 459static void 460test_hash_walking(void) 461{ 462 struct _mesa_HashTable *t = _mesa_NewHashTable(); 463 const GLuint limit = 50000; 464 GLuint i; 465 466 /* create some entries */ 467 for (i = 0; i < limit; i++) { 468 GLuint dummy; 469 GLuint k = (rand() % (limit * 10)) + 1; 470 while (_mesa_HashLookup(t, k)) { 471 /* id already in use, try another */ 472 k = (rand() % (limit * 10)) + 1; 473 } 474 _mesa_HashInsert(t, k, &dummy); 475 } 476 477 /* walk over all entries */ 478 { 479 GLuint k = _mesa_HashFirstEntry(t); 480 GLuint count = 0; 481 while (k) { 482 GLuint knext = _mesa_HashNextEntry(t, k); 483 assert(knext != k); 484 _mesa_HashRemove(t, k); 485 count++; 486 k = knext; 487 } 488 assert(count == limit); 489 k = _mesa_HashFirstEntry(t); 490 assert(k==0); 491 } 492 493 _mesa_DeleteHashTable(t); 494} 495 496 497void 498_mesa_test_hash_functions(void) 499{ 500 int a, b, c; 501 struct _mesa_HashTable *t; 502 503 t = _mesa_NewHashTable(); 504 _mesa_HashInsert(t, 501, &a); 505 _mesa_HashInsert(t, 10, &c); 506 _mesa_HashInsert(t, 0xfffffff8, &b); 507 /*_mesa_HashPrint(t);*/ 508 509 assert(_mesa_HashLookup(t,501)); 510 assert(!_mesa_HashLookup(t,1313)); 511 assert(_mesa_HashFindFreeKeyBlock(t, 100)); 512 513 _mesa_DeleteHashTable(t); 514 515 test_hash_walking(); 516} 517 518#endif 519