1 /* $Id: hash.c,v 1.4 1998/02/07 14:25:12 brianp Exp $ */
2
3 /*
4 * Mesa 3-D graphics library
5 * Version: 2.5
6 * Copyright (C) 1995-1997 Brian Paul
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public
19 * License along with this library; if not, write to the Free
20 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22
23
24 /*
25 * $Log: hash.c,v $
26 * Revision 1.4 1998/02/07 14:25:12 brianp
27 * fixed small Sun compiler warning (John Stone)
28 *
29 * Revision 1.3 1997/09/22 02:33:07 brianp
30 * added HashRemove() and HashFirstEntry()
31 *
32 * Revision 1.2 1997/09/03 13:13:45 brianp
33 * added a few pointer casts
34 *
35 * Revision 1.1 1997/08/22 01:15:10 brianp
36 * Initial revision
37 *
38 */
39
40
41 #ifdef PC_HEADER
42 #include "all.h"
43 #else
44 #include <assert.h>
45 #include <stdlib.h>
46 #include <stdio.h>
47 #include "hash.h"
48 #endif
49
50
51 /*
52 * Generic hash table. Only dependency is the GLuint datatype.
53 *
54 * This is used to implement display list and texture object lookup.
55 * NOTE: key=0 is illegal.
56 */
57
58
59 #define TABLE_SIZE 1001
60
61 struct HashEntry {
62 GLuint Key;
63 void *Data;
64 struct HashEntry *Next;
65 };
66
67 struct HashTable {
68 struct HashEntry *Table[TABLE_SIZE];
69 GLuint MaxKey;
70 };
71
72
73
74 /*
75 * Return pointer to a new, empty hash table.
76 */
NewHashTable(void)77 struct HashTable *NewHashTable(void)
78 {
79 return (struct HashTable *) calloc(sizeof (struct HashTable), 1);
80 }
81
82
83
84 /*
85 * Delete a hash table.
86 */
DeleteHashTable(struct HashTable * table)87 void DeleteHashTable(struct HashTable *table)
88 {
89 GLuint i;
90 assert(table);
91 for (i=0;i<TABLE_SIZE;i++) {
92 struct HashEntry *entry = table->Table[i];
93 while (entry) {
94 struct HashEntry *next = entry->Next;
95 free(entry);
96 entry = next;
97 }
98 }
99 free(table);
100 }
101
102
103
104 /*
105 * Lookup an entry in the hash table.
106 * Input: table - the hash table
107 * key - the key
108 * Return: user data pointer or NULL if key not in table
109 */
HashLookup(const struct HashTable * table,GLuint key)110 void *HashLookup(const struct HashTable *table, GLuint key)
111 {
112 GLuint pos;
113 struct HashEntry *entry;
114
115 assert(table);
116 assert(key);
117
118 pos = key % TABLE_SIZE;
119 entry = table->Table[pos];
120 while (entry) {
121 if (entry->Key == key) {
122 return entry->Data;
123 }
124 entry = entry->Next;
125 }
126 return NULL;
127 }
128
129
130
131 /*
132 * Insert into the hash table. If an entry with this key already exists
133 * we'll replace the existing entry.
134 * Input: table - the hash table
135 * key - the key (not zero)
136 * data - pointer to user data
137 */
HashInsert(struct HashTable * table,GLuint key,void * data)138 void HashInsert(struct HashTable *table, GLuint key, void *data)
139 {
140 /* search for existing entry with this key */
141 GLuint pos;
142 struct HashEntry *entry;
143
144 assert(table);
145 assert(key);
146
147 if (key > table->MaxKey)
148 table->MaxKey = key;
149
150 pos = key % TABLE_SIZE;
151 entry = table->Table[pos];
152 while (entry) {
153 if (entry->Key == key) {
154 /* replace entry's data */
155 entry->Data = data;
156 return;
157 }
158 entry = entry->Next;
159 }
160
161 /* alloc and insert new table entry */
162 entry = (struct HashEntry *) calloc(sizeof(struct HashEntry), 1);
163 entry->Key = key;
164 entry->Data = data;
165 entry->Next = table->Table[pos];
166 table->Table[pos] = entry;
167 }
168
169
170
171 /*
172 * Remove an entry from the hash table.
173 * Input: table - the hash table
174 * key - key of entry to remove
175 */
HashRemove(struct HashTable * table,GLuint key)176 void HashRemove(struct HashTable *table, GLuint key)
177 {
178 GLuint pos;
179 struct HashEntry *entry, *prev;
180
181 assert(table);
182 assert(key);
183
184 pos = key % TABLE_SIZE;
185 prev = NULL;
186 entry = table->Table[pos];
187 while (entry) {
188 if (entry->Key == key) {
189 /* found it! */
190 if (prev) {
191 prev->Next = entry->Next;
192 }
193 else {
194 table->Table[pos] = entry->Next;
195 }
196 free(entry);
197 return;
198 }
199 prev = entry;
200 entry = entry->Next;
201 }
202 }
203
204
205
206 /*
207 * Return the key of the "first" entry in the hash table.
208 * By calling this function until zero is returned we can get
209 * the keys of all entries in the table.
210 */
HashFirstEntry(const struct HashTable * table)211 GLuint HashFirstEntry(const struct HashTable *table)
212 {
213 GLuint pos;
214 assert(table);
215 for (pos=0; pos < TABLE_SIZE; pos++) {
216 if (table->Table[pos])
217 return table->Table[pos]->Key;
218 }
219 return 0;
220 }
221
222
223
224 /*
225 * Dump contents of hash table for debugging.
226 */
HashPrint(const struct HashTable * table)227 void HashPrint(const struct HashTable *table)
228 {
229 GLuint i;
230 assert(table);
231 for (i=0;i<TABLE_SIZE;i++) {
232 struct HashEntry *entry = table->Table[i];
233 while (entry) {
234 printf("%u %p\n", entry->Key, entry->Data);
235 entry = entry->Next;
236 }
237 }
238 }
239
240
241
242 /*
243 * Find a block of 'numKeys' adjacent unused hash keys.
244 * Input: table - the hash table
245 * numKeys - number of keys needed
246 * Return: startint key of free block or 0 if failure
247 */
HashFindFreeKeyBlock(const struct HashTable * table,GLuint numKeys)248 GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys)
249 {
250 GLuint maxKey = ~((GLuint) 0);
251 if (maxKey - numKeys > table->MaxKey) {
252 /* the quick solution */
253 return table->MaxKey + 1;
254 }
255 else {
256 /* the slow solution */
257 GLuint freeCount = 0;
258 GLuint freeStart = 0;
259 GLuint key;
260 for (key=0; key!=maxKey; key++) {
261 if (HashLookup(table, key)) {
262 /* darn, this key is already in use */
263 freeCount = 0;
264 freeStart = key+1;
265 }
266 else {
267 /* this key not in use, check if we've found enough */
268 freeCount++;
269 if (freeCount == numKeys) {
270 return freeStart;
271 }
272 }
273 }
274 /* cannot allocate a block of numKeys consecutive keys */
275 return 0;
276 }
277 }
278
279
280
281 #ifdef HASH_TEST_HARNESS
main(int argc,char * argv[])282 int main(int argc, char *argv[])
283 {
284 int a, b, c;
285 struct HashTable *t;
286
287 printf("&a = %p\n", &a);
288 printf("&b = %p\n", &b);
289
290 t = NewHashTable();
291 HashInsert(t, 501, &a);
292 HashInsert(t, 10, &c);
293 HashInsert(t, 0xfffffff8, &b);
294 HashPrint(t);
295 printf("Find 501: %p\n", HashLookup(t,501));
296 printf("Find 1313: %p\n", HashLookup(t,1313));
297 printf("Find block of 100: %d\n", HashFindFreeKeyBlock(t, 100));
298 DeleteHashTable(t);
299
300 return 0;
301 }
302 #endif
303