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 */ 12afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 13afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach/* 14afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Mesa 3-D graphics library 1522144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 169f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. 1722144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 18afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Permission is hereby granted, free of charge, to any person obtaining a 19afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * copy of this software and associated documentation files (the "Software"), 20afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * to deal in the Software without restriction, including without limitation 21afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * the rights to use, copy, modify, merge, publish, distribute, sublicense, 22afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * and/or sell copies of the Software, and to permit persons to whom the 23afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Software is furnished to do so, subject to the following conditions: 2422144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 25afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * The above copyright notice and this permission notice shall be included 26afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * in all copies or substantial portions of the Software. 2722144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 28afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 29afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 313d8d5b298a268b119d840bc9bae0ee9e0c9244a9Kenneth Graunke * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 323d8d5b298a268b119d840bc9bae0ee9e0c9244a9Kenneth Graunke * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 333d8d5b298a268b119d840bc9bae0ee9e0c9244a9Kenneth Graunke * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 343d8d5b298a268b119d840bc9bae0ee9e0c9244a9Kenneth Graunke * OTHER DEALINGS IN THE SOFTWARE. 35afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 36afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 37fbd8f212c3866ec98c1d8c9d3db3ddb7e7c479a5Brian Paul#include "glheader.h" 383c63452e64df7e10aa073c6c3b9492b1d7dabbb8Brian Paul#include "imports.h" 39485f04074151686fa24d40e3eeb83029d3d8c425Keith Whitwell#include "hash.h" 4072e55bb6888ff4d6b69b10d9c58573e4c3d492ecKenneth Graunke#include "util/hash_table.h" 41afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 42c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 436991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * Magic GLuint object name that gets stored outside of the struct hash_table. 446991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * 456991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * The hash table needs a particular pointer to be the marker for a key that 466991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * was deleted from the table, along with NULL for the "never allocated in the 476991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * table" marker. Legacy GL allows any GLuint to be used as a GL object name, 486991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * and we use a 1:1 mapping from GLuints to key pointers, so we need to be 496991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * able to track a GLuint that happens to match the deleted key outside of 506991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * struct hash_table. We tell the hash table to use "1" as the deleted key 516991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * value, so that we test the deleted-key-in-the-table path as best we can. 52c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul */ 536991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt#define DELETED_KEY_VALUE 1 54f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul 55c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 566dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * The hash table data structure. 57c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul */ 58bb79790662f56eb71aafd3f020cd86ad810f56b2Brian Paulstruct _mesa_HashTable { 596991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt struct hash_table *ht; 60c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul GLuint MaxKey; /**< highest key inserted so far */ 61d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_t Mutex; /**< mutual exclusion lock */ 629f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul GLboolean InDeleteAll; /**< Debug check */ 636991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt /** Value that would be in the table for DELETED_KEY_VALUE. */ 646991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt void *deleted_key_data; 65afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach}; 66afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 676991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt/** @{ 686991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * Mapping from our use of GLuint as both the key and the hash value to the 696991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * hash_table.h API 706991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * 716991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * There exist many integer hash functions, designed to avoid collisions when 726991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * the integers are spread across key space with some patterns. In GL, the 736991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * pattern (in the case of glGen*()ed object IDs) is that the keys are unique 746991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * contiguous integers starting from 1. Because of that, we just use the key 756991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * as the hash value, to minimize the cost of the hash function. If objects 766991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * are never deleted, we will never see a collision in the table, because the 776991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * table resizes itself when it approaches full, and thus key % table_size == 786991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * key. 796991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * 806991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * The case where we could have collisions for genned objects would be 816991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * something like: glGenBuffers(&a, 100); glDeleteBuffers(&a + 50, 50); 826991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * glGenBuffers(&b, 100), because objects 1-50 and 101-200 are allocated at 836991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * the end of that sequence, instead of 1-150. So far it doesn't appear to be 846991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt * a problem. 856991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt */ 866991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtstatic bool 876991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtuint_key_compare(const void *a, const void *b) 886991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt{ 896991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return a == b; 906991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt} 916991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 926991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtstatic uint32_t 936991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtuint_hash(GLuint id) 946991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt{ 956991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return id; 966991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt} 97afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 9894303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrandstatic uint32_t 9994303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstranduint_key_hash(const void *key) 10094303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand{ 10194303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand return uint_hash((uintptr_t)key); 10294303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand} 10394303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand 1046991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtstatic void * 1056991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtuint_key(GLuint id) 1066991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt{ 1076991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return (void *)(uintptr_t) id; 1086991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt} 1096991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt/** @} */ 110f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul 111c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 112c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul * Create a new hash table. 1136dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 114c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul * \return pointer to a new, empty hash table. 115afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 116c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulstruct _mesa_HashTable * 117c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_NewHashTable(void) 118afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 119dc31d67c0e48a8380baad738bec2673416c44911Brian Paul struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); 1206991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 121dc31d67c0e48a8380baad738bec2673416c44911Brian Paul if (table) { 12294303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand table->ht = _mesa_hash_table_create(NULL, uint_key_hash, 12394303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand uint_key_compare); 12477a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila if (table->ht == NULL) { 12577a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila free(table); 12677a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila _mesa_error_no_memory(__func__); 12777a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila return NULL; 12877a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila } 12977a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila 1302cc0b3294ae0b1181bdcbca91fd68ebab374dbb2Ian Romanick _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE)); 1312e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson /* 1322e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson * Needs to be recursive, since the callback in _mesa_HashWalk() 1332e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson * is allowed to call _mesa_HashRemove(). 1342e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson */ 1352e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson mtx_init(&table->Mutex, mtx_recursive); 136dc31d67c0e48a8380baad738bec2673416c44911Brian Paul } 13777a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila else { 13877a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila _mesa_error_no_memory(__func__); 13977a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila } 14077a00c71bb3ecaafc9ceec035937c02e75a505b6Juha-Pekka Heikkila 141dc31d67c0e48a8380baad738bec2673416c44911Brian Paul return table; 142afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 143afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 144afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 145afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 146c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 147afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Delete a hash table. 1486dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Frees each entry on the hash table and then the hash table structure itself. 149c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * Note that the caller should have already traversed the table and deleted 150c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * the objects in the table (i.e. We don't free the entries' data pointer). 151c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * 152c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul * \param table the hash table to delete. 153afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 154c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 155c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_DeleteHashTable(struct _mesa_HashTable *table) 156afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 157afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(table); 1586991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 1596991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) { 1606991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_problem(NULL, "In _mesa_DeleteHashTable, found non-freed data"); 161afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 1626991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 1636991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_hash_table_destroy(table->ht, NULL); 1646991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 165d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_destroy(&table->Mutex); 16632f2fd1c5d6088692551c80352b7d6fa35b0cd09Kristian Høgsberg free(table); 167afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 168afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 169afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 170afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 171c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 1729903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * Lookup an entry in the hash table, without locking. 1739903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \sa _mesa_HashLookup 174afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 1759520f483b8f1e45fa474674b415554988de5d8d3Brian Paulstatic inline void * 176038d2607ab759638217ded3bd1b232d389975af5Brian Paul_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) 177afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 1786991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt const struct hash_entry *entry; 179afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 180afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(table); 181afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(key); 182afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 1836991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (key == DELETED_KEY_VALUE) 1846991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return table->deleted_key_data; 1856991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 18694303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand entry = _mesa_hash_table_search(table->ht, uint_key(key)); 1876991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (!entry) 1886991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return NULL; 1896991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 1906991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return entry->data; 191afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 192afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 1939903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul 1949903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul/** 1959903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * Lookup an entry in the hash table. 1969903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * 1979903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \param table the hash table. 1989903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \param key the key. 1999903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * 2009903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul * \return pointer to user's data or NULL if key not in table 2019903d09f82c525690cd016e7747ba2fe96c6468fBrian Paul */ 202038d2607ab759638217ded3bd1b232d389975af5Brian Paulvoid * 203038d2607ab759638217ded3bd1b232d389975af5Brian Paul_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) 204038d2607ab759638217ded3bd1b232d389975af5Brian Paul{ 205038d2607ab759638217ded3bd1b232d389975af5Brian Paul void *res; 206038d2607ab759638217ded3bd1b232d389975af5Brian Paul assert(table); 207d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_lock(&table->Mutex); 208038d2607ab759638217ded3bd1b232d389975af5Brian Paul res = _mesa_HashLookup_unlocked(table, key); 209d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_unlock(&table->Mutex); 210038d2607ab759638217ded3bd1b232d389975af5Brian Paul return res; 211038d2607ab759638217ded3bd1b232d389975af5Brian Paul} 212afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 213afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 214c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 21582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * Lookup an entry in the hash table without locking the mutex. 21682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 21782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * The hash table mutex must be locked manually by calling 21882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * _mesa_HashLockMutex() before calling this function. 21982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 22082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param table the hash table. 22182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param key the key. 22282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 22382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \return pointer to user's data or NULL if key not in table 22482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund */ 22582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglundvoid * 22682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key) 22782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund{ 22882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund return _mesa_HashLookup_unlocked(table, key); 22982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund} 23082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 23182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 23282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund/** 23382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * Lock the hash table mutex. 23482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 23582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * This function should be used when multiple objects need 23682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * to be looked up in the hash table, to avoid having to lock 23782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * and unlock the mutex each time. 23882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 2396dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 240afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 241c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 24282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashLockMutex(struct _mesa_HashTable *table) 24382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund{ 24482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund assert(table); 24582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund mtx_lock(&table->Mutex); 24682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund} 24782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 24882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 24982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund/** 25082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * Unlock the hash table mutex. 25182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 25282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param table the hash table. 25382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund */ 25482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglundvoid 25582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashUnlockMutex(struct _mesa_HashTable *table) 25682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund{ 25782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund assert(table); 25882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund mtx_unlock(&table->Mutex); 25982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund} 26082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 26182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 26282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglundstatic inline void 26382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data) 264afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 2656991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt uint32_t hash = uint_hash(key); 2666991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt struct hash_entry *entry; 267afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 268afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(table); 269afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(key); 270afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 271afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach if (key > table->MaxKey) 272afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach table->MaxKey = key; 273afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 2746991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (key == DELETED_KEY_VALUE) { 2756991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt table->deleted_key_data = data; 2766991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt } else { 27794303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key)); 2786991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (entry) { 2796991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt entry->data = data; 2806991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt } else { 2818ed5305d28d9309d651dfec3fbf4349854694694Jason Ekstrand _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data); 282afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 283afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 28482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund} 285afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 28682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 28782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund/** 28882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * Insert a key/pointer pair into the hash table without locking the mutex. 28982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * If an entry with this key already exists we'll replace the existing entry. 29082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 29182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * The hash table mutex must be locked manually by calling 29282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * _mesa_HashLockMutex() before calling this function. 29382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 29482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param table the hash table. 29582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param key the key (not zero). 29682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param data pointer to user data. 29782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund */ 29882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglundvoid 29982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data) 30082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund{ 30182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund _mesa_HashInsert_unlocked(table, key, data); 302afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 303afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 304afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 30582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund/** 30682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * Insert a key/pointer pair into the hash table. 30782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * If an entry with this key already exists we'll replace the existing entry. 30882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * 30982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param table the hash table. 31082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param key the key (not zero). 31182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund * \param data pointer to user data. 31282291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund */ 31382291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglundvoid 31482291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) 31582291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund{ 31682291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund assert(table); 31782291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund mtx_lock(&table->Mutex); 31882291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund _mesa_HashInsert_unlocked(table, key, data); 31982291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund mtx_unlock(&table->Mutex); 32082291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund} 32182291f64e378825e1c716742fc215db99fc8cbb2Fredrik Höglund 322afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 323c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 324afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Remove an entry from the hash table. 3256dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 3266dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 3276dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param key key of entry to remove. 3286dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 3296dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * While holding the hash table's lock, searches the entry with the matching 3306dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * key and unlinks it. 331afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 332aded1160e5e722610dd474583d78e745291cbd75Matt Turnerstatic inline void 333aded1160e5e722610dd474583d78e745291cbd75Matt Turner_mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key) 334afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 3356991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt struct hash_entry *entry; 336afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 337afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(table); 338afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach assert(key); 339afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 3409f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul /* have to check this outside of mutex lock */ 3419f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul if (table->InDeleteAll) { 3429f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul _mesa_problem(NULL, "_mesa_HashRemove illegally called from " 3439f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul "_mesa_HashDeleteAll callback function"); 3449f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul return; 3459f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 3469f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 3476991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (key == DELETED_KEY_VALUE) { 3486991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt table->deleted_key_data = NULL; 3496991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt } else { 35094303a0750f9eaae3fcf598b7bf1320e521898fbJason Ekstrand entry = _mesa_hash_table_search(table->ht, uint_key(key)); 3516991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_hash_table_remove(table->ht, entry); 352afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 353afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 354afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 355afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 356aded1160e5e722610dd474583d78e745291cbd75Matt Turnervoid 357aded1160e5e722610dd474583d78e745291cbd75Matt Turner_mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key) 358aded1160e5e722610dd474583d78e745291cbd75Matt Turner{ 359aded1160e5e722610dd474583d78e745291cbd75Matt Turner _mesa_HashRemove_unlocked(table, key); 360aded1160e5e722610dd474583d78e745291cbd75Matt Turner} 361aded1160e5e722610dd474583d78e745291cbd75Matt Turner 362aded1160e5e722610dd474583d78e745291cbd75Matt Turnervoid 363aded1160e5e722610dd474583d78e745291cbd75Matt Turner_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 364aded1160e5e722610dd474583d78e745291cbd75Matt Turner{ 365aded1160e5e722610dd474583d78e745291cbd75Matt Turner mtx_lock(&table->Mutex); 366aded1160e5e722610dd474583d78e745291cbd75Matt Turner _mesa_HashRemove_unlocked(table, key); 367aded1160e5e722610dd474583d78e745291cbd75Matt Turner mtx_unlock(&table->Mutex); 368aded1160e5e722610dd474583d78e745291cbd75Matt Turner} 369afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 370c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 3719f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Delete all entries in a hash table, but don't delete the table itself. 3729f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Invoke the given callback function for each table entry. 3736dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 3749f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param table the hash table to delete 3759f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param callback the callback function 3769f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param userData arbitrary pointer to pass along to the callback 377f9995b30756140724f41daf963fa06167912be7fKristian Høgsberg * (this is typically a struct gl_context pointer) 3789f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul */ 3799f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paulvoid 3809f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul_mesa_HashDeleteAll(struct _mesa_HashTable *table, 3819f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void (*callback)(GLuint key, void *data, void *userData), 3829f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void *userData) 3839f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul{ 3846991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt struct hash_entry *entry; 3856991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 386bfcdb843830bba0190e00e35e3c5c18c4bdb5de1Matt Turner assert(table); 387bfcdb843830bba0190e00e35e3c5c18c4bdb5de1Matt Turner assert(callback); 388d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_lock(&table->Mutex); 3899f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul table->InDeleteAll = GL_TRUE; 3906991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt hash_table_foreach(table->ht, entry) { 3916991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt callback((uintptr_t)entry->key, entry->data, userData); 3926991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_hash_table_remove(table->ht, entry); 3936991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt } 3946991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (table->deleted_key_data) { 3956991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); 3966991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt table->deleted_key_data = NULL; 3979f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 3989f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul table->InDeleteAll = GL_FALSE; 399d129ea7fa2e57288f64cd247a0ac6d876e1717d2Brian Paul mtx_unlock(&table->Mutex); 4009f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul} 4019f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 4029f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 4039f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul/** 4049f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * Walk over all entries in a hash table, calling callback function for each. 4059f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param table the hash table to walk 4069f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param callback the callback function 4079f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul * \param userData arbitrary pointer to pass along to the callback 408f9995b30756140724f41daf963fa06167912be7fKristian Høgsberg * (this is typically a struct gl_context pointer) 4099f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul */ 4109f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paulvoid 4119f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul_mesa_HashWalk(const struct _mesa_HashTable *table, 4129f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void (*callback)(GLuint key, void *data, void *userData), 4139f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul void *userData) 4149f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul{ 4159f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul /* cast-away const */ 4169f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; 4176991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt struct hash_entry *entry; 4186991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt 419bfcdb843830bba0190e00e35e3c5c18c4bdb5de1Matt Turner assert(table); 420bfcdb843830bba0190e00e35e3c5c18c4bdb5de1Matt Turner assert(callback); 4212e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson mtx_lock(&table2->Mutex); 4226991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt hash_table_foreach(table->ht, entry) { 4236991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt callback((uintptr_t)entry->key, entry->data, userData); 4249f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul } 4256991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (table->deleted_key_data) 4266991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); 4272e2562cabbe9a1d3fb997ccaccc20ba31b2006c3Steinar H. Gunderson mtx_unlock(&table2->Mutex); 4289f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul} 4299f6798d6e1a59b8a0ca258d49d6afae128735f41Brian Paul 4306991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtstatic void 4316991c2922f530d88622900039c24bd04d9c15ce7Eric Anholtdebug_print_entry(GLuint key, void *data, void *userData) 432c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul{ 4336991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_debug(NULL, "%u %p\n", key, data); 434c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul} 435c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul 436c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 437afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach * Dump contents of hash table for debugging. 4386dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4396dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 440afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 441c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paulvoid 442c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashPrint(const struct _mesa_HashTable *table) 443afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 4446991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (table->deleted_key_data) 4456991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt debug_print_entry(DELETED_KEY_VALUE, table->deleted_key_data, NULL); 4466991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt _mesa_HashWalk(table, debug_print_entry, NULL); 447afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 448afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 449afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 450c84e84a7342f4a10a69c0ab96f649f54586afb9dBrian Paul/** 4516dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Find a block of adjacent unused hash keys. 4526dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4536dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param table the hash table. 4546dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param numKeys number of keys needed. 4556dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4566dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return Starting key of free block or 0 if failure. 4576dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 4586dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * If there are enough free keys between the maximum key existing in the table 4596dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return 4606dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * the adjacent key. Otherwise do a full search for a free key block in the 4616dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * allowable key range. 462afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach */ 463c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian PaulGLuint 464c74ffb8266dc55914cba6a37143b38b5fd05b01cBrian Paul_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) 465afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach{ 4666991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt const GLuint maxKey = ~((GLuint) 0) - 1; 467afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach if (maxKey - numKeys > table->MaxKey) { 468afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach /* the quick solution */ 469afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach return table->MaxKey + 1; 470afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 471afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach else { 472afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach /* the slow solution */ 473afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach GLuint freeCount = 0; 47490d9e02f3ac9bda1650caaf37fe5f0e3f4ce01cfBrian Paul GLuint freeStart = 1; 475afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach GLuint key; 476f63623779a44c677d8731cbd706a02a615e03b0fBrian Paul for (key = 1; key != maxKey; key++) { 477038d2607ab759638217ded3bd1b232d389975af5Brian Paul if (_mesa_HashLookup_unlocked(table, key)) { 478afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach /* darn, this key is already in use */ 479afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach freeCount = 0; 480afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach freeStart = key+1; 481afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 482afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach else { 483afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach /* this key not in use, check if we've found enough */ 484afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach freeCount++; 485afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach if (freeCount == numKeys) { 486afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach return freeStart; 487afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 488afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 489afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 490afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach /* cannot allocate a block of numKeys consecutive keys */ 491afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach return 0; 492afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach } 493afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 494afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 495afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach 496f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul/** 497f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul * Return the number of entries in the hash table. 498f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul */ 499f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian PaulGLuint 500f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul_mesa_HashNumEntries(const struct _mesa_HashTable *table) 501f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul{ 5026991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt GLuint count = 0; 503f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 5046991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt if (table->deleted_key_data) 5056991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt count++; 506f1b33c74dc11b97a86a7f0e9cbe4cb168b2b9540Brian Paul 50755fb921d691f6d2d9e1ab105adb63a61fea7dc50Nicolai Hähnle count += _mesa_hash_table_num_entries(table->ht); 508a2c65f47930ab1c5a56a8c7c81b35dc77b08d472Brian Paul 5096991c2922f530d88622900039c24bd04d9c15ce7Eric Anholt return count; 510afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cJochen Gerlach} 511