150276Speter/**************************************************************************** 2184989Srafan * Copyright (c) 1998-2007,2008 Free Software Foundation, Inc. * 350276Speter * * 450276Speter * Permission is hereby granted, free of charge, to any person obtaining a * 550276Speter * copy of this software and associated documentation files (the * 650276Speter * "Software"), to deal in the Software without restriction, including * 750276Speter * without limitation the rights to use, copy, modify, merge, publish, * 850276Speter * distribute, distribute with modifications, sublicense, and/or sell * 950276Speter * copies of the Software, and to permit persons to whom the Software is * 1050276Speter * furnished to do so, subject to the following conditions: * 1150276Speter * * 1250276Speter * The above copyright notice and this permission notice shall be included * 1350276Speter * in all copies or substantial portions of the Software. * 1450276Speter * * 1550276Speter * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 1650276Speter * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 1750276Speter * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 1850276Speter * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 1950276Speter * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 2050276Speter * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 2150276Speter * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 2250276Speter * * 2350276Speter * Except as contained in this notice, the name(s) of the above copyright * 2450276Speter * holders shall not be used in advertising or otherwise to promote the * 2550276Speter * sale, use or other dealings in this Software without prior written * 2650276Speter * authorization. * 2750276Speter ****************************************************************************/ 2850276Speter 2950276Speter/**************************************************************************** 3050276Speter * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 3150276Speter * and: Eric S. Raymond <esr@snark.thyrsus.com> * 32166124Srafan * and: Thomas E. Dickey 1996-on * 3350276Speter ****************************************************************************/ 3450276Speter 3550276Speter/* 3650276Speter * comp_hash.c --- Routines to deal with the hashtable of capability 3750276Speter * names. 3850276Speter * 3950276Speter */ 4050276Speter 41166124Srafan#define USE_TERMLIB 1 4250276Speter#include <curses.priv.h> 4350276Speter 4450276Speter#include <tic.h> 4550276Speter#include <hashsize.h> 4650276Speter 4750276Speter#ifdef MAIN_PROGRAM 4850276Speter#include <ctype.h> 4950276Speter#undef DEBUG 5076726Speter#define DEBUG(level, params) /*nothing */ 5150276Speter#endif 5250276Speter 53184989SrafanMODULE_ID("$Id: comp_hash.c,v 1.36 2008/08/16 17:06:53 tom Exp $") 5450276Speter 5576726Speterstatic int hash_function(const char *); 5650276Speter 5750276Speter/* 5850276Speter * _nc_make_hash_table() 5950276Speter * 6050276Speter * Takes the entries in table[] and hashes them into hash_table[] 6150276Speter * by name. There are CAPTABSIZE entries in table[] and HASHTABSIZE 6250276Speter * slots in hash_table[]. 6350276Speter * 6450276Speter */ 6550276Speter 6650276Speter#ifdef MAIN_PROGRAM 6750276Speter 6850276Speter#undef MODULE_ID 6976726Speter#define MODULE_ID(id) /*nothing */ 7050276Speter#include <tinfo/doalloc.c> 7150276Speter 7276726Speterstatic void 7376726Speter_nc_make_hash_table(struct name_table_entry *table, 74174993Srafan short *hash_table) 7550276Speter{ 76184989Srafan short i; 7776726Speter int hashvalue; 7876726Speter int collisions = 0; 7950276Speter 80174993Srafan for (i = 0; i < HASHTABSIZE; i++) { 81174993Srafan hash_table[i] = -1; 82174993Srafan } 8376726Speter for (i = 0; i < CAPTABSIZE; i++) { 8476726Speter hashvalue = hash_function(table[i].nte_name); 8550276Speter 86174993Srafan if (hash_table[hashvalue] >= 0) 8776726Speter collisions++; 8850276Speter 8976726Speter if (hash_table[hashvalue] != 0) 90174993Srafan table[i].nte_link = hash_table[hashvalue]; 91174993Srafan hash_table[hashvalue] = i; 9276726Speter } 9350276Speter 9476726Speter DEBUG(4, ("Hash table complete: %d collisions out of %d entries", 9576726Speter collisions, CAPTABSIZE)); 9650276Speter} 9750276Speter#endif 9850276Speter 9950276Speter/* 10050276Speter * int hash_function(string) 10150276Speter * 10250276Speter * Computes the hashing function on the given string. 10350276Speter * 10450276Speter * The current hash function is the sum of each consectutive pair 105166124Srafan * of characters, taken as two-byte integers, mod HASHTABSIZE. 10650276Speter * 10750276Speter */ 10850276Speter 109166124Srafanstatic int 11050276Speterhash_function(const char *string) 11150276Speter{ 11276726Speter long sum = 0; 11350276Speter 11476726Speter DEBUG(9, ("hashing %s", string)); 11576726Speter while (*string) { 11676726Speter sum += (long) (*string + (*(string + 1) << 8)); 11776726Speter string++; 11876726Speter } 11950276Speter 12076726Speter DEBUG(9, ("sum is %ld", sum)); 12176726Speter return (int) (sum % HASHTABSIZE); 12250276Speter} 12350276Speter 12450276Speter/* 12550276Speter * struct name_table_entry * 12650276Speter * find_entry(string) 12750276Speter * 12850276Speter * Finds the entry for the given string in the hash table if present. 12950276Speter * Returns a pointer to the entry in the table or 0 if not found. 13050276Speter * 13150276Speter */ 13250276Speter 13350276Speter#ifndef MAIN_PROGRAM 13476726SpeterNCURSES_EXPORT(struct name_table_entry const *) 135166124Srafan_nc_find_entry(const char *string, 136174993Srafan const short *hash_table) 13750276Speter{ 13876726Speter int hashvalue; 139174993Srafan struct name_table_entry const *ptr = 0; 140174993Srafan struct name_table_entry const *real_table; 14150276Speter 14276726Speter hashvalue = hash_function(string); 14350276Speter 144174993Srafan if (hash_table[hashvalue] >= 0) { 145174993Srafan real_table = _nc_get_table(hash_table != _nc_get_hash_table(FALSE)); 146174993Srafan ptr = real_table + hash_table[hashvalue]; 14776726Speter while (strcmp(ptr->nte_name, string) != 0) { 14876726Speter if (ptr->nte_link < 0) 14976726Speter return 0; 150174993Srafan ptr = real_table + (ptr->nte_link + hash_table[HASHTABSIZE]); 15150276Speter } 15276726Speter } 15350276Speter 15476726Speter return (ptr); 15550276Speter} 15650276Speter 15750276Speter/* 15850276Speter * struct name_table_entry * 15950276Speter * find_type_entry(string, type, table) 16050276Speter * 16150276Speter * Finds the first entry for the given name with the given type in the 16250276Speter * given table if present (as distinct from find_entry, which finds the 16350276Speter * the last entry regardless of type). You can use this if you detect 16450276Speter * a name clash. It's slower, though. Returns a pointer to the entry 16550276Speter * in the table or 0 if not found. 16650276Speter */ 16750276Speter 16876726SpeterNCURSES_EXPORT(struct name_table_entry const *) 169166124Srafan_nc_find_type_entry(const char *string, 170166124Srafan int type, 171166124Srafan const struct name_table_entry *table) 17250276Speter{ 17376726Speter struct name_table_entry const *ptr; 17450276Speter 17576726Speter for (ptr = table; ptr < table + CAPTABSIZE; ptr++) { 17676726Speter if (ptr->nte_type == type && strcmp(string, ptr->nte_name) == 0) 17776726Speter return (ptr); 17876726Speter } 17950276Speter 18076726Speter return ((struct name_table_entry *) NULL); 18150276Speter} 18250276Speter#endif 18350276Speter 18450276Speter#ifdef MAIN_PROGRAM 18550276Speter/* 18650276Speter * This filter reads from standard input a list of tab-delimited columns, 18750276Speter * (e.g., from Caps.filtered) computes the hash-value of a specified column and 18850276Speter * writes the hashed tables to standard output. 18950276Speter * 19050276Speter * By compiling the hash table at build time, we're able to make the entire 19150276Speter * set of terminfo and termcap tables readonly (and also provide some runtime 19250276Speter * performance enhancement). 19350276Speter */ 19450276Speter 19550276Speter#define MAX_COLUMNS BUFSIZ /* this _has_ to be worst-case */ 19650276Speter 19776726Speterstatic char ** 19876726Speterparse_columns(char *buffer) 19950276Speter{ 20076726Speter static char **list; 20150276Speter 20276726Speter int col = 0; 20350276Speter 20476726Speter if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0) 20576726Speter return (0); 20650276Speter 20776726Speter if (*buffer != '#') { 20876726Speter while (*buffer != '\0') { 20976726Speter char *s; 21097049Speter for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++) 21176726Speter /*EMPTY */ ; 21276726Speter if (s != buffer) { 21376726Speter char mark = *s; 21476726Speter *s = '\0'; 21576726Speter if ((s - buffer) > 1 21676726Speter && (*buffer == '"') 21776726Speter && (s[-1] == '"')) { /* strip the quotes */ 218184989Srafan assert(s > buffer + 1); 219184989Srafan s[-1] = '\0'; 22076726Speter buffer++; 22150276Speter } 22276726Speter list[col] = buffer; 22376726Speter col++; 22476726Speter if (mark == '\0') 22576726Speter break; 22697049Speter while (*++s && isspace(UChar(*s))) 22776726Speter /*EMPTY */ ; 22876726Speter buffer = s; 22976726Speter } else 23076726Speter break; 23150276Speter } 23276726Speter } 23376726Speter return col ? list : 0; 23450276Speter} 23550276Speter 23676726Speterint 23776726Spetermain(int argc, char **argv) 23850276Speter{ 23976726Speter struct name_table_entry *name_table = typeCalloc(struct 24076726Speter name_table_entry, CAPTABSIZE); 241174993Srafan short *hash_table = typeCalloc(short, HASHTABSIZE); 24276726Speter const char *root_name = ""; 24376726Speter int column = 0; 244174993Srafan int bigstring = 0; 24576726Speter int n; 24676726Speter char buffer[BUFSIZ]; 24750276Speter 24876726Speter static const char *typenames[] = 24976726Speter {"BOOLEAN", "NUMBER", "STRING"}; 25050276Speter 25176726Speter short BoolCount = 0; 25276726Speter short NumCount = 0; 25376726Speter short StrCount = 0; 25450276Speter 25576726Speter /* The first argument is the column-number (starting with 0). 25676726Speter * The second is the root name of the tables to generate. 25776726Speter */ 258174993Srafan if (argc <= 3 25976726Speter || (column = atoi(argv[1])) <= 0 26076726Speter || (column >= MAX_COLUMNS) 261174993Srafan || *(root_name = argv[2]) == 0 262184989Srafan || (bigstring = atoi(argv[3])) < 0 263184989Srafan || name_table == 0 264184989Srafan || hash_table == 0) { 265174993Srafan fprintf(stderr, "usage: make_hash column root_name bigstring\n"); 26676726Speter exit(EXIT_FAILURE); 26776726Speter } 26850276Speter 26976726Speter /* 27076726Speter * Read the table into our arrays. 27176726Speter */ 27276726Speter for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) { 27376726Speter char **list, *nlp = strchr(buffer, '\n'); 27476726Speter if (nlp) 27576726Speter *nlp = '\0'; 27676726Speter list = parse_columns(buffer); 27776726Speter if (list == 0) /* blank or comment */ 27876726Speter continue; 27976726Speter name_table[n].nte_link = -1; /* end-of-hash */ 28076726Speter name_table[n].nte_name = strdup(list[column]); 28176726Speter if (!strcmp(list[2], "bool")) { 28276726Speter name_table[n].nte_type = BOOLEAN; 28376726Speter name_table[n].nte_index = BoolCount++; 28476726Speter } else if (!strcmp(list[2], "num")) { 28576726Speter name_table[n].nte_type = NUMBER; 28676726Speter name_table[n].nte_index = NumCount++; 28776726Speter } else if (!strcmp(list[2], "str")) { 28876726Speter name_table[n].nte_type = STRING; 28976726Speter name_table[n].nte_index = StrCount++; 29076726Speter } else { 29176726Speter fprintf(stderr, "Unknown type: %s\n", list[2]); 29276726Speter exit(EXIT_FAILURE); 29350276Speter } 29476726Speter n++; 29576726Speter } 29676726Speter _nc_make_hash_table(name_table, hash_table); 29750276Speter 29876726Speter /* 29976726Speter * Write the compiled tables to standard output 30076726Speter */ 301174993Srafan if (bigstring) { 302174993Srafan int len = 0; 303174993Srafan int nxt; 304174993Srafan 305174993Srafan printf("static const char %s_names_text[] = \\\n", root_name); 306174993Srafan for (n = 0; n < CAPTABSIZE; n++) { 307184989Srafan nxt = (int) strlen(name_table[n].nte_name) + 5; 308174993Srafan if (nxt + len > 72) { 309174993Srafan printf("\\\n"); 310174993Srafan len = 0; 311174993Srafan } 312174993Srafan printf("\"%s\\0\" ", name_table[n].nte_name); 313174993Srafan len += nxt; 314174993Srafan } 315174993Srafan printf(";\n\n"); 316174993Srafan 317174993Srafan len = 0; 318174993Srafan printf("static name_table_data const %s_names_data[] =\n", 319174993Srafan root_name); 320174993Srafan printf("{\n"); 321174993Srafan for (n = 0; n < CAPTABSIZE; n++) { 322174993Srafan printf("\t{ %15d,\t%10s,\t%3d, %3d }%c\n", 323174993Srafan len, 324174993Srafan typenames[name_table[n].nte_type], 325174993Srafan name_table[n].nte_index, 326174993Srafan name_table[n].nte_link, 327174993Srafan n < CAPTABSIZE - 1 ? ',' : ' '); 328184989Srafan len += (int) strlen(name_table[n].nte_name) + 1; 329174993Srafan } 330174993Srafan printf("};\n\n"); 331174993Srafan printf("static struct name_table_entry *_nc_%s_table = 0;\n\n", root_name); 332174993Srafan } else { 333174993Srafan 334174993Srafan printf("static struct name_table_entry %s _nc_%s_table[] =\n", 335174993Srafan bigstring ? "" : "const", 336174993Srafan root_name); 337174993Srafan printf("{\n"); 338174993Srafan for (n = 0; n < CAPTABSIZE; n++) { 339174993Srafan sprintf(buffer, "\"%s\"", 340174993Srafan name_table[n].nte_name); 341174993Srafan printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n", 342174993Srafan buffer, 343174993Srafan typenames[name_table[n].nte_type], 344174993Srafan name_table[n].nte_index, 345174993Srafan name_table[n].nte_link, 346174993Srafan n < CAPTABSIZE - 1 ? ',' : ' '); 347174993Srafan } 348174993Srafan printf("};\n\n"); 34976726Speter } 35050276Speter 351174993Srafan printf("static const short _nc_%s_hash_table[%d] =\n", 35276726Speter root_name, 35376726Speter HASHTABSIZE + 1); 35476726Speter printf("{\n"); 35576726Speter for (n = 0; n < HASHTABSIZE; n++) { 356174993Srafan printf("\t%3d,\n", hash_table[n]); 35776726Speter } 358174993Srafan printf("\t0\t/* base-of-table */\n"); 35976726Speter printf("};\n\n"); 36050276Speter 36176726Speter printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n", 36276726Speter BoolCount, NumCount, StrCount); 36376726Speter printf("#error\t--> term.h and comp_captab.c disagree about the <--\n"); 36476726Speter printf("#error\t--> numbers of booleans, numbers and/or strings <--\n"); 36576726Speter printf("#endif\n\n"); 36650276Speter 367184989Srafan free(hash_table); 36876726Speter return EXIT_SUCCESS; 36950276Speter} 37050276Speter#endif 371