1 /****************************************************************************
2 * Copyright (c) 1998-2012,2013 Free Software Foundation, Inc. *
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: *
12 * The above copyright notice and this permission notice shall be included *
13 * in all copies or substantial portions of the Software. *
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. *
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 *
27 ****************************************************************************/
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 ****************************************************************************/
36 * make_hash.c --- build-time program for constructing comp_captab.c
40 #include <build.priv.h>
47 MODULE_ID("$Id: make_hash.c,v 1.13 2013/09/28 20:55:47 tom Exp $")
50 * _nc_make_hash_table()
52 * Takes the entries in table[] and hashes them into hash_table[]
53 * by name. There are CAPTABSIZE entries in table[] and HASHTABSIZE
54 * slots in hash_table[].
59 #define MODULE_ID(id) /*nothing */
60 #include <tinfo/doalloc.c>
72 size_t need
= strlen(s
) + 1;
73 char *result
= malloc(need
);
76 _nc_STRCPY(result
, s
, need
);
81 * int hash_function(string)
83 * Computes the hashing function on the given string.
85 * The current hash function is the sum of each consectutive pair
86 * of characters, taken as two-byte integers, mod HASHTABSIZE.
91 hash_function(const char *string
)
96 sum
+= (long) (*string
+ (*(string
+ 1) << 8));
100 return (int) (sum
% HASHTABSIZE
);
104 _nc_make_hash_table(struct name_table_entry
*table
,
105 HashValue
* hash_table
)
111 for (i
= 0; i
< HASHTABSIZE
; i
++) {
114 for (i
= 0; i
< CAPTABSIZE
; i
++) {
115 hashvalue
= hash_function(table
[i
].nte_name
);
117 if (hash_table
[hashvalue
] >= 0)
120 if (hash_table
[hashvalue
] != 0)
121 table
[i
].nte_link
= hash_table
[hashvalue
];
122 hash_table
[hashvalue
] = i
;
125 printf("/* %d collisions out of %d entries */\n", collisions
, CAPTABSIZE
);
129 * This filter reads from standard input a list of tab-delimited columns,
130 * (e.g., from Caps.filtered) computes the hash-value of a specified column and
131 * writes the hashed tables to standard output.
133 * By compiling the hash table at build time, we're able to make the entire
134 * set of terminfo and termcap tables readonly (and also provide some runtime
135 * performance enhancement).
138 #define MAX_COLUMNS BUFSIZ /* this _has_ to be worst-case */
141 count_columns(char **list
)
153 parse_columns(char *buffer
)
159 if (list
== 0 && (list
= typeCalloc(char *, (MAX_COLUMNS
+ 1))) == 0)
162 if (*buffer
!= '#') {
163 while (*buffer
!= '\0') {
165 for (s
= buffer
; (*s
!= '\0') && !isspace(UChar(*s
)); s
++)
172 && (s
[-1] == '"')) { /* strip the quotes */
173 assert(s
> buffer
+ 1);
181 while (*++s
&& isspace(UChar(*s
)))
188 return col
? list
: 0;
192 main(int argc
, char **argv
)
194 struct name_table_entry
*name_table
= typeCalloc(struct
195 name_table_entry
, CAPTABSIZE
);
196 HashValue
*hash_table
= typeCalloc(HashValue
, HASHTABSIZE
);
197 const char *root_name
= "";
203 static const char *typenames
[] =
204 {"BOOLEAN", "NUMBER", "STRING"};
210 /* The first argument is the column-number (starting with 0).
211 * The second is the root name of the tables to generate.
214 || (column
= atoi(argv
[1])) <= 0
215 || (column
>= MAX_COLUMNS
)
216 || *(root_name
= argv
[2]) == 0
217 || (bigstring
= atoi(argv
[3])) < 0
219 || hash_table
== 0) {
220 fprintf(stderr
, "usage: make_hash column root_name bigstring\n");
225 * Read the table into our arrays.
227 for (n
= 0; (n
< CAPTABSIZE
) && fgets(buffer
, BUFSIZ
, stdin
);) {
228 char **list
, *nlp
= strchr(buffer
, '\n');
231 list
= parse_columns(buffer
);
232 if (list
== 0) /* blank or comment */
234 if (column
> count_columns(list
)) {
235 fprintf(stderr
, "expected %d columns, have %d:\n%s\n",
241 name_table
[n
].nte_link
= -1; /* end-of-hash */
242 name_table
[n
].nte_name
= strmalloc(list
[column
]);
243 if (!strcmp(list
[2], "bool")) {
244 name_table
[n
].nte_type
= BOOLEAN
;
245 name_table
[n
].nte_index
= BoolCount
++;
246 } else if (!strcmp(list
[2], "num")) {
247 name_table
[n
].nte_type
= NUMBER
;
248 name_table
[n
].nte_index
= NumCount
++;
249 } else if (!strcmp(list
[2], "str")) {
250 name_table
[n
].nte_type
= STRING
;
251 name_table
[n
].nte_index
= StrCount
++;
253 fprintf(stderr
, "Unknown type: %s\n", list
[2]);
258 _nc_make_hash_table(name_table
, hash_table
);
261 * Write the compiled tables to standard output
267 printf("static const char %s_names_text[] = \\\n", root_name
);
268 for (n
= 0; n
< CAPTABSIZE
; n
++) {
269 nxt
= (int) strlen(name_table
[n
].nte_name
) + 5;
270 if (nxt
+ len
> 72) {
274 printf("\"%s\\0\" ", name_table
[n
].nte_name
);
280 printf("static name_table_data const %s_names_data[] =\n",
283 for (n
= 0; n
< CAPTABSIZE
; n
++) {
284 printf("\t{ %15d,\t%10s,\t%3d, %3d }%c\n",
286 typenames
[name_table
[n
].nte_type
],
287 name_table
[n
].nte_index
,
288 name_table
[n
].nte_link
,
289 n
< CAPTABSIZE
- 1 ? ',' : ' ');
290 len
+= (int) strlen(name_table
[n
].nte_name
) + 1;
293 printf("static struct name_table_entry *_nc_%s_table = 0;\n\n", root_name
);
296 printf("static struct name_table_entry const _nc_%s_table[] =\n",
299 for (n
= 0; n
< CAPTABSIZE
; n
++) {
300 _nc_SPRINTF(buffer
, _nc_SLIMIT(sizeof(buffer
)) "\"%s\"",
301 name_table
[n
].nte_name
);
302 printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n",
304 typenames
[name_table
[n
].nte_type
],
305 name_table
[n
].nte_index
,
306 name_table
[n
].nte_link
,
307 n
< CAPTABSIZE
- 1 ? ',' : ' ');
312 printf("static const HashValue _nc_%s_hash_table[%d] =\n",
316 for (n
= 0; n
< HASHTABSIZE
; n
++) {
317 printf("\t%3d,\n", hash_table
[n
]);
319 printf("\t0\t/* base-of-table */\n");
322 printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n",
323 BoolCount
, NumCount
, StrCount
);
324 printf("#error\t--> term.h and comp_captab.c disagree about the <--\n");
325 printf("#error\t--> numbers of booleans, numbers and/or strings <--\n");
326 printf("#endif\n\n");