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