5
* This code taken from Mesa and adapted.
14
#define TABLE_SIZE 1023 /**< Size of lookup table/array */
16
#define HASH_FUNC(K) ((K) % TABLE_SIZE)
20
* Unfinished mutex stuff
23
typedef int _EGLMutex;
26
_eglInitMutex(_EGLMutex m)
31
_eglDestroyMutex(_EGLMutex m)
36
_eglLockMutex(_EGLMutex m)
41
_eglUnlockMutex(_EGLMutex m)
47
typedef struct _egl_hashentry _EGLHashentry;
51
EGLuint Key; /**< the entry's key */
52
void *Data; /**< the entry's data */
53
_EGLHashentry *Next; /**< pointer to next entry */
59
_EGLHashentry *Table[TABLE_SIZE]; /**< the lookup table */
60
EGLuint MaxKey; /**< highest key inserted so far */
61
_EGLMutex Mutex; /**< mutual exclusion lock */
66
* Create a new hash table.
68
* \return pointer to a new, empty hash table.
71
_eglNewHashTable(void)
73
_EGLHashtable *table = (_EGLHashtable *) calloc(1, sizeof(_EGLHashtable));
75
_eglInitMutex(table->Mutex);
84
* Delete a hash table.
85
* Frees each entry on the hash table and then the hash table structure itself.
86
* Note that the caller should have already traversed the table and deleted
87
* the objects in the table (i.e. We don't free the entries' data pointer).
89
* \param table the hash table to delete.
92
_eglDeleteHashTable(_EGLHashtable *table)
96
for (i = 0; i < TABLE_SIZE; i++) {
97
_EGLHashentry *entry = table->Table[i];
99
_EGLHashentry *next = entry->Next;
104
_eglDestroyMutex(table->Mutex);
111
* Lookup an entry in the hash table.
113
* \param table the hash table.
114
* \param key the key.
116
* \return pointer to user's data or NULL if key not in table
119
_eglHashLookup(const _EGLHashtable *table, EGLuint key)
122
const _EGLHashentry *entry;
129
pos = HASH_FUNC(key);
130
entry = table->Table[pos];
132
if (entry->Key == key) {
143
* Insert a key/pointer pair into the hash table.
144
* If an entry with this key already exists we'll replace the existing entry.
146
* \param table the hash table.
147
* \param key the key (not zero).
148
* \param data pointer to user data.
151
_eglHashInsert(_EGLHashtable *table, EGLuint key, void *data)
153
/* search for existing entry with this key */
155
_EGLHashentry *entry;
160
_eglLockMutex(table->Mutex);
162
if (key > table->MaxKey)
165
pos = HASH_FUNC(key);
166
entry = table->Table[pos];
168
if (entry->Key == key) {
169
/* replace entry's data */
171
_eglUnlockMutex(table->Mutex);
177
/* alloc and insert new table entry */
178
entry = (_EGLHashentry *) malloc(sizeof(_EGLHashentry));
181
entry->Next = table->Table[pos];
182
table->Table[pos] = entry;
184
_eglUnlockMutex(table->Mutex);
190
* Remove an entry from the hash table.
192
* \param table the hash table.
193
* \param key key of entry to remove.
195
* While holding the hash table's lock, searches the entry with the matching
196
* key and unlinks it.
199
_eglHashRemove(_EGLHashtable *table, EGLuint key)
202
_EGLHashentry *entry, *prev;
207
_eglLockMutex(table->Mutex);
209
pos = HASH_FUNC(key);
211
entry = table->Table[pos];
213
if (entry->Key == key) {
216
prev->Next = entry->Next;
219
table->Table[pos] = entry->Next;
222
_eglUnlockMutex(table->Mutex);
229
_eglUnlockMutex(table->Mutex);
235
* Get the key of the "first" entry in the hash table.
237
* This is used in the course of deleting all display lists when
238
* a context is destroyed.
240
* \param table the hash table
242
* \return key for the "first" entry in the hash table.
244
* While holding the lock, walks through all table positions until finding
245
* the first entry of the first non-empty one.
248
_eglHashFirstEntry(_EGLHashtable *table)
252
_eglLockMutex(table->Mutex);
253
for (pos = 0; pos < TABLE_SIZE; pos++) {
254
if (table->Table[pos]) {
255
_eglUnlockMutex(table->Mutex);
256
return table->Table[pos]->Key;
259
_eglUnlockMutex(table->Mutex);
265
* Given a hash table key, return the next key. This is used to walk
266
* over all entries in the table. Note that the keys returned during
267
* walking won't be in any particular order.
268
* \return next hash key or 0 if end of table.
271
_eglHashNextEntry(const _EGLHashtable *table, EGLuint key)
273
const _EGLHashentry *entry;
279
/* Find the entry with given key */
280
pos = HASH_FUNC(key);
281
entry = table->Table[pos];
283
if (entry->Key == key) {
290
/* the key was not found, we can't find next entry */
295
/* return next in linked list */
296
return entry->Next->Key;
299
/* look for next non-empty table slot */
301
while (pos < TABLE_SIZE) {
302
if (table->Table[pos]) {
303
return table->Table[pos]->Key;
313
* Dump contents of hash table for debugging.
315
* \param table the hash table.
318
_eglHashPrint(const _EGLHashtable *table)
322
for (i = 0; i < TABLE_SIZE; i++) {
323
const _EGLHashentry *entry = table->Table[i];
325
printf("%u %p\n", entry->Key, entry->Data);
334
* Return a new, unused hash key.
337
_eglHashGenKey(_EGLHashtable *table)
341
_eglLockMutex(table->Mutex);
344
_eglUnlockMutex(table->Mutex);
added
removed
src/egl/main/eglhash.c
