11034bfcdelphij/****************************************************************************
201cf73abapt * Copyright 2018-2019,2020 Thomas E. Dickey                                *
301cf73abapt * Copyright 2009-2013,2017 Free Software Foundation, Inc.                  *
41034bfcdelphij *                                                                          *
51034bfcdelphij * Permission is hereby granted, free of charge, to any person obtaining a  *
61034bfcdelphij * copy of this software and associated documentation files (the            *
71034bfcdelphij * "Software"), to deal in the Software without restriction, including      *
81034bfcdelphij * without limitation the rights to use, copy, modify, merge, publish,      *
91034bfcdelphij * distribute, distribute with modifications, sublicense, and/or sell       *
101034bfcdelphij * copies of the Software, and to permit persons to whom the Software is    *
111034bfcdelphij * furnished to do so, subject to the following conditions:                 *
121034bfcdelphij *                                                                          *
131034bfcdelphij * The above copyright notice and this permission notice shall be included  *
141034bfcdelphij * in all copies or substantial portions of the Software.                   *
151034bfcdelphij *                                                                          *
161034bfcdelphij * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
171034bfcdelphij * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
181034bfcdelphij * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
191034bfcdelphij * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
201034bfcdelphij * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
211034bfcdelphij * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
221034bfcdelphij * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
231034bfcdelphij *                                                                          *
241034bfcdelphij * Except as contained in this notice, the name(s) of the above copyright   *
251034bfcdelphij * holders shall not be used in advertising or otherwise to promote the     *
261034bfcdelphij * sale, use or other dealings in this Software without prior written       *
271034bfcdelphij * authorization.                                                           *
281034bfcdelphij ****************************************************************************/
291034bfcdelphij
301034bfcdelphij/****************************************************************************
311034bfcdelphij *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
321034bfcdelphij *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
331034bfcdelphij *     and: Thomas E. Dickey                        1996-on                 *
341034bfcdelphij ****************************************************************************/
351034bfcdelphij
361034bfcdelphij/*
371034bfcdelphij *	make_hash.c --- build-time program for constructing comp_captab.c
381034bfcdelphij */
391034bfcdelphij
401034bfcdelphij#include <build.priv.h>
411034bfcdelphij
421034bfcdelphij#include <tic.h>
431034bfcdelphij#include <hashsize.h>
441034bfcdelphij
451034bfcdelphij#include <ctype.h>
461034bfcdelphij
4701cf73abaptMODULE_ID("$Id: make_hash.c,v 1.33 2020/02/02 23:34:34 tom Exp $")
481034bfcdelphij
491034bfcdelphij/*
501034bfcdelphij *	_nc_make_hash_table()
511034bfcdelphij *
521034bfcdelphij *	Takes the entries in table[] and hashes them into hash_table[]
53f52ca6ebapt *	by name.  There are CAPTABSIZE entries in the predefined table[]
54f52ca6ebapt *	and HASHTABSIZE slots in hash_table[].
551034bfcdelphij *
561034bfcdelphij */
571034bfcdelphij
581034bfcdelphij#undef MODULE_ID
591034bfcdelphij#define MODULE_ID(id)		/*nothing */
601034bfcdelphij#include <tinfo/doalloc.c>
611034bfcdelphij
62f52ca6ebapt#define L_PAREN "("
63f52ca6ebapt#define R_PAREN ")"
64f52ca6ebapt#define L_BRACE "{"
65f52ca6ebapt#define R_BRACE "}"
66f52ca6ebapt
67f52ca6ebaptstatic const char *typenames[] =
68f52ca6ebapt{"BOOLEAN", "NUMBER", "STRING"};
69f52ca6ebapt
707dbeededelphijstatic void
717dbeededelphijfailed(const char *s)
727dbeededelphij{
737dbeededelphij    perror(s);
747dbeededelphij    exit(EXIT_FAILURE);
757dbeededelphij}
767dbeededelphij
777dbeededelphijstatic char *
787dbeededelphijstrmalloc(char *s)
797dbeededelphij{
807dbeededelphij    size_t need = strlen(s) + 1;
817dbeededelphij    char *result = malloc(need);
827dbeededelphij    if (result == 0)
837dbeededelphij	failed("strmalloc");
847dbeededelphij    _nc_STRCPY(result, s, need);
857dbeededelphij    return result;
867dbeededelphij}
877dbeededelphij
881034bfcdelphij/*
891034bfcdelphij *	int hash_function(string)
901034bfcdelphij *
911034bfcdelphij *	Computes the hashing function on the given string.
921034bfcdelphij *
93f52ca6ebapt *	The current hash function is the sum of each consecutive pair
941034bfcdelphij *	of characters, taken as two-byte integers, mod HASHTABSIZE.
951034bfcdelphij *
961034bfcdelphij */
971034bfcdelphij
981034bfcdelphijstatic int
991034bfcdelphijhash_function(const char *string)
1001034bfcdelphij{
1011034bfcdelphij    long sum = 0;
1021034bfcdelphij
1031034bfcdelphij    while (*string) {
10401cf73abapt	sum += (long) (UChar(*string) + (UChar(*(string + 1)) << 8));
1051034bfcdelphij	string++;
1061034bfcdelphij    }
1071034bfcdelphij
1081034bfcdelphij    return (int) (sum % HASHTABSIZE);
1091034bfcdelphij}
1101034bfcdelphij
11101cf73abapt#define UNUSED -1
11201cf73abapt
1131034bfcdelphijstatic void
114f52ca6ebapt_nc_make_hash_table(struct user_table_entry *table,
115f52ca6ebapt		    HashValue * hash_table,
116f52ca6ebapt		    unsigned tablesize)
1171034bfcdelphij{
118f52ca6ebapt    unsigned i;
1191034bfcdelphij    int hashvalue;
1201034bfcdelphij    int collisions = 0;
1211034bfcdelphij
1221034bfcdelphij    for (i = 0; i < HASHTABSIZE; i++) {
12301cf73abapt	hash_table[i] = UNUSED;
1241034bfcdelphij    }
125f52ca6ebapt    for (i = 0; i < tablesize; i++) {
126f52ca6ebapt	hashvalue = hash_function(table[i].ute_name);
1271034bfcdelphij
1281034bfcdelphij	if (hash_table[hashvalue] >= 0)
1291034bfcdelphij	    collisions++;
1301034bfcdelphij
13101cf73abapt	if (hash_table[hashvalue] != UNUSED) {
132f52ca6ebapt	    table[i].ute_link = hash_table[hashvalue];
13301cf73abapt	}
134f52ca6ebapt	hash_table[hashvalue] = (HashValue) i;
1351034bfcdelphij    }
1361034bfcdelphij
137f52ca6ebapt    printf("/* %d collisions out of %d entries */\n", collisions, tablesize);
1381034bfcdelphij}
1391034bfcdelphij
1401034bfcdelphij/*
1411034bfcdelphij * This filter reads from standard input a list of tab-delimited columns,
1421034bfcdelphij * (e.g., from Caps.filtered) computes the hash-value of a specified column and
1431034bfcdelphij * writes the hashed tables to standard output.
1441034bfcdelphij *
1451034bfcdelphij * By compiling the hash table at build time, we're able to make the entire
1461034bfcdelphij * set of terminfo and termcap tables readonly (and also provide some runtime
1471034bfcdelphij * performance enhancement).
1481034bfcdelphij */
1491034bfcdelphij
1501034bfcdelphij#define MAX_COLUMNS BUFSIZ	/* this _has_ to be worst-case */
1511034bfcdelphij
1527dbeededelphijstatic int
1537dbeededelphijcount_columns(char **list)
1547dbeededelphij{
1557dbeededelphij    int result = 0;
1567dbeededelphij    if (list != 0) {
1577dbeededelphij	while (*list++) {
1587dbeededelphij	    ++result;
1597dbeededelphij	}
1607dbeededelphij    }
1617dbeededelphij    return result;
1627dbeededelphij}
1637dbeededelphij
1641034bfcdelphijstatic char **
1651034bfcdelphijparse_columns(char *buffer)
1661034bfcdelphij{
1671034bfcdelphij    static char **list;
1681034bfcdelphij
1691034bfcdelphij    int col = 0;
1701034bfcdelphij
171f52ca6ebapt    if (buffer == 0) {
172f52ca6ebapt	free(list);
173f52ca6ebapt	list = 0;
174f52ca6ebapt	return 0;
175f52ca6ebapt    }
1761034bfcdelphij
1771034bfcdelphij    if (*buffer != '#') {
178f52ca6ebapt	if (list == 0) {
179f52ca6ebapt	    list = typeCalloc(char *, (MAX_COLUMNS + 1));
180f52ca6ebapt	    if (list == 0)
181f52ca6ebapt		return (0);
182f52ca6ebapt	}
1831034bfcdelphij	while (*buffer != '\0') {
1841034bfcdelphij	    char *s;
1851034bfcdelphij	    for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++)
1861034bfcdelphij		/*EMPTY */ ;
1871034bfcdelphij	    if (s != buffer) {
1881034bfcdelphij		char mark = *s;
1891034bfcdelphij		*s = '\0';
1901034bfcdelphij		if ((s - buffer) > 1
1911034bfcdelphij		    && (*buffer == '"')
1921034bfcdelphij		    && (s[-1] == '"')) {	/* strip the quotes */
1931034bfcdelphij		    assert(s > buffer + 1);
1941034bfcdelphij		    s[-1] = '\0';
1951034bfcdelphij		    buffer++;
1961034bfcdelphij		}
1971034bfcdelphij		list[col] = buffer;
1981034bfcdelphij		col++;
1991034bfcdelphij		if (mark == '\0')
2001034bfcdelphij		    break;
2011034bfcdelphij		while (*++s && isspace(UChar(*s)))
2021034bfcdelphij		    /*EMPTY */ ;
2031034bfcdelphij		buffer = s;
2041034bfcdelphij	    } else
2051034bfcdelphij		break;
2061034bfcdelphij	}
2071034bfcdelphij    }
2081034bfcdelphij    return col ? list : 0;
2091034bfcdelphij}
2101034bfcdelphij
211f52ca6ebapt#define SetType(n,t) \
212f52ca6ebapt	if (is_user) \
213f52ca6ebapt	    name_table[n].ute_type |= (int)(1 << (t)); \
214f52ca6ebapt	else \
215f52ca6ebapt	    name_table[n].ute_type = (t)
216f52ca6ebapt
217f52ca6ebapt#define GetType(n) \
218f52ca6ebapt	(is_user \
219f52ca6ebapt	 ? get_type(name_table[n].ute_type) \
220f52ca6ebapt	 : typenames[name_table[n].ute_type])
221f52ca6ebapt
222f52ca6ebaptstatic char *
223f52ca6ebaptget_type(int type_mask)
224f52ca6ebapt{
225f52ca6ebapt    static char result[80];
226f52ca6ebapt    unsigned n;
227f52ca6ebapt    _nc_STRCPY(result, L_PAREN, sizeof(result));
228f52ca6ebapt    for (n = 0; n < 3; ++n) {
229f52ca6ebapt	if ((1 << n) & type_mask) {
230f52ca6ebapt	    size_t want = 5 + strlen(typenames[n]);
231f52ca6ebapt	    if (want > sizeof(result)) {
232f52ca6ebapt		fprintf(stderr, "Buffer is not large enough for %s + %s\n",
233f52ca6ebapt			result, typenames[n]);
234f52ca6ebapt		exit(EXIT_FAILURE);
235f52ca6ebapt	    }
236f52ca6ebapt	    if (result[1])
237f52ca6ebapt		_nc_STRCAT(result, "|", sizeof(result));
238f52ca6ebapt	    _nc_STRCAT(result, "1<<", sizeof(result));
239f52ca6ebapt	    _nc_STRCAT(result, typenames[n], sizeof(result));
240f52ca6ebapt	}
241f52ca6ebapt    }
242f52ca6ebapt    _nc_STRCAT(result, R_PAREN, sizeof(result));
243f52ca6ebapt    return result;
244f52ca6ebapt}
245f52ca6ebapt
2461034bfcdelphijint
2471034bfcdelphijmain(int argc, char **argv)
2481034bfcdelphij{
249f52ca6ebapt    unsigned tablesize = CAPTABSIZE;
250f52ca6ebapt    struct user_table_entry *name_table = typeCalloc(struct
251f52ca6ebapt						     user_table_entry, tablesize);
2521034bfcdelphij    HashValue *hash_table = typeCalloc(HashValue, HASHTABSIZE);
2531034bfcdelphij    const char *root_name = "";
2541034bfcdelphij    int column = 0;
2551034bfcdelphij    int bigstring = 0;
256f52ca6ebapt    unsigned n;
257f52ca6ebapt    unsigned nn;
258f52ca6ebapt    unsigned tableused = 0;
259f52ca6ebapt    bool is_user;
260f52ca6ebapt    const char *table_name;
2611034bfcdelphij    char buffer[BUFSIZ];
2621034bfcdelphij
2631034bfcdelphij    short BoolCount = 0;
2641034bfcdelphij    short NumCount = 0;
2651034bfcdelphij    short StrCount = 0;
2661034bfcdelphij
2671034bfcdelphij    /* The first argument is the column-number (starting with 0).
2681034bfcdelphij     * The second is the root name of the tables to generate.
2691034bfcdelphij     */
2701034bfcdelphij    if (argc <= 3
2711034bfcdelphij	|| (column = atoi(argv[1])) <= 0
2721034bfcdelphij	|| (column >= MAX_COLUMNS)
2731034bfcdelphij	|| *(root_name = argv[2]) == 0
2741034bfcdelphij	|| (bigstring = atoi(argv[3])) < 0
2751034bfcdelphij	|| name_table == 0
2761034bfcdelphij	|| hash_table == 0) {
2771034bfcdelphij	fprintf(stderr, "usage: make_hash column root_name bigstring\n");
2781034bfcdelphij	exit(EXIT_FAILURE);
2791034bfcdelphij    }
280f52ca6ebapt    is_user = (*root_name == 'u');
281f52ca6ebapt    table_name = (is_user ? "user" : "name");
2821034bfcdelphij
2831034bfcdelphij    /*
2841034bfcdelphij     * Read the table into our arrays.
2851034bfcdelphij     */
286f52ca6ebapt    for (n = 0; (n < tablesize) && fgets(buffer, BUFSIZ, stdin);) {
287f52ca6ebapt	char **list;
288f52ca6ebapt	char *nlp = strchr(buffer, '\n');
2891034bfcdelphij	if (nlp)
2901034bfcdelphij	    *nlp = '\0';
291f52ca6ebapt	else
292f52ca6ebapt	    buffer[sizeof(buffer) - 2] = '\0';
2931034bfcdelphij	list = parse_columns(buffer);
2941034bfcdelphij	if (list == 0)		/* blank or comment */
2951034bfcdelphij	    continue;
296f52ca6ebapt	if (is_user) {
297f52ca6ebapt	    if (strcmp(list[0], "userdef"))
298f52ca6ebapt		continue;
299f52ca6ebapt	} else if (!strcmp(list[0], "userdef")) {
300f52ca6ebapt	    continue;
301f52ca6ebapt	}
302f52ca6ebapt	if (column < 0 || column > count_columns(list)) {
3037dbeededelphij	    fprintf(stderr, "expected %d columns, have %d:\n%s\n",
3047dbeededelphij		    column,
3057dbeededelphij		    count_columns(list),
3067dbeededelphij		    buffer);
3077dbeededelphij	    exit(EXIT_FAILURE);
3087dbeededelphij	}
309f52ca6ebapt	nn = tableused;
310f52ca6ebapt	if (is_user) {
311f52ca6ebapt	    unsigned j;
312f52ca6ebapt	    for (j = 0; j < tableused; ++j) {
313f52ca6ebapt		if (!strcmp(list[column], name_table[j].ute_name)) {
314f52ca6ebapt		    nn = j;
315f52ca6ebapt		    break;
316f52ca6ebapt		}
317f52ca6ebapt	    }
318f52ca6ebapt	}
319f52ca6ebapt	if (nn == tableused) {
320f52ca6ebapt	    name_table[nn].ute_link = -1;	/* end-of-hash */
321f52ca6ebapt	    name_table[nn].ute_name = strmalloc(list[column]);
322f52ca6ebapt	    ++tableused;
323f52ca6ebapt	}
324f52ca6ebapt
3251034bfcdelphij	if (!strcmp(list[2], "bool")) {
326f52ca6ebapt	    SetType(nn, BOOLEAN);
327f52ca6ebapt	    name_table[nn].ute_index = BoolCount++;
3281034bfcdelphij	} else if (!strcmp(list[2], "num")) {
329f52ca6ebapt	    SetType(nn, NUMBER);
330f52ca6ebapt	    name_table[nn].ute_index = NumCount++;
3311034bfcdelphij	} else if (!strcmp(list[2], "str")) {
332f52ca6ebapt	    SetType(nn, STRING);
333f52ca6ebapt	    name_table[nn].ute_index = StrCount++;
334f52ca6ebapt	    if (is_user) {
335f52ca6ebapt		if (*list[3] != '-') {
336f52ca6ebapt		    unsigned j;
337f52ca6ebapt		    name_table[nn].ute_argc = (unsigned) strlen(list[3]);
338f52ca6ebapt		    for (j = 0; j < name_table[nn].ute_argc; ++j) {
339f52ca6ebapt			if (list[3][j] == 's') {
340f52ca6ebapt			    name_table[nn].ute_args |= (1U << j);
341f52ca6ebapt			}
342f52ca6ebapt		    }
343f52ca6ebapt		}
344f52ca6ebapt	    }
3451034bfcdelphij	} else {
3461034bfcdelphij	    fprintf(stderr, "Unknown type: %s\n", list[2]);
3471034bfcdelphij	    exit(EXIT_FAILURE);
3481034bfcdelphij	}
3491034bfcdelphij	n++;
3501034bfcdelphij    }
351f52ca6ebapt    if (tablesize > tableused)
352f52ca6ebapt	tablesize = tableused;
353f52ca6ebapt    _nc_make_hash_table(name_table, hash_table, tablesize);
3541034bfcdelphij
3551034bfcdelphij    /*
3561034bfcdelphij     * Write the compiled tables to standard output
3571034bfcdelphij     */
3581034bfcdelphij    if (bigstring) {
3591034bfcdelphij	int len = 0;
3601034bfcdelphij	int nxt;
3611034bfcdelphij
3621034bfcdelphij	printf("static const char %s_names_text[] = \\\n", root_name);
363f52ca6ebapt	for (n = 0; n < tablesize; n++) {
364f52ca6ebapt	    nxt = (int) strlen(name_table[n].ute_name) + 5;
3651034bfcdelphij	    if (nxt + len > 72) {
3661034bfcdelphij		printf("\\\n");
3671034bfcdelphij		len = 0;
3681034bfcdelphij	    }
369f52ca6ebapt	    printf("\"%s\\0\" ", name_table[n].ute_name);
3701034bfcdelphij	    len += nxt;
3711034bfcdelphij	}
3721034bfcdelphij	printf(";\n\n");
3731034bfcdelphij
3741034bfcdelphij	len = 0;
375f52ca6ebapt	printf("static %s_table_data const %s_names_data[] =\n",
376f52ca6ebapt	       table_name,
3771034bfcdelphij	       root_name);
378f52ca6ebapt	printf("%s\n", L_BRACE);
379f52ca6ebapt	for (n = 0; n < tablesize; n++) {
380f52ca6ebapt	    printf("\t%s %15d,\t%10s,", L_BRACE, len, GetType(n));
381f52ca6ebapt	    if (is_user)
382f52ca6ebapt		printf("\t%d,%d,",
383f52ca6ebapt		       name_table[n].ute_argc,
384f52ca6ebapt		       name_table[n].ute_args);
385f52ca6ebapt	    printf("\t%3d, %3d %s%c\n",
386f52ca6ebapt		   name_table[n].ute_index,
387f52ca6ebapt		   name_table[n].ute_link,
388f52ca6ebapt		   R_BRACE,
389f52ca6ebapt		   n < tablesize - 1 ? ',' : ' ');
390f52ca6ebapt	    len += (int) strlen(name_table[n].ute_name) + 1;
3911034bfcdelphij	}
392f52ca6ebapt	printf("%s;\n\n", R_BRACE);
393f52ca6ebapt	printf("static struct %s_table_entry *_nc_%s_table = 0;\n\n",
394f52ca6ebapt	       table_name,
395f52ca6ebapt	       root_name);
3961034bfcdelphij    } else {
3971034bfcdelphij
398f52ca6ebapt	printf("static struct %s_table_entry const _nc_%s_table[] =\n",
399f52ca6ebapt	       table_name,
4001034bfcdelphij	       root_name);
401f52ca6ebapt	printf("%s\n", L_BRACE);
402f52ca6ebapt	for (n = 0; n < tablesize; n++) {
4037dbeededelphij	    _nc_SPRINTF(buffer, _nc_SLIMIT(sizeof(buffer)) "\"%s\"",
404f52ca6ebapt			name_table[n].ute_name);
405f52ca6ebapt	    printf("\t%s %15s,\t%10s,", L_BRACE, buffer, GetType(n));
406f52ca6ebapt	    if (is_user)
407f52ca6ebapt		printf("\t%d,%d,",
408f52ca6ebapt		       name_table[n].ute_argc,
409f52ca6ebapt		       name_table[n].ute_args);
410f52ca6ebapt	    printf("\t%3d, %3d %s%c\n",
411f52ca6ebapt		   name_table[n].ute_index,
412f52ca6ebapt		   name_table[n].ute_link,
413f52ca6ebapt		   R_BRACE,
414f52ca6ebapt		   n < tablesize - 1 ? ',' : ' ');
4151034bfcdelphij	}
416f52ca6ebapt	printf("%s;\n\n", R_BRACE);
4171034bfcdelphij    }
4181034bfcdelphij
4191034bfcdelphij    printf("static const HashValue _nc_%s_hash_table[%d] =\n",
4201034bfcdelphij	   root_name,
4211034bfcdelphij	   HASHTABSIZE + 1);
422f52ca6ebapt    printf("%s\n", L_BRACE);
4231034bfcdelphij    for (n = 0; n < HASHTABSIZE; n++) {
4241034bfcdelphij	printf("\t%3d,\n", hash_table[n]);
4251034bfcdelphij    }
4261034bfcdelphij    printf("\t0\t/* base-of-table */\n");
427f52ca6ebapt    printf("%s;\n\n", R_BRACE);
428f52ca6ebapt
429f52ca6ebapt    if (!is_user) {
430f52ca6ebapt	printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n",
431f52ca6ebapt	       BoolCount, NumCount, StrCount);
432f52ca6ebapt	printf("#error\t--> term.h and comp_captab.c disagree about the <--\n");
433f52ca6ebapt	printf("#error\t--> numbers of booleans, numbers and/or strings <--\n");
434f52ca6ebapt	printf("#endif\n\n");
435f52ca6ebapt    }
4361034bfcdelphij
4371034bfcdelphij    free(hash_table);
438f52ca6ebapt    for (n = 0; (n < tablesize); ++n) {
439f52ca6ebapt	free((void *) name_table[n].ute_name);
440f52ca6ebapt    }
441f52ca6ebapt    free(name_table);
442f52ca6ebapt    parse_columns(0);
443f52ca6ebapt
4441034bfcdelphij    return EXIT_SUCCESS;
4451034bfcdelphij}
446