1 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping 2 * Created: Sun Apr 18 09:35:45 1999 by faith (at) 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 (at) 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++) 84 dist[i] = 0; 85 } 86 87 static int count_entries(HashBucketPtr bucket) 88 { 89 int count = 0; 90 91 for (; bucket; bucket = bucket->next) 92 ++count; 93 return count; 94 } 95 96 static void update_dist(int count) 97 { 98 if (count >= DIST_LIMIT) 99 ++dist[DIST_LIMIT-1]; 100 else 101 ++dist[count]; 102 } 103 104 static void compute_dist(HashTablePtr table) 105 { 106 int i; 107 HashBucketPtr bucket; 108 109 printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n", 110 table->entries, table->hits, table->partials, table->misses); 111 clear_dist(); 112 for (i = 0; i < HASH_SIZE; i++) { 113 bucket = table->buckets[i]; 114 update_dist(count_entries(bucket)); 115 } 116 for (i = 0; i < DIST_LIMIT; i++) { 117 if (i != DIST_LIMIT-1) 118 printf("%5d %10d\n", i, dist[i]); 119 else 120 printf("other %10d\n", dist[i]); 121 } 122 } 123 124 static int check_table(HashTablePtr table, 125 unsigned long key, void * value) 126 { 127 void *retval; 128 int retcode = drmHashLookup(table, key, &retval); 129 130 switch (retcode) { 131 case -1: 132 printf("Bad magic = 0x%08lx:" 133 " key = %lu, expected = %p, returned = %p\n", 134 table->magic, key, value, retval); 135 break; 136 case 1: 137 printf("Not found: key = %lu, expected = %p, returned = %p\n", 138 key, value, retval); 139 break; 140 case 0: 141 if (value != retval) { 142 printf("Bad value: key = %lu, expected = %p, returned = %p\n", 143 key, value, retval); 144 retcode = -1; 145 } 146 break; 147 default: 148 printf("Bad retcode = %d: key = %lu, expected = %p, returned = %p\n", 149 retcode, key, value, retval); 150 break; 151 } 152 return retcode; 153 } 154 155 int main(void) 156 { 157 HashTablePtr table; 158 unsigned long i; 159 int ret = 0; 160 161 printf("\n***** 256 consecutive integers ****\n"); 162 table = drmHashCreate(); 163 for (i = 0; i < 256; i++) 164 drmHashInsert(table, i, (void *)(i << 16 | i)); 165 for (i = 0; i < 256; i++) 166 ret |= check_table(table, i, (void *)(i << 16 | i)); 167 compute_dist(table); 168 drmHashDestroy(table); 169 170 printf("\n***** 1024 consecutive integers ****\n"); 171 table = drmHashCreate(); 172 for (i = 0; i < 1024; i++) 173 drmHashInsert(table, i, (void *)(i << 16 | i)); 174 for (i = 0; i < 1024; i++) 175 ret |= check_table(table, i, (void *)(i << 16 | i)); 176 compute_dist(table); 177 drmHashDestroy(table); 178 179 printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); 180 table = drmHashCreate(); 181 for (i = 0; i < 1024; i++) 182 drmHashInsert(table, i*4096, (void *)(i << 16 | i)); 183 for (i = 0; i < 1024; i++) 184 ret |= check_table(table, i*4096, (void *)(i << 16 | i)); 185 compute_dist(table); 186 drmHashDestroy(table); 187 188 printf("\n***** 1024 random integers ****\n"); 189 table = drmHashCreate(); 190 srandom(0xbeefbeef); 191 for (i = 0; i < 1024; i++) 192 drmHashInsert(table, random(), (void *)(i << 16 | i)); 193 srandom(0xbeefbeef); 194 for (i = 0; i < 1024; i++) 195 ret |= check_table(table, random(), (void *)(i << 16 | i)); 196 srandom(0xbeefbeef); 197 for (i = 0; i < 1024; i++) 198 ret |= check_table(table, random(), (void *)(i << 16 | i)); 199 compute_dist(table); 200 drmHashDestroy(table); 201 202 printf("\n***** 5000 random integers ****\n"); 203 table = drmHashCreate(); 204 srandom(0xbeefbeef); 205 for (i = 0; i < 5000; i++) 206 drmHashInsert(table, random(), (void *)(i << 16 | i)); 207 srandom(0xbeefbeef); 208 for (i = 0; i < 5000; i++) 209 ret |= check_table(table, random(), (void *)(i << 16 | i)); 210 srandom(0xbeefbeef); 211 for (i = 0; i < 5000; i++) 212 ret |= check_table(table, random(), (void *)(i << 16 | i)); 213 compute_dist(table); 214 drmHashDestroy(table); 215 216 return ret; 217 } 218
