Lines Matching refs:Table
3 * Generic hash table.
44 #define TABLE_SIZE 1023 /**< Size of lookup table/array */
50 * An entry in the hash table.
60 * The hash table data structure.
63 struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */
73 * Create a new hash table.
75 * \return pointer to a new, empty hash table.
80 struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
81 if (table) {
82 _glthread_INIT_MUTEX(table->Mutex);
83 _glthread_INIT_MUTEX(table->WalkMutex);
85 return table;
91 * Delete a hash table.
92 * Frees each entry on the hash table and then the hash table structure itself.
93 * Note that the caller should have already traversed the table and deleted
94 * the objects in the table (i.e. We don't free the entries' data pointer).
96 * \param table the hash table to delete.
99 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
102 assert(table);
104 struct HashEntry *entry = table->Table[pos];
115 _glthread_DESTROY_MUTEX(table->Mutex);
116 _glthread_DESTROY_MUTEX(table->WalkMutex);
117 free(table);
123 * Lookup an entry in the hash table, without locking.
127 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
132 assert(table);
136 entry = table->Table[pos];
148 * Lookup an entry in the hash table.
150 * \param table the hash table.
153 * \return pointer to user's data or NULL if key not in table
156 _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
159 assert(table);
160 _glthread_LOCK_MUTEX(table->Mutex);
161 res = _mesa_HashLookup_unlocked(table, key);
162 _glthread_UNLOCK_MUTEX(table->Mutex);
168 * Insert a key/pointer pair into the hash table.
171 * \param table the hash table.
176 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
182 assert(table);
185 _glthread_LOCK_MUTEX(table->Mutex);
187 if (key > table->MaxKey)
188 table->MaxKey = key;
193 for (entry = table->Table[pos]; entry; entry = entry->Next) {
202 _glthread_UNLOCK_MUTEX(table->Mutex);
207 /* alloc and insert new table entry */
212 entry->Next = table->Table[pos];
213 table->Table[pos] = entry;
216 _glthread_UNLOCK_MUTEX(table->Mutex);
222 * Remove an entry from the hash table.
224 * \param table the hash table.
227 * While holding the hash table's lock, searches the entry with the matching
231 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
236 assert(table);
240 if (table->InDeleteAll) {
246 _glthread_LOCK_MUTEX(table->Mutex);
250 entry = table->Table[pos];
258 table->Table[pos] = entry->Next;
261 _glthread_UNLOCK_MUTEX(table->Mutex);
268 _glthread_UNLOCK_MUTEX(table->Mutex);
274 * Delete all entries in a hash table, but don't delete the table itself.
275 * Invoke the given callback function for each table entry.
277 * \param table the hash table to delete
283 _mesa_HashDeleteAll(struct _mesa_HashTable *table,
288 ASSERT(table);
290 _glthread_LOCK_MUTEX(table->Mutex);
291 table->InDeleteAll = GL_TRUE;
294 for (entry = table->Table[pos]; entry; entry = next) {
299 table->Table[pos] = NULL;
301 table->InDeleteAll = GL_FALSE;
302 _glthread_UNLOCK_MUTEX(table->Mutex);
307 * Walk over all entries in a hash table, calling callback function for each.
311 * A lock-less version of this function could be used when the table will
313 * \param table the hash table to walk
319 _mesa_HashWalk(const struct _mesa_HashTable *table,
324 struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
326 ASSERT(table);
331 for (entry = table->Table[pos]; entry; entry = next) {
342 * Return the key of the "first" entry in the hash table.
343 * While holding the lock, walks through all table positions until finding
346 * \param table the hash table
347 * \return key for the "first" entry in the hash table.
350 _mesa_HashFirstEntry(struct _mesa_HashTable *table)
353 assert(table);
354 _glthread_LOCK_MUTEX(table->Mutex);
356 if (table->Table[pos]) {
357 _glthread_UNLOCK_MUTEX(table->Mutex);
358 return table->Table[pos]->Key;
361 _glthread_UNLOCK_MUTEX(table->Mutex);
367 * Given a hash table key, return the next key. This is used to walk
368 * over all entries in the table. Note that the keys returned during
370 * \return next hash key or 0 if end of table.
373 _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
378 assert(table);
383 for (entry = table->Table[pos]; entry ; entry = entry->Next) {
399 /* look for next non-empty table slot */
402 if (table->Table[pos]) {
403 return table->Table[pos]->Key;
413 * Dump contents of hash table for debugging.
415 * \param table the hash table.
418 _mesa_HashPrint(const struct _mesa_HashTable *table)
421 assert(table);
423 const struct HashEntry *entry = table->Table[pos];
436 * \param table the hash table.
441 * If there are enough free keys between the maximum key existing in the table
447 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
450 _glthread_LOCK_MUTEX(table->Mutex);
451 if (maxKey - numKeys > table->MaxKey) {
453 _glthread_UNLOCK_MUTEX(table->Mutex);
454 return table->MaxKey + 1;
462 if (_mesa_HashLookup_unlocked(table, key)) {
471 _glthread_UNLOCK_MUTEX(table->Mutex);
477 _glthread_UNLOCK_MUTEX(table->Mutex);
484 * Return the number of entries in the hash table.
487 _mesa_HashNumEntries(const struct _mesa_HashTable *table)
493 for (entry = table->Table[pos]; entry; entry = entry->Next) {
506 * Test walking over all the entries in a hash table.
