xref: /third_party/mesa3d/src/mesa/main/hash.c (revision bf215546)
1/**
2 * \file hash.c
3 * Generic hash table.
4 *
5 * Used for display lists, texture objects, vertex/fragment programs,
6 * buffer objects, etc.  The hash functions are thread-safe.
7 *
8 * \note key=0 is illegal.
9 *
10 * \author Brian Paul
11 */
12
13/*
14 * Mesa 3-D graphics library
15 *
16 * Copyright (C) 1999-2006  Brian Paul   All Rights Reserved.
17 *
18 * Permission is hereby granted, free of charge, to any person obtaining a
19 * copy of this software and associated documentation files (the "Software"),
20 * to deal in the Software without restriction, including without limitation
21 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
22 * and/or sell copies of the Software, and to permit persons to whom the
23 * Software is furnished to do so, subject to the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be included
26 * in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
29 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
31 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
32 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
33 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
34 * OTHER DEALINGS IN THE SOFTWARE.
35 */
36
37#include "errors.h"
38#include "glheader.h"
39#include "hash.h"
40#include "util/hash_table.h"
41#include "util/u_memory.h"
42#include "util/u_idalloc.h"
43
44
45/**
46 * Create a new hash table.
47 *
48 * \return pointer to a new, empty hash table.
49 */
50struct _mesa_HashTable *
51_mesa_NewHashTable(void)
52{
53   struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
54
55   if (table) {
56      table->ht = _mesa_hash_table_create(NULL, uint_key_hash,
57                                          uint_key_compare);
58      if (table->ht == NULL) {
59         free(table);
60         _mesa_error_no_memory(__func__);
61         return NULL;
62      }
63
64      _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE));
65      simple_mtx_init(&table->Mutex, mtx_plain);
66   }
67   else {
68      _mesa_error_no_memory(__func__);
69   }
70
71   return table;
72}
73
74
75
76/**
77 * Delete a hash table.
78 * Frees each entry on the hash table and then the hash table structure itself.
79 * Note that the caller should have already traversed the table and deleted
80 * the objects in the table (i.e. We don't free the entries' data pointer).
81 *
82 * \param table the hash table to delete.
83 */
84void
85_mesa_DeleteHashTable(struct _mesa_HashTable *table)
86{
87   assert(table);
88
89   if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) {
90      _mesa_problem(NULL, "In _mesa_DeleteHashTable, found non-freed data");
91   }
92
93   _mesa_hash_table_destroy(table->ht, NULL);
94   if (table->id_alloc) {
95      util_idalloc_fini(table->id_alloc);
96      free(table->id_alloc);
97   }
98
99   simple_mtx_destroy(&table->Mutex);
100   FREE(table);
101}
102
103static void init_name_reuse(struct _mesa_HashTable *table)
104{
105   assert(_mesa_hash_table_num_entries(table->ht) == 0);
106   table->id_alloc = MALLOC_STRUCT(util_idalloc);
107   util_idalloc_init(table->id_alloc, 8);
108   ASSERTED GLuint reserve0 = util_idalloc_alloc(table->id_alloc);
109   assert (reserve0 == 0);
110}
111
112void
113_mesa_HashEnableNameReuse(struct _mesa_HashTable *table)
114{
115   _mesa_HashLockMutex(table);
116   init_name_reuse(table);
117   _mesa_HashUnlockMutex(table);
118}
119
120/**
121 * Lookup an entry in the hash table, without locking.
122 * \sa _mesa_HashLookup
123 */
124static inline void *
125_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
126{
127   const struct hash_entry *entry;
128
129   assert(table);
130   assert(key);
131
132   if (key == DELETED_KEY_VALUE)
133      return table->deleted_key_data;
134
135   entry = _mesa_hash_table_search_pre_hashed(table->ht,
136                                              uint_hash(key),
137                                              uint_key(key));
138   if (!entry)
139      return NULL;
140
141   return entry->data;
142}
143
144
145/**
146 * Lookup an entry in the hash table.
147 *
148 * \param table the hash table.
149 * \param key the key.
150 *
151 * \return pointer to user's data or NULL if key not in table
152 */
153void *
154_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
155{
156   void *res;
157   _mesa_HashLockMutex(table);
158   res = _mesa_HashLookup_unlocked(table, key);
159   _mesa_HashUnlockMutex(table);
160   return res;
161}
162
163
164/**
165 * Lookup an entry in the hash table without locking the mutex.
166 *
167 * The hash table mutex must be locked manually by calling
168 * _mesa_HashLockMutex() before calling this function.
169 *
170 * \param table the hash table.
171 * \param key the key.
172 *
173 * \return pointer to user's data or NULL if key not in table
174 */
175void *
176_mesa_HashLookupLocked(struct _mesa_HashTable *table, GLuint key)
177{
178   return _mesa_HashLookup_unlocked(table, key);
179}
180
181
182static inline void
183_mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data)
184{
185   uint32_t hash = uint_hash(key);
186   struct hash_entry *entry;
187
188   assert(table);
189   assert(key);
190
191   if (key > table->MaxKey)
192      table->MaxKey = key;
193
194   if (key == DELETED_KEY_VALUE) {
195      table->deleted_key_data = data;
196   } else {
197      entry = _mesa_hash_table_search_pre_hashed(table->ht, hash, uint_key(key));
198      if (entry) {
199         entry->data = data;
200      } else {
201         _mesa_hash_table_insert_pre_hashed(table->ht, hash, uint_key(key), data);
202      }
203   }
204}
205
206
207/**
208 * Insert a key/pointer pair into the hash table without locking the mutex.
209 * If an entry with this key already exists we'll replace the existing entry.
210 *
211 * The hash table mutex must be locked manually by calling
212 * _mesa_HashLockMutex() before calling this function.
213 *
214 * \param table the hash table.
215 * \param key the key (not zero).
216 * \param data pointer to user data.
217 * \param isGenName true if the key has been generated by a HashFindFreeKey* function
218 */
219void
220_mesa_HashInsertLocked(struct _mesa_HashTable *table, GLuint key, void *data,
221                       GLboolean isGenName)
222{
223   _mesa_HashInsert_unlocked(table, key, data);
224   if (!isGenName && table->id_alloc)
225      util_idalloc_reserve(table->id_alloc, key);
226}
227
228
229/**
230 * Insert a key/pointer pair into the hash table.
231 * If an entry with this key already exists we'll replace the existing entry.
232 *
233 * \param table the hash table.
234 * \param key the key (not zero).
235 * \param data pointer to user data.
236 * \param isGenName true if the key has been generated by a HashFindFreeKey* function
237 */
238void
239_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data,
240                 GLboolean isGenName)
241{
242   _mesa_HashLockMutex(table);
243   _mesa_HashInsert_unlocked(table, key, data);
244   if (!isGenName && table->id_alloc)
245      util_idalloc_reserve(table->id_alloc, key);
246   _mesa_HashUnlockMutex(table);
247}
248
249
250/**
251 * Remove an entry from the hash table.
252 *
253 * \param table the hash table.
254 * \param key key of entry to remove.
255 *
256 * While holding the hash table's lock, searches the entry with the matching
257 * key and unlinks it.
258 */
259static inline void
260_mesa_HashRemove_unlocked(struct _mesa_HashTable *table, GLuint key)
261{
262   struct hash_entry *entry;
263
264   assert(table);
265   assert(key);
266
267   #ifndef NDEBUG
268   /* assert if _mesa_HashRemove illegally called from _mesa_HashDeleteAll
269    * callback function. Have to check this outside of mutex lock.
270    */
271   assert(!table->InDeleteAll);
272   #endif
273
274   if (key == DELETED_KEY_VALUE) {
275      table->deleted_key_data = NULL;
276   } else {
277      entry = _mesa_hash_table_search_pre_hashed(table->ht,
278                                                 uint_hash(key),
279                                                 uint_key(key));
280      _mesa_hash_table_remove(table->ht, entry);
281   }
282
283   if (table->id_alloc)
284      util_idalloc_free(table->id_alloc, key);
285}
286
287
288void
289_mesa_HashRemoveLocked(struct _mesa_HashTable *table, GLuint key)
290{
291   _mesa_HashRemove_unlocked(table, key);
292}
293
294void
295_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
296{
297   _mesa_HashLockMutex(table);
298   _mesa_HashRemove_unlocked(table, key);
299   _mesa_HashUnlockMutex(table);
300}
301
302/**
303 * Delete all entries in a hash table, but don't delete the table itself.
304 * Invoke the given callback function for each table entry.
305 *
306 * \param table  the hash table to delete
307 * \param callback  the callback function
308 * \param userData  arbitrary pointer to pass along to the callback
309 *                  (this is typically a struct gl_context pointer)
310 */
311void
312_mesa_HashDeleteAll(struct _mesa_HashTable *table,
313                    void (*callback)(void *data, void *userData),
314                    void *userData)
315{
316   assert(callback);
317   _mesa_HashLockMutex(table);
318   #ifndef NDEBUG
319   table->InDeleteAll = GL_TRUE;
320   #endif
321   hash_table_foreach(table->ht, entry) {
322      callback(entry->data, userData);
323      _mesa_hash_table_remove(table->ht, entry);
324   }
325   if (table->deleted_key_data) {
326      callback(table->deleted_key_data, userData);
327      table->deleted_key_data = NULL;
328   }
329   if (table->id_alloc) {
330      util_idalloc_fini(table->id_alloc);
331      free(table->id_alloc);
332      init_name_reuse(table);
333   }
334   #ifndef NDEBUG
335   table->InDeleteAll = GL_FALSE;
336   #endif
337   table->MaxKey = 0;
338   _mesa_HashUnlockMutex(table);
339}
340
341
342/**
343 * Walk over all entries in a hash table, calling callback function for each.
344 * \param table  the hash table to walk
345 * \param callback  the callback function
346 * \param userData  arbitrary pointer to pass along to the callback
347 *                  (this is typically a struct gl_context pointer)
348 */
349static void
350hash_walk_unlocked(const struct _mesa_HashTable *table,
351                   void (*callback)(void *data, void *userData),
352                   void *userData)
353{
354   assert(table);
355   assert(callback);
356
357   hash_table_foreach(table->ht, entry) {
358      callback(entry->data, userData);
359   }
360   if (table->deleted_key_data)
361      callback(table->deleted_key_data, userData);
362}
363
364
365void
366_mesa_HashWalk(const struct _mesa_HashTable *table,
367               void (*callback)(void *data, void *userData),
368               void *userData)
369{
370   /* cast-away const */
371   struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
372
373   _mesa_HashLockMutex(table2);
374   hash_walk_unlocked(table, callback, userData);
375   _mesa_HashUnlockMutex(table2);
376}
377
378void
379_mesa_HashWalkLocked(const struct _mesa_HashTable *table,
380               void (*callback)(void *data, void *userData),
381               void *userData)
382{
383   hash_walk_unlocked(table, callback, userData);
384}
385
386/**
387 * Dump contents of hash table for debugging.
388 *
389 * \param table the hash table.
390 */
391void
392_mesa_HashPrint(const struct _mesa_HashTable *table)
393{
394   if (table->deleted_key_data)
395      _mesa_debug(NULL, "%u %p\n", DELETED_KEY_VALUE, table->deleted_key_data);
396
397   hash_table_foreach(table->ht, entry) {
398      _mesa_debug(NULL, "%u %p\n", (unsigned)(uintptr_t) entry->key,
399                  entry->data);
400   }
401}
402
403
404/**
405 * Find a block of adjacent unused hash keys.
406 *
407 * \param table the hash table.
408 * \param numKeys number of keys needed.
409 *
410 * \return Starting key of free block or 0 if failure.
411 *
412 * If there are enough free keys between the maximum key existing in the table
413 * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return
414 * the adjacent key. Otherwise do a full search for a free key block in the
415 * allowable key range.
416 */
417GLuint
418_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
419{
420   const GLuint maxKey = ~((GLuint) 0) - 1;
421   if (table->id_alloc && numKeys == 1) {
422      return util_idalloc_alloc(table->id_alloc);
423   } else if (maxKey - numKeys > table->MaxKey) {
424      /* the quick solution */
425      return table->MaxKey + 1;
426   }
427   else {
428      /* the slow solution */
429      GLuint freeCount = 0;
430      GLuint freeStart = 1;
431      GLuint key;
432      for (key = 1; key != maxKey; key++) {
433	 if (_mesa_HashLookup_unlocked(table, key)) {
434	    /* darn, this key is already in use */
435	    freeCount = 0;
436	    freeStart = key+1;
437	 }
438	 else {
439	    /* this key not in use, check if we've found enough */
440	    freeCount++;
441	    if (freeCount == numKeys) {
442	       return freeStart;
443	    }
444	 }
445      }
446      /* cannot allocate a block of numKeys consecutive keys */
447      return 0;
448   }
449}
450
451
452bool
453_mesa_HashFindFreeKeys(struct _mesa_HashTable *table, GLuint* keys, GLuint numKeys)
454{
455   if (!table->id_alloc) {
456      GLuint first = _mesa_HashFindFreeKeyBlock(table, numKeys);
457      for (int i = 0; i < numKeys; i++) {
458         keys[i] = first + i;
459      }
460      return first != 0;
461   }
462
463   for (int i = 0; i < numKeys; i++) {
464      keys[i] = util_idalloc_alloc(table->id_alloc);
465   }
466
467   return true;
468}
469
470
471/**
472 * Return the number of entries in the hash table.
473 */
474GLuint
475_mesa_HashNumEntries(const struct _mesa_HashTable *table)
476{
477   GLuint count = 0;
478
479   if (table->deleted_key_data)
480      count++;
481
482   count += _mesa_hash_table_num_entries(table->ht);
483
484   return count;
485}
486