comp_hash.c revision 166124
150276Speter/**************************************************************************** 2166124Srafan * Copyright (c) 1998-2003,2005 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 53166124SrafanMODULE_ID("$Id: comp_hash.c,v 1.28 2005/08/20 19:58:18 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, 7476726Speter struct name_table_entry **hash_table) 7550276Speter{ 7676726Speter int i; 7776726Speter int hashvalue; 7876726Speter int collisions = 0; 7950276Speter 8076726Speter for (i = 0; i < CAPTABSIZE; i++) { 8176726Speter hashvalue = hash_function(table[i].nte_name); 8250276Speter 8376726Speter if (hash_table[hashvalue] != (struct name_table_entry *) 0) 8476726Speter collisions++; 8550276Speter 8676726Speter if (hash_table[hashvalue] != 0) 8776726Speter table[i].nte_link = (short) (hash_table[hashvalue] - table); 8876726Speter hash_table[hashvalue] = &table[i]; 8976726Speter } 9050276Speter 9176726Speter DEBUG(4, ("Hash table complete: %d collisions out of %d entries", 9276726Speter collisions, CAPTABSIZE)); 9350276Speter} 9450276Speter#endif 9550276Speter 9650276Speter/* 9750276Speter * int hash_function(string) 9850276Speter * 9950276Speter * Computes the hashing function on the given string. 10050276Speter * 10150276Speter * The current hash function is the sum of each consectutive pair 102166124Srafan * of characters, taken as two-byte integers, mod HASHTABSIZE. 10350276Speter * 10450276Speter */ 10550276Speter 106166124Srafanstatic int 10750276Speterhash_function(const char *string) 10850276Speter{ 10976726Speter long sum = 0; 11050276Speter 11176726Speter DEBUG(9, ("hashing %s", string)); 11276726Speter while (*string) { 11376726Speter sum += (long) (*string + (*(string + 1) << 8)); 11476726Speter string++; 11576726Speter } 11650276Speter 11776726Speter DEBUG(9, ("sum is %ld", sum)); 11876726Speter return (int) (sum % HASHTABSIZE); 11950276Speter} 12050276Speter 12150276Speter/* 12250276Speter * struct name_table_entry * 12350276Speter * find_entry(string) 12450276Speter * 12550276Speter * Finds the entry for the given string in the hash table if present. 12650276Speter * Returns a pointer to the entry in the table or 0 if not found. 12750276Speter * 12850276Speter */ 12950276Speter 13050276Speter#ifndef MAIN_PROGRAM 13176726SpeterNCURSES_EXPORT(struct name_table_entry const *) 132166124Srafan_nc_find_entry(const char *string, 133166124Srafan const struct name_table_entry *const *hash_table) 13450276Speter{ 13576726Speter int hashvalue; 13676726Speter struct name_table_entry const *ptr; 13750276Speter 13876726Speter hashvalue = hash_function(string); 13950276Speter 14076726Speter if ((ptr = hash_table[hashvalue]) != 0) { 14176726Speter while (strcmp(ptr->nte_name, string) != 0) { 14276726Speter if (ptr->nte_link < 0) 14376726Speter return 0; 14476726Speter ptr = ptr->nte_link + hash_table[HASHTABSIZE]; 14550276Speter } 14676726Speter } 14750276Speter 14876726Speter return (ptr); 14950276Speter} 15050276Speter 15150276Speter/* 15250276Speter * struct name_table_entry * 15350276Speter * find_type_entry(string, type, table) 15450276Speter * 15550276Speter * Finds the first entry for the given name with the given type in the 15650276Speter * given table if present (as distinct from find_entry, which finds the 15750276Speter * the last entry regardless of type). You can use this if you detect 15850276Speter * a name clash. It's slower, though. Returns a pointer to the entry 15950276Speter * in the table or 0 if not found. 16050276Speter */ 16150276Speter 16276726SpeterNCURSES_EXPORT(struct name_table_entry const *) 163166124Srafan_nc_find_type_entry(const char *string, 164166124Srafan int type, 165166124Srafan const struct name_table_entry *table) 16650276Speter{ 16776726Speter struct name_table_entry const *ptr; 16850276Speter 16976726Speter for (ptr = table; ptr < table + CAPTABSIZE; ptr++) { 17076726Speter if (ptr->nte_type == type && strcmp(string, ptr->nte_name) == 0) 17176726Speter return (ptr); 17276726Speter } 17350276Speter 17476726Speter return ((struct name_table_entry *) NULL); 17550276Speter} 17650276Speter#endif 17750276Speter 17850276Speter#ifdef MAIN_PROGRAM 17950276Speter/* 18050276Speter * This filter reads from standard input a list of tab-delimited columns, 18150276Speter * (e.g., from Caps.filtered) computes the hash-value of a specified column and 18250276Speter * writes the hashed tables to standard output. 18350276Speter * 18450276Speter * By compiling the hash table at build time, we're able to make the entire 18550276Speter * set of terminfo and termcap tables readonly (and also provide some runtime 18650276Speter * performance enhancement). 18750276Speter */ 18850276Speter 18950276Speter#define MAX_COLUMNS BUFSIZ /* this _has_ to be worst-case */ 19050276Speter 19176726Speterstatic char ** 19276726Speterparse_columns(char *buffer) 19350276Speter{ 19476726Speter static char **list; 19550276Speter 19676726Speter int col = 0; 19750276Speter 19876726Speter if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0) 19976726Speter return (0); 20050276Speter 20176726Speter if (*buffer != '#') { 20276726Speter while (*buffer != '\0') { 20376726Speter char *s; 20497049Speter for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++) 20576726Speter /*EMPTY */ ; 20676726Speter if (s != buffer) { 20776726Speter char mark = *s; 20876726Speter *s = '\0'; 20976726Speter if ((s - buffer) > 1 21076726Speter && (*buffer == '"') 21176726Speter && (s[-1] == '"')) { /* strip the quotes */ 21276726Speter buffer++; 21376726Speter s[-1] = '\0'; 21450276Speter } 21576726Speter list[col] = buffer; 21676726Speter col++; 21776726Speter if (mark == '\0') 21876726Speter break; 21997049Speter while (*++s && isspace(UChar(*s))) 22076726Speter /*EMPTY */ ; 22176726Speter buffer = s; 22276726Speter } else 22376726Speter break; 22450276Speter } 22576726Speter } 22676726Speter return col ? list : 0; 22750276Speter} 22850276Speter 22976726Speterint 23076726Spetermain(int argc, char **argv) 23150276Speter{ 23276726Speter struct name_table_entry *name_table = typeCalloc(struct 23376726Speter name_table_entry, CAPTABSIZE); 23476726Speter struct name_table_entry **hash_table = typeCalloc(struct name_table_entry 23576726Speter *, HASHTABSIZE); 23676726Speter const char *root_name = ""; 23776726Speter int column = 0; 23876726Speter int n; 23976726Speter char buffer[BUFSIZ]; 24050276Speter 24176726Speter static const char *typenames[] = 24276726Speter {"BOOLEAN", "NUMBER", "STRING"}; 24350276Speter 24476726Speter short BoolCount = 0; 24576726Speter short NumCount = 0; 24676726Speter short StrCount = 0; 24750276Speter 24876726Speter /* The first argument is the column-number (starting with 0). 24976726Speter * The second is the root name of the tables to generate. 25076726Speter */ 25176726Speter if (argc <= 2 25276726Speter || (column = atoi(argv[1])) <= 0 25376726Speter || (column >= MAX_COLUMNS) 25476726Speter || *(root_name = argv[2]) == 0) { 25576726Speter fprintf(stderr, "usage: make_hash column root_name\n"); 25676726Speter exit(EXIT_FAILURE); 25776726Speter } 25850276Speter 25976726Speter /* 26076726Speter * Read the table into our arrays. 26176726Speter */ 26276726Speter for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) { 26376726Speter char **list, *nlp = strchr(buffer, '\n'); 26476726Speter if (nlp) 26576726Speter *nlp = '\0'; 26676726Speter list = parse_columns(buffer); 26776726Speter if (list == 0) /* blank or comment */ 26876726Speter continue; 26976726Speter name_table[n].nte_link = -1; /* end-of-hash */ 27076726Speter name_table[n].nte_name = strdup(list[column]); 27176726Speter if (!strcmp(list[2], "bool")) { 27276726Speter name_table[n].nte_type = BOOLEAN; 27376726Speter name_table[n].nte_index = BoolCount++; 27476726Speter } else if (!strcmp(list[2], "num")) { 27576726Speter name_table[n].nte_type = NUMBER; 27676726Speter name_table[n].nte_index = NumCount++; 27776726Speter } else if (!strcmp(list[2], "str")) { 27876726Speter name_table[n].nte_type = STRING; 27976726Speter name_table[n].nte_index = StrCount++; 28076726Speter } else { 28176726Speter fprintf(stderr, "Unknown type: %s\n", list[2]); 28276726Speter exit(EXIT_FAILURE); 28350276Speter } 28476726Speter n++; 28576726Speter } 28676726Speter _nc_make_hash_table(name_table, hash_table); 28750276Speter 28876726Speter /* 28976726Speter * Write the compiled tables to standard output 29076726Speter */ 29176726Speter printf("static struct name_table_entry const _nc_%s_table[] =\n", 29276726Speter root_name); 29376726Speter printf("{\n"); 29476726Speter for (n = 0; n < CAPTABSIZE; n++) { 29576726Speter sprintf(buffer, "\"%s\"", 29676726Speter name_table[n].nte_name); 29776726Speter printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n", 29876726Speter buffer, 29976726Speter typenames[name_table[n].nte_type], 30076726Speter name_table[n].nte_index, 30176726Speter name_table[n].nte_link, 30276726Speter n < CAPTABSIZE - 1 ? ',' : ' '); 30376726Speter } 30476726Speter printf("};\n\n"); 30550276Speter 30676726Speter printf("const struct name_table_entry * const _nc_%s_hash_table[%d] =\n", 30776726Speter root_name, 30876726Speter HASHTABSIZE + 1); 30976726Speter printf("{\n"); 31076726Speter for (n = 0; n < HASHTABSIZE; n++) { 31176726Speter if (hash_table[n] != 0) { 31276726Speter sprintf(buffer, "_nc_%s_table + %3ld", 31376726Speter root_name, 31476726Speter (long) (hash_table[n] - name_table)); 31576726Speter } else { 31676726Speter strcpy(buffer, "0"); 31750276Speter } 31876726Speter printf("\t%s,\n", buffer); 31976726Speter } 32076726Speter printf("\t_nc_%s_table\t/* base-of-table */\n", root_name); 32176726Speter printf("};\n\n"); 32250276Speter 32376726Speter printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n", 32476726Speter BoolCount, NumCount, StrCount); 32576726Speter printf("#error\t--> term.h and comp_captab.c disagree about the <--\n"); 32676726Speter printf("#error\t--> numbers of booleans, numbers and/or strings <--\n"); 32776726Speter printf("#endif\n\n"); 32850276Speter 32976726Speter return EXIT_SUCCESS; 33050276Speter} 33150276Speter#endif 332