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 * HSEARCH_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
main()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 HSEARCH_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
hcreate(size_t size)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
hdestroy(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
hsearch(ENTRY item,ACTION action)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 HSEARCH_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 HSEARCH_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 HSEARCH_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
compare(a,b)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
hsearch(item,action)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
build(last,next,item)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
hashd(key)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
hashm(POINTER key)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
hash2m(POINTER key)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
crunch(POINTER key)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
hdump()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