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