Lines Matching full:table
3 * Generic hash table.
45 * The hash table needs a particular pointer to be the marker for a key that
46 * was deleted from the table, along with NULL for the "never allocated in the
47 * table" marker. Legacy GL allows any GLuint to be used as a GL object name,
50 * struct hash_table. We tell the hash table to use "1" as the deleted key
51 * value, so that we test the deleted-key-in-the-table path as best we can.
56 * The hash table data structure.
63 /** Value that would be in the table for DELETED_KEY_VALUE. */
76 * are never deleted, we will never see a collision in the table, because the
77 * table resizes itself when it approaches full, and thus key % table_size ==
112 * Create a new hash table.
114 * \return pointer to a new, empty hash table.
119 struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); in _mesa_NewHashTable() local
121 if (table) { in _mesa_NewHashTable()
122 table->ht = _mesa_hash_table_create(NULL, uint_key_hash, in _mesa_NewHashTable()
124 if (table->ht == NULL) { in _mesa_NewHashTable()
125 free(table); in _mesa_NewHashTable()
130 _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE)); in _mesa_NewHashTable()
135 mtx_init(&table->Mutex, mtx_recursive); in _mesa_NewHashTable()
141 return table; in _mesa_NewHashTable()
147 * Delete a hash table.
148 * Frees each entry on the hash table and then the hash table structure itself.
149 * Note that the caller should have already traversed the table and deleted
150 * the objects in the table (i.e. We don't free the entries' data pointer).
152 * \param table the hash table to delete.
155 _mesa_DeleteHashTable(struct _mesa_HashTable *table) in _mesa_DeleteHashTable() argument
157 assert(table); in _mesa_DeleteHashTable()
159 if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) { in _mesa_DeleteHashTable()
163 _mesa_hash_table_destroy(table->ht, NULL); in _mesa_DeleteHashTable()
165 mtx_destroy(&table->Mutex); in _mesa_DeleteHashTable()
166 free(table); in _mesa_DeleteHashTable()
172 * Lookup an entry in the hash table, without locking.
176 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookup_unlocked() argument
180 assert(table); in _mesa_HashLookup_unlocked()
184 return table->deleted_key_data; in _mesa_HashLookup_unlocked()
186 entry = _mesa_hash_table_search(table->ht, uint_key(key)); in _mesa_HashLookup_unlocked()
195 * Lookup an entry in the hash table.
197 * \param table the hash table.
200 * \return pointer to user's data or NULL if key not in table
203 _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookup() argument
206 assert(table); in _mesa_HashLookup()
207 mtx_lock(&table->Mutex); in _mesa_HashLookup()
208 res = _mesa_HashLookup_unlocked(table, key); in _mesa_HashLookup()
209 mtx_unlock(&table->Mutex); in _mesa_HashLookup()
215 * Lookup an entry in the hash table without locking the mutex.
217 * The hash table mutex must be locked manually by calling
220 * \param table the hash table.
223 * \return pointer to user's data or NULL if key not in table
226 _mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashLookupLocked() argument
228 return _mesa_HashLookup_unlocked(table, key); in _mesa_HashLookupLocked()
233 * Lock the hash table mutex.
236 * to be looked up in the hash table, to avoid having to lock
239 * \param table the hash table.
242 _mesa_HashLockMutex(struct _mesa_HashTable *table) in _mesa_HashLockMutex() argument
244 assert(table); in _mesa_HashLockMutex()
245 mtx_lock(&table->Mutex); in _mesa_HashLockMutex()
250 * Unlock the hash table mutex.
252 * \param table the hash table.
255 _mesa_HashUnlockMutex(struct _mesa_HashTable *table) in _mesa_HashUnlockMutex() argument
257 assert(table); in _mesa_HashUnlockMutex()
258 mtx_unlock(&table->Mutex); in _mesa_HashUnlockMutex()
263 _mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data) in _mesa_HashInsert_unlocked() argument
268 assert(table); in _mesa_HashInsert_unlocked()
271 if (key > table->MaxKey) in _mesa_HashInsert_unlocked()
272 table->MaxKey = key; in _mesa_HashInsert_unlocked()
275 table->deleted_key_data = data; in _mesa_HashInsert_unlocked()
277 entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key)); in _mesa_HashInsert_unlocked()
281 _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data); in _mesa_HashInsert_unlocked()
288 * Insert a key/pointer pair into the hash table without locking the mutex.
291 * The hash table mutex must be locked manually by calling
294 * \param table the hash table.
299 _mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data) in _mesa_HashInsertLocked() argument
301 _mesa_HashInsert_unlocked(table, key, data); in _mesa_HashInsertLocked()
306 * Insert a key/pointer pair into the hash table.
309 * \param table the hash table.
314 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) in _mesa_HashInsert() argument
316 assert(table); in _mesa_HashInsert()
317 mtx_lock(&table->Mutex); in _mesa_HashInsert()
318 _mesa_HashInsert_unlocked(table, key, data); in _mesa_HashInsert()
319 mtx_unlock(&table->Mutex); in _mesa_HashInsert()
324 * Remove an entry from the hash table.
326 * \param table the hash table.
329 * While holding the hash table's lock, searches the entry with the matching
333 _mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemove_unlocked() argument
337 assert(table); in _mesa_HashRemove_unlocked()
341 if (table->InDeleteAll) { in _mesa_HashRemove_unlocked()
348 table->deleted_key_data = NULL; in _mesa_HashRemove_unlocked()
350 entry = _mesa_hash_table_search(table->ht, uint_key(key)); in _mesa_HashRemove_unlocked()
351 _mesa_hash_table_remove(table->ht, entry); in _mesa_HashRemove_unlocked()
357 _mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemoveLocked() argument
359 _mesa_HashRemove_unlocked(table, key); in _mesa_HashRemoveLocked()
363 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) in _mesa_HashRemove() argument
365 mtx_lock(&table->Mutex); in _mesa_HashRemove()
366 _mesa_HashRemove_unlocked(table, key); in _mesa_HashRemove()
367 mtx_unlock(&table->Mutex); in _mesa_HashRemove()
371 * Delete all entries in a hash table, but don't delete the table itself.
372 * Invoke the given callback function for each table entry.
374 * \param table the hash table to delete
380 _mesa_HashDeleteAll(struct _mesa_HashTable *table, in _mesa_HashDeleteAll() argument
386 assert(table); in _mesa_HashDeleteAll()
388 mtx_lock(&table->Mutex); in _mesa_HashDeleteAll()
389 table->InDeleteAll = GL_TRUE; in _mesa_HashDeleteAll()
390 hash_table_foreach(table->ht, entry) { in _mesa_HashDeleteAll()
392 _mesa_hash_table_remove(table->ht, entry); in _mesa_HashDeleteAll()
394 if (table->deleted_key_data) { in _mesa_HashDeleteAll()
395 callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); in _mesa_HashDeleteAll()
396 table->deleted_key_data = NULL; in _mesa_HashDeleteAll()
398 table->InDeleteAll = GL_FALSE; in _mesa_HashDeleteAll()
399 mtx_unlock(&table->Mutex); in _mesa_HashDeleteAll()
404 * Walk over all entries in a hash table, calling callback function for each.
405 * \param table the hash table to walk
411 _mesa_HashWalk(const struct _mesa_HashTable *table, in _mesa_HashWalk() argument
416 struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; in _mesa_HashWalk()
419 assert(table); in _mesa_HashWalk()
422 hash_table_foreach(table->ht, entry) { in _mesa_HashWalk()
425 if (table->deleted_key_data) in _mesa_HashWalk()
426 callback(DELETED_KEY_VALUE, table->deleted_key_data, userData); in _mesa_HashWalk()
437 * Dump contents of hash table for debugging.
439 * \param table the hash table.
442 _mesa_HashPrint(const struct _mesa_HashTable *table) in _mesa_HashPrint() argument
444 if (table->deleted_key_data) in _mesa_HashPrint()
445 debug_print_entry(DELETED_KEY_VALUE, table->deleted_key_data, NULL); in _mesa_HashPrint()
446 _mesa_HashWalk(table, debug_print_entry, NULL); in _mesa_HashPrint()
453 * \param table the hash table.
458 * If there are enough free keys between the maximum key existing in the table
464 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) in _mesa_HashFindFreeKeyBlock() argument
467 if (maxKey - numKeys > table->MaxKey) { in _mesa_HashFindFreeKeyBlock()
469 return table->MaxKey + 1; in _mesa_HashFindFreeKeyBlock()
477 if (_mesa_HashLookup_unlocked(table, key)) { in _mesa_HashFindFreeKeyBlock()
497 * Return the number of entries in the hash table.
500 _mesa_HashNumEntries(const struct _mesa_HashTable *table) in _mesa_HashNumEntries() argument
504 if (table->deleted_key_data) in _mesa_HashNumEntries()
507 count += _mesa_hash_table_num_entries(table->ht); in _mesa_HashNumEntries()