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 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 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 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 * 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