Lines Matching full:table
3 * Generic hash table.
46 * Create a new hash table.
48 * \return pointer to a new, empty hash table.
53 struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); in _mesa_NewHashTable() local
55 if (table) { in _mesa_NewHashTable()
56 table->ht = _mesa_hash_table_create(NULL, uint_key_hash, in _mesa_NewHashTable()
58 if (table->ht == NULL) { in _mesa_NewHashTable()
59 free(table); in _mesa_NewHashTable()
64 _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE)); in _mesa_NewHashTable()
69 mtx_init(&table->Mutex, mtx_recursive); in _mesa_NewHashTable()
75 return table; in _mesa_NewHashTable()
81 * Delete a hash table.
82 * Frees each entry on the hash table and then the hash table structure itself.
83 * Note that the caller should have already traversed the table and deleted
84 * the objects in the table (i.e. We don't free the entries' data pointer).
86 * \param table the hash table to delete.
89 _mesa_DeleteHashTable(struct _mesa_HashTable *table) in _mesa_DeleteHashTable() argument
91 assert(table); in _mesa_DeleteHashTable()
93 if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) { in _mesa_DeleteHashTable()
97 _mesa_hash_table_destroy(table->ht, NULL); in _mesa_DeleteHashTable()
98 if (table->id_alloc) { in _mesa_DeleteHashTable()
99 util_idalloc_fini(table->id_alloc); in _mesa_DeleteHashTable()
100 free(table->id_alloc); in _mesa_DeleteHashTable()
103 mtx_destroy(&table->Mutex); in _mesa_DeleteHashTable()
104 free(table); in _mesa_DeleteHashTable()
108 _mesa_HashEnableNameReuse(struct _mesa_HashTable *table) in _mesa_HashEnableNameReuse() argument
110 _mesa_HashLockMutex(table); in _mesa_HashEnableNameReuse()
111 assert(_mesa_hash_table_num_entries(table->ht) == 0); in _mesa_HashEnableNameReuse()
112 table->id_alloc = MALLOC_STRUCT(util_idalloc); in _mesa_HashEnableNameReuse()
113 util_idalloc_init(table->id_alloc); in _mesa_HashEnableNameReuse()
114 util_idalloc_resize(table->id_alloc, 8); in _mesa_HashEnableNameReuse()
115 ASSERTED GLuint reserve0 = util_idalloc_alloc(table->id_alloc); in _mesa_HashEnableNameReuse()
117 _mesa_HashUnlockMutex(table); in _mesa_HashEnableNameReuse()
122 * Lookup an entry in the hash table, without locking.
126 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookup_unlocked() argument
130 assert(table); in _mesa_HashLookup_unlocked()
134 return table->deleted_key_data; in _mesa_HashLookup_unlocked()
136 entry = _mesa_hash_table_search_pre_hashed(table->ht, in _mesa_HashLookup_unlocked()
147 * Lookup an entry in the hash table.
149 * \param table the hash table.
152 * \return pointer to user's data or NULL if key not in table
155 _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookup() argument
158 _mesa_HashLockMutex(table); in _mesa_HashLookup()
159 res = _mesa_HashLookup_unlocked(table, key); in _mesa_HashLookup()
160 _mesa_HashUnlockMutex(table); in _mesa_HashLookup()
166 * Lookup an entry in the hash table without locking the mutex.
168 * The hash table mutex must be locked manually by calling
171 * \param table the hash table.
174 * \return pointer to user's data or NULL if key not in table
177 _mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookupLocked() argument
179 return _mesa_HashLookup_unlocked(table, key); in _mesa_HashLookupLocked()
184 _mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data) in _mesa_HashInsert_unlocked() argument
189 assert(table); in _mesa_HashInsert_unlocked()
192 if (key > table->MaxKey) in _mesa_HashInsert_unlocked()
193 table->MaxKey = key; in _mesa_HashInsert_unlocked()
196 table->deleted_key_data = data; in _mesa_HashInsert_unlocked()
198 entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key)); in _mesa_HashInsert_unlocked()
202 _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data); in _mesa_HashInsert_unlocked()
209 * Insert a key/pointer pair into the hash table without locking the mutex.
212 * The hash table mutex must be locked manually by calling
215 * \param table the hash table.
221 _mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data, in _mesa_HashInsertLocked() argument
224 _mesa_HashInsert_unlocked(table, key, data); in _mesa_HashInsertLocked()
225 if (!isGenName && table->id_alloc) in _mesa_HashInsertLocked()
226 util_idalloc_reserve(table->id_alloc, key); in _mesa_HashInsertLocked()
231 * Insert a key/pointer pair into the hash table.
234 * \param table the hash table.
240 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data, in _mesa_HashInsert() argument
243 _mesa_HashLockMutex(table); in _mesa_HashInsert()
244 _mesa_HashInsert_unlocked(table, key, data); in _mesa_HashInsert()
245 if (!isGenName && table->id_alloc) in _mesa_HashInsert()
246 util_idalloc_reserve(table->id_alloc, key); in _mesa_HashInsert()
247 _mesa_HashUnlockMutex(table); in _mesa_HashInsert()
252 * Remove an entry from the hash table.
254 * \param table the hash table.
257 * While holding the hash table's lock, searches the entry with the matching
261 _mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemove_unlocked() argument
265 assert(table); in _mesa_HashRemove_unlocked()
271 assert(!table->InDeleteAll); in _mesa_HashRemove_unlocked()
274 table->deleted_key_data = NULL; in _mesa_HashRemove_unlocked()
276 entry = _mesa_hash_table_search_pre_hashed(table->ht, in _mesa_HashRemove_unlocked()
279 _mesa_hash_table_remove(table->ht, entry); in _mesa_HashRemove_unlocked()
282 if (table->id_alloc) in _mesa_HashRemove_unlocked()
283 util_idalloc_free(table->id_alloc, key); in _mesa_HashRemove_unlocked()
288 _mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemoveLocked() argument
290 _mesa_HashRemove_unlocked(table, key); in _mesa_HashRemoveLocked()
294 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemove() argument
296 _mesa_HashLockMutex(table); in _mesa_HashRemove()
297 _mesa_HashRemove_unlocked(table, key); in _mesa_HashRemove()
298 _mesa_HashUnlockMutex(table); in _mesa_HashRemove()
302 * Delete all entries in a hash table, but don't delete the table itself.
303 * Invoke the given callback function for each table entry.
305 * \param table the hash table to delete
311 _mesa_HashDeleteAll(struct _mesa_HashTable *table, in _mesa_HashDeleteAll() argument
316 _mesa_HashLockMutex(table); in _mesa_HashDeleteAll()
317 table->InDeleteAll = GL_TRUE; in _mesa_HashDeleteAll()
318 hash_table_foreach(table->ht, entry) { in _mesa_HashDeleteAll()
320 _mesa_hash_table_remove(table->ht, entry); in _mesa_HashDeleteAll()
322 if (table->deleted_key_data) { in _mesa_HashDeleteAll()
323 callback(table->deleted_key_data, userData); in _mesa_HashDeleteAll()
324 table->deleted_key_data = NULL; in _mesa_HashDeleteAll()
326 table->InDeleteAll = GL_FALSE; in _mesa_HashDeleteAll()
327 if (table->id_alloc) { in _mesa_HashDeleteAll()
328 util_idalloc_fini(table->id_alloc); in _mesa_HashDeleteAll()
329 free(table->id_alloc); in _mesa_HashDeleteAll()
330 _mesa_HashEnableNameReuse(table); in _mesa_HashDeleteAll()
332 table->MaxKey = 0; in _mesa_HashDeleteAll()
333 _mesa_HashUnlockMutex(table); in _mesa_HashDeleteAll()
338 * Walk over all entries in a hash table, calling callback function for each.
339 * \param table the hash table to walk
345 hash_walk_unlocked(const struct _mesa_HashTable *table, in hash_walk_unlocked() argument
349 assert(table); in hash_walk_unlocked()
352 hash_table_foreach(table->ht, entry) { in hash_walk_unlocked()
355 if (table->deleted_key_data) in hash_walk_unlocked()
356 callback(table->deleted_key_data, userData); in hash_walk_unlocked()
361 _mesa_HashWalk(const struct _mesa_HashTable *table, in _mesa_HashWalk() argument
366 struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; in _mesa_HashWalk()
369 hash_walk_unlocked(table, callback, userData); in _mesa_HashWalk()
374 _mesa_HashWalkLocked(const struct _mesa_HashTable *table, in _mesa_HashWalkLocked() argument
378 hash_walk_unlocked(table, callback, userData); in _mesa_HashWalkLocked()
382 * Dump contents of hash table for debugging.
384 * \param table the hash table.
387 _mesa_HashPrint(const struct _mesa_HashTable *table) in _mesa_HashPrint() argument
389 if (table->deleted_key_data) in _mesa_HashPrint()
390 _mesa_debug(NULL, "%u %p\n", DELETED_KEY_VALUE, table->deleted_key_data); in _mesa_HashPrint()
392 hash_table_foreach(table->ht, entry) { in _mesa_HashPrint()
402 * \param table the hash table.
407 * If there are enough free keys between the maximum key existing in the table
413 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) in _mesa_HashFindFreeKeyBlock() argument
416 if (table->id_alloc && numKeys == 1) { in _mesa_HashFindFreeKeyBlock()
417 return util_idalloc_alloc(table->id_alloc); in _mesa_HashFindFreeKeyBlock()
418 } else if (maxKey - numKeys > table->MaxKey) { in _mesa_HashFindFreeKeyBlock()
420 return table->MaxKey + 1; in _mesa_HashFindFreeKeyBlock()
428 if (_mesa_HashLookup_unlocked(table, key)) { in _mesa_HashFindFreeKeyBlock()
448 _mesa_HashFindFreeKeys(struct _mesa_HashTable *table, GLuint* keys, GLuint numKeys) in _mesa_HashFindFreeKeys() argument
450 if (!table->id_alloc) { in _mesa_HashFindFreeKeys()
451 GLuint first = _mesa_HashFindFreeKeyBlock(table, numKeys); in _mesa_HashFindFreeKeys()
459 keys[i] = util_idalloc_alloc(table->id_alloc); in _mesa_HashFindFreeKeys()
467 * Return the number of entries in the hash table.
470 _mesa_HashNumEntries(const struct _mesa_HashTable *table) in _mesa_HashNumEntries() argument
474 if (table->deleted_key_data) in _mesa_HashNumEntries()
477 count += _mesa_hash_table_num_entries(table->ht); in _mesa_HashNumEntries()