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