ReactOS 0.4.15-dev-7788-g1ad9096
hash.c
Go to the documentation of this file.
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
61struct HashEntry {
63 void *Data;
64 struct HashEntry *Next;
65};
66
67struct HashTable {
70};
71
72
73
74/*
75 * Return pointer to a new, empty hash table.
76 */
78{
79 return (struct HashTable *) calloc(sizeof (struct HashTable), 1);
80}
81
82
83
84/*
85 * Delete a hash table.
86 */
88{
89 GLuint i;
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 */
110void *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 */
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 */
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 */
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 */
227void 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 */
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
282int 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));
299
300 return 0;
301}
302#endif
static int argc
Definition: ServiceArgs.c:12
#define free
Definition: debug_ros.c:5
#define NULL
Definition: types.h:112
#define TABLE_SIZE
Definition: hash.c:59
void HashRemove(struct HashTable *table, GLuint key)
Definition: hash.c:176
GLuint HashFirstEntry(const struct HashTable *table)
Definition: hash.c:211
struct HashTable * NewHashTable(void)
Definition: hash.c:77
void DeleteHashTable(struct HashTable *table)
Definition: hash.c:87
void * HashLookup(const struct HashTable *table, GLuint key)
Definition: hash.c:110
void HashPrint(const struct HashTable *table)
Definition: hash.c:227
GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys)
Definition: hash.c:248
void HashInsert(struct HashTable *table, GLuint key, void *data)
Definition: hash.c:138
#define assert(x)
Definition: debug.h:53
int main()
Definition: test.c:6
#define printf
Definition: freeldr.h:93
unsigned int GLuint
Definition: gl.h:159
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLdouble GLdouble t
Definition: gl.h:2047
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
uint32_t entry
Definition: isohybrid.c:63
#define a
Definition: ke_i.h:78
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
#define argv
Definition: mplay32.c:18
static unsigned __int64 next
Definition: rand_nt.c:6
#define calloc
Definition: rosglue.h:14
Definition: hash.c:61
GLuint Key
Definition: hash.c:62
void * Data
Definition: hash.c:63
struct HashEntry * Next
Definition: hash.c:64
Definition: hash.c:67
struct HashEntry * Table[TABLE_SIZE]
Definition: hash.c:68
GLuint MaxKey
Definition: hash.c:69
Definition: copy.c:22