usr/src/lib/libc/port/gen/hsearch.c

   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         free(old_table);
 236         return (local_table != NULL);
 237 }
 238
 239 void
 240 hdestroy(void)  /* Reset the module to its initial state */
 241 {
 242         POINTER local_table;
 243
 244         lmutex_lock(&table_lock);
 245 #ifdef CHAINED
 246         int i;
 247         NODE *p, *oldp;
 248         for (i = 0; i < length; i++) {
 249                 if (table[i] != (NODE *)NULL) {
 250                         p = table[i];
 251                         while (p != (NODE *)NULL) {
 252                                 oldp = p;
 253                                 p = p -> next;
 254                                 /*
 255                                  * This is a locking vs malloc() violation.
 256                                  * Fortunately, it is not actually compiled.
 257                                  */
 258                                 free(oldp);
 259                         }
 260                 }
 261         }
 262 #endif
 263         local_table = (POINTER)table;
 264         table = 0;
 265 #ifdef OPEN
 266         count = 0;
 267 #endif
 268         lmutex_unlock(&table_lock);
 269         free(local_table);
 270 }
 271
 272 #ifdef OPEN
 273 /*
 274  * Hash search of a fixed-capacity table.  Open addressing used to
 275  *  resolve collisions.  Algorithm modified from Knuth, Volume 3,
 276  *  section 6.4, algorithm D.  Labels flag corresponding actions.
 277  */
 278
 279 /* Find or insert the item into the table */
 280 ENTRY
 281 *hsearch(ENTRY item, ACTION action)
 282         /* "item" to be inserted or found */
 283         /* action: FIND or ENTER */
 284 {
 285         unsigned int i; /* Insertion index */
 286         unsigned int c; /* Secondary probe displacement */
 287
 288         lmutex_lock(&table_lock);
 289         prcnt = 1;
 290
 291 /* D1: */
 292         i = HASH(item.key);     /* Primary hash on key */
 293 #ifdef DEBUG
 294         if (action == ENTER)
 295                 printf("hash = %o\n", i);
 296 #endif
 297
 298 /* D2: */
 299         if (table[i].key == NULL)       /* Empty slot? */
 300                 goto D6;
 301         else if (COMPARE(table[i].key, item.key) == 0)  /* Match? */
 302                 RETURN(&table[i]);
 303
 304 /* D3: */
 305         c = HASH2(item.key);    /* No match => compute secondary hash */
 306 #ifdef DEBUG
 307         if (action == ENTER)
 308                 printf("hash2 = %o\n", c);
 309 #endif
 310
 311 D4:
 312         i = (i + c) % length;   /* Advance to next slot */
 313         prcnt++;
 314
 315 /* D5: */
 316         if (table[i].key == NULL)       /* Empty slot? */
 317                 goto D6;
 318         else if (COMPARE(table[i].key, item.key) == 0)  /* Match? */
 319                 RETURN(&table[i])
 320         else
 321                 goto D4;
 322
 323 D6:     if (action == FIND)             /* Insert if requested */
 324                 RETURN((ENTRY *) NULL);
 325         if (count == (length - 1))      /* Table full? */
 326                 RETURN((ENTRY *) 0);
 327
 328 #ifdef BRENT
 329 /*
 330  * Brent's variation of the open addressing algorithm.  Do extra
 331  * work during insertion to speed retrieval.  May require switching
 332  * of previously placed items.  Adapted from Knuth, Volume 3, section
 333  * 4.6 and Brent's article in CACM, volume 10, #2, February 1973.
 334  */
 335
 336         {
 337         unsigned int p0 = HASH(item.key);   /* First probe index */
 338         unsigned int c0 = HASH2(item.key);  /* Main branch increment */
 339         unsigned int r = prcnt - 1; /* Current minimum distance */
 340         unsigned int j;         /* Counts along main branch */
 341         unsigned int k;         /* Counts along secondary branch */
 342         unsigned int curj;      /* Current best main branch site */
 343         unsigned int curpos;    /* Current best table index */
 344         unsigned int pj;        /* Main branch indices */
 345         unsigned int cj;        /* Secondary branch increment distance */
 346         unsigned int pjk;       /* Secondary branch probe indices */
 347
 348         if (prcnt >= 3) {
 349                 for (j = 0; j < prcnt; j++) {   /* Count along main branch */
 350                         pj = (p0 + j * c0) % length; /* New main branch index */
 351                         cj = HASH2(table[pj].key); /* Secondary branch incr. */
 352                         for (k = 1; j+k <= r; k++) {
 353                                         /* Count on secondary branch */
 354                                 pjk = (pj + k * cj) % length;
 355                                         /* Secondary probe */
 356                                 if (table[pjk].key == NULL) {
 357                                         /* Improvement found */
 358                                         r = j + k; /* Decrement upper bound */
 359                                         curj = pj; /* Save main probe index */
 360                                         curpos = pjk;
 361                                                 /* Save secondeary index */
 362                                 }
 363                         }
 364                 }
 365                 if (r != prcnt - 1) {   /* If an improvement occurred */
 366                         table[curpos] = table[curj]; /* Old key to new site */
 367 #ifdef DEBUG
 368                         printf("Switch curpos = %o, curj = %o, oldi = %o\n",
 369                                 curj, curpos, i);
 370 #endif
 371                         i = curj;
 372                 }
 373         }
 374         }
 375 #endif
 376         count++;                        /* Increment table occupancy count */
 377         table[i] = item;                /* Save item */
 378
 379         lmutex_unlock(&table_lock);
 380         return (&table[i]);             /* Address of item is returned */
 381 }
 382 #endif
 383
 384 #ifdef USCR
 385 #ifdef DRIVER
 386 static int
 387 compare(a, b)
 388 POINTER a;
 389 POINTER b;
 390 {
 391     return (strcmp(a, b));
 392 }
 393
 394 int (* hcompar)() = compare;
 395 #endif
 396 #endif
 397
 398 #ifdef CHAINED
 399 #ifdef SORTUP
 400 #define STRCMP(A, B) (COMPARE((A), (B)) > 0)
 401 #else
 402 #ifdef SORTDOWN
 403 #define STRCMP(A, B) (COMPARE((A), (B)) < 0)
 404 #else
 405 #define STRCMP(A, B) (COMPARE((A), (B)) != 0)
 406 #endif
 407 #endif
 408
 409 ENTRY
 410 *hsearch(item, action)  /* Chained search with sorted lists */
 411 ENTRY item;             /* Item to be inserted or found */
 412 ACTION action;          /* FIND or ENTER */
 413 {
 414         NODE *p;                /* Searches through the linked list */
 415         NODE **q;               /* Where to store the pointer to a new NODE */
 416         unsigned int i;         /* Result of hash */
 417         int res;                /* Result of string comparison */
 418
 419         lmutex_lock(&table_lock);
 420         prcnt = 1;
 421
 422         i = HASH(item.key);     /* Table[i] contains list head */
 423
 424         if (table[i] == (NODE*)NULL) { /* List has not yet been begun */
 425                 if (action == FIND)
 426                         RETURN((ENTRY *) NULL);
 427                 else
 428                         RETURN(build(&table[i], (NODE *) NULL, item));
 429         } else {                /* List is not empty */
 430                 q = &table[i];
 431                 p = table[i];
 432                 while (p != NULL && (res = STRCMP(item.key, p->item.key))) {
 433                         prcnt++;
 434                         q = &(p->next);
 435                         p = p->next;
 436                 }
 437
 438                 if (p != NULL && res == 0)      /* Item has been found */
 439                         RETURN(&(p->item));
 440                 else {                  /* Item is not yet on list */
 441                         if (action == FIND)
 442                                 RETURN((ENTRY *) NULL);
 443                         else
 444 #ifdef START
 445                                 RETURN(build(&table[i], table[i], item));
 446 #else
 447                                 RETURN(build(q, p, item));
 448 #endif
 449                 }
 450         }
 451 }
 452
 453 static ENTRY
 454 *build(last, next, item)
 455 NODE **last;            /* Where to store in last list item */
 456 NODE *next;             /* Link to next list item */
 457 ENTRY item;             /* Item to be kept in node */
 458 {
 459         /*
 460          * This is a locking vs malloc() violation.
 461          * Fortunately, it is not actually compiled.
 462          */
 463         NODE *p = (NODE *) malloc(sizeof (NODE));
 464
 465         if (p != NULL) {
 466                 p->item = item;
 467                 *last = p;
 468                 p->next = next;
 469                 return (&(p->item));
 470         } else
 471                 return (NULL);
 472 }
 473 #endif
 474
 475 #ifdef DIV
 476 static unsigned int
 477 hashd(key)              /* Division hashing scheme */
 478 POINTER key;            /* Key to be hashed */
 479 {
 480     return (crunch(key) % length);
 481 }
 482 #else
 483 #ifdef MULT
 484 /*
 485  *  NOTE: The following algorithm only works on machines where
 486  *  the results of multiplying two integers is the least
 487  *  significant part of the double word integer required to hold
 488  *  the result.  It is adapted from Knuth, Volume 3, section 6.4.
 489  */
 490
 491 static unsigned int
 492 hashm(POINTER key)      /* Multiplication hashing scheme */
 493         /* "key" to be hashed */
 494 {
 495         return ((int)(((unsigned)(crunch(key) * FACTOR)) >> SHIFT));
 496 }
 497
 498 /*
 499  * Secondary hashing, for use with multiplicitive hashing scheme.
 500  * Adapted from Knuth, Volume 3, section 6.4.
 501  */
 502
 503 static unsigned int
 504 hash2m(POINTER key)     /* Secondary hashing routine */
 505         /* "key" is the string to be hashed */
 506 {
 507     return (((unsigned int)((crunch(key) * FACTOR) << m) >> SHIFT) | 1);
 508 }
 509 #endif
 510 #endif
 511
 512 /* PJ Weinberger's hash function */
 513 static unsigned int
 514 crunch(POINTER key)     /* Convert multicharacter key to unsigned int */
 515 {
 516         unsigned int h = 0;
 517         unsigned int g;
 518         unsigned char *p = (unsigned char *)key;
 519
 520         for (; *p; p++) {
 521                 h = (h << 4) + *p;
 522                 g = h & 0xf0000000;
 523                 if (g != 0) {
 524                         h ^= (g >> 24);
 525                         h ^= g;
 526                 }
 527         }
 528         return (h);
 529 }
 530
 531 #ifdef DRIVER
 532 static void
 533 hdump()                 /* Dumps loc, data, probe count, key */
 534 {
 535         unsigned int i; /* Counts table slots */
 536 #ifdef OPEN
 537         unsigned int sum = 0;   /* Counts probes */
 538 #else
 539 #ifdef CHAINED
 540         NODE *a;                /* Current Node on list */
 541 #endif
 542 #endif
 543
 544         for (i = 0; i < length; i++)
 545 #ifdef OPEN
 546                 if (table[i].key == NULL)
 547                         printf("%o.\t-,\t-,\t(NULL)\n", i);
 548                 else {
 549                         unsigned int oldpr = prcnt;
 550                                 /* Save current probe count */
 551
 552                         hsearch(table[i], FIND);
 553                         sum += prcnt;
 554                         printf("%o.\t%d,\t%d,\t%s\n", i,
 555                             *table[i].data, prcnt, table[i].key);
 556                         prcnt = oldpr;
 557                 }
 558         printf("Total probes = %d\n", sum);
 559 #else
 560 #ifdef CHAINED
 561         if (table[i] == NULL)
 562                 printf("%o.\t-,\t-,\t(NULL)\n", i);
 563         else {
 564                 printf("%o.", i);
 565                 for (a = table[i]; a != NULL; a = a->next)
 566                         printf("\t%d,\t%#0.4x,\t%s\n",
 567                             *a->item.data, a, a->item.key);
 568         }
 569 #endif
 570 #endif
 571 }
 572 #endif