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
);