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