3  * Generic hash table. 
44  * Create a new hash table.
46  * \return pointer to a new, empty hash table.
51    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
53    if (table) {
54       table->ht = _mesa_hash_table_create(NULL, uint_key_hash,
56       if (table->ht == NULL) {
57          free(table);
62       _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE));
67       mtx_init(&table->Mutex, mtx_recursive);
73    return table;
79  * Delete a hash table.
80  * Frees each entry on the hash table and then the hash table structure itself.
81  * Note that the caller should have already traversed the table and deleted
82  * the objects in the table (i.e. We don't free the entries' data pointer).
84  * \param table the hash table to delete.
87 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
89    assert(table);
91    if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) {
95    _mesa_hash_table_destroy(table->ht, NULL);
97    mtx_destroy(&table->Mutex);
98    free(table);
104  * Lookup an entry in the hash table, without locking.
108 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
112    assert(table);
116       return table->deleted_key_data;
118    entry = _mesa_hash_table_search_pre_hashed(table->ht,
129  * Lookup an entry in the hash table.
131  * \param table the hash table.
134  * \return pointer to user's data or NULL if key not in table
137 _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
140    _mesa_HashLockMutex(table);
141    res = _mesa_HashLookup_unlocked(table, key);
142    _mesa_HashUnlockMutex(table);
148  * Lookup an entry in the hash table without locking the mutex.
150  * The hash table mutex must be locked manually by calling
153  * \param table the hash table.
156  * \return pointer to user's data or NULL if key not in table
159 _mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key)
161    return _mesa_HashLookup_unlocked(table, key);
166 _mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data)
171    assert(table);
174    if (key > table->MaxKey)
175       table->MaxKey = key;
178       table->deleted_key_data = data;
180       entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key));
184          _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data);
191  * Insert a key/pointer pair into the hash table without locking the mutex.
194  * The hash table mutex must be locked manually by calling
197  * \param table the hash table.
202 _mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data)
204    _mesa_HashInsert_unlocked(table, key, data);
209  * Insert a key/pointer pair into the hash table.
212  * \param table the hash table.
217 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
219    _mesa_HashLockMutex(table);
220    _mesa_HashInsert_unlocked(table, key, data);
221    _mesa_HashUnlockMutex(table);
226  * Remove an entry from the hash table.
228  * \param table the hash table.
231  * While holding the hash table's lock, searches the entry with the matching
235 _mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key)
239    assert(table);
245    assert(!table->InDeleteAll);
248       table->deleted_key_data = NULL;
250       entry = _mesa_hash_table_search_pre_hashed(table->ht,
253       _mesa_hash_table_remove(table->ht, entry);
259 _mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key)
261    _mesa_HashRemove_unlocked(table, key);
265 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
267    _mesa_HashLockMutex(table);
268    _mesa_HashRemove_unlocked(table, key);
269    _mesa_HashUnlockMutex(table);
273  * Delete all entries in a hash table, but don't delete the table itself.
274  * Invoke the given callback function for each table entry.
276  * \param table  the hash table to delete
282 _mesa_HashDeleteAll(struct _mesa_HashTable *table,
287    _mesa_HashLockMutex(table);
288    table->InDeleteAll = GL_TRUE;
289    hash_table_foreach(table->ht, entry) {
291       _mesa_hash_table_remove(table->ht, entry);
293    if (table->deleted_key_data) {
294       callback(DELETED_KEY_VALUE, table->deleted_key_data, userData);
295       table->deleted_key_data = NULL;
297    table->InDeleteAll = GL_FALSE;
298    _mesa_HashUnlockMutex(table);
303  * Walk over all entries in a hash table, calling callback function for each.
304  * \param table  the hash table to walk
310 hash_walk_unlocked(const struct _mesa_HashTable *table,
314    assert(table);
317    hash_table_foreach(table->ht, entry) {
320    if (table->deleted_key_data)
321       callback(DELETED_KEY_VALUE, table->deleted_key_data, userData);
326 _mesa_HashWalk(const struct _mesa_HashTable *table,
331    struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
334    hash_walk_unlocked(table, callback, userData);
339 _mesa_HashWalkLocked(const struct _mesa_HashTable *table,
343    hash_walk_unlocked(table, callback, userData);
353  * Dump contents of hash table for debugging.
355  * \param table the hash table.
358 _mesa_HashPrint(const struct _mesa_HashTable *table)
360    if (table->deleted_key_data)
361       debug_print_entry(DELETED_KEY_VALUE, table->deleted_key_data, NULL);
362    _mesa_HashWalk(table, debug_print_entry, NULL);
369  * \param table the hash table.
374  * If there are enough free keys between the maximum key existing in the table
380 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
383    if (maxKey - numKeys > table->MaxKey) {
385       return table->MaxKey + 1;
393 	 if (_mesa_HashLookup_unlocked(table, key)) {
413  * Return the number of entries in the hash table.
416 _mesa_HashNumEntries(const struct _mesa_HashTable *table)
420    if (table->deleted_key_data)
423    count += _mesa_hash_table_num_entries(table->ht);

Indexes created Sat Nov 29 20:09:40 GMT 2025