Changeset 3598 for trunk/src/opengl/mesa/hash.c
- Timestamp:
- May 23, 2000, 10:41:28 PM (25 years ago)
- File:
-
- 1 edited
-
trunk/src/opengl/mesa/hash.c (modified) (20 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/opengl/mesa/hash.c
r2962 r3598 1 /* $Id: hash.c,v 1. 2 2000-03-01 18:49:29jeroen Exp $ */1 /* $Id: hash.c,v 1.3 2000-05-23 20:40:36 jeroen Exp $ */ 2 2 3 3 /* 4 4 * Mesa 3-D graphics library 5 * Version: 3. 15 * Version: 3.3 6 6 * 7 7 * Copyright (C) 1999 Brian Paul All Rights Reserved. … … 26 26 27 27 28 29 28 #ifdef PC_HEADER 30 29 #include "all.h" 31 30 #else 32 #ifndef XFree86Server 33 #include <assert.h> 34 #include <stdlib.h> 35 #include <stdio.h> 36 #else 37 #include "GL/xf86glx.h" 31 #include "glheader.h" 32 #include "macros.h" 33 #include "hash.h" 34 #include "mem.h" 35 #include "glthread.h" 38 36 #endif 39 #include "hash.h" 40 #include "macros.h" 41 #endif 42 43 44 /* 45 * Generic hash table. Only dependency is the GLuint datatype. 37 38 39 /* 40 * Generic hash table. 46 41 * 47 42 * This is used to implement display list and texture object lookup. … … 58 53 }; 59 54 60 struct HashTable {55 struct _mesa_HashTable { 61 56 struct HashEntry *Table[TABLE_SIZE]; 62 57 GLuint MaxKey; 58 _glthread_Mutex Mutex; 63 59 }; 64 60 … … 68 64 * Return pointer to a new, empty hash table. 69 65 */ 70 struct HashTable *NewHashTable(void)71 { 72 return CALLOC_STRUCT( HashTable);66 struct _mesa_HashTable *_mesa_NewHashTable(void) 67 { 68 return CALLOC_STRUCT(_mesa_HashTable); 73 69 } 74 70 … … 78 74 * Delete a hash table. 79 75 */ 80 void DeleteHashTable(structHashTable *table)76 void _mesa_DeleteHashTable(struct _mesa_HashTable *table) 81 77 { 82 78 GLuint i; 83 assert(table);79 ASSERT(table); 84 80 for (i=0;i<TABLE_SIZE;i++) { 85 81 struct HashEntry *entry = table->Table[i]; … … 101 97 * Return: user data pointer or NULL if key not in table 102 98 */ 103 void * HashLookup(const structHashTable *table, GLuint key)99 void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key) 104 100 { 105 101 GLuint pos; 106 102 const struct HashEntry *entry; 107 103 108 /* assert(table);109 assert(key);110 */ 104 ASSERT(table); 105 ASSERT(key); 106 111 107 pos = key & (TABLE_SIZE-1); 112 108 entry = table->Table[pos]; … … 129 125 * data - pointer to user data 130 126 */ 131 void HashInsert(structHashTable *table, GLuint key, void *data)127 void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) 132 128 { 133 129 /* search for existing entry with this key */ … … 135 131 struct HashEntry *entry; 136 132 137 assert(table); 138 assert(key); 133 ASSERT(table); 134 ASSERT(key); 135 136 _glthread_LOCK_MUTEX(table->Mutex); 139 137 140 138 if (key > table->MaxKey) … … 147 145 /* replace entry's data */ 148 146 entry->Data = data; 147 _glthread_UNLOCK_MUTEX(table->Mutex); 149 148 return; 150 149 } … … 158 157 entry->Next = table->Table[pos]; 159 158 table->Table[pos] = entry; 159 160 _glthread_UNLOCK_MUTEX(table->Mutex); 160 161 } 161 162 … … 167 168 * key - key of entry to remove 168 169 */ 169 void HashRemove(structHashTable *table, GLuint key)170 void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 170 171 { 171 172 GLuint pos; 172 173 struct HashEntry *entry, *prev; 173 174 174 assert(table); 175 assert(key); 175 ASSERT(table); 176 ASSERT(key); 177 178 _glthread_LOCK_MUTEX(table->Mutex); 176 179 177 180 pos = key & (TABLE_SIZE-1); … … 188 191 } 189 192 FREE(entry); 193 _glthread_UNLOCK_MUTEX(table->Mutex); 190 194 return; 191 195 } … … 193 197 entry = entry->Next; 194 198 } 199 200 _glthread_UNLOCK_MUTEX(table->Mutex); 195 201 } 196 202 … … 199 205 /* 200 206 * Return the key of the "first" entry in the hash table. 201 * By calling this function until zero is returned we can get202 * the keys of all entries in the table.203 */ 204 GLuint HashFirstEntry(const structHashTable *table)207 * This is used in the course of deleting all display lists when 208 * a context is destroyed. 209 */ 210 GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table) 205 211 { 206 212 GLuint pos; 207 assert(table); 213 ASSERT(table); 214 _glthread_LOCK_MUTEX(table->Mutex); 208 215 for (pos=0; pos < TABLE_SIZE; pos++) { 209 if (table->Table[pos]) 216 if (table->Table[pos]) { 217 _glthread_UNLOCK_MUTEX(table->Mutex); 210 218 return table->Table[pos]->Key; 211 } 219 } 220 } 221 _glthread_UNLOCK_MUTEX(table->Mutex); 212 222 return 0; 213 223 } … … 218 228 * Dump contents of hash table for debugging. 219 229 */ 220 void HashPrint(const structHashTable *table)230 void _mesa_HashPrint(const struct _mesa_HashTable *table) 221 231 { 222 232 GLuint i; 223 assert(table);233 ASSERT(table); 224 234 for (i=0;i<TABLE_SIZE;i++) { 225 235 const struct HashEntry *entry = table->Table[i]; … … 237 247 * Input: table - the hash table 238 248 * numKeys - number of keys needed 239 * Return: startin tkey of free block or 0 if failure240 */ 241 GLuint HashFindFreeKeyBlock(const structHashTable *table, GLuint numKeys)249 * Return: starting key of free block or 0 if failure 250 */ 251 GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) 242 252 { 243 253 GLuint maxKey = ~((GLuint) 0); 254 _glthread_LOCK_MUTEX(table->Mutex); 244 255 if (maxKey - numKeys > table->MaxKey) { 245 256 /* the quick solution */ 257 _glthread_UNLOCK_MUTEX(table->Mutex); 246 258 return table->MaxKey + 1; 247 259 } … … 249 261 /* the slow solution */ 250 262 GLuint freeCount = 0; 251 GLuint freeStart = 0;263 GLuint freeStart = 1; 252 264 GLuint key; 253 for (key= 0; key!=maxKey; key++) {254 if ( HashLookup(table, key)) {265 for (key=1; key!=maxKey; key++) { 266 if (_mesa_HashLookup(table, key)) { 255 267 /* darn, this key is already in use */ 256 268 freeCount = 0; … … 261 273 freeCount++; 262 274 if (freeCount == numKeys) { 275 _glthread_UNLOCK_MUTEX(table->Mutex); 263 276 return freeStart; 264 277 } … … 266 279 } 267 280 /* cannot allocate a block of numKeys consecutive keys */ 281 _glthread_UNLOCK_MUTEX(table->Mutex); 268 282 return 0; 269 283 } … … 281 295 printf("&b = %p\n", &b); 282 296 283 t = NewHashTable();284 HashInsert(t, 501, &a);285 HashInsert(t, 10, &c);286 HashInsert(t, 0xfffffff8, &b);287 HashPrint(t);288 printf("Find 501: %p\n", HashLookup(t,501));289 printf("Find 1313: %p\n", HashLookup(t,1313));290 printf("Find block of 100: %d\n", HashFindFreeKeyBlock(t, 100));291 DeleteHashTable(t);297 t = _mesa_NewHashTable(); 298 _mesa_HashInsert(t, 501, &a); 299 _mesa_HashInsert(t, 10, &c); 300 _mesa_HashInsert(t, 0xfffffff8, &b); 301 _mesa_HashPrint(t); 302 printf("Find 501: %p\n", _mesa_HashLookup(t,501)); 303 printf("Find 1313: %p\n", _mesa_HashLookup(t,1313)); 304 printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100)); 305 _mesa_DeleteHashTable(t); 292 306 293 307 return 0;
Note:
See TracChangeset
for help on using the changeset viewer.
