1 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping
2 * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
4 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
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:
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
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.
26 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.4 2001/03/21 18:08:54 dawes Exp $
32 * This file contains a straightforward implementation of a fixed-sized
33 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
34 * collision resolution. There are two potentially interesting things
35 * about this implementation:
37 * 1) The table is power-of-two sized. Prime sized tables are more
38 * traditional, but do not have a significant advantage over power-of-two
39 * sized table, especially when double hashing is not used for collision
42 * 2) The hash computation uses a table of random integers [Hanson97,
47 * With a table size of 512, the current implementation is sufficient for a
48 * few hundred keys. Since this is well above the expected size of the
49 * tables for which this implementation was designed, the implementation of
50 * dynamic hash tables was postponed until the need arises. A common (and
51 * naive) approach to dynamic hash table implementation simply creates a
52 * new hash table when necessary, rehashes all the data into the new table,
53 * and destroys the old table. The approach in [Larson88] is superior in
54 * two ways: 1) only a portion of the table is expanded when needed,
55 * distributing the expansion cost over several insertions, and 2) portions
56 * of the table can be locked, enabling a scalable thread-safe
61 * [Hanson97] David R. Hanson. C Interfaces and Implementations:
62 * Techniques for Creating Reusable Software. Reading, Massachusetts:
63 * Addison-Wesley, 1997.
65 * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3:
66 * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973.
68 * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April
82 # include "xf86_ansic.h"
91 #define HASH_MAGIC 0xdeadbeef
93 #define HASH_SIZE 512 /* Good for about 100 entries */
94 /* If you change this value, you probably
95 have to change the HashHash hashing
99 #define HASH_ALLOC malloc
100 #define HASH_FREE free
101 #define HASH_RANDOM_DECL
102 #define HASH_RANDOM_INIT(seed) srandom(seed)
103 #define HASH_RANDOM random()
105 #define HASH_ALLOC drmMalloc
106 #define HASH_FREE drmFree
107 #define HASH_RANDOM_DECL void *state
108 #define HASH_RANDOM_INIT(seed) state = drmRandomCreate(seed)
109 #define HASH_RANDOM drmRandom(state)
113 typedef struct HashBucket
{
116 struct HashBucket
*next
;
117 } HashBucket
, *HashBucketPtr
;
119 typedef struct HashTable
{
121 unsigned long entries
;
122 unsigned long hits
; /* At top of linked list */
123 unsigned long partials
; /* Not at top of linked list */
124 unsigned long misses
; /* Not in table */
125 HashBucketPtr buckets
[HASH_SIZE
];
128 } HashTable
, *HashTablePtr
;
131 extern void *N(HashCreate
)(void);
132 extern int N(HashDestroy
)(void *t
);
133 extern int N(HashLookup
)(void *t
, unsigned long key
, unsigned long *value
);
134 extern int N(HashInsert
)(void *t
, unsigned long key
, unsigned long value
);
135 extern int N(HashDelete
)(void *t
, unsigned long key
);
138 static unsigned long HashHash(unsigned long key
)
140 unsigned long hash
= 0;
141 unsigned long tmp
= key
;
143 static unsigned long scatter
[256];
148 HASH_RANDOM_INIT(37);
149 for (i
= 0; i
< 256; i
++) scatter
[i
] = HASH_RANDOM
;
154 hash
= (hash
<< 1) + scatter
[tmp
& 0xff];
160 printf( "Hash(%d) = %d\n", key
, hash
);
165 void *N(HashCreate
)(void)
170 table
= HASH_ALLOC(sizeof(*table
));
171 if (!table
) return NULL
;
172 table
->magic
= HASH_MAGIC
;
178 for (i
= 0; i
< HASH_SIZE
; i
++) table
->buckets
[i
] = NULL
;
182 int N(HashDestroy
)(void *t
)
184 HashTablePtr table
= (HashTablePtr
)t
;
185 HashBucketPtr bucket
;
189 if (table
->magic
!= HASH_MAGIC
) return -1; /* Bad magic */
191 for (i
= 0; i
< HASH_SIZE
; i
++) {
192 for (bucket
= table
->buckets
[i
]; bucket
;) {
202 /* Find the bucket and organize the list so that this bucket is at the
205 static HashBucketPtr
HashFind(HashTablePtr table
,
206 unsigned long key
, unsigned long *h
)
208 unsigned long hash
= HashHash(key
);
209 HashBucketPtr prev
= NULL
;
210 HashBucketPtr bucket
;
214 for (bucket
= table
->buckets
[hash
]; bucket
; bucket
= bucket
->next
) {
215 if (bucket
->key
== key
) {
218 prev
->next
= bucket
->next
;
219 bucket
->next
= table
->buckets
[hash
];
220 table
->buckets
[hash
] = bucket
;
233 int N(HashLookup
)(void *t
, unsigned long key
, void **value
)
235 HashTablePtr table
= (HashTablePtr
)t
;
236 HashBucketPtr bucket
;
238 if (!table
|| table
->magic
!= HASH_MAGIC
) return -1; /* Bad magic */
240 bucket
= HashFind(table
, key
, NULL
);
241 if (!bucket
) return 1; /* Not found */
242 *value
= bucket
->value
;
243 return 0; /* Found */
246 int N(HashInsert
)(void *t
, unsigned long key
, void *value
)
248 HashTablePtr table
= (HashTablePtr
)t
;
249 HashBucketPtr bucket
;
252 if (table
->magic
!= HASH_MAGIC
) return -1; /* Bad magic */
254 if (HashFind(table
, key
, &hash
)) return 1; /* Already in table */
256 bucket
= HASH_ALLOC(sizeof(*bucket
));
257 if (!bucket
) return -1; /* Error */
259 bucket
->value
= value
;
260 bucket
->next
= table
->buckets
[hash
];
261 table
->buckets
[hash
] = bucket
;
263 printf("Inserted %d at %d/%p\n", key
, hash
, bucket
);
265 return 0; /* Added to table */
268 int N(HashDelete
)(void *t
, unsigned long key
)
270 HashTablePtr table
= (HashTablePtr
)t
;
272 HashBucketPtr bucket
;
274 if (table
->magic
!= HASH_MAGIC
) return -1; /* Bad magic */
276 bucket
= HashFind(table
, key
, &hash
);
278 if (!bucket
) return 1; /* Not found */
280 table
->buckets
[hash
] = bucket
->next
;
285 int N(HashNext
)(void *t
, unsigned long *key
, void **value
)
287 HashTablePtr table
= (HashTablePtr
)t
;
289 for (; table
->p0
< HASH_SIZE
;
290 ++table
->p0
, table
->p1
= table
->buckets
[table
->p0
]) {
292 *key
= table
->p1
->key
;
293 *value
= table
->p1
->value
;
294 table
->p1
= table
->p1
->next
;
301 int N(HashFirst
)(void *t
, unsigned long *key
, void **value
)
303 HashTablePtr table
= (HashTablePtr
)t
;
305 if (table
->magic
!= HASH_MAGIC
) return -1; /* Bad magic */
308 table
->p1
= table
->buckets
[0];
309 return N(HashNext
)(table
, key
, value
);
313 #define DIST_LIMIT 10
314 static int dist
[DIST_LIMIT
];
316 static void clear_dist(void) {
319 for (i
= 0; i
< DIST_LIMIT
; i
++) dist
[i
] = 0;
322 static int count_entries(HashBucketPtr bucket
)
326 for (; bucket
; bucket
= bucket
->next
) ++count
;
330 static void update_dist(int count
)
332 if (count
>= DIST_LIMIT
) ++dist
[DIST_LIMIT
-1];
336 static void compute_dist(HashTablePtr table
)
339 HashBucketPtr bucket
;
341 printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
342 table
->entries
, table
->hits
, table
->partials
, table
->misses
);
344 for (i
= 0; i
< HASH_SIZE
; i
++) {
345 bucket
= table
->buckets
[i
];
346 update_dist(count_entries(bucket
));
348 for (i
= 0; i
< DIST_LIMIT
; i
++) {
349 if (i
!= DIST_LIMIT
-1) printf("%5d %10d\n", i
, dist
[i
]);
350 else printf("other %10d\n", dist
[i
]);
354 static void check_table(HashTablePtr table
,
355 unsigned long key
, unsigned long value
)
357 unsigned long retval
= 0;
358 int retcode
= N(HashLookup
)(table
, key
, &retval
);
362 printf("Bad magic = 0x%08lx:"
363 " key = %lu, expected = %lu, returned = %lu\n",
364 table
->magic
, key
, value
, retval
);
367 printf("Not found: key = %lu, expected = %lu returned = %lu\n",
372 printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
376 printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
377 retcode
, key
, value
, retval
);
387 printf("\n***** 256 consecutive integers ****\n");
388 table
= N(HashCreate
)();
389 for (i
= 0; i
< 256; i
++) N(HashInsert
)(table
, i
, i
);
390 for (i
= 0; i
< 256; i
++) check_table(table
, i
, i
);
391 for (i
= 256; i
>= 0; i
--) check_table(table
, i
, i
);
393 N(HashDestroy
)(table
);
395 printf("\n***** 1024 consecutive integers ****\n");
396 table
= N(HashCreate
)();
397 for (i
= 0; i
< 1024; i
++) N(HashInsert
)(table
, i
, i
);
398 for (i
= 0; i
< 1024; i
++) check_table(table
, i
, i
);
399 for (i
= 1024; i
>= 0; i
--) check_table(table
, i
, i
);
401 N(HashDestroy
)(table
);
403 printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
404 table
= N(HashCreate
)();
405 for (i
= 0; i
< 1024; i
++) N(HashInsert
)(table
, i
*4096, i
);
406 for (i
= 0; i
< 1024; i
++) check_table(table
, i
*4096, i
);
407 for (i
= 1024; i
>= 0; i
--) check_table(table
, i
*4096, i
);
409 N(HashDestroy
)(table
);
411 printf("\n***** 1024 random integers ****\n");
412 table
= N(HashCreate
)();
414 for (i
= 0; i
< 1024; i
++) N(HashInsert
)(table
, random(), i
);
416 for (i
= 0; i
< 1024; i
++) check_table(table
, random(), i
);
418 for (i
= 0; i
< 1024; i
++) check_table(table
, random(), i
);
420 N(HashDestroy
)(table
);
422 printf("\n***** 5000 random integers ****\n");
423 table
= N(HashCreate
)();
425 for (i
= 0; i
< 5000; i
++) N(HashInsert
)(table
, random(), i
);
427 for (i
= 0; i
< 5000; i
++) check_table(table
, random(), i
);
429 for (i
= 0; i
< 5000; i
++) check_table(table
, random(), i
);
431 N(HashDestroy
)(table
);