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