ReactOS  0.4.14-dev-390-g34947ad
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 
61 struct HashEntry {
63  void *Data;
64  struct HashEntry *Next;
65 };
66 
67 struct HashTable {
70 };
71 
72 
73 
74 /*
75  * Return pointer to a new, empty hash table.
76  */
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  */
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  */
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  */
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  */
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  */
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  */
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
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));
299 
300  return 0;
301 }
302 #endif
static int argc
Definition: ServiceArgs.c:12
Definition: hash.c:67
int main(int argc, char *argv[])
Definition: atactl.cpp:1685
#define free
Definition: debug_ros.c:5
void DeleteHashTable(struct HashTable *table)
Definition: hash.c:87
GLdouble GLdouble t
Definition: gl.h:2047
#define assert(x)
Definition: debug.h:53
GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys)
Definition: hash.c:248
struct HashEntry * Table[TABLE_SIZE]
Definition: hash.c:68
#define argv
Definition: mplay32.c:18
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
void HashPrint(const struct HashTable *table)
Definition: hash.c:227
#define a
Definition: ke_i.h:78
void * HashLookup(const struct HashTable *table, GLuint key)
Definition: hash.c:110
smooth NULL
Definition: ftsmooth.c:416
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
void HashInsert(struct HashTable *table, GLuint key, void *data)
Definition: hash.c:138
void * Data
Definition: hash.c:63
const GLubyte * c
Definition: glext.h:8905
void HashRemove(struct HashTable *table, GLuint key)
Definition: hash.c:176
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLuint HashFirstEntry(const struct HashTable *table)
Definition: hash.c:211
HKEY key
Definition: reg.c:42
uint32_t entry
Definition: isohybrid.c:63
Definition: hash.c:61
static unsigned __int64 next
Definition: rand_nt.c:6
unsigned int GLuint
Definition: gl.h:159
struct HashTable * NewHashTable(void)
Definition: hash.c:77
#define calloc
Definition: rosglue.h:14
#define c
Definition: ke_i.h:80
GLuint MaxKey
Definition: hash.c:69
GLuint Key
Definition: hash.c:62
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define TABLE_SIZE
Definition: hash.c:59
struct HashEntry * Next
Definition: hash.c:64
Definition: path.c:42
#define printf
Definition: config.h:203