xref: /illumos-gate/usr/src/cmd/sh/hash.c (revision 2a8bcb4efb45d99ac41c94a75c396b362c414f7f)
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 /*
24  * Copyright 1990 Sun Microsystems, Inc.  All rights reserved.
25  * Use is subject to license terms.
26  */
27 
28 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
29 /*	  All Rights Reserved  	*/
30 
31 #include	"hash.h"
32 #include	"defs.h"
33 
34 #define STRCMP(A, B)	(cf(A, B) != 0)
35 #define FACTOR 	 		035761254233	/* Magic multiplication factor */
36 #define TABLENGTH		64				/* must be multiple of 2 */
37 #define LOG2LEN			6				/* log2 of TABLENGTH */
38 
39 /*
40     NOTE: The following algorithm only works on machines where
41     the results of multiplying two integers is the least
42     significant part of the double word integer required to hold
43     the result.  It is adapted from Knuth, Volume 3, section 6.4.
44 */
45 
46 #define hash(str)		(int)(((unsigned)(crunch(str) * FACTOR)) >> shift)
47 struct node
48 {
49 	ENTRY item;
50 	struct node *next;
51 };
52 
53 static struct node	**last;
54 static struct node	*next;
55 static struct node 	**table;
56 
57 static unsigned int 	bitsper;		/* Bits per byte */
58 static unsigned int	shift;
59 
60 static unsigned int crunch();
61 
62 void
hcreate(void)63 hcreate(void)
64 {
65 	unsigned char c = (unsigned char)~0;			/* A byte full of 1's */
66 	int j;
67 
68 	table = (struct node **)alloc(TABLENGTH * sizeof(struct node *));
69 
70 	for (j=0; j < TABLENGTH; ++j)
71 	{
72 		table[j] = 0;
73 	}
74 
75 	bitsper = 0;
76 
77 	while (c)
78 	{
79 		c = (unsigned int)c >> 1;
80 		bitsper++;
81 	}
82 
83 	shift = (bitsper * sizeof(int)) - LOG2LEN;
84 }
85 
86 
87 void hscan(uscan)
88 	void	(*uscan)();
89 {
90 	struct node		*p, *nxt;
91 	int				j;
92 
93 	for (j=0; j < TABLENGTH; ++j)
94 	{
95 		p = table[j];
96 		while (p)
97 		{
98 			nxt = p->next;
99 			(*uscan)(&p->item);
100 			p = nxt;
101 		}
102 	}
103 }
104 
105 
106 
107 ENTRY *
hfind(str)108 hfind(str)
109 	unsigned char	*str;
110 {
111 	struct node 	*p;
112 	struct node 	**q;
113 	unsigned int 	i;
114 	int 			res;
115 
116 	i = hash(str);
117 
118 	if(table[i] == 0)
119 	{
120 		last = &table[i];
121 		next = 0;
122 		return(0);
123 	}
124 	else
125 	{
126 		q = &table[i];
127 		p = table[i];
128 		while (p != 0 && (res = STRCMP(str, p->item.key)))
129 		{
130 			q = &(p->next);
131 			p = p->next;
132 		}
133 
134 		if (p != 0 && res == 0)
135 			return(&(p->item));
136 		else
137 		{
138 			last = q;
139 			next = p;
140 			return(0);
141 		}
142 	}
143 }
144 
145 ENTRY *
henter(item)146 henter(item)
147 	ENTRY item;
148 {
149 	struct node	*p = (struct node *)alloc(sizeof(struct node));
150 
151 	p->item = item;
152 	*last = p;
153 	p->next = next;
154 	return(&(p->item));
155 }
156 
157 
158 static unsigned int
crunch(key)159 crunch(key)
160 	unsigned char	*key;
161 {
162 	unsigned int 	sum = 0;
163 	int s;
164 
165 	for (s = 0; *key; s++)				/* Simply add up the bytes */
166 		sum += *key++;
167 
168 	return(sum + s);
169 }
170 
171