xref: /illumos-gate/usr/src/cmd/tic/tic_hash.c (revision d2117003)
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