17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
22965005c8Schin
23965005c8Schin /*
24965005c8Schin * Copyright 1990 Sun Microsystems, Inc. All rights reserved.
25965005c8Schin * Use is subject to license terms.
26965005c8Schin */
27965005c8Schin
287c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
297c478bd9Sstevel@tonic-gate /* All Rights Reserved */
307c478bd9Sstevel@tonic-gate
317c478bd9Sstevel@tonic-gate #include "hash.h"
327c478bd9Sstevel@tonic-gate #include "defs.h"
337c478bd9Sstevel@tonic-gate
347c478bd9Sstevel@tonic-gate #define STRCMP(A, B) (cf(A, B) != 0)
357c478bd9Sstevel@tonic-gate #define FACTOR 035761254233 /* Magic multiplication factor */
367c478bd9Sstevel@tonic-gate #define TABLENGTH 64 /* must be multiple of 2 */
377c478bd9Sstevel@tonic-gate #define LOG2LEN 6 /* log2 of TABLENGTH */
387c478bd9Sstevel@tonic-gate
397c478bd9Sstevel@tonic-gate /*
407c478bd9Sstevel@tonic-gate NOTE: The following algorithm only works on machines where
417c478bd9Sstevel@tonic-gate the results of multiplying two integers is the least
427c478bd9Sstevel@tonic-gate significant part of the double word integer required to hold
437c478bd9Sstevel@tonic-gate the result. It is adapted from Knuth, Volume 3, section 6.4.
447c478bd9Sstevel@tonic-gate */
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate #define hash(str) (int)(((unsigned)(crunch(str) * FACTOR)) >> shift)
477c478bd9Sstevel@tonic-gate struct node
487c478bd9Sstevel@tonic-gate {
497c478bd9Sstevel@tonic-gate ENTRY item;
507c478bd9Sstevel@tonic-gate struct node *next;
517c478bd9Sstevel@tonic-gate };
527c478bd9Sstevel@tonic-gate
537c478bd9Sstevel@tonic-gate static struct node **last;
547c478bd9Sstevel@tonic-gate static struct node *next;
557c478bd9Sstevel@tonic-gate static struct node **table;
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate static unsigned int bitsper; /* Bits per byte */
587c478bd9Sstevel@tonic-gate static unsigned int shift;
597c478bd9Sstevel@tonic-gate
607c478bd9Sstevel@tonic-gate static unsigned int crunch();
617c478bd9Sstevel@tonic-gate
62965005c8Schin void
hcreate(void)63965005c8Schin hcreate(void)
647c478bd9Sstevel@tonic-gate {
657c478bd9Sstevel@tonic-gate unsigned char c = (unsigned char)~0; /* A byte full of 1's */
667c478bd9Sstevel@tonic-gate int j;
677c478bd9Sstevel@tonic-gate
687c478bd9Sstevel@tonic-gate table = (struct node **)alloc(TABLENGTH * sizeof(struct node *));
697c478bd9Sstevel@tonic-gate
70*2a8bcb4eSToomas Soome for (j=0; j < TABLENGTH; ++j)
717c478bd9Sstevel@tonic-gate {
727c478bd9Sstevel@tonic-gate table[j] = 0;
737c478bd9Sstevel@tonic-gate }
747c478bd9Sstevel@tonic-gate
757c478bd9Sstevel@tonic-gate bitsper = 0;
767c478bd9Sstevel@tonic-gate
77*2a8bcb4eSToomas Soome while (c)
787c478bd9Sstevel@tonic-gate {
797c478bd9Sstevel@tonic-gate c = (unsigned int)c >> 1;
807c478bd9Sstevel@tonic-gate bitsper++;
817c478bd9Sstevel@tonic-gate }
827c478bd9Sstevel@tonic-gate
837c478bd9Sstevel@tonic-gate shift = (bitsper * sizeof(int)) - LOG2LEN;
847c478bd9Sstevel@tonic-gate }
857c478bd9Sstevel@tonic-gate
867c478bd9Sstevel@tonic-gate
87*2a8bcb4eSToomas Soome void hscan(uscan)
887c478bd9Sstevel@tonic-gate void (*uscan)();
897c478bd9Sstevel@tonic-gate {
907c478bd9Sstevel@tonic-gate struct node *p, *nxt;
917c478bd9Sstevel@tonic-gate int j;
927c478bd9Sstevel@tonic-gate
937c478bd9Sstevel@tonic-gate for (j=0; j < TABLENGTH; ++j)
947c478bd9Sstevel@tonic-gate {
957c478bd9Sstevel@tonic-gate p = table[j];
967c478bd9Sstevel@tonic-gate while (p)
977c478bd9Sstevel@tonic-gate {
987c478bd9Sstevel@tonic-gate nxt = p->next;
997c478bd9Sstevel@tonic-gate (*uscan)(&p->item);
1007c478bd9Sstevel@tonic-gate p = nxt;
1017c478bd9Sstevel@tonic-gate }
1027c478bd9Sstevel@tonic-gate }
1037c478bd9Sstevel@tonic-gate }
1047c478bd9Sstevel@tonic-gate
1057c478bd9Sstevel@tonic-gate
1067c478bd9Sstevel@tonic-gate
1077c478bd9Sstevel@tonic-gate ENTRY *
hfind(str)1087c478bd9Sstevel@tonic-gate hfind(str)
1097c478bd9Sstevel@tonic-gate unsigned char *str;
1107c478bd9Sstevel@tonic-gate {
1117c478bd9Sstevel@tonic-gate struct node *p;
1127c478bd9Sstevel@tonic-gate struct node **q;
1137c478bd9Sstevel@tonic-gate unsigned int i;
114*2a8bcb4eSToomas Soome int res;
1157c478bd9Sstevel@tonic-gate
1167c478bd9Sstevel@tonic-gate i = hash(str);
1177c478bd9Sstevel@tonic-gate
1187c478bd9Sstevel@tonic-gate if(table[i] == 0)
119*2a8bcb4eSToomas Soome {
1207c478bd9Sstevel@tonic-gate last = &table[i];
1217c478bd9Sstevel@tonic-gate next = 0;
1227c478bd9Sstevel@tonic-gate return(0);
1237c478bd9Sstevel@tonic-gate }
124*2a8bcb4eSToomas Soome else
1257c478bd9Sstevel@tonic-gate {
1267c478bd9Sstevel@tonic-gate q = &table[i];
1277c478bd9Sstevel@tonic-gate p = table[i];
128*2a8bcb4eSToomas Soome while (p != 0 && (res = STRCMP(str, p->item.key)))
1297c478bd9Sstevel@tonic-gate {
1307c478bd9Sstevel@tonic-gate q = &(p->next);
1317c478bd9Sstevel@tonic-gate p = p->next;
1327c478bd9Sstevel@tonic-gate }
1337c478bd9Sstevel@tonic-gate
134*2a8bcb4eSToomas Soome if (p != 0 && res == 0)
1357c478bd9Sstevel@tonic-gate return(&(p->item));
1367c478bd9Sstevel@tonic-gate else
1377c478bd9Sstevel@tonic-gate {
1387c478bd9Sstevel@tonic-gate last = q;
1397c478bd9Sstevel@tonic-gate next = p;
1407c478bd9Sstevel@tonic-gate return(0);
1417c478bd9Sstevel@tonic-gate }
1427c478bd9Sstevel@tonic-gate }
1437c478bd9Sstevel@tonic-gate }
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate ENTRY *
henter(item)1467c478bd9Sstevel@tonic-gate henter(item)
1477c478bd9Sstevel@tonic-gate ENTRY item;
1487c478bd9Sstevel@tonic-gate {
1497c478bd9Sstevel@tonic-gate struct node *p = (struct node *)alloc(sizeof(struct node));
1507c478bd9Sstevel@tonic-gate
1517c478bd9Sstevel@tonic-gate p->item = item;
1527c478bd9Sstevel@tonic-gate *last = p;
1537c478bd9Sstevel@tonic-gate p->next = next;
1547c478bd9Sstevel@tonic-gate return(&(p->item));
1557c478bd9Sstevel@tonic-gate }
1567c478bd9Sstevel@tonic-gate
1577c478bd9Sstevel@tonic-gate
158*2a8bcb4eSToomas Soome static unsigned int
crunch(key)159*2a8bcb4eSToomas Soome crunch(key)
1607c478bd9Sstevel@tonic-gate unsigned char *key;
1617c478bd9Sstevel@tonic-gate {
162*2a8bcb4eSToomas Soome unsigned int sum = 0;
1637c478bd9Sstevel@tonic-gate int s;
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate for (s = 0; *key; s++) /* Simply add up the bytes */
1667c478bd9Sstevel@tonic-gate sum += *key++;
1677c478bd9Sstevel@tonic-gate
1687c478bd9Sstevel@tonic-gate return(sum + s);
1697c478bd9Sstevel@tonic-gate }
1707c478bd9Sstevel@tonic-gate
171