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 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26 /* Copyright (c) 1988 AT&T */
27 /* All Rights Reserved */
28
29 /*
30 * University Copyright- Copyright (c) 1982, 1986, 1988
31 * The Regents of the University of California
32 * All Rights Reserved
33 *
34 * University Acknowledgment- Portions of this document are derived from
35 * software developed by the University of California, Berkeley, and its
36 * contributors.
37 */
38
39 #pragma ident "%Z%%M% %I% %E% SMI"
40
41 /*
42 *************************************************************************
43 * COPYRIGHT NOTICE *
44 *************************************************************************
45 * This software is copyright(C) 1982 by Pavel Curtis *
46 * *
47 * Permission is granted to reproduce and distribute *
48 * this file by any means so long as no fee is charged *
49 * above a nominal handling fee and so long as this *
50 * notice is always included in the copies. *
51 * *
52 * Other rights are reserved except as explicitly granted *
53 * by written permission of the author. *
54 * Pavel Curtis *
55 * Computer Science Dept. *
56 * 405 Upson Hall *
57 * Cornell University *
58 * Ithaca, NY 14853 *
59 * *
60 * Ph- (607) 256-4934 *
61 * *
62 * Pavel.Cornell@Udel-Relay(ARPAnet) *
63 * decvax!cornell!pavel(UUCPnet) *
64 *********************************************************************** */
65
66 /*
67 * comp_hash.c --- Routines to deal with the hashtable of capability
68 * names.
69 *
70 * $Log: RCS/comp_hash.v $
71 * Revision 2.1 82/10/25 14:45:34 pavel
72 * Added Copyright Notice
73 *
74 * Revision 2.0 82/10/24 15:16:34 pavel
75 * Beta-one Test Release
76 *
77 * Revision 1.3 82/08/23 22:29:33 pavel
78 * The REAL Alpha-one Release Version
79 *
80 * Revision 1.2 82/08/19 19:09:46 pavel
81 * Alpha Test Release One
82 *
83 * Revision 1.1 82/08/12 18:36:23 pavel
84 * Initial revision
85 *
86 *
87 */
88
89 #include <strings.h>
90 #include "curses_inc.h"
91 #include "compiler.h"
92
93 static void make_nte(void);
94 static int hash_function(char *);
95
96 /*
97 * make_hash_table()
98 *
99 * Takes the entries in cap_table[] and hashes them into cap_hash_table[]
100 * by name. There are Captabsize entries in cap_table[] and Hashtabsize
101 * slots in cap_hash_table[].
102 *
103 */
104
105 void
make_hash_table()106 make_hash_table()
107 {
108 int i;
109 int hashvalue;
110 int collisions = 0;
111
112 make_nte();
113 for (i = 0; i < Captabsize; i++) {
114 hashvalue = hash_function(cap_table[i].nte_name);
115 DEBUG(9, "%d\n", hashvalue);
116
117 if (cap_hash_table[hashvalue] != (struct name_table_entry *) 0)
118 collisions++;
119
120 cap_table[i].nte_link = cap_hash_table[hashvalue];
121 cap_hash_table[hashvalue] = &cap_table[i];
122 }
123
124 DEBUG(3, "Hash table complete\n%d collisions ", collisions);
125 DEBUG(3, "out of %d entries\n", Captabsize);
126 return;
127 }
128
129 /*
130 * Make the name_table_entry from the capnames.c set of tables.
131 */
132 static void
make_nte(void)133 make_nte(void)
134 {
135 int i, n;
136 extern char *boolnames[], *numnames[], *strnames[];
137
138 n = 0;
139
140 for (i = 0; boolnames[i]; i++) {
141 cap_table[n].nte_link = NULL;
142 cap_table[n].nte_name = boolnames[i];
143 cap_table[n].nte_type = BOOLEAN;
144 cap_table[n].nte_index = i;
145 n++;
146 }
147 BoolCount = i;
148
149 for (i = 0; numnames[i]; i++) {
150 cap_table[n].nte_link = NULL;
151 cap_table[n].nte_name = numnames[i];
152 cap_table[n].nte_type = NUMBER;
153 cap_table[n].nte_index = i;
154 n++;
155 }
156 NumCount = i;
157
158 for (i = 0; strnames[i]; i++) {
159 cap_table[n].nte_link = NULL;
160 cap_table[n].nte_name = strnames[i];
161 cap_table[n].nte_type = STRING;
162 cap_table[n].nte_index = i;
163 n++;
164 }
165 StrCount = i;
166
167 Captabsize = n;
168 }
169
170
171 /*
172 * int hash_function(string)
173 *
174 * Computes the hashing function on the given string.
175 *
176 * The current hash function is the sum of each consectutive pair
177 * of characters, taken as two-byte integers, mod Hashtabsize.
178 *
179 */
180
181 static int
hash_function(char * string)182 hash_function(char *string)
183 {
184 long sum = 0;
185
186 while (*string) {
187 sum += *string + (*(string + 1) << 8);
188 string++;
189 }
190
191 return (sum % Hashtabsize);
192 }
193
194
195
196 /*
197 * struct name_table_entry *
198 * find_entry(string)
199 *
200 * Finds the entry for the given string in the hash table if present.
201 * Returns a pointer to the entry in the table or 0 if not found.
202 *
203 */
204
205 struct name_table_entry *
find_entry(char * string)206 find_entry(char *string)
207 {
208 int hashvalue;
209 struct name_table_entry *ptr;
210
211 hashvalue = hash_function(string);
212
213 ptr = cap_hash_table[hashvalue];
214
215 while (ptr != (struct name_table_entry *) 0 &&
216 strcmp(ptr->nte_name, string) != 0)
217 ptr = ptr->nte_link;
218
219 return (ptr);
220 }
221