1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 1996 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 28 /* All Rights Reserved */ 29 30 #pragma ident "%Z%%M% %I% %E% SMI" 31 32 /*LINTLIBRARY*/ 33 /* Compile time switches: 34 35 MULT - use a multiplicative hashing function. 36 DIV - use the remainder mod table size as a hashing function. 37 CHAINED - use a linked list to resolve collisions. 38 OPEN - use open addressing to resolve collisions. 39 BRENT - use Brent's modification to improve the OPEN algorithm. 40 SORTUP - CHAINED list is sorted in increasing order. 41 SORTDOWN - CHAINED list is sorted in decreasing order. 42 START - CHAINED list with entries appended at front. 43 DRIVER - compile in a main program to drive the tests. 44 DEBUG - compile some debugging printout statements. 45 USCR - user supplied comparison routine. 46 */ 47 48 #include <stdio.h> 49 #include <limits.h> 50 51 #define SUCCEED 0 52 #define FAIL 1 53 #define TRUE 1 54 #define FALSE 0 55 #define repeat for(;;) 56 #define until(A) if(A) break; 57 58 #ifdef OPEN 59 # undef CHAINED 60 #else 61 #ifndef CHAINED 62 # define OPEN 63 #endif 64 #endif 65 66 #ifdef MULT 67 # undef DIV 68 #else 69 #ifndef DIV 70 # define MULT 71 #endif 72 #endif 73 74 #ifdef START 75 # undef SORTUP 76 # undef SORTDOWN 77 #else 78 #ifdef SORTUP 79 # undef SORTDOWN 80 #endif 81 #endif 82 83 #ifdef USCR 84 # define COMPARE(A, B) (* hcompar)((A), (B)) 85 extern int (* hcompar)(); 86 #else 87 # define COMPARE(A, B) strcmp((A), (B)) 88 #endif 89 90 #ifdef MULT 91 # define SHIFT ((bitsper * sizeof(int)) - m) /* Shift factor */ 92 # define FACTOR 035761254233 /* Magic multiplication factor */ 93 # define HASH hashm /* Multiplicative hash function */ 94 # define HASH2 hash2m /* Secondary hash function */ 95 static unsigned int bitsper; /* Bits per byte */ 96 static unsigned int hashm(); 97 static unsigned int hash2m(); 98 #else 99 #ifdef DIV 100 # define HASH hashd /* Division hashing routine */ 101 # define HASH2(A) 1 /* Secondary hash function */ 102 static unsigned int hashd(); 103 #endif 104 #endif 105 106 typedef enum { 107 FIND, /* Find, if present */ 108 ENTER /* Find; enter if not present */ 109 } ACTION; 110 typedef char *POINTER; 111 typedef struct entry { /* Hash table entry */ 112 POINTER key; 113 POINTER data; 114 } ENTRY; 115 116 #ifdef CHAINED 117 typedef struct node { /* Part of the linked list of entries */ 118 ENTRY item; 119 struct node *next; 120 } NODE; 121 typedef NODE *TABELEM; 122 static NODE **table; /* The address of the hash table */ 123 static ENTRY *build(); 124 #else 125 #ifdef OPEN 126 typedef ENTRY TABELEM; /* What the table contains (TABle ELEMents) */ 127 static TABELEM *table; /* The address of the hash table */ 128 static unsigned int count = 0; /* Number of entries in hash table */ 129 #endif 130 #endif 131 132 static unsigned int length; /* Size of the hash table */ 133 static unsigned int m; /* Log base 2 of length */ 134 static unsigned int prcnt; /* Number of probes this item */ 135 136 extern void free(); 137 extern int printf(), fprintf(); 138 extern char *malloc(), *calloc(), *strcpy(); 139 140 int hcreate(); 141 void hdestroy(); 142 ENTRY *hsearch(); 143 static unsigned int crunch(); 144 145 #ifdef DRIVER 146 static void hdump(); 147 148 main() 149 { 150 char line[80]; /* Room for the input line */ 151 int i = 0; /* Data generator */ 152 ENTRY *res; /* Result of hsearch */ 153 ENTRY *new; /* Test entry */ 154 155 if(hcreate(5)) 156 printf("Length = %u, m = %u\n", length, m); 157 else { 158 fprintf(stderr, "Out of core\n"); 159 exit(FAIL); 160 } 161 162 repeat { 163 hdump(); 164 printf("Enter a probe: "); 165 until (EOF == scanf("%s", line)); 166 #ifdef DEBUG 167 printf("%s, ", line); 168 printf("division: %d, ", hashd(line)); 169 printf("multiplication: %d\n", hashm(line)); 170 #endif 171 new = (ENTRY *) malloc(sizeof(ENTRY)); 172 if(new == NULL) { 173 fprintf(stderr, "Out of core \n"); 174 exit(FAIL); 175 } 176 else { 177 new->key = malloc((unsigned) strlen(line) + 1); 178 if(new->key == NULL) { 179 fprintf(stderr, "Out of core \n"); 180 exit(FAIL); 181 } 182 strcpy(new->key, line); 183 new->data = malloc(sizeof(int)); 184 if(new->data == NULL) { 185 fprintf(stderr, "Out of core \n"); 186 exit(FAIL); 187 } 188 *new->data = i++; 189 } 190 res = hsearch(*new, ENTER); 191 printf("The number of probes required was %d\n", prcnt); 192 if(res == (ENTRY *) 0) 193 printf("Table is full\n"); 194 else { 195 printf("Success: "); 196 printf("Key = %s, Value = %d\n", res->key, *res->data); 197 } 198 } 199 exit(SUCCEED); 200 } 201 #endif 202 203 int 204 hcreate(size) /* Create a hash table no smaller than size */ 205 int size; /* Minimum size for hash table */ 206 { 207 unsigned int unsize; /* Holds the shifted size */ 208 209 if(size <= 0) 210 return(FALSE); 211 212 unsize = size; /* +1 for empty table slot; -1 for ceiling */ 213 length = 1; /* Maximum entries in tabbe */ 214 m = 0; /* Log2 length */ 215 while(unsize) { 216 unsize >>= 1; 217 length <<= 1; 218 m++; 219 } 220 221 table = (TABELEM *) calloc(length, sizeof(TABELEM)); 222 return(table != NULL); 223 } 224 225 void 226 hdestroy() /* Reset the module to its initial state */ 227 { 228 free((POINTER) table); 229 #ifdef OPEN 230 count = 0; 231 #endif 232 } 233 234 #ifdef OPEN 235 /* Hash search of a fixed-capacity table. Open addressing used to 236 resolve collisions. Algorithm modified from Knuth, Volume 3, 237 section 6.4, algorithm D. Labels flag corresponding actions. 238 */ 239 240 ENTRY 241 *hsearch(item, action) /* Find or insert the item into the table */ 242 ENTRY item; /* Item to be inserted or found */ 243 ACTION action; /* FIND or ENTER */ 244 { 245 unsigned int i; /* Insertion index */ 246 unsigned int c; /* Secondary probe displacement */ 247 248 prcnt = 1; 249 250 /* D1: */ 251 i = HASH(item.key); /* Primary hash on key */ 252 #ifdef DEBUG 253 if(action == ENTER) 254 printf("hash = %o\n", i); 255 #endif 256 257 /* D2: */ 258 if(table[i].key == NULL) /* Empty slot? */ 259 goto D6; 260 else if(COMPARE(table[i].key, item.key) == 0) /* Match? */ 261 return(&table[i]); 262 263 /* D3: */ 264 c = HASH2(item.key); /* No match => compute secondary hash */ 265 #ifdef DEBUG 266 if(action == ENTER) 267 printf("hash2 = %o\n", c); 268 #endif 269 270 D4: 271 i = (i + c) % length; /* Advance to next slot */ 272 prcnt++; 273 274 /* D5: */ 275 if(table[i].key == NULL) /* Empty slot? */ 276 goto D6; 277 else if(COMPARE(table[i].key, item.key) == 0) /* Match? */ 278 return(&table[i]); 279 else 280 goto D4; 281 282 D6: if(action == FIND) /* Insert if requested */ 283 return((ENTRY *) NULL); 284 if(count == (length - 1)) /* Table full? */ 285 return((ENTRY *) 0); 286 287 #ifdef BRENT 288 /* Brent's variation of the open addressing algorithm. Do extra 289 work during insertion to speed retrieval. May require switching 290 of previously placed items. Adapted from Knuth, Volume 3, section 291 4.6 and Brent's article in CACM, volume 10, #2, February 1973. 292 */ 293 294 { unsigned int p0 = HASH(item.key); /* First probe index */ 295 unsigned int c0 = HASH2(item.key); /* Main branch increment */ 296 unsigned int r = prcnt - 1; /* Current minimum distance */ 297 unsigned int j; /* Counts along main branch */ 298 unsigned int k; /* Counts along secondary branch */ 299 unsigned int curj; /* Current best main branch site */ 300 unsigned int curpos; /* Current best table index */ 301 unsigned int pj; /* Main branch indices */ 302 unsigned int cj; /* Secondary branch increment distance*/ 303 unsigned int pjk; /* Secondary branch probe indices */ 304 305 if(prcnt >= 3) { 306 for(j = 0; j < prcnt; j++) { /* Count along main branch */ 307 pj = (p0 + j * c0) % length; /* New main branch index */ 308 cj = HASH2(table[pj].key); /* Secondary branch incr. */ 309 for(k=1; j+k <= r; k++) { /* Count on secondary branch*/ 310 pjk = (pj + k * cj) % length; /* Secondary probe */ 311 if(table[pjk].key == NULL) { /* Improvement found */ 312 r = j + k; /* Decrement upper bound */ 313 curj = pj; /* Save main probe index */ 314 curpos = pjk; /* Save secondeary index */ 315 } 316 } 317 } 318 if(r != prcnt - 1) { /* If an improvement occurred */ 319 table[curpos] = table[curj]; /* Old key to new site */ 320 #ifdef DEBUG 321 printf("Switch curpos = %o, curj = %o, oldi = %o\n", 322 curj, curpos, i); 323 #endif 324 i = curj; 325 } 326 } 327 } 328 #endif 329 count++; /* Increment table occupancy count */ 330 table[i] = item; /* Save item */ 331 return(&table[i]); /* Address of item is returned */ 332 } 333 #endif 334 335 #ifdef USCR 336 # ifdef DRIVER 337 static int 338 compare(a, b) 339 POINTER a; 340 POINTER b; 341 { 342 return(strcmp(a, b)); 343 } 344 345 int (* hcompar)() = compare; 346 # endif 347 #endif 348 349 #ifdef CHAINED 350 # ifdef SORTUP 351 # define STRCMP(A, B) (COMPARE((A), (B)) > 0) 352 # else 353 # ifdef SORTDOWN 354 # define STRCMP(A, B) (COMPARE((A), (B)) < 0) 355 # else 356 # define STRCMP(A, B) (COMPARE((A), (B)) != 0) 357 # endif 358 # endif 359 360 ENTRY 361 *hsearch(item, action) /* Chained search with sorted lists */ 362 ENTRY item; /* Item to be inserted or found */ 363 ACTION action; /* FIND or ENTER */ 364 { 365 NODE *p; /* Searches through the linked list */ 366 NODE **q; /* Where to store the pointer to a new NODE */ 367 unsigned int i; /* Result of hash */ 368 int res; /* Result of string comparison */ 369 370 prcnt = 1; 371 372 i = HASH(item.key); /* Table[i] contains list head */ 373 374 if(table[i] == (NODE*)NULL) { /* List has not yet been begun */ 375 if(action == FIND) 376 return((ENTRY *) NULL); 377 else 378 return(build(&table[i], (NODE *) NULL, item)); 379 } 380 else { /* List is not empty */ 381 q = &table[i]; 382 p = table[i]; 383 while(p != NULL && (res = STRCMP(item.key, p->item.key))) { 384 prcnt++; 385 q = &(p->next); 386 p = p->next; 387 } 388 389 if(p != NULL && res == 0) /* Item has been found */ 390 return(&(p->item)); 391 else { /* Item is not yet on list */ 392 if(action == FIND) 393 return((ENTRY *) NULL); 394 else 395 #ifdef START 396 return(build(&table[i], table[i], item)); 397 #else 398 return(build(q, p, item)); 399 #endif 400 } 401 } 402 } 403 404 static ENTRY 405 *build(last, next, item) 406 NODE **last; /* Where to store in last list item */ 407 NODE *next; /* Link to next list item */ 408 ENTRY item; /* Item to be kept in node */ 409 { 410 NODE *p = (NODE *) malloc(sizeof(NODE)); 411 412 if(p != NULL) { 413 p->item = item; 414 *last = p; 415 p->next = next; 416 return(&(p->item)); 417 } 418 else 419 return(NULL); 420 } 421 #endif 422 423 #ifdef DIV 424 static unsigned int 425 hashd(key) /* Division hashing scheme */ 426 POINTER key; /* Key to be hashed */ 427 { 428 return(crunch(key) % length); 429 } 430 #else 431 #ifdef MULT 432 /* 433 NOTE: The following algorithm only works on machines where 434 the results of multiplying two integers is the least 435 significant part of the double word integer required to hold 436 the result. It is adapted from Knuth, Volume 3, section 6.4. 437 */ 438 439 static unsigned int 440 hashm(key) /* Multiplication hashing scheme */ 441 POINTER key; /* Key to be hashed */ 442 { 443 static int first = TRUE; /* TRUE on the first call only */ 444 445 if(first) { /* Compute the number of bits in a byte */ 446 unsigned char c = UCHAR_MAX; /* A byte full of 1's */ 447 bitsper = 0; 448 while(c) { /* Shift until no more 1's */ 449 c >>= 1; 450 bitsper++; /* Count number of shifts */ 451 } 452 first = FALSE; 453 } 454 return((int) (((unsigned) (crunch(key) * FACTOR)) >> SHIFT)); 455 } 456 457 /* 458 * Secondary hashing, for use with multiplicitive hashing scheme. 459 * Adapted from Knuth, Volume 3, section 6.4. 460 */ 461 462 static unsigned int 463 hash2m(key) /* Secondary hashing routine */ 464 POINTER key; /* String to be hashed */ 465 { 466 return((int) (((unsigned) ((crunch(key) * FACTOR) << m) >> SHIFT) | 1)); 467 } 468 #endif 469 #endif 470 471 static unsigned int 472 crunch(key) /* Convert multicharacter key to unsigned int */ 473 POINTER key; 474 { 475 unsigned int sum = 0; /* Results */ 476 int s; /* Length of the key */ 477 478 for(s = 0; *key; s++) /* Simply add up the bytes */ 479 sum += *key++; 480 481 return(sum + s); 482 } 483 484 #ifdef DRIVER 485 static void 486 hdump() /* Dumps loc, data, probe count, key */ 487 { 488 unsigned int i; /* Counts table slots */ 489 #ifdef OPEN 490 unsigned int sum = 0; /* Counts probes */ 491 #else 492 #ifdef CHAINED 493 NODE *a; /* Current Node on list */ 494 #endif 495 #endif 496 497 for(i = 0; i < length; i++) 498 #ifdef OPEN 499 if(table[i].key == NULL) 500 printf("%o.\t-,\t-,\t(NULL)\n", i); 501 else { 502 unsigned int oldpr = prcnt; /* Save current probe count */ 503 hsearch(table[i], FIND); 504 sum += prcnt; 505 printf("%o.\t%d,\t%d,\t%s\n", i, 506 *table[i].data, prcnt, table[i].key); 507 prcnt = oldpr; 508 } 509 printf("Total probes = %d\n", sum); 510 #else 511 #ifdef CHAINED 512 if(table[i] == NULL) 513 printf("%o.\t-,\t-,\t(NULL)\n", i); 514 else { 515 printf("%o.", i); 516 for(a = table[i]; a != NULL; a = a->next) 517 printf("\t%d,\t%#0.4x,\t%s\n", 518 *a->item.data, a, a->item.key); 519 } 520 #endif 521 #endif 522 } 523 #endif 524