xref: /illumos-gate/usr/src/cmd/tic/tic_hash.c (revision 2a8bcb4e)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate  * with the License.
87c478bd9Sstevel@tonic-gate  *
97c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate  * and limitations under the License.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate  *
207c478bd9Sstevel@tonic-gate  * CDDL HEADER END
217c478bd9Sstevel@tonic-gate  */
22d2117003Sdp /*
23d2117003Sdp  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
24d2117003Sdp  * Use is subject to license terms.
25d2117003Sdp  */
267c478bd9Sstevel@tonic-gate /*	Copyright (c) 1988 AT&T	*/
277c478bd9Sstevel@tonic-gate /*	  All Rights Reserved  	*/
287c478bd9Sstevel@tonic-gate 
29d2117003Sdp /*
307c478bd9Sstevel@tonic-gate  * University Copyright- Copyright (c) 1982, 1986, 1988
317c478bd9Sstevel@tonic-gate  * The Regents of the University of California
327c478bd9Sstevel@tonic-gate  * All Rights Reserved
33*2a8bcb4eSToomas Soome  *
347c478bd9Sstevel@tonic-gate  * University Acknowledgment- Portions of this document are derived from
357c478bd9Sstevel@tonic-gate  * software developed by the University of California, Berkeley, and its
367c478bd9Sstevel@tonic-gate  * contributors.
377c478bd9Sstevel@tonic-gate  */
387c478bd9Sstevel@tonic-gate 
397c478bd9Sstevel@tonic-gate /*
407c478bd9Sstevel@tonic-gate *************************************************************************
417c478bd9Sstevel@tonic-gate *			COPYRIGHT NOTICE				*
427c478bd9Sstevel@tonic-gate *************************************************************************
437c478bd9Sstevel@tonic-gate *	This software is copyright(C) 1982 by Pavel Curtis		*
447c478bd9Sstevel@tonic-gate *									*
457c478bd9Sstevel@tonic-gate *	Permission is granted to reproduce and distribute		*
467c478bd9Sstevel@tonic-gate *	this file by any means so long as no fee is charged		*
477c478bd9Sstevel@tonic-gate *	above a nominal handling fee and so long as this		*
487c478bd9Sstevel@tonic-gate *	notice is always included in the copies.			*
497c478bd9Sstevel@tonic-gate *									*
507c478bd9Sstevel@tonic-gate *	Other rights are reserved except as explicitly granted		*
517c478bd9Sstevel@tonic-gate *	by written permission of the author.				*
527c478bd9Sstevel@tonic-gate *		Pavel Curtis						*
537c478bd9Sstevel@tonic-gate *		Computer Science Dept.					*
547c478bd9Sstevel@tonic-gate *		405 Upson Hall						*
557c478bd9Sstevel@tonic-gate *		Cornell University					*
567c478bd9Sstevel@tonic-gate *		Ithaca, NY 14853					*
577c478bd9Sstevel@tonic-gate *									*
587c478bd9Sstevel@tonic-gate *		Ph- (607) 256-4934					*
597c478bd9Sstevel@tonic-gate *									*
607c478bd9Sstevel@tonic-gate *		Pavel.Cornell@Udel-Relay(ARPAnet)			*
617c478bd9Sstevel@tonic-gate *		decvax!cornell!pavel(UUCPnet)				*
627c478bd9Sstevel@tonic-gate *********************************************************************** */
637c478bd9Sstevel@tonic-gate 
647c478bd9Sstevel@tonic-gate /*
657c478bd9Sstevel@tonic-gate  *	comp_hash.c --- Routines to deal with the hashtable of capability
667c478bd9Sstevel@tonic-gate  *			names.
677c478bd9Sstevel@tonic-gate  *
687c478bd9Sstevel@tonic-gate  *  $Log:	RCS/comp_hash.v $
697c478bd9Sstevel@tonic-gate  * Revision 2.1  82/10/25  14:45:34  pavel
707c478bd9Sstevel@tonic-gate  * Added Copyright Notice
717c478bd9Sstevel@tonic-gate  *
727c478bd9Sstevel@tonic-gate  * Revision 2.0  82/10/24  15:16:34  pavel
737c478bd9Sstevel@tonic-gate  * Beta-one Test Release
747c478bd9Sstevel@tonic-gate  *
757c478bd9Sstevel@tonic-gate  * Revision 1.3  82/08/23  22:29:33  pavel
767c478bd9Sstevel@tonic-gate  * The REAL Alpha-one Release Version
777c478bd9Sstevel@tonic-gate  *
787c478bd9Sstevel@tonic-gate  * Revision 1.2  82/08/19  19:09:46  pavel
797c478bd9Sstevel@tonic-gate  * Alpha Test Release One
807c478bd9Sstevel@tonic-gate  *
817c478bd9Sstevel@tonic-gate  * Revision 1.1  82/08/12  18:36:23  pavel
827c478bd9Sstevel@tonic-gate  * Initial revision
837c478bd9Sstevel@tonic-gate  *
847c478bd9Sstevel@tonic-gate  *
857c478bd9Sstevel@tonic-gate  */
867c478bd9Sstevel@tonic-gate 
87d2117003Sdp #include <strings.h>
887c478bd9Sstevel@tonic-gate #include "curses_inc.h"
897c478bd9Sstevel@tonic-gate #include "compiler.h"
907c478bd9Sstevel@tonic-gate 
91d2117003Sdp static void make_nte(void);
92d2117003Sdp static int hash_function(char *);
937c478bd9Sstevel@tonic-gate 
947c478bd9Sstevel@tonic-gate /*
957c478bd9Sstevel@tonic-gate  *	make_hash_table()
967c478bd9Sstevel@tonic-gate  *
977c478bd9Sstevel@tonic-gate  *	Takes the entries in cap_table[] and hashes them into cap_hash_table[]
987c478bd9Sstevel@tonic-gate  *	by name.  There are Captabsize entries in cap_table[] and Hashtabsize
997c478bd9Sstevel@tonic-gate  *	slots in cap_hash_table[].
1007c478bd9Sstevel@tonic-gate  *
1017c478bd9Sstevel@tonic-gate  */
1027c478bd9Sstevel@tonic-gate 
1037c478bd9Sstevel@tonic-gate void
make_hash_table()1047c478bd9Sstevel@tonic-gate make_hash_table()
1057c478bd9Sstevel@tonic-gate {
1067c478bd9Sstevel@tonic-gate 	int	i;
1077c478bd9Sstevel@tonic-gate 	int	hashvalue;
1087c478bd9Sstevel@tonic-gate 	int	collisions = 0;
1097c478bd9Sstevel@tonic-gate 
1107c478bd9Sstevel@tonic-gate 	make_nte();
1117c478bd9Sstevel@tonic-gate 	for (i = 0; i < Captabsize; i++) {
1127c478bd9Sstevel@tonic-gate 		hashvalue = hash_function(cap_table[i].nte_name);
1137c478bd9Sstevel@tonic-gate 		DEBUG(9, "%d\n", hashvalue);
1147c478bd9Sstevel@tonic-gate 
1157c478bd9Sstevel@tonic-gate 		if (cap_hash_table[hashvalue] != (struct name_table_entry *) 0)
1167c478bd9Sstevel@tonic-gate 			collisions++;
1177c478bd9Sstevel@tonic-gate 
1187c478bd9Sstevel@tonic-gate 		cap_table[i].nte_link = cap_hash_table[hashvalue];
1197c478bd9Sstevel@tonic-gate 		cap_hash_table[hashvalue] = &cap_table[i];
1207c478bd9Sstevel@tonic-gate 	}
1217c478bd9Sstevel@tonic-gate 
1227c478bd9Sstevel@tonic-gate 	DEBUG(3, "Hash table complete\n%d collisions ", collisions);
1237c478bd9Sstevel@tonic-gate 	DEBUG(3, "out of %d entries\n", Captabsize);
1247c478bd9Sstevel@tonic-gate 	return;
1257c478bd9Sstevel@tonic-gate }
1267c478bd9Sstevel@tonic-gate 
1277c478bd9Sstevel@tonic-gate /*
1287c478bd9Sstevel@tonic-gate  * Make the name_table_entry from the capnames.c set of tables.
1297c478bd9Sstevel@tonic-gate  */
130d2117003Sdp static void
make_nte(void)131d2117003Sdp make_nte(void)
1327c478bd9Sstevel@tonic-gate {
133d2117003Sdp 	int i, n;
1347c478bd9Sstevel@tonic-gate 	extern char *boolnames[], *numnames[], *strnames[];
1357c478bd9Sstevel@tonic-gate 
1367c478bd9Sstevel@tonic-gate 	n = 0;
1377c478bd9Sstevel@tonic-gate 
1387c478bd9Sstevel@tonic-gate 	for (i = 0; boolnames[i]; i++) {
1397c478bd9Sstevel@tonic-gate 		cap_table[n].nte_link = NULL;
1407c478bd9Sstevel@tonic-gate 		cap_table[n].nte_name = boolnames[i];
1417c478bd9Sstevel@tonic-gate 		cap_table[n].nte_type = BOOLEAN;
1427c478bd9Sstevel@tonic-gate 		cap_table[n].nte_index = i;
1437c478bd9Sstevel@tonic-gate 		n++;
1447c478bd9Sstevel@tonic-gate 	}
1457c478bd9Sstevel@tonic-gate 	BoolCount = i;
1467c478bd9Sstevel@tonic-gate 
1477c478bd9Sstevel@tonic-gate 	for (i = 0; numnames[i]; i++) {
1487c478bd9Sstevel@tonic-gate 		cap_table[n].nte_link = NULL;
1497c478bd9Sstevel@tonic-gate 		cap_table[n].nte_name = numnames[i];
1507c478bd9Sstevel@tonic-gate 		cap_table[n].nte_type = NUMBER;
1517c478bd9Sstevel@tonic-gate 		cap_table[n].nte_index = i;
1527c478bd9Sstevel@tonic-gate 		n++;
1537c478bd9Sstevel@tonic-gate 	}
1547c478bd9Sstevel@tonic-gate 	NumCount = i;
1557c478bd9Sstevel@tonic-gate 
1567c478bd9Sstevel@tonic-gate 	for (i 	= 0; strnames[i]; i++) {
1577c478bd9Sstevel@tonic-gate 		cap_table[n].nte_link = NULL;
1587c478bd9Sstevel@tonic-gate 		cap_table[n].nte_name = strnames[i];
1597c478bd9Sstevel@tonic-gate 		cap_table[n].nte_type = STRING;
1607c478bd9Sstevel@tonic-gate 		cap_table[n].nte_index = i;
1617c478bd9Sstevel@tonic-gate 		n++;
1627c478bd9Sstevel@tonic-gate 	}
1637c478bd9Sstevel@tonic-gate 	StrCount = i;
1647c478bd9Sstevel@tonic-gate 
1657c478bd9Sstevel@tonic-gate 	Captabsize = n;
1667c478bd9Sstevel@tonic-gate }
1677c478bd9Sstevel@tonic-gate 
1687c478bd9Sstevel@tonic-gate 
1697c478bd9Sstevel@tonic-gate /*
1707c478bd9Sstevel@tonic-gate  *	int hash_function(string)
1717c478bd9Sstevel@tonic-gate  *
1727c478bd9Sstevel@tonic-gate  *	Computes the hashing function on the given string.
1737c478bd9Sstevel@tonic-gate  *
1747c478bd9Sstevel@tonic-gate  *	The current hash function is the sum of each consectutive pair
1757c478bd9Sstevel@tonic-gate  *	of characters, taken as two-byte integers, mod Hashtabsize.
1767c478bd9Sstevel@tonic-gate  *
1777c478bd9Sstevel@tonic-gate  */
1787c478bd9Sstevel@tonic-gate 
179d2117003Sdp static int
hash_function(char * string)1807c478bd9Sstevel@tonic-gate hash_function(char *string)
1817c478bd9Sstevel@tonic-gate {
1827c478bd9Sstevel@tonic-gate 	long	sum = 0;
1837c478bd9Sstevel@tonic-gate 
1847c478bd9Sstevel@tonic-gate 	while (*string) {
1857c478bd9Sstevel@tonic-gate 		sum += *string + (*(string + 1) << 8);
1867c478bd9Sstevel@tonic-gate 		string++;
1877c478bd9Sstevel@tonic-gate 	}
1887c478bd9Sstevel@tonic-gate 
1897c478bd9Sstevel@tonic-gate 	return (sum % Hashtabsize);
1907c478bd9Sstevel@tonic-gate }
1917c478bd9Sstevel@tonic-gate 
1927c478bd9Sstevel@tonic-gate 
1937c478bd9Sstevel@tonic-gate 
1947c478bd9Sstevel@tonic-gate /*
1957c478bd9Sstevel@tonic-gate  *	struct name_table_entry *
1967c478bd9Sstevel@tonic-gate  *	find_entry(string)
1977c478bd9Sstevel@tonic-gate  *
1987c478bd9Sstevel@tonic-gate  *	Finds the entry for the given string in the hash table if present.
1997c478bd9Sstevel@tonic-gate  *	Returns a pointer to the entry in the table or 0 if not found.
2007c478bd9Sstevel@tonic-gate  *
2017c478bd9Sstevel@tonic-gate  */
2027c478bd9Sstevel@tonic-gate 
2037c478bd9Sstevel@tonic-gate struct name_table_entry *
find_entry(char * string)2047c478bd9Sstevel@tonic-gate find_entry(char *string)
2057c478bd9Sstevel@tonic-gate {
2067c478bd9Sstevel@tonic-gate 	int	hashvalue;
2077c478bd9Sstevel@tonic-gate 	struct name_table_entry	*ptr;
2087c478bd9Sstevel@tonic-gate 
2097c478bd9Sstevel@tonic-gate 	hashvalue = hash_function(string);
2107c478bd9Sstevel@tonic-gate 
2117c478bd9Sstevel@tonic-gate 	ptr = cap_hash_table[hashvalue];
2127c478bd9Sstevel@tonic-gate 
2137c478bd9Sstevel@tonic-gate 	while (ptr != (struct name_table_entry *) 0 &&
2147c478bd9Sstevel@tonic-gate 	    strcmp(ptr->nte_name, string) != 0)
2157c478bd9Sstevel@tonic-gate 		ptr = ptr->nte_link;
2167c478bd9Sstevel@tonic-gate 
2177c478bd9Sstevel@tonic-gate 	return (ptr);
2187c478bd9Sstevel@tonic-gate }
219