16dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 26dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \file hash.c 36dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Generic hash table. 46dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 5c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Used for display lists, texture objects, vertex/fragment programs, 6c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * buffer objects, etc. The hash functions are thread-safe. 76dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 86dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \note key=0 is illegal. 96dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 106dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \author Brian Paul 116dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 12afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 13afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/* 14afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Mesa 3-D graphics library 159f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Version: 6.5.1 1622144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 179f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. 1822144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 19afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Permission is hereby granted, free of charge, to any person obtaining a 20afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * copy of this software and associated documentation files (the "Software"), 21afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * to deal in the Software without restriction, including without limitation 22afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * the rights to use, copy, modify, merge, publish, distribute, sublicense, 23afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * and/or sell copies of the Software, and to permit persons to whom the 24afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Software is furnished to do so, subject to the following conditions: 2522144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 26afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * The above copyright notice and this permission notice shall be included 27afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * in all copies or substantial portions of the Software. 2822144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 29afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 30afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 31afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 32afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 33afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 34afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 35afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 36afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 376dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 38fbd8f212c3866ec98c1d8c9d3db3ddb7e7c479a5Brian Paul#include "glheader.h" 393c63452e64df7e10aa073c6c3b9492b1d7dabbb8Brian Paul#include "imports.h" 40c223c6b663cd5db39ba19c2be74b88cc3b8f53f3Brian#include "glapi/glthread.h" 41485f04074151686fa24d40e3eeb83029d3d8c425Keith Whitwell#include "hash.h" 42afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 43afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 44aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul#define TABLE_SIZE 1023 /**< Size of lookup table/array */ 45aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul 46aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul#define HASH_FUNC(K) ((K) % TABLE_SIZE) 47aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul 48afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 49c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 506dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * An entry in the hash table. 51c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul */ 52afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgstruct HashEntry { 53c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul GLuint Key; /**< the entry's key */ 54c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul void *Data; /**< the entry's data */ 55c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul struct HashEntry *Next; /**< pointer to next entry */ 56afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg}; 57afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 58f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul 59c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 606dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * The hash table data structure. 61c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul */ 62bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paulstruct _mesa_HashTable { 63c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */ 64c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul GLuint MaxKey; /**< highest key inserted so far */ 65c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul _glthread_Mutex Mutex; /**< mutual exclusion lock */ 66deff09921563419a77bd1aad0054afa34214ed1aBrian Paul _glthread_Mutex WalkMutex; /**< for _mesa_HashWalk() */ 679f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul GLboolean InDeleteAll; /**< Debug check */ 68afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg}; 69afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 70afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 71f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul 72c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 73c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul * Create a new hash table. 746dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 75c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul * \return pointer to a new, empty hash table. 76afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 77c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulstruct _mesa_HashTable * 78c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_NewHashTable(void) 79afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 80dc31d67c0e48a8380baad738bec2673416c44911Brian Paul struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); 81dc31d67c0e48a8380baad738bec2673416c44911Brian Paul if (table) { 82dc31d67c0e48a8380baad738bec2673416c44911Brian Paul _glthread_INIT_MUTEX(table->Mutex); 83deff09921563419a77bd1aad0054afa34214ed1aBrian Paul _glthread_INIT_MUTEX(table->WalkMutex); 84dc31d67c0e48a8380baad738bec2673416c44911Brian Paul } 85dc31d67c0e48a8380baad738bec2673416c44911Brian Paul return table; 86afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 87afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 88afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 89afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 90c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 91afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Delete a hash table. 926dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Frees each entry on the hash table and then the hash table structure itself. 93c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Note that the caller should have already traversed the table and deleted 94c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * the objects in the table (i.e. We don't free the entries' data pointer). 95c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * 96c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * \param table the hash table to delete. 97afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 98c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 99c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_DeleteHashTable(struct _mesa_HashTable *table) 100afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 101f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul GLuint pos; 102afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 103f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 104f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul struct HashEntry *entry = table->Table[pos]; 105afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg while (entry) { 106afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg struct HashEntry *next = entry->Next; 107f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul if (entry->Data) { 108f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul _mesa_problem(NULL, 109f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul "In _mesa_DeleteHashTable, found non-freed data"); 110f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul } 11132f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(entry); 112afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = next; 113afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 114afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 115e15fd85727636627e0cc7d4fd2d5367e178e42ccKeith Whitwell _glthread_DESTROY_MUTEX(table->Mutex); 116deff09921563419a77bd1aad0054afa34214ed1aBrian Paul _glthread_DESTROY_MUTEX(table->WalkMutex); 11732f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(table); 118afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 119afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 120afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 121afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 122c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 1239903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * Lookup an entry in the hash table, without locking. 1249903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \sa _mesa_HashLookup 125afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 1269520f483b8f1e45fa474674b415554988de5d8d3Brian Paulstatic inline void * 127038d2607ab759638217ded3bd1b232d389975af5Brian Paul_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) 128afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 129afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint pos; 130afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg const struct HashEntry *entry; 131afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 132afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 133afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(key); 134afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 135aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul pos = HASH_FUNC(key); 136afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = table->Table[pos]; 137afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg while (entry) { 138afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (entry->Key == key) { 139107a2ec9eef53dee038c1bcc0d956c5667e0b68fBrian Paul return entry->Data; 140afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 141afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = entry->Next; 142afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 143afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return NULL; 144afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 145afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1469903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul 1479903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul/** 1489903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * Lookup an entry in the hash table. 1499903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * 1509903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \param table the hash table. 1519903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \param key the key. 1529903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * 1539903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \return pointer to user's data or NULL if key not in table 1549903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul */ 155038d2607ab759638217ded3bd1b232d389975af5Brian Paulvoid * 156038d2607ab759638217ded3bd1b232d389975af5Brian Paul_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) 157038d2607ab759638217ded3bd1b232d389975af5Brian Paul{ 158038d2607ab759638217ded3bd1b232d389975af5Brian Paul void *res; 159038d2607ab759638217ded3bd1b232d389975af5Brian Paul assert(table); 160038d2607ab759638217ded3bd1b232d389975af5Brian Paul _glthread_LOCK_MUTEX(table->Mutex); 161038d2607ab759638217ded3bd1b232d389975af5Brian Paul res = _mesa_HashLookup_unlocked(table, key); 162038d2607ab759638217ded3bd1b232d389975af5Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 163038d2607ab759638217ded3bd1b232d389975af5Brian Paul return res; 164038d2607ab759638217ded3bd1b232d389975af5Brian Paul} 165afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 166afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 167c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 168c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Insert a key/pointer pair into the hash table. 1696dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * If an entry with this key already exists we'll replace the existing entry. 1706dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1716dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 1726dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param key the key (not zero). 1736dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param data pointer to user data. 174afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 175c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 176c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) 177afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 178afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* search for existing entry with this key */ 179afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint pos; 180afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg struct HashEntry *entry; 181afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 182afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 183afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(key); 184afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1859560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_LOCK_MUTEX(table->Mutex); 1869560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul 187afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (key > table->MaxKey) 188afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg table->MaxKey = key; 189afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 190aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul pos = HASH_FUNC(key); 191f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul 192f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul /* check if replacing an existing entry with same key */ 193f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (entry = table->Table[pos]; entry; entry = entry->Next) { 194afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (entry->Key == key) { 195afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* replace entry's data */ 196bfb2729f9ef6cba2b1351826ac83932ab0ed6a5fBrian Paul#if 0 /* not sure this check is always valid */ 197f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul if (entry->Data) { 198f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert"); 199f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul } 200bfb2729f9ef6cba2b1351826ac83932ab0ed6a5fBrian Paul#endif 201afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry->Data = data; 2029560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 203afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return; 204afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 205afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 206afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 207afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* alloc and insert new table entry */ 208bd5cdaf4442872d3cd2ff94eeafadd481d27fcfbBrian Paul entry = MALLOC_STRUCT(HashEntry); 209693f4af63dd98b963e91259029cc0131b791721cBrian Paul if (entry) { 210693f4af63dd98b963e91259029cc0131b791721cBrian Paul entry->Key = key; 211693f4af63dd98b963e91259029cc0131b791721cBrian Paul entry->Data = data; 212693f4af63dd98b963e91259029cc0131b791721cBrian Paul entry->Next = table->Table[pos]; 213693f4af63dd98b963e91259029cc0131b791721cBrian Paul table->Table[pos] = entry; 214693f4af63dd98b963e91259029cc0131b791721cBrian Paul } 2159560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul 2169560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 217afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 218afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 219afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 220afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 221c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 222afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Remove an entry from the hash table. 2236dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 2246dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 2256dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param key key of entry to remove. 2266dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 2276dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * While holding the hash table's lock, searches the entry with the matching 2286dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * key and unlinks it. 229afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 230c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 231c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 232afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 233afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint pos; 234afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg struct HashEntry *entry, *prev; 235afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 236afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 237afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(key); 238afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 2399f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul /* have to check this outside of mutex lock */ 2409f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul if (table->InDeleteAll) { 2419f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul _mesa_problem(NULL, "_mesa_HashRemove illegally called from " 2429f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul "_mesa_HashDeleteAll callback function"); 2439f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul return; 2449f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 2459f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 2469560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_LOCK_MUTEX(table->Mutex); 2479560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul 248aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul pos = HASH_FUNC(key); 249afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg prev = NULL; 250afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = table->Table[pos]; 251afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg while (entry) { 252afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (entry->Key == key) { 253afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* found it! */ 254afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (prev) { 255afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg prev->Next = entry->Next; 256afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 257afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg else { 258afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg table->Table[pos] = entry->Next; 259afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 26032f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(entry); 2619560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 262afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return; 263afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 264afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg prev = entry; 265afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = entry->Next; 266afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 2679560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul 2689560f05deffaf0321bba1bd0fcc8eeef4199e6e0Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 269afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 270afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 271afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 272afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 273c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 2749f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Delete all entries in a hash table, but don't delete the table itself. 2759f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Invoke the given callback function for each table entry. 2766dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 2779f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param table the hash table to delete 2789f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param callback the callback function 2799f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param userData arbitrary pointer to pass along to the callback 280f9995b30756140724f41daf963fa06167912be7fKristian Høgsberg * (this is typically a struct gl_context pointer) 2819f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul */ 2829f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paulvoid 2839f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul_mesa_HashDeleteAll(struct _mesa_HashTable *table, 2849f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void (*callback)(GLuint key, void *data, void *userData), 2859f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void *userData) 2869f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul{ 2879f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul GLuint pos; 2889f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul ASSERT(table); 2899f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul ASSERT(callback); 2909f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul _glthread_LOCK_MUTEX(table->Mutex); 2919f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul table->InDeleteAll = GL_TRUE; 2929f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 2939f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul struct HashEntry *entry, *next; 2949f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul for (entry = table->Table[pos]; entry; entry = next) { 2959f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul callback(entry->Key, entry->Data, userData); 2969f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul next = entry->Next; 29732f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(entry); 2989f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 2999f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul table->Table[pos] = NULL; 3009f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 3019f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul table->InDeleteAll = GL_FALSE; 3029f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 3039f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul} 3049f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 3059f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 3069f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul/** 3079f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Walk over all entries in a hash table, calling callback function for each. 308deff09921563419a77bd1aad0054afa34214ed1aBrian Paul * Note: we use a separate mutex in this function to avoid a recursive 309deff09921563419a77bd1aad0054afa34214ed1aBrian Paul * locking deadlock (in case the callback calls _mesa_HashRemove()) and to 310deff09921563419a77bd1aad0054afa34214ed1aBrian Paul * prevent multiple threads/contexts from getting tangled up. 311deff09921563419a77bd1aad0054afa34214ed1aBrian Paul * A lock-less version of this function could be used when the table will 312deff09921563419a77bd1aad0054afa34214ed1aBrian Paul * not be modified. 3139f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param table the hash table to walk 3149f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param callback the callback function 3159f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param userData arbitrary pointer to pass along to the callback 316f9995b30756140724f41daf963fa06167912be7fKristian Høgsberg * (this is typically a struct gl_context pointer) 3179f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul */ 3189f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paulvoid 3199f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul_mesa_HashWalk(const struct _mesa_HashTable *table, 3209f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void (*callback)(GLuint key, void *data, void *userData), 3219f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void *userData) 3229f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul{ 3239f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul /* cast-away const */ 3249f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; 3259f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul GLuint pos; 3269f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul ASSERT(table); 3279f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul ASSERT(callback); 328deff09921563419a77bd1aad0054afa34214ed1aBrian Paul _glthread_LOCK_MUTEX(table2->WalkMutex); 3299f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 330deff09921563419a77bd1aad0054afa34214ed1aBrian Paul struct HashEntry *entry, *next; 331deff09921563419a77bd1aad0054afa34214ed1aBrian Paul for (entry = table->Table[pos]; entry; entry = next) { 332deff09921563419a77bd1aad0054afa34214ed1aBrian Paul /* save 'next' pointer now in case the callback deletes the entry */ 333deff09921563419a77bd1aad0054afa34214ed1aBrian Paul next = entry->Next; 3349f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul callback(entry->Key, entry->Data, userData); 3359f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 3369f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 337deff09921563419a77bd1aad0054afa34214ed1aBrian Paul _glthread_UNLOCK_MUTEX(table2->WalkMutex); 3389f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul} 3399f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 3409f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 3419f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul/** 3429f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Return the key of the "first" entry in the hash table. 3436dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * While holding the lock, walks through all table positions until finding 3446dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * the first entry of the first non-empty one. 3459f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * 3469f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param table the hash table 3479f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \return key for the "first" entry in the hash table. 348afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 349c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian PaulGLuint 350c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashFirstEntry(struct _mesa_HashTable *table) 351afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 352afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint pos; 353afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 354832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_LOCK_MUTEX(table->Mutex); 355f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 356832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul if (table->Table[pos]) { 357832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 358afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return table->Table[pos]->Key; 359832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul } 360afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 361832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 362afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return 0; 363afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 364afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 365afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 366c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul/** 367c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Given a hash table key, return the next key. This is used to walk 368c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * over all entries in the table. Note that the keys returned during 369c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * walking won't be in any particular order. 370c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * \return next hash key or 0 if end of table. 371c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul */ 372c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian PaulGLuint 373c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key) 374c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul{ 375c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul const struct HashEntry *entry; 376c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint pos; 377c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 378c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(table); 379c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(key); 380c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 381c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* Find the entry with given key */ 382aaa5a664331600139347039419cd5c8d9493b8aaBrian Paul pos = HASH_FUNC(key); 383f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (entry = table->Table[pos]; entry ; entry = entry->Next) { 384c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul if (entry->Key == key) { 385c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul break; 386c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 387c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 388c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 389c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul if (!entry) { 390f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul /* the given key was not found, so we can't find the next entry */ 391c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul return 0; 392c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 393c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 394c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul if (entry->Next) { 395c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* return next in linked list */ 396c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul return entry->Next->Key; 397c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 398c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul else { 399c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* look for next non-empty table slot */ 400c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul pos++; 401c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul while (pos < TABLE_SIZE) { 402c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul if (table->Table[pos]) { 403c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul return table->Table[pos]->Key; 404c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 405c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul pos++; 406c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 407c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul return 0; 408c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 409c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul} 410c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 411afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 412c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 413afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Dump contents of hash table for debugging. 4146dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4156dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 416afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 417c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 418c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashPrint(const struct _mesa_HashTable *table) 419afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 420f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul GLuint pos; 421afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(table); 422f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 423f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul const struct HashEntry *entry = table->Table[pos]; 424afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg while (entry) { 4254e9676fb13f60ecdbc247b120031f18cd3febcb0Brian Paul _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data); 426afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg entry = entry->Next; 427afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 428afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 429afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 430afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 431afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 432afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 433c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 4346dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Find a block of adjacent unused hash keys. 4356dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4366dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 4376dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param numKeys number of keys needed. 4386dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4396dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return Starting key of free block or 0 if failure. 4406dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4416dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * If there are enough free keys between the maximum key existing in the table 4426dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return 4436dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * the adjacent key. Otherwise do a full search for a free key block in the 4446dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * allowable key range. 445afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 446c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian PaulGLuint 447c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) 448afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 449f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul const GLuint maxKey = ~((GLuint) 0); 450832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_LOCK_MUTEX(table->Mutex); 451afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (maxKey - numKeys > table->MaxKey) { 452afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* the quick solution */ 453832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 454afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return table->MaxKey + 1; 455afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 456afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg else { 457afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* the slow solution */ 458afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint freeCount = 0; 45990d9e02f3ac9bda1650caaf37fe5f0e3f4ce01cfBrian Paul GLuint freeStart = 1; 460afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg GLuint key; 461f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (key = 1; key != maxKey; key++) { 462038d2607ab759638217ded3bd1b232d389975af5Brian Paul if (_mesa_HashLookup_unlocked(table, key)) { 463afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* darn, this key is already in use */ 464afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg freeCount = 0; 465afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg freeStart = key+1; 466afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 467afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg else { 468afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* this key not in use, check if we've found enough */ 469afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg freeCount++; 470afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (freeCount == numKeys) { 471832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 472afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return freeStart; 473afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 474afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 475afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 476afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg /* cannot allocate a block of numKeys consecutive keys */ 477832179c50e2cf5de9735241e4767aea4d6fc33bfBrian Paul _glthread_UNLOCK_MUTEX(table->Mutex); 478afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return 0; 479afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 480afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 481afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 482afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 483f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul/** 484f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul * Return the number of entries in the hash table. 485f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul */ 486f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian PaulGLuint 487f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul_mesa_HashNumEntries(const struct _mesa_HashTable *table) 488f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul{ 489f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul GLuint pos, count = 0; 490f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 491f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul for (pos = 0; pos < TABLE_SIZE; pos++) { 492f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul const struct HashEntry *entry; 493f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul for (entry = table->Table[pos]; entry; entry = entry->Next) { 494f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul count++; 495f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul } 496f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul } 497f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 498f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul return count; 499f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul} 500f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 501f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 502f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 503a2c65f47930ab1c5a56a8c7c81b35dc77b08d472Brian Paul#if 0 /* debug only */ 504a2c65f47930ab1c5a56a8c7c81b35dc77b08d472Brian Paul 505c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul/** 506c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Test walking over all the entries in a hash table. 507c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul */ 508c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulstatic void 509c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paultest_hash_walking(void) 510c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul{ 511c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul struct _mesa_HashTable *t = _mesa_NewHashTable(); 512c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul const GLuint limit = 50000; 513c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint i; 514c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 515c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* create some entries */ 516c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul for (i = 0; i < limit; i++) { 517c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint dummy; 518c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint k = (rand() % (limit * 10)) + 1; 519c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul while (_mesa_HashLookup(t, k)) { 520c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* id already in use, try another */ 521c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul k = (rand() % (limit * 10)) + 1; 522c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 523c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul _mesa_HashInsert(t, k, &dummy); 524c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 525c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 526c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /* walk over all entries */ 527c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul { 528c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint k = _mesa_HashFirstEntry(t); 529c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint count = 0; 530c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul while (k) { 531c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul GLuint knext = _mesa_HashNextEntry(t, k); 532c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(knext != k); 533c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul _mesa_HashRemove(t, k); 534c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul count++; 535c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul k = knext; 536c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 537c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(count == limit); 538c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul k = _mesa_HashFirstEntry(t); 539c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(k==0); 540c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul } 541afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 542c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul _mesa_DeleteHashTable(t); 543c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul} 544c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 545c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 546c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 547c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_test_hash_functions(void) 548afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg{ 549afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg int a, b, c; 550c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul struct _mesa_HashTable *t; 551afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 552bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paul t = _mesa_NewHashTable(); 553bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paul _mesa_HashInsert(t, 501, &a); 554bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paul _mesa_HashInsert(t, 10, &c); 555bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paul _mesa_HashInsert(t, 0xfffffff8, &b); 556c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul /*_mesa_HashPrint(t);*/ 5574e9676fb13f60ecdbc247b120031f18cd3febcb0Brian Paul 558c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(_mesa_HashLookup(t,501)); 559c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(!_mesa_HashLookup(t,1313)); 560c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul assert(_mesa_HashFindFreeKeyBlock(t, 100)); 5614e9676fb13f60ecdbc247b120031f18cd3febcb0Brian Paul 562bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paul _mesa_DeleteHashTable(t); 563afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 564c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul test_hash_walking(); 565afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} 566a2c65f47930ab1c5a56a8c7c81b35dc77b08d472Brian Paul 567a2c65f47930ab1c5a56a8c7c81b35dc77b08d472Brian Paul#endif 568