1/**************************************************************************** 2 * Copyright (c) 1998-2003,2005 Free Software Foundation, Inc. * 3 * * 4 * Permission is hereby granted, free of charge, to any person obtaining a * 5 * copy of this software and associated documentation files (the * 6 * "Software"), to deal in the Software without restriction, including * 7 * without limitation the rights to use, copy, modify, merge, publish, * 8 * distribute, distribute with modifications, sublicense, and/or sell * 9 * copies of the Software, and to permit persons to whom the Software is * 10 * furnished to do so, subject to the following conditions: * 11 * * 12 * The above copyright notice and this permission notice shall be included * 13 * in all copies or substantial portions of the Software. * 14 * * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 16 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 18 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 21 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 22 * * 23 * Except as contained in this notice, the name(s) of the above copyright * 24 * holders shall not be used in advertising or otherwise to promote the * 25 * sale, use or other dealings in this Software without prior written * 26 * authorization. * 27 ****************************************************************************/ 28 29/**************************************************************************** 30 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 31 * and: Eric S. Raymond <esr@snark.thyrsus.com> * 32 * and: Thomas E. Dickey 1996-on * 33 ****************************************************************************/ 34 35/* 36 * comp_hash.c --- Routines to deal with the hashtable of capability 37 * names. 38 * 39 */ 40 41#define USE_TERMLIB 1 42#include <curses.priv.h> 43 44#include <tic.h> 45#include <hashsize.h> 46 47#ifdef MAIN_PROGRAM 48#include <ctype.h> 49#undef DEBUG 50#define DEBUG(level, params) /*nothing */ 51#endif 52 53MODULE_ID("$Id: comp_hash.c,v 1.28 2005/08/20 19:58:18 tom Exp $") 54 55static int hash_function(const char *); 56 57/* 58 * _nc_make_hash_table() 59 * 60 * Takes the entries in table[] and hashes them into hash_table[] 61 * by name. There are CAPTABSIZE entries in table[] and HASHTABSIZE 62 * slots in hash_table[]. 63 * 64 */ 65 66#ifdef MAIN_PROGRAM 67 68#undef MODULE_ID 69#define MODULE_ID(id) /*nothing */ 70#include <tinfo/doalloc.c> 71 72static void 73_nc_make_hash_table(struct name_table_entry *table, 74 struct name_table_entry **hash_table) 75{ 76 int i; 77 int hashvalue; 78 int collisions = 0; 79 80 for (i = 0; i < CAPTABSIZE; i++) { 81 hashvalue = hash_function(table[i].nte_name); 82 83 if (hash_table[hashvalue] != (struct name_table_entry *) 0) 84 collisions++; 85 86 if (hash_table[hashvalue] != 0) 87 table[i].nte_link = (short) (hash_table[hashvalue] - table); 88 hash_table[hashvalue] = &table[i]; 89 } 90 91 DEBUG(4, ("Hash table complete: %d collisions out of %d entries", 92 collisions, CAPTABSIZE)); 93} 94#endif 95 96/* 97 * int hash_function(string) 98 * 99 * Computes the hashing function on the given string. 100 * 101 * The current hash function is the sum of each consectutive pair 102 * of characters, taken as two-byte integers, mod HASHTABSIZE. 103 * 104 */ 105 106static int 107hash_function(const char *string) 108{ 109 long sum = 0; 110 111 DEBUG(9, ("hashing %s", string)); 112 while (*string) { 113 sum += (long) (*string + (*(string + 1) << 8)); 114 string++; 115 } 116 117 DEBUG(9, ("sum is %ld", sum)); 118 return (int) (sum % HASHTABSIZE); 119} 120 121/* 122 * struct name_table_entry * 123 * find_entry(string) 124 * 125 * Finds the entry for the given string in the hash table if present. 126 * Returns a pointer to the entry in the table or 0 if not found. 127 * 128 */ 129 130#ifndef MAIN_PROGRAM 131NCURSES_EXPORT(struct name_table_entry const *) 132_nc_find_entry(const char *string, 133 const struct name_table_entry *const *hash_table) 134{ 135 int hashvalue; 136 struct name_table_entry const *ptr; 137 138 hashvalue = hash_function(string); 139 140 if ((ptr = hash_table[hashvalue]) != 0) { 141 while (strcmp(ptr->nte_name, string) != 0) { 142 if (ptr->nte_link < 0) 143 return 0; 144 ptr = ptr->nte_link + hash_table[HASHTABSIZE]; 145 } 146 } 147 148 return (ptr); 149} 150 151/* 152 * struct name_table_entry * 153 * find_type_entry(string, type, table) 154 * 155 * Finds the first entry for the given name with the given type in the 156 * given table if present (as distinct from find_entry, which finds the 157 * the last entry regardless of type). You can use this if you detect 158 * a name clash. It's slower, though. Returns a pointer to the entry 159 * in the table or 0 if not found. 160 */ 161 162NCURSES_EXPORT(struct name_table_entry const *) 163_nc_find_type_entry(const char *string, 164 int type, 165 const struct name_table_entry *table) 166{ 167 struct name_table_entry const *ptr; 168 169 for (ptr = table; ptr < table + CAPTABSIZE; ptr++) { 170 if (ptr->nte_type == type && strcmp(string, ptr->nte_name) == 0) 171 return (ptr); 172 } 173 174 return ((struct name_table_entry *) NULL); 175} 176#endif 177 178#ifdef MAIN_PROGRAM 179/* 180 * This filter reads from standard input a list of tab-delimited columns, 181 * (e.g., from Caps.filtered) computes the hash-value of a specified column and 182 * writes the hashed tables to standard output. 183 * 184 * By compiling the hash table at build time, we're able to make the entire 185 * set of terminfo and termcap tables readonly (and also provide some runtime 186 * performance enhancement). 187 */ 188 189#define MAX_COLUMNS BUFSIZ /* this _has_ to be worst-case */ 190 191static char ** 192parse_columns(char *buffer) 193{ 194 static char **list; 195 196 int col = 0; 197 198 if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0) 199 return (0); 200 201 if (*buffer != '#') { 202 while (*buffer != '\0') { 203 char *s; 204 for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++) 205 /*EMPTY */ ; 206 if (s != buffer) { 207 char mark = *s; 208 *s = '\0'; 209 if ((s - buffer) > 1 210 && (*buffer == '"') 211 && (s[-1] == '"')) { /* strip the quotes */ 212 buffer++; 213 s[-1] = '\0'; 214 } 215 list[col] = buffer; 216 col++; 217 if (mark == '\0') 218 break; 219 while (*++s && isspace(UChar(*s))) 220 /*EMPTY */ ; 221 buffer = s; 222 } else 223 break; 224 } 225 } 226 return col ? list : 0; 227} 228 229int 230main(int argc, char **argv) 231{ 232 struct name_table_entry *name_table = typeCalloc(struct 233 name_table_entry, CAPTABSIZE); 234 struct name_table_entry **hash_table = typeCalloc(struct name_table_entry 235 *, HASHTABSIZE); 236 const char *root_name = ""; 237 int column = 0; 238 int n; 239 char buffer[BUFSIZ]; 240 241 static const char *typenames[] = 242 {"BOOLEAN", "NUMBER", "STRING"}; 243 244 short BoolCount = 0; 245 short NumCount = 0; 246 short StrCount = 0; 247 248 /* The first argument is the column-number (starting with 0). 249 * The second is the root name of the tables to generate. 250 */ 251 if (argc <= 2 252 || (column = atoi(argv[1])) <= 0 253 || (column >= MAX_COLUMNS) 254 || *(root_name = argv[2]) == 0) { 255 fprintf(stderr, "usage: make_hash column root_name\n"); 256 exit(EXIT_FAILURE); 257 } 258 259 /* 260 * Read the table into our arrays. 261 */ 262 for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) { 263 char **list, *nlp = strchr(buffer, '\n'); 264 if (nlp) 265 *nlp = '\0'; 266 list = parse_columns(buffer); 267 if (list == 0) /* blank or comment */ 268 continue; 269 name_table[n].nte_link = -1; /* end-of-hash */ 270 name_table[n].nte_name = strdup(list[column]); 271 if (!strcmp(list[2], "bool")) { 272 name_table[n].nte_type = BOOLEAN; 273 name_table[n].nte_index = BoolCount++; 274 } else if (!strcmp(list[2], "num")) { 275 name_table[n].nte_type = NUMBER; 276 name_table[n].nte_index = NumCount++; 277 } else if (!strcmp(list[2], "str")) { 278 name_table[n].nte_type = STRING; 279 name_table[n].nte_index = StrCount++; 280 } else { 281 fprintf(stderr, "Unknown type: %s\n", list[2]); 282 exit(EXIT_FAILURE); 283 } 284 n++; 285 } 286 _nc_make_hash_table(name_table, hash_table); 287 288 /* 289 * Write the compiled tables to standard output 290 */ 291 printf("static struct name_table_entry const _nc_%s_table[] =\n", 292 root_name); 293 printf("{\n"); 294 for (n = 0; n < CAPTABSIZE; n++) { 295 sprintf(buffer, "\"%s\"", 296 name_table[n].nte_name); 297 printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n", 298 buffer, 299 typenames[name_table[n].nte_type], 300 name_table[n].nte_index, 301 name_table[n].nte_link, 302 n < CAPTABSIZE - 1 ? ',' : ' '); 303 } 304 printf("};\n\n"); 305 306 printf("const struct name_table_entry * const _nc_%s_hash_table[%d] =\n", 307 root_name, 308 HASHTABSIZE + 1); 309 printf("{\n"); 310 for (n = 0; n < HASHTABSIZE; n++) { 311 if (hash_table[n] != 0) { 312 sprintf(buffer, "_nc_%s_table + %3ld", 313 root_name, 314 (long) (hash_table[n] - name_table)); 315 } else { 316 strcpy(buffer, "0"); 317 } 318 printf("\t%s,\n", buffer); 319 } 320 printf("\t_nc_%s_table\t/* base-of-table */\n", root_name); 321 printf("};\n\n"); 322 323 printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n", 324 BoolCount, NumCount, StrCount); 325 printf("#error\t--> term.h and comp_captab.c disagree about the <--\n"); 326 printf("#error\t--> numbers of booleans, numbers and/or strings <--\n"); 327 printf("#endif\n\n"); 328 329 return EXIT_SUCCESS; 330} 331#endif 332