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