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