1/* 2 * Copyright 1993, 1995 Christopher Seiwald. 3 * 4 * This file is part of Jam - see jam.c for Copyright information. 5 */ 6 7/* 8 * hash.c - simple in-memory hashing routines 9 * 10 * External routines: 11 * 12 * hashinit() - initialize a hash table, returning a handle 13 * hashitem() - find a record in the table, and optionally enter a new one 14 * hashdone() - free a hash table, given its handle 15 * 16 * Internal routines: 17 * 18 * hashrehash() - resize and rebuild hp->tab, the hash table 19 * 20 * 4/29/93 - ensure ITEM's are aligned 21 * 11/04/02 (seiwald) - const-ing for string literals 22 * 01/31/02 (seiwald) - keyval now unsigned (cray-ziness) 23 */ 24 25# include "jam.h" 26# include "hash.h" 27 28/* Header attached to all data items entered into a hash table. */ 29 30struct hashhdr { 31 struct item *next; 32 unsigned int keyval; /* for quick comparisons */ 33} ; 34 35/* This structure overlays the one handed to hashenter(). */ 36/* It's actual size is given to hashinit(). */ 37 38struct hashdata { 39 char *key; 40 /* rest of user data */ 41} ; 42 43typedef struct item { 44 struct hashhdr hdr; 45 struct hashdata data; 46} ITEM ; 47 48# define MAX_LISTS 32 49 50struct hash 51{ 52 /* 53 * the hash table, just an array of item pointers 54 */ 55 struct { 56 int nel; 57 ITEM **base; 58 } tab; 59 60 int bloat; /* tab.nel / items.nel */ 61 int inel; /* initial number of elements */ 62 63 /* 64 * the array of records, maintained by these routines 65 * essentially a microallocator 66 */ 67 struct { 68 int more; /* how many more ITEMs fit in lists[ list ] */ 69 char *next; /* where to put more ITEMs in lists[ list ] */ 70 int datalen; /* length of records in this hash table */ 71 int size; /* sizeof( ITEM ) + aligned datalen */ 72 int nel; /* total ITEMs held by all lists[] */ 73 int list; /* index into lists[] */ 74 75 struct { 76 int nel; /* total ITEMs held by this list */ 77 char *base; /* base of ITEMs array */ 78 } lists[ MAX_LISTS ]; 79 } items; 80 81 const char *name; /* just for hashstats() */ 82} ; 83 84static void hashrehash( struct hash *hp ); 85static void hashstat( struct hash *hp ); 86 87/* 88 * hashitem() - find a record in the table, and optionally enter a new one 89 */ 90 91int 92hashitem( 93 register struct hash *hp, 94 HASHDATA **data, 95 int enter ) 96{ 97 ITEM **base; 98 register ITEM *i; 99 unsigned char *b = (unsigned char *)(*data)->key; 100 unsigned int keyval; 101 102 if( enter && !hp->items.more ) 103 hashrehash( hp ); 104 105 if( !enter && !hp->items.nel ) 106 return 0; 107 108 keyval = *b; 109 110 while( *b ) 111 keyval = keyval * 2147059363 + *b++; 112 113 base = hp->tab.base + ( keyval % hp->tab.nel ); 114 115 for( i = *base; i; i = i->hdr.next ) 116 if( keyval == i->hdr.keyval && 117 !strcmp( i->data.key, (*data)->key ) ) 118 { 119 *data = &i->data; 120 return !0; 121 } 122 123 if( enter ) 124 { 125 i = (ITEM *)hp->items.next; 126 hp->items.next += hp->items.size; 127 hp->items.more--; 128 memcpy( (char *)&i->data, (char *)*data, hp->items.datalen ); 129 i->hdr.keyval = keyval; 130 i->hdr.next = *base; 131 *base = i; 132 *data = &i->data; 133 } 134 135 return 0; 136} 137 138/* 139 * hashrehash() - resize and rebuild hp->tab, the hash table 140 */ 141 142static void hashrehash( register struct hash *hp ) 143{ 144 int i = ++hp->items.list; 145 146 hp->items.more = i ? 2 * hp->items.nel : hp->inel; 147 hp->items.next = (char *)malloc( hp->items.more * hp->items.size ); 148 149 hp->items.lists[i].nel = hp->items.more; 150 hp->items.lists[i].base = hp->items.next; 151 hp->items.nel += hp->items.more; 152 153 if( hp->tab.base ) 154 free( (char *)hp->tab.base ); 155 156 hp->tab.nel = hp->items.nel * hp->bloat; 157 hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) ); 158 159 memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) ); 160 161 for( i = 0; i < hp->items.list; i++ ) 162 { 163 int nel = hp->items.lists[i].nel; 164 char *next = hp->items.lists[i].base; 165 166 for( ; nel--; next += hp->items.size ) 167 { 168 register ITEM *i = (ITEM *)next; 169 ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel; 170 171 i->hdr.next = *ip; 172 *ip = i; 173 } 174 } 175} 176 177/* --- */ 178 179# define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) ) 180 181/* 182 * hashinit() - initialize a hash table, returning a handle 183 */ 184 185struct hash * 186hashinit( 187 int datalen, 188 const char *name ) 189{ 190 struct hash *hp = (struct hash *)malloc( sizeof( *hp ) ); 191 192 hp->bloat = 3; 193 hp->tab.nel = 0; 194 hp->tab.base = (ITEM **)0; 195 hp->items.more = 0; 196 hp->items.datalen = datalen; 197 hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen ); 198 hp->items.list = -1; 199 hp->items.nel = 0; 200 hp->inel = 11; 201 hp->name = name; 202 203 return hp; 204} 205 206/* 207 * hashdone() - free a hash table, given its handle 208 */ 209 210void 211hashdone( struct hash *hp ) 212{ 213 int i; 214 215 if( !hp ) 216 return; 217 218 if( DEBUG_MEM ) 219 hashstat( hp ); 220 221 if( hp->tab.base ) 222 free( (char *)hp->tab.base ); 223 for( i = 0; i <= hp->items.list; i++ ) 224 free( hp->items.lists[i].base ); 225 free( (char *)hp ); 226} 227 228/* ---- */ 229 230static void 231hashstat( struct hash *hp ) 232{ 233 ITEM **tab = hp->tab.base; 234 int nel = hp->tab.nel; 235 int count = 0; 236 int sets = 0; 237 int run = ( tab[ nel - 1 ] != (ITEM *)0 ); 238 int i, here; 239 240 for( i = nel; i > 0; i-- ) 241 { 242 if( here = ( *tab++ != (ITEM *)0 ) ) 243 count++; 244 if( here && !run ) 245 sets++; 246 run = here; 247 } 248 249 printf( "%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n", 250 hp->name, 251 count, 252 hp->items.nel, 253 hp->tab.nel, 254 hp->items.nel * hp->items.size / 1024, 255 (int)(hp->tab.nel * sizeof( ITEM ** ) / 1024), 256 (float)count / (float)sets ); 257} 258