Amit Daniel Kachhap | e6a01f5 | 2011-07-20 11:45:59 +0530 | [diff] [blame] | 1 | /**************************************************************************** |
| 2 | * Copyright (c) 1998-2007,2008 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 | |
| 53 | MODULE_ID("$Id: comp_hash.c,v 1.36 2008/08/16 17:06:53 tom Exp $") |
| 54 | |
| 55 | static 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 | |
| 72 | static void |
| 73 | _nc_make_hash_table(struct name_table_entry *table, |
| 74 | short *hash_table) |
| 75 | { |
| 76 | short i; |
| 77 | int hashvalue; |
| 78 | int collisions = 0; |
| 79 | |
| 80 | for (i = 0; i < HASHTABSIZE; i++) { |
| 81 | hash_table[i] = -1; |
| 82 | } |
| 83 | for (i = 0; i < CAPTABSIZE; i++) { |
| 84 | hashvalue = hash_function(table[i].nte_name); |
| 85 | |
| 86 | if (hash_table[hashvalue] >= 0) |
| 87 | collisions++; |
| 88 | |
| 89 | if (hash_table[hashvalue] != 0) |
| 90 | table[i].nte_link = hash_table[hashvalue]; |
| 91 | hash_table[hashvalue] = i; |
| 92 | } |
| 93 | |
| 94 | DEBUG(4, ("Hash table complete: %d collisions out of %d entries", |
| 95 | collisions, CAPTABSIZE)); |
| 96 | } |
| 97 | #endif |
| 98 | |
| 99 | /* |
| 100 | * int hash_function(string) |
| 101 | * |
| 102 | * Computes the hashing function on the given string. |
| 103 | * |
| 104 | * The current hash function is the sum of each consectutive pair |
| 105 | * of characters, taken as two-byte integers, mod HASHTABSIZE. |
| 106 | * |
| 107 | */ |
| 108 | |
| 109 | static int |
| 110 | hash_function(const char *string) |
| 111 | { |
| 112 | long sum = 0; |
| 113 | |
| 114 | DEBUG(9, ("hashing %s", string)); |
| 115 | while (*string) { |
| 116 | sum += (long) (*string + (*(string + 1) << 8)); |
| 117 | string++; |
| 118 | } |
| 119 | |
| 120 | DEBUG(9, ("sum is %ld", sum)); |
| 121 | return (int) (sum % HASHTABSIZE); |
| 122 | } |
| 123 | |
| 124 | /* |
| 125 | * struct name_table_entry * |
| 126 | * find_entry(string) |
| 127 | * |
| 128 | * Finds the entry for the given string in the hash table if present. |
| 129 | * Returns a pointer to the entry in the table or 0 if not found. |
| 130 | * |
| 131 | */ |
| 132 | |
| 133 | #ifndef MAIN_PROGRAM |
| 134 | NCURSES_EXPORT(struct name_table_entry const *) |
| 135 | _nc_find_entry(const char *string, |
| 136 | const short *hash_table) |
| 137 | { |
| 138 | int hashvalue; |
| 139 | struct name_table_entry const *ptr = 0; |
| 140 | struct name_table_entry const *real_table; |
| 141 | |
| 142 | hashvalue = hash_function(string); |
| 143 | |
| 144 | if (hash_table[hashvalue] >= 0) { |
| 145 | real_table = _nc_get_table(hash_table != _nc_get_hash_table(FALSE)); |
| 146 | ptr = real_table + hash_table[hashvalue]; |
| 147 | while (strcmp(ptr->nte_name, string) != 0) { |
| 148 | if (ptr->nte_link < 0) |
| 149 | return 0; |
| 150 | ptr = real_table + (ptr->nte_link + hash_table[HASHTABSIZE]); |
| 151 | } |
| 152 | } |
| 153 | |
| 154 | return (ptr); |
| 155 | } |
| 156 | |
| 157 | /* |
| 158 | * struct name_table_entry * |
| 159 | * find_type_entry(string, type, table) |
| 160 | * |
| 161 | * Finds the first entry for the given name with the given type in the |
| 162 | * given table if present (as distinct from find_entry, which finds the |
| 163 | * the last entry regardless of type). You can use this if you detect |
| 164 | * a name clash. It's slower, though. Returns a pointer to the entry |
| 165 | * in the table or 0 if not found. |
| 166 | */ |
| 167 | |
| 168 | NCURSES_EXPORT(struct name_table_entry const *) |
| 169 | _nc_find_type_entry(const char *string, |
| 170 | int type, |
| 171 | const struct name_table_entry *table) |
| 172 | { |
| 173 | struct name_table_entry const *ptr; |
| 174 | |
| 175 | for (ptr = table; ptr < table + CAPTABSIZE; ptr++) { |
| 176 | if (ptr->nte_type == type && strcmp(string, ptr->nte_name) == 0) |
| 177 | return (ptr); |
| 178 | } |
| 179 | |
| 180 | return ((struct name_table_entry *) NULL); |
| 181 | } |
| 182 | #endif |
| 183 | |
| 184 | #ifdef MAIN_PROGRAM |
| 185 | /* |
| 186 | * This filter reads from standard input a list of tab-delimited columns, |
| 187 | * (e.g., from Caps.filtered) computes the hash-value of a specified column and |
| 188 | * writes the hashed tables to standard output. |
| 189 | * |
| 190 | * By compiling the hash table at build time, we're able to make the entire |
| 191 | * set of terminfo and termcap tables readonly (and also provide some runtime |
| 192 | * performance enhancement). |
| 193 | */ |
| 194 | |
| 195 | #define MAX_COLUMNS BUFSIZ /* this _has_ to be worst-case */ |
| 196 | |
| 197 | static char ** |
| 198 | parse_columns(char *buffer) |
| 199 | { |
| 200 | static char **list; |
| 201 | |
| 202 | int col = 0; |
| 203 | |
| 204 | if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0) |
| 205 | return (0); |
| 206 | |
| 207 | if (*buffer != '#') { |
| 208 | while (*buffer != '\0') { |
| 209 | char *s; |
| 210 | for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++) |
| 211 | /*EMPTY */ ; |
| 212 | if (s != buffer) { |
| 213 | char mark = *s; |
| 214 | *s = '\0'; |
| 215 | if ((s - buffer) > 1 |
| 216 | && (*buffer == '"') |
| 217 | && (s[-1] == '"')) { /* strip the quotes */ |
| 218 | assert(s > buffer + 1); |
| 219 | s[-1] = '\0'; |
| 220 | buffer++; |
| 221 | } |
| 222 | list[col] = buffer; |
| 223 | col++; |
| 224 | if (mark == '\0') |
| 225 | break; |
| 226 | while (*++s && isspace(UChar(*s))) |
| 227 | /*EMPTY */ ; |
| 228 | buffer = s; |
| 229 | } else |
| 230 | break; |
| 231 | } |
| 232 | } |
| 233 | return col ? list : 0; |
| 234 | } |
| 235 | |
| 236 | int |
| 237 | main(int argc, char **argv) |
| 238 | { |
| 239 | struct name_table_entry *name_table = typeCalloc(struct |
| 240 | name_table_entry, CAPTABSIZE); |
| 241 | short *hash_table = typeCalloc(short, HASHTABSIZE); |
| 242 | const char *root_name = ""; |
| 243 | int column = 0; |
| 244 | int bigstring = 0; |
| 245 | int n; |
| 246 | char buffer[BUFSIZ]; |
| 247 | |
| 248 | static const char *typenames[] = |
| 249 | {"BOOLEAN", "NUMBER", "STRING"}; |
| 250 | |
| 251 | short BoolCount = 0; |
| 252 | short NumCount = 0; |
| 253 | short StrCount = 0; |
| 254 | |
| 255 | /* The first argument is the column-number (starting with 0). |
| 256 | * The second is the root name of the tables to generate. |
| 257 | */ |
| 258 | if (argc <= 3 |
| 259 | || (column = atoi(argv[1])) <= 0 |
| 260 | || (column >= MAX_COLUMNS) |
| 261 | || *(root_name = argv[2]) == 0 |
| 262 | || (bigstring = atoi(argv[3])) < 0 |
| 263 | || name_table == 0 |
| 264 | || hash_table == 0) { |
| 265 | fprintf(stderr, "usage: make_hash column root_name bigstring\n"); |
| 266 | exit(EXIT_FAILURE); |
| 267 | } |
| 268 | |
| 269 | /* |
| 270 | * Read the table into our arrays. |
| 271 | */ |
| 272 | for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) { |
| 273 | char **list, *nlp = strchr(buffer, '\n'); |
| 274 | if (nlp) |
| 275 | *nlp = '\0'; |
| 276 | list = parse_columns(buffer); |
| 277 | if (list == 0) /* blank or comment */ |
| 278 | continue; |
| 279 | name_table[n].nte_link = -1; /* end-of-hash */ |
| 280 | name_table[n].nte_name = strdup(list[column]); |
| 281 | if (!strcmp(list[2], "bool")) { |
| 282 | name_table[n].nte_type = BOOLEAN; |
| 283 | name_table[n].nte_index = BoolCount++; |
| 284 | } else if (!strcmp(list[2], "num")) { |
| 285 | name_table[n].nte_type = NUMBER; |
| 286 | name_table[n].nte_index = NumCount++; |
| 287 | } else if (!strcmp(list[2], "str")) { |
| 288 | name_table[n].nte_type = STRING; |
| 289 | name_table[n].nte_index = StrCount++; |
| 290 | } else { |
| 291 | fprintf(stderr, "Unknown type: %s\n", list[2]); |
| 292 | exit(EXIT_FAILURE); |
| 293 | } |
| 294 | n++; |
| 295 | } |
| 296 | _nc_make_hash_table(name_table, hash_table); |
| 297 | |
| 298 | /* |
| 299 | * Write the compiled tables to standard output |
| 300 | */ |
| 301 | if (bigstring) { |
| 302 | int len = 0; |
| 303 | int nxt; |
| 304 | |
| 305 | printf("static const char %s_names_text[] = \\\n", root_name); |
| 306 | for (n = 0; n < CAPTABSIZE; n++) { |
| 307 | nxt = (int) strlen(name_table[n].nte_name) + 5; |
| 308 | if (nxt + len > 72) { |
| 309 | printf("\\\n"); |
| 310 | len = 0; |
| 311 | } |
| 312 | printf("\"%s\\0\" ", name_table[n].nte_name); |
| 313 | len += nxt; |
| 314 | } |
| 315 | printf(";\n\n"); |
| 316 | |
| 317 | len = 0; |
| 318 | printf("static name_table_data const %s_names_data[] =\n", |
| 319 | root_name); |
| 320 | printf("{\n"); |
| 321 | for (n = 0; n < CAPTABSIZE; n++) { |
| 322 | printf("\t{ %15d,\t%10s,\t%3d, %3d }%c\n", |
| 323 | len, |
| 324 | typenames[name_table[n].nte_type], |
| 325 | name_table[n].nte_index, |
| 326 | name_table[n].nte_link, |
| 327 | n < CAPTABSIZE - 1 ? ',' : ' '); |
| 328 | len += (int) strlen(name_table[n].nte_name) + 1; |
| 329 | } |
| 330 | printf("};\n\n"); |
| 331 | printf("static struct name_table_entry *_nc_%s_table = 0;\n\n", root_name); |
| 332 | } else { |
| 333 | |
| 334 | printf("static struct name_table_entry %s _nc_%s_table[] =\n", |
| 335 | bigstring ? "" : "const", |
| 336 | root_name); |
| 337 | printf("{\n"); |
| 338 | for (n = 0; n < CAPTABSIZE; n++) { |
| 339 | sprintf(buffer, "\"%s\"", |
| 340 | name_table[n].nte_name); |
| 341 | printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n", |
| 342 | buffer, |
| 343 | typenames[name_table[n].nte_type], |
| 344 | name_table[n].nte_index, |
| 345 | name_table[n].nte_link, |
| 346 | n < CAPTABSIZE - 1 ? ',' : ' '); |
| 347 | } |
| 348 | printf("};\n\n"); |
| 349 | } |
| 350 | |
| 351 | printf("static const short _nc_%s_hash_table[%d] =\n", |
| 352 | root_name, |
| 353 | HASHTABSIZE + 1); |
| 354 | printf("{\n"); |
| 355 | for (n = 0; n < HASHTABSIZE; n++) { |
| 356 | printf("\t%3d,\n", hash_table[n]); |
| 357 | } |
| 358 | printf("\t0\t/* base-of-table */\n"); |
| 359 | printf("};\n\n"); |
| 360 | |
| 361 | printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n", |
| 362 | BoolCount, NumCount, StrCount); |
| 363 | printf("#error\t--> term.h and comp_captab.c disagree about the <--\n"); |
| 364 | printf("#error\t--> numbers of booleans, numbers and/or strings <--\n"); |
| 365 | printf("#endif\n\n"); |
| 366 | |
| 367 | free(hash_table); |
| 368 | return EXIT_SUCCESS; |
| 369 | } |
| 370 | #endif |