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