diff options
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | Makefile.sources | 1 | ||||
-rw-r--r-- | tests/Makefile.am | 3 | ||||
-rw-r--r-- | tests/hash.c | 198 | ||||
-rw-r--r-- | xf86drmHash.c | 196 | ||||
-rw-r--r-- | xf86drmHash.h | 47 |
6 files changed, 260 insertions, 186 deletions
@@ -79,6 +79,7 @@ tests/drmstat | |||
79 | tests/getclient | 79 | tests/getclient |
80 | tests/getstats | 80 | tests/getstats |
81 | tests/getversion | 81 | tests/getversion |
82 | tests/hash | ||
82 | tests/lock | 83 | tests/lock |
83 | tests/openclose | 84 | tests/openclose |
84 | tests/setversion | 85 | tests/setversion |
diff --git a/Makefile.sources b/Makefile.sources index 566f7b55..ff4fe5e3 100644 --- a/Makefile.sources +++ b/Makefile.sources | |||
@@ -1,6 +1,7 @@ | |||
1 | LIBDRM_FILES := \ | 1 | LIBDRM_FILES := \ |
2 | xf86drm.c \ | 2 | xf86drm.c \ |
3 | xf86drmHash.c \ | 3 | xf86drmHash.c \ |
4 | xf86drmHash.h \ | ||
4 | xf86drmRandom.c \ | 5 | xf86drmRandom.c \ |
5 | xf86drmSL.c \ | 6 | xf86drmSL.c \ |
6 | xf86drmMode.c \ | 7 | xf86drmMode.c \ |
diff --git a/tests/Makefile.am b/tests/Makefile.am index 75fc2413..d4674f75 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am | |||
@@ -29,7 +29,8 @@ LDADD = $(top_builddir)/libdrm.la | |||
29 | 29 | ||
30 | check_PROGRAMS = \ | 30 | check_PROGRAMS = \ |
31 | dristat \ | 31 | dristat \ |
32 | drmstat | 32 | drmstat \ |
33 | hash | ||
33 | 34 | ||
34 | if HAVE_NOUVEAU | 35 | if HAVE_NOUVEAU |
35 | SUBDIRS += nouveau | 36 | SUBDIRS += nouveau |
diff --git a/tests/hash.c b/tests/hash.c new file mode 100644 index 00000000..517a667c --- /dev/null +++ b/tests/hash.c | |||
@@ -0,0 +1,198 @@ | |||
1 | /* xf86drmHash.c -- Small hash table support for integer -> integer mapping | ||
2 | * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com | ||
3 | * | ||
4 | * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. | ||
5 | * All Rights Reserved. | ||
6 | * | ||
7 | * Permission is hereby granted, free of charge, to any person obtaining a | ||
8 | * copy of this software and associated documentation files (the "Software"), | ||
9 | * to deal in the Software without restriction, including without limitation | ||
10 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, | ||
11 | * and/or sell copies of the Software, and to permit persons to whom the | ||
12 | * Software is furnished to do so, subject to the following conditions: | ||
13 | * | ||
14 | * The above copyright notice and this permission notice (including the next | ||
15 | * paragraph) shall be included in all copies or substantial portions of the | ||
16 | * Software. | ||
17 | * | ||
18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
19 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
20 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | ||
21 | * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR | ||
22 | * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | ||
23 | * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | ||
24 | * DEALINGS IN THE SOFTWARE. | ||
25 | * | ||
26 | * Authors: Rickard E. (Rik) Faith <faith@valinux.com> | ||
27 | * | ||
28 | * DESCRIPTION | ||
29 | * | ||
30 | * This file contains a straightforward implementation of a fixed-sized | ||
31 | * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for | ||
32 | * collision resolution. There are two potentially interesting things | ||
33 | * about this implementation: | ||
34 | * | ||
35 | * 1) The table is power-of-two sized. Prime sized tables are more | ||
36 | * traditional, but do not have a significant advantage over power-of-two | ||
37 | * sized table, especially when double hashing is not used for collision | ||
38 | * resolution. | ||
39 | * | ||
40 | * 2) The hash computation uses a table of random integers [Hanson97, | ||
41 | * pp. 39-41]. | ||
42 | * | ||
43 | * FUTURE ENHANCEMENTS | ||
44 | * | ||
45 | * With a table size of 512, the current implementation is sufficient for a | ||
46 | * few hundred keys. Since this is well above the expected size of the | ||
47 | * tables for which this implementation was designed, the implementation of | ||
48 | * dynamic hash tables was postponed until the need arises. A common (and | ||
49 | * naive) approach to dynamic hash table implementation simply creates a | ||
50 | * new hash table when necessary, rehashes all the data into the new table, | ||
51 | * and destroys the old table. The approach in [Larson88] is superior in | ||
52 | * two ways: 1) only a portion of the table is expanded when needed, | ||
53 | * distributing the expansion cost over several insertions, and 2) portions | ||
54 | * of the table can be locked, enabling a scalable thread-safe | ||
55 | * implementation. | ||
56 | * | ||
57 | * REFERENCES | ||
58 | * | ||
59 | * [Hanson97] David R. Hanson. C Interfaces and Implementations: | ||
60 | * Techniques for Creating Reusable Software. Reading, Massachusetts: | ||
61 | * Addison-Wesley, 1997. | ||
62 | * | ||
63 | * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3: | ||
64 | * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973. | ||
65 | * | ||
66 | * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April | ||
67 | * 1988, pp. 446-457. | ||
68 | * | ||
69 | */ | ||
70 | |||
71 | #include <stdio.h> | ||
72 | #include <stdlib.h> | ||
73 | |||
74 | #include "xf86drm.h" | ||
75 | #include "xf86drmHash.h" | ||
76 | |||
77 | #define DIST_LIMIT 10 | ||
78 | static int dist[DIST_LIMIT]; | ||
79 | |||
80 | static void clear_dist(void) { | ||
81 | int i; | ||
82 | |||
83 | for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0; | ||
84 | } | ||
85 | |||
86 | static int count_entries(HashBucketPtr bucket) | ||
87 | { | ||
88 | int count = 0; | ||
89 | |||
90 | for (; bucket; bucket = bucket->next) ++count; | ||
91 | return count; | ||
92 | } | ||
93 | |||
94 | static void update_dist(int count) | ||
95 | { | ||
96 | if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1]; | ||
97 | else ++dist[count]; | ||
98 | } | ||
99 | |||
100 | static void compute_dist(HashTablePtr table) | ||
101 | { | ||
102 | int i; | ||
103 | HashBucketPtr bucket; | ||
104 | |||
105 | printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n", | ||
106 | table->entries, table->hits, table->partials, table->misses); | ||
107 | clear_dist(); | ||
108 | for (i = 0; i < HASH_SIZE; i++) { | ||
109 | bucket = table->buckets[i]; | ||
110 | update_dist(count_entries(bucket)); | ||
111 | } | ||
112 | for (i = 0; i < DIST_LIMIT; i++) { | ||
113 | if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]); | ||
114 | else printf("other %10d\n", dist[i]); | ||
115 | } | ||
116 | } | ||
117 | |||
118 | static void check_table(HashTablePtr table, | ||
119 | unsigned long key, unsigned long value) | ||
120 | { | ||
121 | unsigned long retval = 0; | ||
122 | int retcode = drmHashLookup(table, key, &retval); | ||
123 | |||
124 | switch (retcode) { | ||
125 | case -1: | ||
126 | printf("Bad magic = 0x%08lx:" | ||
127 | " key = %lu, expected = %lu, returned = %lu\n", | ||
128 | table->magic, key, value, retval); | ||
129 | break; | ||
130 | case 1: | ||
131 | printf("Not found: key = %lu, expected = %lu returned = %lu\n", | ||
132 | key, value, retval); | ||
133 | break; | ||
134 | case 0: | ||
135 | if (value != retval) | ||
136 | printf("Bad value: key = %lu, expected = %lu, returned = %lu\n", | ||
137 | key, value, retval); | ||
138 | break; | ||
139 | default: | ||
140 | printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n", | ||
141 | retcode, key, value, retval); | ||
142 | break; | ||
143 | } | ||
144 | } | ||
145 | |||
146 | int main(void) | ||
147 | { | ||
148 | HashTablePtr table; | ||
149 | int i; | ||
150 | |||
151 | printf("\n***** 256 consecutive integers ****\n"); | ||
152 | table = drmHashCreate(); | ||
153 | for (i = 0; i < 256; i++) drmHashInsert(table, i, i); | ||
154 | for (i = 0; i < 256; i++) check_table(table, i, i); | ||
155 | for (i = 256; i >= 0; i--) check_table(table, i, i); | ||
156 | compute_dist(table); | ||
157 | drmHashDestroy(table); | ||
158 | |||
159 | printf("\n***** 1024 consecutive integers ****\n"); | ||
160 | table = drmHashCreate(); | ||
161 | for (i = 0; i < 1024; i++) drmHashInsert(table, i, i); | ||
162 | for (i = 0; i < 1024; i++) check_table(table, i, i); | ||
163 | for (i = 1024; i >= 0; i--) check_table(table, i, i); | ||
164 | compute_dist(table); | ||
165 | drmHashDestroy(table); | ||
166 | |||
167 | printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); | ||
168 | table = drmHashCreate(); | ||
169 | for (i = 0; i < 1024; i++) drmHashInsert(table, i*4096, i); | ||
170 | for (i = 0; i < 1024; i++) check_table(table, i*4096, i); | ||
171 | for (i = 1024; i >= 0; i--) check_table(table, i*4096, i); | ||
172 | compute_dist(table); | ||
173 | drmHashDestroy(table); | ||
174 | |||
175 | printf("\n***** 1024 random integers ****\n"); | ||
176 | table = drmHashCreate(); | ||
177 | srandom(0xbeefbeef); | ||
178 | for (i = 0; i < 1024; i++) drmHashInsert(table, random(), i); | ||
179 | srandom(0xbeefbeef); | ||
180 | for (i = 0; i < 1024; i++) check_table(table, random(), i); | ||
181 | srandom(0xbeefbeef); | ||
182 | for (i = 0; i < 1024; i++) check_table(table, random(), i); | ||
183 | compute_dist(table); | ||
184 | drmHashDestroy(table); | ||
185 | |||
186 | printf("\n***** 5000 random integers ****\n"); | ||
187 | table = drmHashCreate(); | ||
188 | srandom(0xbeefbeef); | ||
189 | for (i = 0; i < 5000; i++) drmHashInsert(table, random(), i); | ||
190 | srandom(0xbeefbeef); | ||
191 | for (i = 0; i < 5000; i++) check_table(table, random(), i); | ||
192 | srandom(0xbeefbeef); | ||
193 | for (i = 0; i < 5000; i++) check_table(table, random(), i); | ||
194 | compute_dist(table); | ||
195 | drmHashDestroy(table); | ||
196 | |||
197 | return 0; | ||
198 | } | ||
diff --git a/xf86drmHash.c b/xf86drmHash.c index 82cbc2a5..f7d7f73b 100644 --- a/xf86drmHash.c +++ b/xf86drmHash.c | |||
@@ -71,60 +71,11 @@ | |||
71 | #include <stdio.h> | 71 | #include <stdio.h> |
72 | #include <stdlib.h> | 72 | #include <stdlib.h> |
73 | 73 | ||
74 | #define HASH_MAIN 0 | 74 | #include "xf86drm.h" |
75 | 75 | #include "xf86drmHash.h" | |
76 | #if !HASH_MAIN | ||
77 | # include "xf86drm.h" | ||
78 | #endif | ||
79 | 76 | ||
80 | #define HASH_MAGIC 0xdeadbeef | 77 | #define HASH_MAGIC 0xdeadbeef |
81 | #define HASH_DEBUG 0 | 78 | #define HASH_DEBUG 0 |
82 | #define HASH_SIZE 512 /* Good for about 100 entries */ | ||
83 | /* If you change this value, you probably | ||
84 | have to change the HashHash hashing | ||
85 | function! */ | ||
86 | |||
87 | #if HASH_MAIN | ||
88 | #define HASH_ALLOC malloc | ||
89 | #define HASH_FREE free | ||
90 | #define HASH_RANDOM_DECL | ||
91 | #define HASH_RANDOM_INIT(seed) srandom(seed) | ||
92 | #define HASH_RANDOM random() | ||
93 | #define HASH_RANDOM_DESTROY | ||
94 | #else | ||
95 | #define HASH_ALLOC drmMalloc | ||
96 | #define HASH_FREE drmFree | ||
97 | #define HASH_RANDOM_DECL void *state | ||
98 | #define HASH_RANDOM_INIT(seed) state = drmRandomCreate(seed) | ||
99 | #define HASH_RANDOM drmRandom(state) | ||
100 | #define HASH_RANDOM_DESTROY drmRandomDestroy(state) | ||
101 | |||
102 | #endif | ||
103 | |||
104 | typedef struct HashBucket { | ||
105 | unsigned long key; | ||
106 | void *value; | ||
107 | struct HashBucket *next; | ||
108 | } HashBucket, *HashBucketPtr; | ||
109 | |||
110 | typedef struct HashTable { | ||
111 | unsigned long magic; | ||
112 | unsigned long entries; | ||
113 | unsigned long hits; /* At top of linked list */ | ||
114 | unsigned long partials; /* Not at top of linked list */ | ||
115 | unsigned long misses; /* Not in table */ | ||
116 | HashBucketPtr buckets[HASH_SIZE]; | ||
117 | int p0; | ||
118 | HashBucketPtr p1; | ||
119 | } HashTable, *HashTablePtr; | ||
120 | |||
121 | #if HASH_MAIN | ||
122 | extern void *drmHashCreate(void); | ||
123 | extern int drmHashDestroy(void *t); | ||
124 | extern int drmHashLookup(void *t, unsigned long key, unsigned long *value); | ||
125 | extern int drmHashInsert(void *t, unsigned long key, unsigned long value); | ||
126 | extern int drmHashDelete(void *t, unsigned long key); | ||
127 | #endif | ||
128 | 79 | ||
129 | static unsigned long HashHash(unsigned long key) | 80 | static unsigned long HashHash(unsigned long key) |
130 | { | 81 | { |
@@ -135,10 +86,10 @@ static unsigned long HashHash(unsigned long key) | |||
135 | int i; | 86 | int i; |
136 | 87 | ||
137 | if (!init) { | 88 | if (!init) { |
138 | HASH_RANDOM_DECL; | 89 | void *state; |
139 | HASH_RANDOM_INIT(37); | 90 | state = drmRandomCreate(37); |
140 | for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM; | 91 | for (i = 0; i < 256; i++) scatter[i] = drmRandom(state); |
141 | HASH_RANDOM_DESTROY; | 92 | drmRandomDestroy(state); |
142 | ++init; | 93 | ++init; |
143 | } | 94 | } |
144 | 95 | ||
@@ -159,7 +110,7 @@ void *drmHashCreate(void) | |||
159 | HashTablePtr table; | 110 | HashTablePtr table; |
160 | int i; | 111 | int i; |
161 | 112 | ||
162 | table = HASH_ALLOC(sizeof(*table)); | 113 | table = drmMalloc(sizeof(*table)); |
163 | if (!table) return NULL; | 114 | if (!table) return NULL; |
164 | table->magic = HASH_MAGIC; | 115 | table->magic = HASH_MAGIC; |
165 | table->entries = 0; | 116 | table->entries = 0; |
@@ -183,11 +134,11 @@ int drmHashDestroy(void *t) | |||
183 | for (i = 0; i < HASH_SIZE; i++) { | 134 | for (i = 0; i < HASH_SIZE; i++) { |
184 | for (bucket = table->buckets[i]; bucket;) { | 135 | for (bucket = table->buckets[i]; bucket;) { |
185 | next = bucket->next; | 136 | next = bucket->next; |
186 | HASH_FREE(bucket); | 137 | drmFree(bucket); |
187 | bucket = next; | 138 | bucket = next; |
188 | } | 139 | } |
189 | } | 140 | } |
190 | HASH_FREE(table); | 141 | drmFree(table); |
191 | return 0; | 142 | return 0; |
192 | } | 143 | } |
193 | 144 | ||
@@ -245,7 +196,7 @@ int drmHashInsert(void *t, unsigned long key, void *value) | |||
245 | 196 | ||
246 | if (HashFind(table, key, &hash)) return 1; /* Already in table */ | 197 | if (HashFind(table, key, &hash)) return 1; /* Already in table */ |
247 | 198 | ||
248 | bucket = HASH_ALLOC(sizeof(*bucket)); | 199 | bucket = drmMalloc(sizeof(*bucket)); |
249 | if (!bucket) return -1; /* Error */ | 200 | if (!bucket) return -1; /* Error */ |
250 | bucket->key = key; | 201 | bucket->key = key; |
251 | bucket->value = value; | 202 | bucket->value = value; |
@@ -270,7 +221,7 @@ int drmHashDelete(void *t, unsigned long key) | |||
270 | if (!bucket) return 1; /* Not found */ | 221 | if (!bucket) return 1; /* Not found */ |
271 | 222 | ||
272 | table->buckets[hash] = bucket->next; | 223 | table->buckets[hash] = bucket->next; |
273 | HASH_FREE(bucket); | 224 | drmFree(bucket); |
274 | return 0; | 225 | return 0; |
275 | } | 226 | } |
276 | 227 | ||
@@ -301,128 +252,3 @@ int drmHashFirst(void *t, unsigned long *key, void **value) | |||
301 | table->p1 = table->buckets[0]; | 252 | table->p1 = table->buckets[0]; |
302 | return drmHashNext(table, key, value); | 253 | return drmHashNext(table, key, value); |
303 | } | 254 | } |
304 | |||
305 | #if HASH_MAIN | ||
306 | #define DIST_LIMIT 10 | ||
307 | static int dist[DIST_LIMIT]; | ||
308 | |||
309 | static void clear_dist(void) { | ||
310 | int i; | ||
311 | |||
312 | for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0; | ||
313 | } | ||
314 | |||
315 | static int count_entries(HashBucketPtr bucket) | ||
316 | { | ||
317 | int count = 0; | ||
318 | |||
319 | for (; bucket; bucket = bucket->next) ++count; | ||
320 | return count; | ||
321 | } | ||
322 | |||
323 | static void update_dist(int count) | ||
324 | { | ||
325 | if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1]; | ||
326 | else ++dist[count]; | ||
327 | } | ||
328 | |||
329 | static void compute_dist(HashTablePtr table) | ||
330 | { | ||
331 | int i; | ||
332 | HashBucketPtr bucket; | ||
333 | |||
334 | printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n", | ||
335 | table->entries, table->hits, table->partials, table->misses); | ||
336 | clear_dist(); | ||
337 | for (i = 0; i < HASH_SIZE; i++) { | ||
338 | bucket = table->buckets[i]; | ||
339 | update_dist(count_entries(bucket)); | ||
340 | } | ||
341 | for (i = 0; i < DIST_LIMIT; i++) { | ||
342 | if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]); | ||
343 | else printf("other %10d\n", dist[i]); | ||
344 | } | ||
345 | } | ||
346 | |||
347 | static void check_table(HashTablePtr table, | ||
348 | unsigned long key, unsigned long value) | ||
349 | { | ||
350 | unsigned long retval = 0; | ||
351 | int retcode = drmHashLookup(table, key, &retval); | ||
352 | |||
353 | switch (retcode) { | ||
354 | case -1: | ||
355 | printf("Bad magic = 0x%08lx:" | ||
356 | " key = %lu, expected = %lu, returned = %lu\n", | ||
357 | table->magic, key, value, retval); | ||
358 | break; | ||
359 | case 1: | ||
360 | printf("Not found: key = %lu, expected = %lu returned = %lu\n", | ||
361 | key, value, retval); | ||
362 | break; | ||
363 | case 0: | ||
364 | if (value != retval) | ||
365 | printf("Bad value: key = %lu, expected = %lu, returned = %lu\n", | ||
366 | key, value, retval); | ||
367 | break; | ||
368 | default: | ||
369 | printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n", | ||
370 | retcode, key, value, retval); | ||
371 | break; | ||
372 | } | ||
373 | } | ||
374 | |||
375 | int main(void) | ||
376 | { | ||
377 | HashTablePtr table; | ||
378 | int i; | ||
379 | |||
380 | printf("\n***** 256 consecutive integers ****\n"); | ||
381 | table = drmHashCreate(); | ||
382 | for (i = 0; i < 256; i++) drmHashInsert(table, i, i); | ||
383 | for (i = 0; i < 256; i++) check_table(table, i, i); | ||
384 | for (i = 256; i >= 0; i--) check_table(table, i, i); | ||
385 | compute_dist(table); | ||
386 | drmHashDestroy(table); | ||
387 | |||
388 | printf("\n***** 1024 consecutive integers ****\n"); | ||
389 | table = drmHashCreate(); | ||
390 | for (i = 0; i < 1024; i++) drmHashInsert(table, i, i); | ||
391 | for (i = 0; i < 1024; i++) check_table(table, i, i); | ||
392 | for (i = 1024; i >= 0; i--) check_table(table, i, i); | ||
393 | compute_dist(table); | ||
394 | drmHashDestroy(table); | ||
395 | |||
396 | printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); | ||
397 | table = drmHashCreate(); | ||
398 | for (i = 0; i < 1024; i++) drmHashInsert(table, i*4096, i); | ||
399 | for (i = 0; i < 1024; i++) check_table(table, i*4096, i); | ||
400 | for (i = 1024; i >= 0; i--) check_table(table, i*4096, i); | ||
401 | compute_dist(table); | ||
402 | drmHashDestroy(table); | ||
403 | |||
404 | printf("\n***** 1024 random integers ****\n"); | ||
405 | table = drmHashCreate(); | ||
406 | srandom(0xbeefbeef); | ||
407 | for (i = 0; i < 1024; i++) drmHashInsert(table, random(), i); | ||
408 | srandom(0xbeefbeef); | ||
409 | for (i = 0; i < 1024; i++) check_table(table, random(), i); | ||
410 | srandom(0xbeefbeef); | ||
411 | for (i = 0; i < 1024; i++) check_table(table, random(), i); | ||
412 | compute_dist(table); | ||
413 | drmHashDestroy(table); | ||
414 | |||
415 | printf("\n***** 5000 random integers ****\n"); | ||
416 | table = drmHashCreate(); | ||
417 | srandom(0xbeefbeef); | ||
418 | for (i = 0; i < 5000; i++) drmHashInsert(table, random(), i); | ||
419 | srandom(0xbeefbeef); | ||
420 | for (i = 0; i < 5000; i++) check_table(table, random(), i); | ||
421 | srandom(0xbeefbeef); | ||
422 | for (i = 0; i < 5000; i++) check_table(table, random(), i); | ||
423 | compute_dist(table); | ||
424 | drmHashDestroy(table); | ||
425 | |||
426 | return 0; | ||
427 | } | ||
428 | #endif | ||
diff --git a/xf86drmHash.h b/xf86drmHash.h new file mode 100644 index 00000000..38fd84b7 --- /dev/null +++ b/xf86drmHash.h | |||
@@ -0,0 +1,47 @@ | |||
1 | /* | ||
2 | * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. | ||
3 | * All Rights Reserved. | ||
4 | * | ||
5 | * Permission is hereby granted, free of charge, to any person obtaining a | ||
6 | * copy of this software and associated documentation files (the "Software"), | ||
7 | * to deal in the Software without restriction, including without limitation | ||
8 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, | ||
9 | * and/or sell copies of the Software, and to permit persons to whom the | ||
10 | * Software is furnished to do so, subject to the following conditions: | ||
11 | * | ||
12 | * The above copyright notice and this permission notice (including the next | ||
13 | * paragraph) shall be included in all copies or substantial portions of the | ||
14 | * Software. | ||
15 | * | ||
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | ||
19 | * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR | ||
20 | * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | ||
21 | * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | ||
22 | * DEALINGS IN THE SOFTWARE. | ||
23 | * | ||
24 | * Authors: Rickard E. (Rik) Faith <faith@valinux.com> | ||
25 | */ | ||
26 | |||
27 | #define HASH_SIZE 512 /* Good for about 100 entries */ | ||
28 | /* If you change this value, you probably | ||
29 | have to change the HashHash hashing | ||
30 | function! */ | ||
31 | |||
32 | typedef struct HashBucket { | ||
33 | unsigned long key; | ||
34 | void *value; | ||
35 | struct HashBucket *next; | ||
36 | } HashBucket, *HashBucketPtr; | ||
37 | |||
38 | typedef struct HashTable { | ||
39 | unsigned long magic; | ||
40 | unsigned long entries; | ||
41 | unsigned long hits; /* At top of linked list */ | ||
42 | unsigned long partials; /* Not at top of linked list */ | ||
43 | unsigned long misses; /* Not in table */ | ||
44 | HashBucketPtr buckets[HASH_SIZE]; | ||
45 | int p0; | ||
46 | HashBucketPtr p1; | ||
47 | } HashTable, *HashTablePtr; | ||