28  * Generic hash table.
45  * Initialize a hash table.
48 _mesa_InitHashTable(struct _mesa_HashTable *table)  in _mesa_InitHashTable()  argument
50    memset(table, 0, sizeof(*table));  in _mesa_InitHashTable()
51    util_sparse_array_init(&table->array, sizeof(void*), 1024);  in _mesa_InitHashTable()
52    util_idalloc_init(&table->id_alloc, 8);  in _mesa_InitHashTable()
54    util_idalloc_reserve(&table->id_alloc, 0);  in _mesa_InitHashTable()
55    simple_mtx_init(&table->Mutex, mtx_plain);  in _mesa_InitHashTable()
59  * Delete a hash table.
60  * Frees each entry on the hash table and then the hash table structure itself.
61  * Note that the caller should have already traversed the table and deleted
62  * the objects in the table (i.e. We don't free the entries' data pointer).
64  * Invoke the given callback function for each table entry if not NULL.
66  * \param table the hash table to delete.
67  * \param table  the hash table to delete
73 _mesa_DeinitHashTable(struct _mesa_HashTable *table,  in _mesa_DeinitHashTable()  argument
78       util_idalloc_foreach_no_zero_safe(&table->id_alloc, id) {  in _mesa_DeinitHashTable()
79          free_callback(*(void**)util_sparse_array_get(&table->array, id),  in _mesa_DeinitHashTable()
84    util_idalloc_fini(&table->id_alloc);  in _mesa_DeinitHashTable()
85    util_sparse_array_finish(&table->array);  in _mesa_DeinitHashTable()
86    simple_mtx_destroy(&table->Mutex);  in _mesa_DeinitHashTable()
90 _mesa_HashEnableNameReuse(struct _mesa_HashTable *table)  in _mesa_HashEnableNameReuse()  argument
92    _mesa_HashLockMutex(table);  in _mesa_HashEnableNameReuse()
93    table->alloc_via_idalloc = true;  in _mesa_HashEnableNameReuse()
94    _mesa_HashUnlockMutex(table);  in _mesa_HashEnableNameReuse()
98  * Insert a key/pointer pair into the hash table without locking the mutex.
101  * The hash table mutex must be locked manually by calling
104  * \param table the hash table.
109 _mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data)  in _mesa_HashInsertLocked()  argument
113    if (key > table->MaxKey)  in _mesa_HashInsertLocked()
114       table->MaxKey = key;  in _mesa_HashInsertLocked()
116    *(void**)util_sparse_array_get(&table->array, key) = data;  in _mesa_HashInsertLocked()
118    util_idalloc_reserve(&table->id_alloc, key);  in _mesa_HashInsertLocked()
122  * Insert a key/pointer pair into the hash table.
125  * \param table the hash table.
130 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)  in _mesa_HashInsert()  argument
132    _mesa_HashLockMutex(table);  in _mesa_HashInsert()
133    _mesa_HashInsertLocked(table, key, data);  in _mesa_HashInsert()
134    _mesa_HashUnlockMutex(table);  in _mesa_HashInsert()
138  * Remove an entry from the hash table.
140  * \param table the hash table.
143  * While holding the hash table's lock, searches the entry with the matching
147 _mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key)  in _mesa_HashRemoveLocked()  argument
150    *(void**)util_sparse_array_get(&table->array, key) = NULL;  in _mesa_HashRemoveLocked()
152    util_idalloc_free(&table->id_alloc, key);  in _mesa_HashRemoveLocked()
156 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)  in _mesa_HashRemove()  argument
158    _mesa_HashLockMutex(table);  in _mesa_HashRemove()
159    _mesa_HashRemoveLocked(table, key);  in _mesa_HashRemove()
160    _mesa_HashUnlockMutex(table);  in _mesa_HashRemove()
164  * Walk over all entries in a hash table, calling callback function for each.
165  * \param table  the hash table to walk
171 _mesa_HashWalkLocked(struct _mesa_HashTable *table,  in _mesa_HashWalkLocked()  argument
177    util_idalloc_foreach_no_zero_safe(&table->id_alloc, id) {  in _mesa_HashWalkLocked()
178       callback(*(void**)util_sparse_array_get(&table->array, id), userData);  in _mesa_HashWalkLocked()
183 _mesa_HashWalk(struct _mesa_HashTable *table,  in _mesa_HashWalk()  argument
187    _mesa_HashLockMutex(table);  in _mesa_HashWalk()
188    _mesa_HashWalkLocked(table, callback, userData);  in _mesa_HashWalk()
189    _mesa_HashUnlockMutex(table);  in _mesa_HashWalk()
195  * \param table the hash table.
200  * If there are enough free keys between the maximum key existing in the table
206 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)  in _mesa_HashFindFreeKeyBlock()  argument
209    if (table->alloc_via_idalloc) {  in _mesa_HashFindFreeKeyBlock()
210       return util_idalloc_alloc_range(&table->id_alloc, numKeys);  in _mesa_HashFindFreeKeyBlock()
211    } else if (maxKey - numKeys > table->MaxKey) {  in _mesa_HashFindFreeKeyBlock()
213       return table->MaxKey + 1;  in _mesa_HashFindFreeKeyBlock()
221 	 if (_mesa_HashLookupLocked(table, key)) {  in _mesa_HashFindFreeKeyBlock()
240 _mesa_HashFindFreeKeys(struct _mesa_HashTable *table, GLuint* keys, GLuint numKeys)  in _mesa_HashFindFreeKeys()  argument
242    if (!table->alloc_via_idalloc) {  in _mesa_HashFindFreeKeys()
243       GLuint first = _mesa_HashFindFreeKeyBlock(table, numKeys);  in _mesa_HashFindFreeKeys()
251       keys[i] = util_idalloc_alloc(&table->id_alloc);  in _mesa_HashFindFreeKeys()