trunk/js/jskwgen.cpp

/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set sw=4 ts=8 et tw=80:
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is String Switch Generator for JavaScript Keywords,
 * released 2005-12-09.
 *
 * The Initial Developer of the Original Code is
 * Igor Bukanov.
 * Portions created by the Initial Developer are Copyright (C) 2005-2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

#include "jsstddef.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <ctype.h>

#include "jsversion.h"

const char * const keyword_list[] = {
#define JS_KEYWORD(keyword, type, op, version) #keyword,
#include "jskeyword.tbl"
#undef JS_KEYWORD
};

struct gen_opt {
    FILE *output;                       /* output file for generated source */
    unsigned use_if_threshold;          /* max number of choices to generate
                                           "if" selector instead of "switch" */
    unsigned char_tail_test_threshold;  /* max number of unprocessed columns
                                           to use inlined char compare
                                           for remaining chars and not generic
                                           string compare code */
    unsigned indent_level;              /* current source identation level */
};

static unsigned column_to_compare;

static int
length_comparator(const void *a, const void *b)
{
    const char *str1 = keyword_list[*(unsigned *)a];
    const char *str2 = keyword_list[*(unsigned *)b];
    return (int)strlen(str1) - (int)strlen(str2);
}

static int
column_comparator(const void *a, const void *b)
{
    const char *str1 = keyword_list[*(unsigned *)a];
    const char *str2 = keyword_list[*(unsigned *)b];
    return (int)str1[column_to_compare] - (int)str2[column_to_compare];
}

static unsigned
count_different_lengths(unsigned indexes[], unsigned nelem)
{
    unsigned nlength, current_length, i, l;

    current_length = 0;
    nlength = 0;
    for (i = 0; i != nelem; ++i) {
        l = (unsigned)strlen(keyword_list[indexes[i]]);
        assert(l != 0);
        if (current_length != l) {
            ++nlength;
            current_length = l;
        }
    }
    return nlength;
}

static void
find_char_span_and_count(unsigned indexes[], unsigned nelem, unsigned column,
                         unsigned *span_result, unsigned *count_result)
{
    unsigned i, count;
    unsigned char c, prev, minc, maxc;

    assert(nelem != 0);
    minc = maxc = prev = (unsigned char)keyword_list[indexes[0]][column];
    count = 1;
    for (i = 1; i != nelem; ++i) {
        c = (unsigned char)keyword_list[indexes[i]][column];
        if (prev != c) {
            prev = c;
            ++count;
            if (minc > c) {
                minc = c;
            } else if (maxc < c) {
                maxc = c;
            }
        }
    }

    *span_result = maxc - minc + 1;
    *count_result = count;
}

static unsigned
find_optimal_switch_column(struct gen_opt *opt,
                           unsigned indexes[], unsigned nelem,
                           unsigned columns[], unsigned unprocessed_columns,
                           int *use_if_result)
{
    unsigned i;
    unsigned span, min_span, min_span_index;
    unsigned nchar, min_nchar, min_nchar_index;

    assert(unprocessed_columns != 0);
    i = 0;
    min_nchar = min_span = (unsigned)-1;
    min_nchar_index = min_span_index = 0;
    do {
        column_to_compare = columns[i];
        qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
        find_char_span_and_count(indexes, nelem, column_to_compare,
                                 &span, &nchar);
        assert(span != 0);
        if (span == 1) {
            assert(nchar == 1);
            *use_if_result = 1;
            return 1;
        }
        assert(nchar != 1);
        if (min_span > span) {
            min_span = span;
            min_span_index = i;
        }
        if (min_nchar > nchar) {
            min_nchar = nchar;
            min_nchar_index = i;
        }
    } while (++i != unprocessed_columns);

    if (min_nchar <= opt->use_if_threshold) {
        *use_if_result = 1;
        i = min_nchar_index;
    } else {
        *use_if_result = 0;
        i = min_span_index;
    }

    /*
     * Restore order corresponding to i if it was destroyed by
     * subsequent sort.
     */
    if (i != unprocessed_columns - 1) {
        column_to_compare = columns[i];
        qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
    }

    return i;
}


static void
p(struct gen_opt *opt, const char *format, ...)
{
    va_list ap;

    va_start(ap, format);
    vfprintf(opt->output, format, ap);
    va_end(ap);
}

/* Size for '\xxx' where xxx is octal escape */
#define MIN_QUOTED_CHAR_BUFFER 7

static char *
qchar(char c, char *quoted_buffer)
{
    char *s;

    s = quoted_buffer;
    *s++ = '\'';
    switch (c) {
      case '\n': c = 'n'; goto one_char_escape;
      case '\r': c = 'r'; goto one_char_escape;
      case '\t': c = 't'; goto one_char_escape;
      case '\f': c = 't'; goto one_char_escape;
      case '\0': c = '0'; goto one_char_escape;
      case '\'': goto one_char_escape;
      one_char_escape:
        *s++ = '\\';
        break;
      default:
        if (!isprint(c)) {
            *s++ = '\\';
            *s++ = (char)('0' + (0x3 & (((unsigned char)c) >> 6)));
            *s++ = (char)('0' + (0x7 & (((unsigned char)c) >> 3)));
            c = (char)('0' + (0x7 & ((unsigned char)c)));
        }
    }
    *s++ = c;
    *s++ = '\'';
    *s = '\0';
    assert(s + 1 <= quoted_buffer + MIN_QUOTED_CHAR_BUFFER);
    return quoted_buffer;
}

static void
nl(struct gen_opt *opt)
{
    putc('\n', opt->output);
}

static void
indent(struct gen_opt *opt)
{
    unsigned n = opt->indent_level;
    while (n != 0) {
        --n;
        fputs("    ", opt->output);
    }
}

static void
line(struct gen_opt *opt, const char *format, ...)
{
    va_list ap;

    indent(opt);
    va_start(ap, format);
    vfprintf(opt->output, format, ap);
    va_end(ap);
    nl(opt);
}

static void
generate_letter_switch_r(struct gen_opt *opt,
                         unsigned indexes[], unsigned nelem,
                         unsigned columns[], unsigned unprocessed_columns)
{
    char qbuf[MIN_QUOTED_CHAR_BUFFER];

    assert(nelem != 0);
    if (nelem == 1) {
        unsigned kw_index = indexes[0];
        const char *keyword = keyword_list[kw_index];

        if (unprocessed_columns == 0) {
            line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
        } else if (unprocessed_columns > opt->char_tail_test_threshold) {
            line(opt, "JSKW_TEST_GUESS(%u) /* %s */", kw_index, keyword);
        } else {
            unsigned i, column;

            indent(opt); p(opt, "if (");
            for (i = 0; i != unprocessed_columns; ++i) {
                column = columns[i];
                qchar(keyword[column], qbuf);
                p(opt, "%sJSKW_AT(%u)==%s", (i == 0) ? "" : " && ",
                  column, qbuf);
            }
            p(opt, ") {"); nl(opt);
            ++opt->indent_level;
            line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
            --opt->indent_level;
            line(opt, "}");
            line(opt, "JSKW_NO_MATCH()");
        }
    } else {
        unsigned optimal_column_index, optimal_column;
        unsigned i;
        int use_if;
        char current;

        assert(unprocessed_columns != 0);
        optimal_column_index = find_optimal_switch_column(opt, indexes, nelem,
                                                          columns,
                                                          unprocessed_columns,
                                                          &use_if);
        optimal_column = columns[optimal_column_index];
        columns[optimal_column_index] = columns[unprocessed_columns - 1];

        if (!use_if)
            line(opt, "switch (JSKW_AT(%u)) {", optimal_column);

        current = keyword_list[indexes[0]][optimal_column];
        for (i = 0; i != nelem;) {
            unsigned same_char_begin = i;
            char next = current;

            for (++i; i != nelem; ++i) {
                next = keyword_list[indexes[i]][optimal_column];
                if (next != current)
                    break;
            }
            qchar(current, qbuf);
            if (use_if) {
                line(opt, "if (JSKW_AT(%u) == %s) {", optimal_column, qbuf);
            } else {
                line(opt, "  case %s:", qbuf);
            }
            ++opt->indent_level;
            generate_letter_switch_r(opt, indexes + same_char_begin,
                                     i - same_char_begin,
                                     columns, unprocessed_columns - 1);
            --opt->indent_level;
            if (use_if) {
                line(opt, "}");
            }
            current = next;
        }

        if (!use_if) {
            line(opt, "}");
        }

        columns[optimal_column_index] = optimal_column;

        line(opt, "JSKW_NO_MATCH()");
    }
}

static void
generate_letter_switch(struct gen_opt *opt,
                       unsigned indexes[], unsigned nelem,
                       unsigned current_length)
{
    unsigned *columns;
    unsigned i;

    columns = (unsigned *) malloc(sizeof(columns[0]) * current_length);
    if (!columns) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    for (i = 0; i != current_length; ++i) {
        columns[i] = i;
    }
    generate_letter_switch_r(opt, indexes, nelem, columns, current_length);
    free(columns);
}


static void
generate_switch(struct gen_opt *opt)
{
    unsigned *indexes;
    unsigned nlength;
    unsigned i, current;
    int use_if;
    unsigned nelem;

    nelem = sizeof(keyword_list)/sizeof(keyword_list[0]);

    line(opt, "/*");
    line(opt, " * Generating switch for the list of %u entries:", nelem);
    for (i = 0; i != nelem; ++i) {
        line(opt, " * %s", keyword_list[i]);
    }
    line(opt, " */");

    indexes = (unsigned *) malloc(sizeof(indexes[0]) * nelem);
    if (!indexes) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    for (i = 0; i != nelem; ++i)
        indexes[i] = i;
    qsort(indexes, nelem, sizeof(indexes[i]), length_comparator);
    nlength = count_different_lengths(indexes, nelem);

    use_if = (nlength <= opt->use_if_threshold);

    if (!use_if)
        line(opt, "switch (JSKW_LENGTH()) {");

    current = (unsigned)strlen(keyword_list[indexes[0]]);
    for (i = 0; i != nelem;) {
        unsigned same_length_begin = i;
        unsigned next = current;

        for (++i; i != nelem; ++i) {
            next = (unsigned)strlen(keyword_list[indexes[i]]);
            if (next != current)
                break;
        }
        if (use_if) {
            line(opt, "if (JSKW_LENGTH() == %u) {", current);
        } else {
            line(opt, "  case %u:", current);
        }
        ++opt->indent_level;
        generate_letter_switch(opt, indexes + same_length_begin,
                               i - same_length_begin,
                               current);
        --opt->indent_level;
        if (use_if) {
            line(opt, "}");
        }
        current = next;
    }
    if (!use_if)
        line(opt, "}");
    line(opt, "JSKW_NO_MATCH()");
    free(indexes);
}

int main(int argc, char **argv)
{
    struct gen_opt opt;

    if (argc < 2) {
        opt.output = stdout;
    } else {
        opt.output = fopen(argv[1], "w");
        if (!opt.output) {
            perror("fopen");
            exit(EXIT_FAILURE);
        }
    }
    opt.indent_level = 1;
    opt.use_if_threshold = 3;
    opt.char_tail_test_threshold = 4;

    generate_switch(&opt);

    if (opt.output != stdout) {
        if (fclose(opt.output)) {
            perror("fclose");
            exit(EXIT_FAILURE);
        }
    }

    return EXIT_SUCCESS;
}
1	/* -- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
2	* vim: set sw=4 ts=8 et tw=80:
3	*
4	* *** BEGIN LICENSE BLOCK ***
5	* Version: MPL 1.1/GPL 2.0/LGPL 2.1
6	*
7	* The contents of this file are subject to the Mozilla Public License Version
8	* 1.1 (the "License"); you may not use this file except in compliance with
9	* the License. You may obtain a copy of the License at
10	* http://www.mozilla.org/MPL/
11	*
12	* Software distributed under the License is distributed on an "AS IS" basis,
13	* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14	* for the specific language governing rights and limitations under the
15	* License.
16	*
17	* The Original Code is String Switch Generator for JavaScript Keywords,
18	* released 2005-12-09.
19	*
20	* The Initial Developer of the Original Code is
21	* Igor Bukanov.
22	* Portions created by the Initial Developer are Copyright (C) 2005-2006
23	* the Initial Developer. All Rights Reserved.
24	*
25	* Contributor(s):
26	*
27	* Alternatively, the contents of this file may be used under the terms of
28	* either of the GNU General Public License Version 2 or later (the "GPL"),
29	* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30	* in which case the provisions of the GPL or the LGPL are applicable instead
31	* of those above. If you wish to allow use of your version of this file only
32	* under the terms of either the GPL or the LGPL, and not to allow others to
33	* use your version of this file under the terms of the MPL, indicate your
34	* decision by deleting the provisions above and replace them with the notice
35	* and other provisions required by the GPL or the LGPL. If you do not delete
36	* the provisions above, a recipient may use your version of this file under
37	* the terms of any one of the MPL, the GPL or the LGPL.
38	*
39	* *** END LICENSE BLOCK *** */
40
41	#include "jsstddef.h"
42	#include <assert.h>
43	#include <stdio.h>
44	#include <stdlib.h>
45	#include <string.h>
46	#include <stdarg.h>
47	#include <ctype.h>
48
49	#include "jsversion.h"
50
51	const char * const keyword_list[] = {
52	#define JS_KEYWORD(keyword, type, op, version) #keyword,
53	#include "jskeyword.tbl"
54	#undef JS_KEYWORD
55	};
56
57	struct gen_opt {
58	FILE output; / output file for generated source */
59	unsigned use_if_threshold; /* max number of choices to generate
60	"if" selector instead of "switch" */
61	unsigned char_tail_test_threshold; /* max number of unprocessed columns
62	to use inlined char compare
63	for remaining chars and not generic
64	string compare code */
65	unsigned indent_level; /* current source identation level */
66	};
67
68	static unsigned column_to_compare;
69
70	static int
71	length_comparator(const void a, const void b)
72	{
73	const char str1 = keyword_list[(unsigned *)a];
74	const char str2 = keyword_list[(unsigned *)b];
75	return (int)strlen(str1) - (int)strlen(str2);
76	}
77
78	static int
79	column_comparator(const void a, const void b)
80	{
81	const char str1 = keyword_list[(unsigned *)a];
82	const char str2 = keyword_list[(unsigned *)b];
83	return (int)str1[column_to_compare] - (int)str2[column_to_compare];
84	}
85
86	static unsigned
87	count_different_lengths(unsigned indexes[], unsigned nelem)
88	{
89	unsigned nlength, current_length, i, l;
90
91	current_length = 0;
92	nlength = 0;
93	for (i = 0; i != nelem; ++i) {
94	l = (unsigned)strlen(keyword_list[indexes[i]]);
95	assert(l != 0);
96	if (current_length != l) {
97	++nlength;
98	current_length = l;
99	}
100	}
101	return nlength;
102	}
103
104	static void
105	find_char_span_and_count(unsigned indexes[], unsigned nelem, unsigned column,
106	unsigned span_result, unsigned count_result)
107	{
108	unsigned i, count;
109	unsigned char c, prev, minc, maxc;
110
111	assert(nelem != 0);
112	minc = maxc = prev = (unsigned char)keyword_list[indexes[0]][column];
113	count = 1;
114	for (i = 1; i != nelem; ++i) {
115	c = (unsigned char)keyword_list[indexes[i]][column];
116	if (prev != c) {
117	prev = c;
118	++count;
119	if (minc > c) {
120	minc = c;
121	} else if (maxc < c) {
122	maxc = c;
123	}
124	}
125	}
126
127	*span_result = maxc - minc + 1;
128	*count_result = count;
129	}
130
131	static unsigned
132	find_optimal_switch_column(struct gen_opt *opt,
133	unsigned indexes[], unsigned nelem,
134	unsigned columns[], unsigned unprocessed_columns,
135	int *use_if_result)
136	{
137	unsigned i;
138	unsigned span, min_span, min_span_index;
139	unsigned nchar, min_nchar, min_nchar_index;
140
141	assert(unprocessed_columns != 0);
142	i = 0;
143	min_nchar = min_span = (unsigned)-1;
144	min_nchar_index = min_span_index = 0;
145	do {
146	column_to_compare = columns[i];
147	qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
148	find_char_span_and_count(indexes, nelem, column_to_compare,
149	&span, &nchar);
150	assert(span != 0);
151	if (span == 1) {
152	assert(nchar == 1);
153	*use_if_result = 1;
154	return 1;
155	}
156	assert(nchar != 1);
157	if (min_span > span) {
158	min_span = span;
159	min_span_index = i;
160	}
161	if (min_nchar > nchar) {
162	min_nchar = nchar;
163	min_nchar_index = i;
164	}
165	} while (++i != unprocessed_columns);
166
167	if (min_nchar <= opt->use_if_threshold) {
168	*use_if_result = 1;
169	i = min_nchar_index;
170	} else {
171	*use_if_result = 0;
172	i = min_span_index;
173	}
174
175	/*
176	* Restore order corresponding to i if it was destroyed by
177	* subsequent sort.
178	*/
179	if (i != unprocessed_columns - 1) {
180	column_to_compare = columns[i];
181	qsort(indexes, nelem, sizeof(indexes[0]), column_comparator);
182	}
183
184	return i;
185	}
186
187
188	static void
189	p(struct gen_opt opt, const char format, ...)
190	{
191	va_list ap;
192
193	va_start(ap, format);
194	vfprintf(opt->output, format, ap);
195	va_end(ap);
196	}
197
198	/* Size for '\xxx' where xxx is octal escape */
199	#define MIN_QUOTED_CHAR_BUFFER 7
200
201	static char *
202	qchar(char c, char *quoted_buffer)
203	{
204	char *s;
205
206	s = quoted_buffer;
207	*s++ = '\'';
208	switch (c) {
209	case '\n': c = 'n'; goto one_char_escape;
210	case '\r': c = 'r'; goto one_char_escape;
211	case '\t': c = 't'; goto one_char_escape;
212	case '\f': c = 't'; goto one_char_escape;
213	case '\0': c = '0'; goto one_char_escape;
214	case '\'': goto one_char_escape;
215	one_char_escape:
216	*s++ = '\\';
217	break;
218	default:
219	if (!isprint(c)) {
220	*s++ = '\\';
221	*s++ = (char)('0' + (0x3 & (((unsigned char)c) >> 6)));
222	*s++ = (char)('0' + (0x7 & (((unsigned char)c) >> 3)));
223	c = (char)('0' + (0x7 & ((unsigned char)c)));
224	}
225	}
226	*s++ = c;
227	*s++ = '\'';
228	*s = '\0';
229	assert(s + 1 <= quoted_buffer + MIN_QUOTED_CHAR_BUFFER);
230	return quoted_buffer;
231	}
232
233	static void
234	nl(struct gen_opt *opt)
235	{
236	putc('\n', opt->output);
237	}
238
239	static void
240	indent(struct gen_opt *opt)
241	{
242	unsigned n = opt->indent_level;
243	while (n != 0) {
244	--n;
245	fputs(" ", opt->output);
246	}
247	}
248
249	static void
250	line(struct gen_opt opt, const char format, ...)
251	{
252	va_list ap;
253
254	indent(opt);
255	va_start(ap, format);
256	vfprintf(opt->output, format, ap);
257	va_end(ap);
258	nl(opt);
259	}
260
261	static void
262	generate_letter_switch_r(struct gen_opt *opt,
263	unsigned indexes[], unsigned nelem,
264	unsigned columns[], unsigned unprocessed_columns)
265	{
266	char qbuf[MIN_QUOTED_CHAR_BUFFER];
267
268	assert(nelem != 0);
269	if (nelem == 1) {
270	unsigned kw_index = indexes[0];
271	const char *keyword = keyword_list[kw_index];
272
273	if (unprocessed_columns == 0) {
274	line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
275	} else if (unprocessed_columns > opt->char_tail_test_threshold) {
276	line(opt, "JSKW_TEST_GUESS(%u) /* %s */", kw_index, keyword);
277	} else {
278	unsigned i, column;
279
280	indent(opt); p(opt, "if (");
281	for (i = 0; i != unprocessed_columns; ++i) {
282	column = columns[i];
283	qchar(keyword[column], qbuf);
284	p(opt, "%sJSKW_AT(%u)==%s", (i == 0) ? "" : " && ",
285	column, qbuf);
286	}
287	p(opt, ") {"); nl(opt);
288	++opt->indent_level;
289	line(opt, "JSKW_GOT_MATCH(%u) /* %s */", kw_index, keyword);
290	--opt->indent_level;
291	line(opt, "}");
292	line(opt, "JSKW_NO_MATCH()");
293	}
294	} else {
295	unsigned optimal_column_index, optimal_column;
296	unsigned i;
297	int use_if;
298	char current;
299
300	assert(unprocessed_columns != 0);
301	optimal_column_index = find_optimal_switch_column(opt, indexes, nelem,
302	columns,
303	unprocessed_columns,
304	&use_if);
305	optimal_column = columns[optimal_column_index];
306	columns[optimal_column_index] = columns[unprocessed_columns - 1];
307
308	if (!use_if)
309	line(opt, "switch (JSKW_AT(%u)) {", optimal_column);
310
311	current = keyword_list[indexes[0]][optimal_column];
312	for (i = 0; i != nelem;) {
313	unsigned same_char_begin = i;
314	char next = current;
315
316	for (++i; i != nelem; ++i) {
317	next = keyword_list[indexes[i]][optimal_column];
318	if (next != current)
319	break;
320	}
321	qchar(current, qbuf);
322	if (use_if) {
323	line(opt, "if (JSKW_AT(%u) == %s) {", optimal_column, qbuf);
324	} else {
325	line(opt, " case %s:", qbuf);
326	}
327	++opt->indent_level;
328	generate_letter_switch_r(opt, indexes + same_char_begin,
329	i - same_char_begin,
330	columns, unprocessed_columns - 1);
331	--opt->indent_level;
332	if (use_if) {
333	line(opt, "}");
334	}
335	current = next;
336	}
337
338	if (!use_if) {
339	line(opt, "}");
340	}
341
342	columns[optimal_column_index] = optimal_column;
343
344	line(opt, "JSKW_NO_MATCH()");
345	}
346	}
347
348	static void
349	generate_letter_switch(struct gen_opt *opt,
350	unsigned indexes[], unsigned nelem,
351	unsigned current_length)
352	{
353	unsigned *columns;
354	unsigned i;
355
356	columns = (unsigned ) malloc(sizeof(columns[0]) current_length);
357	if (!columns) {
358	perror("malloc");
359	exit(EXIT_FAILURE);
360	}
361	for (i = 0; i != current_length; ++i) {
362	columns[i] = i;
363	}
364	generate_letter_switch_r(opt, indexes, nelem, columns, current_length);
365	free(columns);
366	}
367
368
369	static void
370	generate_switch(struct gen_opt *opt)
371	{
372	unsigned *indexes;
373	unsigned nlength;
374	unsigned i, current;
375	int use_if;
376	unsigned nelem;
377
378	nelem = sizeof(keyword_list)/sizeof(keyword_list[0]);
379
380	line(opt, "/*");
381	line(opt, " * Generating switch for the list of %u entries:", nelem);
382	for (i = 0; i != nelem; ++i) {
383	line(opt, " * %s", keyword_list[i]);
384	}
385	line(opt, " */");
386
387	indexes = (unsigned ) malloc(sizeof(indexes[0]) nelem);
388	if (!indexes) {
389	perror("malloc");
390	exit(EXIT_FAILURE);
391	}
392	for (i = 0; i != nelem; ++i)
393	indexes[i] = i;
394	qsort(indexes, nelem, sizeof(indexes[i]), length_comparator);
395	nlength = count_different_lengths(indexes, nelem);
396
397	use_if = (nlength <= opt->use_if_threshold);
398
399	if (!use_if)
400	line(opt, "switch (JSKW_LENGTH()) {");
401
402	current = (unsigned)strlen(keyword_list[indexes[0]]);
403	for (i = 0; i != nelem;) {
404	unsigned same_length_begin = i;
405	unsigned next = current;
406
407	for (++i; i != nelem; ++i) {
408	next = (unsigned)strlen(keyword_list[indexes[i]]);
409	if (next != current)
410	break;
411	}
412	if (use_if) {
413	line(opt, "if (JSKW_LENGTH() == %u) {", current);
414	} else {
415	line(opt, " case %u:", current);
416	}
417	++opt->indent_level;
418	generate_letter_switch(opt, indexes + same_length_begin,
419	i - same_length_begin,
420	current);
421	--opt->indent_level;
422	if (use_if) {
423	line(opt, "}");
424	}
425	current = next;
426	}
427	if (!use_if)
428	line(opt, "}");
429	line(opt, "JSKW_NO_MATCH()");
430	free(indexes);
431	}
432
433	int main(int argc, char **argv)
434	{
435	struct gen_opt opt;
436
437	if (argc < 2) {
438	opt.output = stdout;
439	} else {
440	opt.output = fopen(argv[1], "w");
441	if (!opt.output) {
442	perror("fopen");
443	exit(EXIT_FAILURE);
444	}
445	}
446	opt.indent_level = 1;
447	opt.use_if_threshold = 3;
448	opt.char_tail_test_threshold = 4;
449
450	generate_switch(&opt);
451
452	if (opt.output != stdout) {
453	if (fclose(opt.output)) {
454	perror("fclose");
455	exit(EXIT_FAILURE);
456	}
457	}
458
459	return EXIT_SUCCESS;
460	}