Subversion Repositories shark

Rev

Rev 55 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
55 pj 1
/* $Id: hash.c,v 1.1 2003-02-28 11:42:02 pj Exp $ */
2
 
3
/*
4
 * Mesa 3-D graphics library
5
 * Version:  4.1
6
 *
7
 * Copyright (C) 1999-2002  Brian Paul   All Rights Reserved.
8
 *
9
 * Permission is hereby granted, free of charge, to any person obtaining a
10
 * copy of this software and associated documentation files (the "Software"),
11
 * to deal in the Software without restriction, including without limitation
12
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
13
 * and/or sell copies of the Software, and to permit persons to whom the
14
 * Software is furnished to do so, subject to the following conditions:
15
 *
16
 * The above copyright notice and this permission notice shall be included
17
 * in all copies or substantial portions of the Software.
18
 *
19
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
22
 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
23
 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25
 */
26
 
27
#include "glheader.h"
28
#include "imports.h"
29
#include "glthread.h"
30
#include "hash.h"
31
#include "context.h"
32
 
33
 
34
/**
35
 * \file hash.c
36
 * \brief Generic hash table.  Used for display lists and texture objects.
37
 * The hash functions are thread-safe.
38
 * \author Brian Paul
39
 * \note key=0 is illegal
40
 */
41
 
42
 
43
#define TABLE_SIZE 1023  /**< Size of lookup table/array */
44
 
45
/**
46
 * An entry in the hash table.  This struct is private to this file.
47
 */
48
struct HashEntry {
49
   GLuint Key;             /**< the entry's key */
50
   void *Data;             /**< the entry's data */
51
   struct HashEntry *Next; /**< pointer to next entry */
52
};
53
 
54
/**
55
 * The hashtable data structure.  This is an opaque types (it's not
56
 * defined in the .h file).
57
 */
58
struct _mesa_HashTable {
59
   struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
60
   GLuint MaxKey;                        /**< highest key inserted so far */
61
   _glthread_Mutex Mutex;                /**< mutual exclusion lock */
62
};
63
 
64
 
65
 
66
/**
67
 * Create a new hash table.
68
 * \return pointer to a new, empty hash table.
69
 */
70
struct _mesa_HashTable *_mesa_NewHashTable(void)
71
{
72
   struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
73
   if (table) {
74
      _glthread_INIT_MUTEX(table->Mutex);
75
   }
76
   return table;
77
}
78
 
79
 
80
 
81
/**
82
 * Delete a hash table.
83
 * \param table - the hash table to delete
84
 */
85
void _mesa_DeleteHashTable(struct _mesa_HashTable *table)
86
{
87
   GLuint i;
88
   assert(table);
89
   for (i=0;i<TABLE_SIZE;i++) {
90
      struct HashEntry *entry = table->Table[i];
91
      while (entry) {
92
         struct HashEntry *next = entry->Next;
93
         FREE(entry);
94
         entry = next;
95
      }
96
   }
97
   FREE(table);
98
}
99
 
100
 
101
 
102
/**
103
 * Lookup an entry in the hash table.
104
 * \param table - the hash table
105
 * \param key - the key
106
 * \return pointer to user's data or NULL if key not in table
107
 */
108
void *_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
109
{
110
   GLuint pos;
111
   const struct HashEntry *entry;
112
 
113
   assert(table);
114
   assert(key);
115
 
116
   pos = key & (TABLE_SIZE-1);
117
   entry = table->Table[pos];
118
   while (entry) {
119
      if (entry->Key == key) {
120
         return entry->Data;
121
      }
122
      entry = entry->Next;
123
   }
124
   return NULL;
125
}
126
 
127
 
128
 
129
/**
130
 * Insert into the hash table.  If an entry with this key already exists
131
 * we'll replace the existing entry.
132
 * \param table - the hash table
133
 * \param key - the key (not zero)
134
 * \param data - pointer to user data
135
 */
136
void _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
137
{
138
   /* search for existing entry with this key */
139
   GLuint pos;
140
   struct HashEntry *entry;
141
 
142
   assert(table);
143
   assert(key);
144
 
145
   _glthread_LOCK_MUTEX(table->Mutex);
146
 
147
   if (key > table->MaxKey)
148
      table->MaxKey = key;
149
 
150
   pos = key & (TABLE_SIZE-1);
151
   entry = table->Table[pos];
152
   while (entry) {
153
      if (entry->Key == key) {
154
         /* replace entry's data */
155
         entry->Data = data;
156
         _glthread_UNLOCK_MUTEX(table->Mutex);
157
         return;
158
      }
159
      entry = entry->Next;
160
   }
161
 
162
   /* alloc and insert new table entry */
163
   entry = MALLOC_STRUCT(HashEntry);
164
   entry->Key = key;
165
   entry->Data = data;
166
   entry->Next = table->Table[pos];
167
   table->Table[pos] = entry;
168
 
169
   _glthread_UNLOCK_MUTEX(table->Mutex);
170
}
171
 
172
 
173
 
174
/**
175
 * Remove an entry from the hash table.
176
 * \param table - the hash table
177
 * \param key - key of entry to remove
178
 */
179
void _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
180
{
181
   GLuint pos;
182
   struct HashEntry *entry, *prev;
183
 
184
   assert(table);
185
   assert(key);
186
 
187
   _glthread_LOCK_MUTEX(table->Mutex);
188
 
189
   pos = key & (TABLE_SIZE-1);
190
   prev = NULL;
191
   entry = table->Table[pos];
192
   while (entry) {
193
      if (entry->Key == key) {
194
         /* found it! */
195
         if (prev) {
196
            prev->Next = entry->Next;
197
         }
198
         else {
199
            table->Table[pos] = entry->Next;
200
         }
201
         FREE(entry);
202
         _glthread_UNLOCK_MUTEX(table->Mutex);
203
         return;
204
      }
205
      prev = entry;
206
      entry = entry->Next;
207
   }
208
 
209
   _glthread_UNLOCK_MUTEX(table->Mutex);
210
}
211
 
212
 
213
 
214
/**
215
 * Get the key of the "first" entry in the hash table.
216
 * This is used in the course of deleting all display lists when
217
 * a context is destroyed.
218
 * \param table - the hash table
219
 * \return key for the "first" entry in the hash table.
220
 */
221
GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table)
222
{
223
   GLuint pos;
224
   assert(table);
225
   _glthread_LOCK_MUTEX(table->Mutex);
226
   for (pos=0; pos < TABLE_SIZE; pos++) {
227
      if (table->Table[pos]) {
228
         _glthread_UNLOCK_MUTEX(table->Mutex);
229
         return table->Table[pos]->Key;
230
      }
231
   }
232
   _glthread_UNLOCK_MUTEX(table->Mutex);
233
   return 0;
234
}
235
 
236
 
237
 
238
/**
239
 * Dump contents of hash table for debugging.
240
 * \param table - the hash table
241
 */
242
void _mesa_HashPrint(const struct _mesa_HashTable *table)
243
{
244
   GLuint i;
245
   assert(table);
246
   for (i=0;i<TABLE_SIZE;i++) {
247
      const struct HashEntry *entry = table->Table[i];
248
      while (entry) {
249
         _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
250
         entry = entry->Next;
251
      }
252
   }
253
}
254
 
255
 
256
 
257
/**
258
 * Find a block of 'numKeys' adjacent unused hash keys.
259
 * \param table - the hash table
260
 * \param numKeys - number of keys needed
261
 * \return Starting key of free block or 0 if failure
262
 */
263
GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
264
{
265
   GLuint maxKey = ~((GLuint) 0);
266
   _glthread_LOCK_MUTEX(table->Mutex);
267
   if (maxKey - numKeys > table->MaxKey) {
268
      /* the quick solution */
269
      _glthread_UNLOCK_MUTEX(table->Mutex);
270
      return table->MaxKey + 1;
271
   }
272
   else {
273
      /* the slow solution */
274
      GLuint freeCount = 0;
275
      GLuint freeStart = 1;
276
      GLuint key;
277
      for (key=1; key!=maxKey; key++) {
278
         if (_mesa_HashLookup(table, key)) {
279
            /* darn, this key is already in use */
280
            freeCount = 0;
281
            freeStart = key+1;
282
         }
283
         else {
284
            /* this key not in use, check if we've found enough */
285
            freeCount++;
286
            if (freeCount == numKeys) {
287
               _glthread_UNLOCK_MUTEX(table->Mutex);
288
               return freeStart;
289
            }
290
         }
291
      }
292
      /* cannot allocate a block of numKeys consecutive keys */
293
      _glthread_UNLOCK_MUTEX(table->Mutex);
294
      return 0;
295
   }
296
}
297
 
298
 
299
 
300
#ifdef HASH_TEST_HARNESS
301
int main(int argc, char *argv[])
302
{
303
   int a, b, c;
304
   struct HashTable *t;
305
 
306
   _mesa_printf("&a = %p\n", &a);
307
   _mesa_printf("&b = %p\n", &b);
308
 
309
   t = _mesa_NewHashTable();
310
   _mesa_HashInsert(t, 501, &a);
311
   _mesa_HashInsert(t, 10, &c);
312
   _mesa_HashInsert(t, 0xfffffff8, &b);
313
   _mesa_HashPrint(t);
314
 
315
   _mesa_printf("Find 501: %p\n", _mesa_HashLookup(t,501));
316
   _mesa_printf("Find 1313: %p\n", _mesa_HashLookup(t,1313));
317
   _mesa_printf("Find block of 100: %d\n", _mesa_HashFindFreeKeyBlock(t, 100));
318
 
319
   _mesa_DeleteHashTable(t);
320
 
321
   return 0;
322
}
323
#endif