1/* Output routines.
2 Copyright (C) 1989-1998, 2000, 2002-2004, 2006-2007 Free Software Foundation, Inc.
3 Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
4 and Bruno Haible <bruno@clisp.org>.
5
6 This file is part of GNU GPERF.
7
8 GNU GPERF is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GNU GPERF is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22
23/* Specification. */
24#include "output.h"
25
26#include <stdio.h>
27#include <string.h> /* declares strncpy(), strchr() */
28#include <ctype.h> /* declares isprint() */
29#include <assert.h> /* defines assert() */
30#include <limits.h> /* defines SCHAR_MAX etc. */
31#include "options.h"
32#include "version.h"
33
34/* The "const " qualifier. */
35static const char *const_always;
36
37/* The "const " qualifier, for read-only arrays. */
38static const char *const_readonly_array;
39
40/* The "const " qualifier, for the array type. */
41static const char *const_for_struct;
42
43/* Returns the smallest unsigned C type capable of holding integers
44 up to N. */
45
46static const char *
47smallest_integral_type (int n)
48{
49 if (n <= UCHAR_MAX) return "unsigned char";
50 if (n <= USHRT_MAX) return "unsigned short";
51 return "unsigned int";
52}
53
54/* Returns the smallest signed C type capable of holding integers
55 from MIN to MAX. */
56
57static const char *
58smallest_integral_type (int min, int max)
59{
60 if (option[ANSIC] | option[CPLUSPLUS])
61 if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char";
62 if (min >= SHRT_MIN && max <= SHRT_MAX) return "short";
63 return "int";
64}
65
66/* ------------------------------------------------------------------------- */
67
68/* Constructor.
69 Note about the keyword list starting at head:
70 - The list is ordered by increasing _hash_value. This has been achieved
71 by Search::sort().
72 - Duplicates, i.e. keywords with the same _selchars set, are chained
73 through the _duplicate_link pointer. Only one representative per
74 duplicate equivalence class remains on the linear keyword list.
75 - Accidental duplicates, i.e. keywords for which the _asso_values[] search
76 couldn't achieve different hash values, cannot occur on the linear
77 keyword list. Search::optimize would catch this mistake.
78 */
79Output::Output (KeywordExt_List *head, const char *struct_decl,
80 unsigned int struct_decl_lineno, const char *return_type,
81 const char *struct_tag, const char *verbatim_declarations,
82 const char *verbatim_declarations_end,
83 unsigned int verbatim_declarations_lineno,
84 const char *verbatim_code, const char *verbatim_code_end,
85 unsigned int verbatim_code_lineno, bool charset_dependent,
86 int total_keys, int max_key_len, int min_key_len,
87 const Positions& positions, const unsigned int *alpha_inc,
88 int total_duplicates, unsigned int alpha_size,
89 const int *asso_values)
90 : _head (head), _struct_decl (struct_decl),
91 _struct_decl_lineno (struct_decl_lineno), _return_type (return_type),
92 _struct_tag (struct_tag),
93 _verbatim_declarations (verbatim_declarations),
94 _verbatim_declarations_end (verbatim_declarations_end),
95 _verbatim_declarations_lineno (verbatim_declarations_lineno),
96 _verbatim_code (verbatim_code),
97 _verbatim_code_end (verbatim_code_end),
98 _verbatim_code_lineno (verbatim_code_lineno),
99 _charset_dependent (charset_dependent),
100 _total_keys (total_keys),
101 _max_key_len (max_key_len), _min_key_len (min_key_len),
102 _key_positions (positions), _alpha_inc (alpha_inc),
103 _total_duplicates (total_duplicates), _alpha_size (alpha_size),
104 _asso_values (asso_values)
105{
106}
107
108/* ------------------------------------------------------------------------- */
109
110/* Computes the minimum and maximum hash values, and stores them
111 in _min_hash_value and _max_hash_value. */
112
113void
114Output::compute_min_max ()
115{
116 /* Since the list is already sorted by hash value all we need to do is
117 to look at the first and the last element of the list. */
118
119 _min_hash_value = _head->first()->_hash_value;
120
121 KeywordExt_List *temp;
122 for (temp = _head; temp->rest(); temp = temp->rest())
123 ;
124 _max_hash_value = temp->first()->_hash_value;
125}
126
127/* ------------------------------------------------------------------------- */
128
129/* Returns the number of different hash values. */
130
131int
132Output::num_hash_values () const
133{
134 /* Since the list is already sorted by hash value and doesn't contain
135 duplicates, we can simply count the number of keywords on the list. */
136 int count = 0;
137 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
138 count++;
139 return count;
140}
141
142/* -------------------- Output_Constants and subclasses -------------------- */
143
144/* This class outputs an enumeration defining some constants. */
145
146struct Output_Constants
147{
148 virtual void output_start () = 0;
149 virtual void output_item (const char *name, int value) = 0;
150 virtual void output_end () = 0;
151 Output_Constants () {}
152 virtual ~Output_Constants () {}
153};
154
155/* This class outputs an enumeration in #define syntax. */
156
157struct Output_Defines : public Output_Constants
158{
159 virtual void output_start ();
160 virtual void output_item (const char *name, int value);
161 virtual void output_end ();
162 Output_Defines () {}
163 virtual ~Output_Defines () {}
164};
165
166void Output_Defines::output_start ()
167{
168 printf ("\n");
169}
170
171void Output_Defines::output_item (const char *name, int value)
172{
173 printf ("#define %s %d\n", name, value);
174}
175
176void Output_Defines::output_end ()
177{
178}
179
180/* This class outputs an enumeration using 'enum'. */
181
182struct Output_Enum : public Output_Constants
183{
184 virtual void output_start ();
185 virtual void output_item (const char *name, int value);
186 virtual void output_end ();
187 Output_Enum (const char *indent)
188 : _indentation (indent) {}
189 virtual ~Output_Enum () {}
190private:
191 const char *_indentation;
192 bool _pending_comma;
193};
194
195void Output_Enum::output_start ()
196{
197 printf ("%senum\n"
198 "%s {\n",
199 _indentation, _indentation);
200 _pending_comma = false;
201}
202
203void Output_Enum::output_item (const char *name, int value)
204{
205 if (_pending_comma)
206 printf (",\n");
207 printf ("%s %s = %d", _indentation, name, value);
208 _pending_comma = true;
209}
210
211void Output_Enum::output_end ()
212{
213 if (_pending_comma)
214 printf ("\n");
215 printf ("%s };\n\n", _indentation);
216}
217
218/* Outputs the maximum and minimum hash values etc. */
219
220void
221Output::output_constants (struct Output_Constants& style) const
222{
223 style.output_start ();
224 style.output_item ("TOTAL_KEYWORDS", _total_keys);
225 style.output_item ("MIN_WORD_LENGTH", _min_key_len);
226 style.output_item ("MAX_WORD_LENGTH", _max_key_len);
227 style.output_item ("MIN_HASH_VALUE", _min_hash_value);
228 style.output_item ("MAX_HASH_VALUE", _max_hash_value);
229 style.output_end ();
230}
231
232/* ------------------------------------------------------------------------- */
233
234/* We use a downcase table because when called repeatedly, the code
235 gperf_downcase[c]
236 is faster than
237 if (c >= 'A' && c <= 'Z')
238 c += 'a' - 'A';
239 */
240#define USE_DOWNCASE_TABLE 1
241
242#if USE_DOWNCASE_TABLE
243
244/* Output gperf's ASCII-downcase table. */
245
246static void
247output_upperlower_table ()
248{
249 unsigned int c;
250
251 printf ("#ifndef GPERF_DOWNCASE\n"
252 "#define GPERF_DOWNCASE 1\n"
253 "static unsigned char gperf_downcase[256] =\n"
254 " {");
255 for (c = 0; c < 256; c++)
256 {
257 if ((c % 15) == 0)
258 printf ("\n ");
259 printf (" %3d", c >= 'A' && c <= 'Z' ? c + 'a' - 'A' : c);
260 if (c < 255)
261 printf (",");
262 }
263 printf ("\n"
264 " };\n"
265 "#endif\n\n");
266}
267
268#endif
269
270/* Output gperf's ASCII-case insensitive strcmp replacement. */
271
272static void
273output_upperlower_strcmp ()
274{
275 printf ("#ifndef GPERF_CASE_STRCMP\n"
276 "#define GPERF_CASE_STRCMP 1\n"
277 "static int\n"
278 "gperf_case_strcmp ");
279 printf (option[KRC] ?
280 "(s1, s2)\n"
281 " register char *s1;\n"
282 " register char *s2;\n" :
283 option[C] ?
284 "(s1, s2)\n"
285 " register const char *s1;\n"
286 " register const char *s2;\n" :
287 option[ANSIC] | option[CPLUSPLUS] ?
288 "(register const char *s1, register const char *s2)\n" :
289 "");
290 #if USE_DOWNCASE_TABLE
291 printf ("{\n"
292 " for (;;)\n"
293 " {\n"
294 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
295 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
296 " if (c1 != 0 && c1 == c2)\n"
297 " continue;\n"
298 " return (int)c1 - (int)c2;\n"
299 " }\n"
300 "}\n");
301 #else
302 printf ("{\n"
303 " for (;;)\n"
304 " {\n"
305 " unsigned char c1 = *s1++;\n"
306 " unsigned char c2 = *s2++;\n"
307 " if (c1 >= 'A' && c1 <= 'Z')\n"
308 " c1 += 'a' - 'A';\n"
309 " if (c2 >= 'A' && c2 <= 'Z')\n"
310 " c2 += 'a' - 'A';\n"
311 " if (c1 != 0 && c1 == c2)\n"
312 " continue;\n"
313 " return (int)c1 - (int)c2;\n"
314 " }\n"
315 "}\n");
316 #endif
317 printf ("#endif\n\n");
318}
319
320/* Output gperf's ASCII-case insensitive strncmp replacement. */
321
322static void
323output_upperlower_strncmp ()
324{
325 printf ("#ifndef GPERF_CASE_STRNCMP\n"
326 "#define GPERF_CASE_STRNCMP 1\n"
327 "static int\n"
328 "gperf_case_strncmp ");
329 printf (option[KRC] ?
330 "(s1, s2, n)\n"
331 " register char *s1;\n"
332 " register char *s2;\n"
333 " register unsigned int n;\n" :
334 option[C] ?
335 "(s1, s2, n)\n"
336 " register const char *s1;\n"
337 " register const char *s2;\n"
338 " register unsigned int n;\n" :
339 option[ANSIC] | option[CPLUSPLUS] ?
340 "(register const char *s1, register const char *s2, register unsigned int n)\n" :
341 "");
342 #if USE_DOWNCASE_TABLE
343 printf ("{\n"
344 " for (; n > 0;)\n"
345 " {\n"
346 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
347 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
348 " if (c1 != 0 && c1 == c2)\n"
349 " {\n"
350 " n--;\n"
351 " continue;\n"
352 " }\n"
353 " return (int)c1 - (int)c2;\n"
354 " }\n"
355 " return 0;\n"
356 "}\n");
357 #else
358 printf ("{\n"
359 " for (; n > 0;)\n"
360 " {\n"
361 " unsigned char c1 = *s1++;\n"
362 " unsigned char c2 = *s2++;\n"
363 " if (c1 >= 'A' && c1 <= 'Z')\n"
364 " c1 += 'a' - 'A';\n"
365 " if (c2 >= 'A' && c2 <= 'Z')\n"
366 " c2 += 'a' - 'A';\n"
367 " if (c1 != 0 && c1 == c2)\n"
368 " {\n"
369 " n--;\n"
370 " continue;\n"
371 " }\n"
372 " return (int)c1 - (int)c2;\n"
373 " }\n"
374 " return 0;\n"
375 "}\n");
376 #endif
377 printf ("#endif\n\n");
378}
379
380/* Output gperf's ASCII-case insensitive memcmp replacement. */
381
382static void
383output_upperlower_memcmp ()
384{
385 printf ("#ifndef GPERF_CASE_MEMCMP\n"
386 "#define GPERF_CASE_MEMCMP 1\n"
387 "static int\n"
388 "gperf_case_memcmp ");
389 printf (option[KRC] ?
390 "(s1, s2, n)\n"
391 " register char *s1;\n"
392 " register char *s2;\n"
393 " register unsigned int n;\n" :
394 option[C] ?
395 "(s1, s2, n)\n"
396 " register const char *s1;\n"
397 " register const char *s2;\n"
398 " register unsigned int n;\n" :
399 option[ANSIC] | option[CPLUSPLUS] ?
400 "(register const char *s1, register const char *s2, register unsigned int n)\n" :
401 "");
402 #if USE_DOWNCASE_TABLE
403 printf ("{\n"
404 " for (; n > 0;)\n"
405 " {\n"
406 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
407 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
408 " if (c1 == c2)\n"
409 " {\n"
410 " n--;\n"
411 " continue;\n"
412 " }\n"
413 " return (int)c1 - (int)c2;\n"
414 " }\n"
415 " return 0;\n"
416 "}\n");
417 #else
418 printf ("{\n"
419 " for (; n > 0;)\n"
420 " {\n"
421 " unsigned char c1 = *s1++;\n"
422 " unsigned char c2 = *s2++;\n"
423 " if (c1 >= 'A' && c1 <= 'Z')\n"
424 " c1 += 'a' - 'A';\n"
425 " if (c2 >= 'A' && c2 <= 'Z')\n"
426 " c2 += 'a' - 'A';\n"
427 " if (c1 == c2)\n"
428 " {\n"
429 " n--;\n"
430 " continue;\n"
431 " }\n"
432 " return (int)c1 - (int)c2;\n"
433 " }\n"
434 " return 0;\n"
435 "}\n");
436 #endif
437 printf ("#endif\n\n");
438}
439
440/* ------------------------------------------------------------------------- */
441
442/* Outputs a keyword, as a string: enclosed in double quotes, escaping
443 backslashes, double quote and unprintable characters. */
444
445static void
446output_string (const char *key, int len)
447{
448 putchar ('"');
449 for (; len > 0; len--)
450 {
451 unsigned char c = static_cast<unsigned char>(*key++);
452 if (isprint (c))
453 {
454 if (c == '"' || c == '\\')
455 putchar ('\\');
456 putchar (c);
457 }
458 else
459 {
460 /* Use octal escapes, not hexadecimal escapes, because some old
461 C compilers didn't understand hexadecimal escapes, and because
462 hexadecimal escapes are not limited to 2 digits, thus needing
463 special care if the following character happens to be a digit. */
464 putchar ('\\');
465 putchar ('0' + ((c >> 6) & 7));
466 putchar ('0' + ((c >> 3) & 7));
467 putchar ('0' + (c & 7));
468 }
469 }
470 putchar ('"');
471}
472
473/* ------------------------------------------------------------------------- */
474
475/* Outputs a #line directive, referring to the given line number. */
476
477static void
478output_line_directive (unsigned int lineno)
479{
480 const char *file_name = option.get_input_file_name ();
481 if (file_name != NULL)
482 {
483 printf ("#line %u ", lineno);
484 output_string (file_name, strlen (file_name));
485 printf ("\n");
486 }
487}
488
489/* ------------------------------------------------------------------------- */
490
491/* Outputs a type and a const specifier (i.e. "const " or "").
492 The output is terminated with a space. */
493
494static void
495output_const_type (const char *const_string, const char *type_string)
496{
497 if (type_string[strlen(type_string)-1] == '*')
498 /* For pointer types, put the 'const' after the type. */
499 printf ("%s %s", type_string, const_string);
500 else
501 /* For scalar or struct types, put the 'const' before the type. */
502 printf ("%s%s ", const_string, type_string);
503}
504
505/* ----------------------- Output_Expr and subclasses ----------------------- */
506
507/* This class outputs a general expression. */
508
509struct Output_Expr
510{
511 virtual void output_expr () const = 0;
512 Output_Expr () {}
513 virtual ~Output_Expr () {}
514};
515
516/* This class outputs an expression formed by a single string. */
517
518struct Output_Expr1 : public Output_Expr
519{
520 virtual void output_expr () const;
521 Output_Expr1 (const char *piece1) : _p1 (piece1) {}
522 virtual ~Output_Expr1 () {}
523private:
524 const char *_p1;
525};
526
527void Output_Expr1::output_expr () const
528{
529 printf ("%s", _p1);
530}
531
532#if 0 /* unused */
533
534/* This class outputs an expression formed by the concatenation of two
535 strings. */
536
537struct Output_Expr2 : public Output_Expr
538{
539 virtual void output_expr () const;
540 Output_Expr2 (const char *piece1, const char *piece2)
541 : _p1 (piece1), _p2 (piece2) {}
542 virtual ~Output_Expr2 () {}
543private:
544 const char *_p1;
545 const char *_p2;
546};
547
548void Output_Expr2::output_expr () const
549{
550 printf ("%s%s", _p1, _p2);
551}
552
553#endif
554
555/* --------------------- Output_Compare and subclasses --------------------- */
556
557/* This class outputs a comparison expression. */
558
559struct Output_Compare
560{
561 /* Outputs the comparison expression.
562 expr1 outputs a simple expression of type 'const char *' referring to
563 the string being looked up. expr2 outputs a simple expression of type
564 'const char *' referring to the constant string stored in the gperf
565 generated hash table. */
566 virtual void output_comparison (const Output_Expr& expr1,
567 const Output_Expr& expr2) const = 0;
568 /* Outputs the comparison expression for the first byte.
569 Returns true if the this comparison is complete. */
570 bool output_firstchar_comparison (const Output_Expr& expr1,
571 const Output_Expr& expr2) const;
572 Output_Compare () {}
573 virtual ~Output_Compare () {}
574};
575
576bool Output_Compare::output_firstchar_comparison (const Output_Expr& expr1,
577 const Output_Expr& expr2) const
578{
579 /* First, we emit a comparison of the first byte of the two strings.
580 This catches most cases where the string being looked up is not in the
581 hash table but happens to have the same hash code as an element of the
582 hash table. */
583 if (option[UPPERLOWER])
584 {
585 /* Incomplete comparison, just for speedup. */
586 printf ("(((unsigned char)*");
587 expr1.output_expr ();
588 printf (" ^ (unsigned char)*");
589 expr2.output_expr ();
590 printf (") & ~32) == 0");
591 return false;
592 }
593 else
594 {
595 /* Complete comparison. */
596 printf ("*");
597 expr1.output_expr ();
598 printf (" == *");
599 expr2.output_expr ();
600 return true;
601 }
602}
603
604/* This class outputs a comparison using strcmp. */
605
606struct Output_Compare_Strcmp : public Output_Compare
607{
608 virtual void output_comparison (const Output_Expr& expr1,
609 const Output_Expr& expr2) const;
610 Output_Compare_Strcmp () {}
611 virtual ~Output_Compare_Strcmp () {}
612};
613
614void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
615 const Output_Expr& expr2) const
616{
617 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
618 printf (" && !");
619 if (option[UPPERLOWER])
620 printf ("gperf_case_");
621 printf ("strcmp (");
622 if (firstchar_done)
623 {
624 expr1.output_expr ();
625 printf (" + 1, ");
626 expr2.output_expr ();
627 printf (" + 1");
628 }
629 else
630 {
631 expr1.output_expr ();
632 printf (", ");
633 expr2.output_expr ();
634 }
635 printf (")");
636}
637
638/* This class outputs a comparison using strncmp.
639 Note that the length of expr1 will be available through the local variable
640 'len'. */
641
642struct Output_Compare_Strncmp : public Output_Compare
643{
644 virtual void output_comparison (const Output_Expr& expr1,
645 const Output_Expr& expr2) const;
646 Output_Compare_Strncmp () {}
647 virtual ~Output_Compare_Strncmp () {}
648};
649
650void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
651 const Output_Expr& expr2) const
652{
653 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
654 printf (" && !");
655 if (option[UPPERLOWER])
656 printf ("gperf_case_");
657 printf ("strncmp (");
658 if (firstchar_done)
659 {
660 expr1.output_expr ();
661 printf (" + 1, ");
662 expr2.output_expr ();
663 printf (" + 1, len - 1");
664 }
665 else
666 {
667 expr1.output_expr ();
668 printf (", ");
669 expr2.output_expr ();
670 printf (", len");
671 }
672 printf (") && ");
673 expr2.output_expr ();
674 printf ("[len] == '\\0'");
675}
676
677/* This class outputs a comparison using memcmp.
678 Note that the length of expr1 (available through the local variable 'len')
679 must be verified to be equal to the length of expr2 prior to this
680 comparison. */
681
682struct Output_Compare_Memcmp : public Output_Compare
683{
684 virtual void output_comparison (const Output_Expr& expr1,
685 const Output_Expr& expr2) const;
686 Output_Compare_Memcmp () {}
687 virtual ~Output_Compare_Memcmp () {}
688};
689
690void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
691 const Output_Expr& expr2) const
692{
693 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
694 printf (" && !");
695 if (option[UPPERLOWER])
696 printf ("gperf_case_");
697 printf ("memcmp (");
698 if (firstchar_done)
699 {
700 expr1.output_expr ();
701 printf (" + 1, ");
702 expr2.output_expr ();
703 printf (" + 1, len - 1");
704 }
705 else
706 {
707 expr1.output_expr ();
708 printf (", ");
709 expr2.output_expr ();
710 printf (", len");
711 }
712 printf (")");
713}
714
715/* ------------------------------------------------------------------------- */
716
717/* Generates a C expression for an asso_values[] reference. */
718
719void
720Output::output_asso_values_ref (int pos) const
721{
722 printf ("asso_values[");
723 /* Always cast to unsigned char. This is necessary when the alpha_inc
724 is nonzero, and also avoids a gcc warning "subscript has type 'char'". */
725 printf ("(unsigned char)");
726 if (pos == Positions::LASTCHAR)
727 printf ("str[len - 1]");
728 else
729 {
730 printf ("str[%d]", pos);
731 if (_alpha_inc[pos])
732 printf ("+%u", _alpha_inc[pos]);
733 }
734 printf ("]");
735}
736
737/* Generates C code for the hash function that returns the
738 proper encoding for each keyword.
739 The hash function has the signature
740 unsigned int <hash> (const char *str, unsigned int len). */
741
742void
743Output::output_hash_function () const
744{
745 /* Output the function's head. */
746 if (option[CPLUSPLUS])
747 printf ("inline ");
748 else if (option[KRC] | option[C] | option[ANSIC])
749 printf ("#ifdef __GNUC__\n"
750 "__inline\n"
751 "#else\n"
752 "#ifdef __cplusplus\n"
753 "inline\n"
754 "#endif\n"
755 "#endif\n");
756
757 if (/* The function does not use the 'str' argument? */
758 _key_positions.get_size() == 0
759 || /* The function uses 'str', but not the 'len' argument? */
760 (option[NOLENGTH]
761 && _key_positions[0] < _min_key_len
762 && _key_positions[_key_positions.get_size() - 1] != Positions::LASTCHAR))
763 /* Pacify lint. */
764 printf ("/*ARGSUSED*/\n");
765
766 if (option[KRC] | option[C] | option[ANSIC])
767 printf ("static ");
768 printf ("unsigned int\n");
769 if (option[CPLUSPLUS])
770 printf ("%s::", option.get_class_name ());
771 printf ("%s ", option.get_hash_name ());
772 printf (option[KRC] ?
773 "(str, len)\n"
774 " register char *str;\n"
| 1/* Output routines.
2 Copyright (C) 1989-1998, 2000, 2002-2004, 2006-2007 Free Software Foundation, Inc.
3 Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
4 and Bruno Haible <bruno@clisp.org>.
5
6 This file is part of GNU GPERF.
7
8 GNU GPERF is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GNU GPERF is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22
23/* Specification. */
24#include "output.h"
25
26#include <stdio.h>
27#include <string.h> /* declares strncpy(), strchr() */
28#include <ctype.h> /* declares isprint() */
29#include <assert.h> /* defines assert() */
30#include <limits.h> /* defines SCHAR_MAX etc. */
31#include "options.h"
32#include "version.h"
33
34/* The "const " qualifier. */
35static const char *const_always;
36
37/* The "const " qualifier, for read-only arrays. */
38static const char *const_readonly_array;
39
40/* The "const " qualifier, for the array type. */
41static const char *const_for_struct;
42
43/* Returns the smallest unsigned C type capable of holding integers
44 up to N. */
45
46static const char *
47smallest_integral_type (int n)
48{
49 if (n <= UCHAR_MAX) return "unsigned char";
50 if (n <= USHRT_MAX) return "unsigned short";
51 return "unsigned int";
52}
53
54/* Returns the smallest signed C type capable of holding integers
55 from MIN to MAX. */
56
57static const char *
58smallest_integral_type (int min, int max)
59{
60 if (option[ANSIC] | option[CPLUSPLUS])
61 if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char";
62 if (min >= SHRT_MIN && max <= SHRT_MAX) return "short";
63 return "int";
64}
65
66/* ------------------------------------------------------------------------- */
67
68/* Constructor.
69 Note about the keyword list starting at head:
70 - The list is ordered by increasing _hash_value. This has been achieved
71 by Search::sort().
72 - Duplicates, i.e. keywords with the same _selchars set, are chained
73 through the _duplicate_link pointer. Only one representative per
74 duplicate equivalence class remains on the linear keyword list.
75 - Accidental duplicates, i.e. keywords for which the _asso_values[] search
76 couldn't achieve different hash values, cannot occur on the linear
77 keyword list. Search::optimize would catch this mistake.
78 */
79Output::Output (KeywordExt_List *head, const char *struct_decl,
80 unsigned int struct_decl_lineno, const char *return_type,
81 const char *struct_tag, const char *verbatim_declarations,
82 const char *verbatim_declarations_end,
83 unsigned int verbatim_declarations_lineno,
84 const char *verbatim_code, const char *verbatim_code_end,
85 unsigned int verbatim_code_lineno, bool charset_dependent,
86 int total_keys, int max_key_len, int min_key_len,
87 const Positions& positions, const unsigned int *alpha_inc,
88 int total_duplicates, unsigned int alpha_size,
89 const int *asso_values)
90 : _head (head), _struct_decl (struct_decl),
91 _struct_decl_lineno (struct_decl_lineno), _return_type (return_type),
92 _struct_tag (struct_tag),
93 _verbatim_declarations (verbatim_declarations),
94 _verbatim_declarations_end (verbatim_declarations_end),
95 _verbatim_declarations_lineno (verbatim_declarations_lineno),
96 _verbatim_code (verbatim_code),
97 _verbatim_code_end (verbatim_code_end),
98 _verbatim_code_lineno (verbatim_code_lineno),
99 _charset_dependent (charset_dependent),
100 _total_keys (total_keys),
101 _max_key_len (max_key_len), _min_key_len (min_key_len),
102 _key_positions (positions), _alpha_inc (alpha_inc),
103 _total_duplicates (total_duplicates), _alpha_size (alpha_size),
104 _asso_values (asso_values)
105{
106}
107
108/* ------------------------------------------------------------------------- */
109
110/* Computes the minimum and maximum hash values, and stores them
111 in _min_hash_value and _max_hash_value. */
112
113void
114Output::compute_min_max ()
115{
116 /* Since the list is already sorted by hash value all we need to do is
117 to look at the first and the last element of the list. */
118
119 _min_hash_value = _head->first()->_hash_value;
120
121 KeywordExt_List *temp;
122 for (temp = _head; temp->rest(); temp = temp->rest())
123 ;
124 _max_hash_value = temp->first()->_hash_value;
125}
126
127/* ------------------------------------------------------------------------- */
128
129/* Returns the number of different hash values. */
130
131int
132Output::num_hash_values () const
133{
134 /* Since the list is already sorted by hash value and doesn't contain
135 duplicates, we can simply count the number of keywords on the list. */
136 int count = 0;
137 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
138 count++;
139 return count;
140}
141
142/* -------------------- Output_Constants and subclasses -------------------- */
143
144/* This class outputs an enumeration defining some constants. */
145
146struct Output_Constants
147{
148 virtual void output_start () = 0;
149 virtual void output_item (const char *name, int value) = 0;
150 virtual void output_end () = 0;
151 Output_Constants () {}
152 virtual ~Output_Constants () {}
153};
154
155/* This class outputs an enumeration in #define syntax. */
156
157struct Output_Defines : public Output_Constants
158{
159 virtual void output_start ();
160 virtual void output_item (const char *name, int value);
161 virtual void output_end ();
162 Output_Defines () {}
163 virtual ~Output_Defines () {}
164};
165
166void Output_Defines::output_start ()
167{
168 printf ("\n");
169}
170
171void Output_Defines::output_item (const char *name, int value)
172{
173 printf ("#define %s %d\n", name, value);
174}
175
176void Output_Defines::output_end ()
177{
178}
179
180/* This class outputs an enumeration using 'enum'. */
181
182struct Output_Enum : public Output_Constants
183{
184 virtual void output_start ();
185 virtual void output_item (const char *name, int value);
186 virtual void output_end ();
187 Output_Enum (const char *indent)
188 : _indentation (indent) {}
189 virtual ~Output_Enum () {}
190private:
191 const char *_indentation;
192 bool _pending_comma;
193};
194
195void Output_Enum::output_start ()
196{
197 printf ("%senum\n"
198 "%s {\n",
199 _indentation, _indentation);
200 _pending_comma = false;
201}
202
203void Output_Enum::output_item (const char *name, int value)
204{
205 if (_pending_comma)
206 printf (",\n");
207 printf ("%s %s = %d", _indentation, name, value);
208 _pending_comma = true;
209}
210
211void Output_Enum::output_end ()
212{
213 if (_pending_comma)
214 printf ("\n");
215 printf ("%s };\n\n", _indentation);
216}
217
218/* Outputs the maximum and minimum hash values etc. */
219
220void
221Output::output_constants (struct Output_Constants& style) const
222{
223 style.output_start ();
224 style.output_item ("TOTAL_KEYWORDS", _total_keys);
225 style.output_item ("MIN_WORD_LENGTH", _min_key_len);
226 style.output_item ("MAX_WORD_LENGTH", _max_key_len);
227 style.output_item ("MIN_HASH_VALUE", _min_hash_value);
228 style.output_item ("MAX_HASH_VALUE", _max_hash_value);
229 style.output_end ();
230}
231
232/* ------------------------------------------------------------------------- */
233
234/* We use a downcase table because when called repeatedly, the code
235 gperf_downcase[c]
236 is faster than
237 if (c >= 'A' && c <= 'Z')
238 c += 'a' - 'A';
239 */
240#define USE_DOWNCASE_TABLE 1
241
242#if USE_DOWNCASE_TABLE
243
244/* Output gperf's ASCII-downcase table. */
245
246static void
247output_upperlower_table ()
248{
249 unsigned int c;
250
251 printf ("#ifndef GPERF_DOWNCASE\n"
252 "#define GPERF_DOWNCASE 1\n"
253 "static unsigned char gperf_downcase[256] =\n"
254 " {");
255 for (c = 0; c < 256; c++)
256 {
257 if ((c % 15) == 0)
258 printf ("\n ");
259 printf (" %3d", c >= 'A' && c <= 'Z' ? c + 'a' - 'A' : c);
260 if (c < 255)
261 printf (",");
262 }
263 printf ("\n"
264 " };\n"
265 "#endif\n\n");
266}
267
268#endif
269
270/* Output gperf's ASCII-case insensitive strcmp replacement. */
271
272static void
273output_upperlower_strcmp ()
274{
275 printf ("#ifndef GPERF_CASE_STRCMP\n"
276 "#define GPERF_CASE_STRCMP 1\n"
277 "static int\n"
278 "gperf_case_strcmp ");
279 printf (option[KRC] ?
280 "(s1, s2)\n"
281 " register char *s1;\n"
282 " register char *s2;\n" :
283 option[C] ?
284 "(s1, s2)\n"
285 " register const char *s1;\n"
286 " register const char *s2;\n" :
287 option[ANSIC] | option[CPLUSPLUS] ?
288 "(register const char *s1, register const char *s2)\n" :
289 "");
290 #if USE_DOWNCASE_TABLE
291 printf ("{\n"
292 " for (;;)\n"
293 " {\n"
294 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
295 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
296 " if (c1 != 0 && c1 == c2)\n"
297 " continue;\n"
298 " return (int)c1 - (int)c2;\n"
299 " }\n"
300 "}\n");
301 #else
302 printf ("{\n"
303 " for (;;)\n"
304 " {\n"
305 " unsigned char c1 = *s1++;\n"
306 " unsigned char c2 = *s2++;\n"
307 " if (c1 >= 'A' && c1 <= 'Z')\n"
308 " c1 += 'a' - 'A';\n"
309 " if (c2 >= 'A' && c2 <= 'Z')\n"
310 " c2 += 'a' - 'A';\n"
311 " if (c1 != 0 && c1 == c2)\n"
312 " continue;\n"
313 " return (int)c1 - (int)c2;\n"
314 " }\n"
315 "}\n");
316 #endif
317 printf ("#endif\n\n");
318}
319
320/* Output gperf's ASCII-case insensitive strncmp replacement. */
321
322static void
323output_upperlower_strncmp ()
324{
325 printf ("#ifndef GPERF_CASE_STRNCMP\n"
326 "#define GPERF_CASE_STRNCMP 1\n"
327 "static int\n"
328 "gperf_case_strncmp ");
329 printf (option[KRC] ?
330 "(s1, s2, n)\n"
331 " register char *s1;\n"
332 " register char *s2;\n"
333 " register unsigned int n;\n" :
334 option[C] ?
335 "(s1, s2, n)\n"
336 " register const char *s1;\n"
337 " register const char *s2;\n"
338 " register unsigned int n;\n" :
339 option[ANSIC] | option[CPLUSPLUS] ?
340 "(register const char *s1, register const char *s2, register unsigned int n)\n" :
341 "");
342 #if USE_DOWNCASE_TABLE
343 printf ("{\n"
344 " for (; n > 0;)\n"
345 " {\n"
346 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
347 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
348 " if (c1 != 0 && c1 == c2)\n"
349 " {\n"
350 " n--;\n"
351 " continue;\n"
352 " }\n"
353 " return (int)c1 - (int)c2;\n"
354 " }\n"
355 " return 0;\n"
356 "}\n");
357 #else
358 printf ("{\n"
359 " for (; n > 0;)\n"
360 " {\n"
361 " unsigned char c1 = *s1++;\n"
362 " unsigned char c2 = *s2++;\n"
363 " if (c1 >= 'A' && c1 <= 'Z')\n"
364 " c1 += 'a' - 'A';\n"
365 " if (c2 >= 'A' && c2 <= 'Z')\n"
366 " c2 += 'a' - 'A';\n"
367 " if (c1 != 0 && c1 == c2)\n"
368 " {\n"
369 " n--;\n"
370 " continue;\n"
371 " }\n"
372 " return (int)c1 - (int)c2;\n"
373 " }\n"
374 " return 0;\n"
375 "}\n");
376 #endif
377 printf ("#endif\n\n");
378}
379
380/* Output gperf's ASCII-case insensitive memcmp replacement. */
381
382static void
383output_upperlower_memcmp ()
384{
385 printf ("#ifndef GPERF_CASE_MEMCMP\n"
386 "#define GPERF_CASE_MEMCMP 1\n"
387 "static int\n"
388 "gperf_case_memcmp ");
389 printf (option[KRC] ?
390 "(s1, s2, n)\n"
391 " register char *s1;\n"
392 " register char *s2;\n"
393 " register unsigned int n;\n" :
394 option[C] ?
395 "(s1, s2, n)\n"
396 " register const char *s1;\n"
397 " register const char *s2;\n"
398 " register unsigned int n;\n" :
399 option[ANSIC] | option[CPLUSPLUS] ?
400 "(register const char *s1, register const char *s2, register unsigned int n)\n" :
401 "");
402 #if USE_DOWNCASE_TABLE
403 printf ("{\n"
404 " for (; n > 0;)\n"
405 " {\n"
406 " unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
407 " unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
408 " if (c1 == c2)\n"
409 " {\n"
410 " n--;\n"
411 " continue;\n"
412 " }\n"
413 " return (int)c1 - (int)c2;\n"
414 " }\n"
415 " return 0;\n"
416 "}\n");
417 #else
418 printf ("{\n"
419 " for (; n > 0;)\n"
420 " {\n"
421 " unsigned char c1 = *s1++;\n"
422 " unsigned char c2 = *s2++;\n"
423 " if (c1 >= 'A' && c1 <= 'Z')\n"
424 " c1 += 'a' - 'A';\n"
425 " if (c2 >= 'A' && c2 <= 'Z')\n"
426 " c2 += 'a' - 'A';\n"
427 " if (c1 == c2)\n"
428 " {\n"
429 " n--;\n"
430 " continue;\n"
431 " }\n"
432 " return (int)c1 - (int)c2;\n"
433 " }\n"
434 " return 0;\n"
435 "}\n");
436 #endif
437 printf ("#endif\n\n");
438}
439
440/* ------------------------------------------------------------------------- */
441
442/* Outputs a keyword, as a string: enclosed in double quotes, escaping
443 backslashes, double quote and unprintable characters. */
444
445static void
446output_string (const char *key, int len)
447{
448 putchar ('"');
449 for (; len > 0; len--)
450 {
451 unsigned char c = static_cast<unsigned char>(*key++);
452 if (isprint (c))
453 {
454 if (c == '"' || c == '\\')
455 putchar ('\\');
456 putchar (c);
457 }
458 else
459 {
460 /* Use octal escapes, not hexadecimal escapes, because some old
461 C compilers didn't understand hexadecimal escapes, and because
462 hexadecimal escapes are not limited to 2 digits, thus needing
463 special care if the following character happens to be a digit. */
464 putchar ('\\');
465 putchar ('0' + ((c >> 6) & 7));
466 putchar ('0' + ((c >> 3) & 7));
467 putchar ('0' + (c & 7));
468 }
469 }
470 putchar ('"');
471}
472
473/* ------------------------------------------------------------------------- */
474
475/* Outputs a #line directive, referring to the given line number. */
476
477static void
478output_line_directive (unsigned int lineno)
479{
480 const char *file_name = option.get_input_file_name ();
481 if (file_name != NULL)
482 {
483 printf ("#line %u ", lineno);
484 output_string (file_name, strlen (file_name));
485 printf ("\n");
486 }
487}
488
489/* ------------------------------------------------------------------------- */
490
491/* Outputs a type and a const specifier (i.e. "const " or "").
492 The output is terminated with a space. */
493
494static void
495output_const_type (const char *const_string, const char *type_string)
496{
497 if (type_string[strlen(type_string)-1] == '*')
498 /* For pointer types, put the 'const' after the type. */
499 printf ("%s %s", type_string, const_string);
500 else
501 /* For scalar or struct types, put the 'const' before the type. */
502 printf ("%s%s ", const_string, type_string);
503}
504
505/* ----------------------- Output_Expr and subclasses ----------------------- */
506
507/* This class outputs a general expression. */
508
509struct Output_Expr
510{
511 virtual void output_expr () const = 0;
512 Output_Expr () {}
513 virtual ~Output_Expr () {}
514};
515
516/* This class outputs an expression formed by a single string. */
517
518struct Output_Expr1 : public Output_Expr
519{
520 virtual void output_expr () const;
521 Output_Expr1 (const char *piece1) : _p1 (piece1) {}
522 virtual ~Output_Expr1 () {}
523private:
524 const char *_p1;
525};
526
527void Output_Expr1::output_expr () const
528{
529 printf ("%s", _p1);
530}
531
532#if 0 /* unused */
533
534/* This class outputs an expression formed by the concatenation of two
535 strings. */
536
537struct Output_Expr2 : public Output_Expr
538{
539 virtual void output_expr () const;
540 Output_Expr2 (const char *piece1, const char *piece2)
541 : _p1 (piece1), _p2 (piece2) {}
542 virtual ~Output_Expr2 () {}
543private:
544 const char *_p1;
545 const char *_p2;
546};
547
548void Output_Expr2::output_expr () const
549{
550 printf ("%s%s", _p1, _p2);
551}
552
553#endif
554
555/* --------------------- Output_Compare and subclasses --------------------- */
556
557/* This class outputs a comparison expression. */
558
559struct Output_Compare
560{
561 /* Outputs the comparison expression.
562 expr1 outputs a simple expression of type 'const char *' referring to
563 the string being looked up. expr2 outputs a simple expression of type
564 'const char *' referring to the constant string stored in the gperf
565 generated hash table. */
566 virtual void output_comparison (const Output_Expr& expr1,
567 const Output_Expr& expr2) const = 0;
568 /* Outputs the comparison expression for the first byte.
569 Returns true if the this comparison is complete. */
570 bool output_firstchar_comparison (const Output_Expr& expr1,
571 const Output_Expr& expr2) const;
572 Output_Compare () {}
573 virtual ~Output_Compare () {}
574};
575
576bool Output_Compare::output_firstchar_comparison (const Output_Expr& expr1,
577 const Output_Expr& expr2) const
578{
579 /* First, we emit a comparison of the first byte of the two strings.
580 This catches most cases where the string being looked up is not in the
581 hash table but happens to have the same hash code as an element of the
582 hash table. */
583 if (option[UPPERLOWER])
584 {
585 /* Incomplete comparison, just for speedup. */
586 printf ("(((unsigned char)*");
587 expr1.output_expr ();
588 printf (" ^ (unsigned char)*");
589 expr2.output_expr ();
590 printf (") & ~32) == 0");
591 return false;
592 }
593 else
594 {
595 /* Complete comparison. */
596 printf ("*");
597 expr1.output_expr ();
598 printf (" == *");
599 expr2.output_expr ();
600 return true;
601 }
602}
603
604/* This class outputs a comparison using strcmp. */
605
606struct Output_Compare_Strcmp : public Output_Compare
607{
608 virtual void output_comparison (const Output_Expr& expr1,
609 const Output_Expr& expr2) const;
610 Output_Compare_Strcmp () {}
611 virtual ~Output_Compare_Strcmp () {}
612};
613
614void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
615 const Output_Expr& expr2) const
616{
617 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
618 printf (" && !");
619 if (option[UPPERLOWER])
620 printf ("gperf_case_");
621 printf ("strcmp (");
622 if (firstchar_done)
623 {
624 expr1.output_expr ();
625 printf (" + 1, ");
626 expr2.output_expr ();
627 printf (" + 1");
628 }
629 else
630 {
631 expr1.output_expr ();
632 printf (", ");
633 expr2.output_expr ();
634 }
635 printf (")");
636}
637
638/* This class outputs a comparison using strncmp.
639 Note that the length of expr1 will be available through the local variable
640 'len'. */
641
642struct Output_Compare_Strncmp : public Output_Compare
643{
644 virtual void output_comparison (const Output_Expr& expr1,
645 const Output_Expr& expr2) const;
646 Output_Compare_Strncmp () {}
647 virtual ~Output_Compare_Strncmp () {}
648};
649
650void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
651 const Output_Expr& expr2) const
652{
653 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
654 printf (" && !");
655 if (option[UPPERLOWER])
656 printf ("gperf_case_");
657 printf ("strncmp (");
658 if (firstchar_done)
659 {
660 expr1.output_expr ();
661 printf (" + 1, ");
662 expr2.output_expr ();
663 printf (" + 1, len - 1");
664 }
665 else
666 {
667 expr1.output_expr ();
668 printf (", ");
669 expr2.output_expr ();
670 printf (", len");
671 }
672 printf (") && ");
673 expr2.output_expr ();
674 printf ("[len] == '\\0'");
675}
676
677/* This class outputs a comparison using memcmp.
678 Note that the length of expr1 (available through the local variable 'len')
679 must be verified to be equal to the length of expr2 prior to this
680 comparison. */
681
682struct Output_Compare_Memcmp : public Output_Compare
683{
684 virtual void output_comparison (const Output_Expr& expr1,
685 const Output_Expr& expr2) const;
686 Output_Compare_Memcmp () {}
687 virtual ~Output_Compare_Memcmp () {}
688};
689
690void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
691 const Output_Expr& expr2) const
692{
693 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
694 printf (" && !");
695 if (option[UPPERLOWER])
696 printf ("gperf_case_");
697 printf ("memcmp (");
698 if (firstchar_done)
699 {
700 expr1.output_expr ();
701 printf (" + 1, ");
702 expr2.output_expr ();
703 printf (" + 1, len - 1");
704 }
705 else
706 {
707 expr1.output_expr ();
708 printf (", ");
709 expr2.output_expr ();
710 printf (", len");
711 }
712 printf (")");
713}
714
715/* ------------------------------------------------------------------------- */
716
717/* Generates a C expression for an asso_values[] reference. */
718
719void
720Output::output_asso_values_ref (int pos) const
721{
722 printf ("asso_values[");
723 /* Always cast to unsigned char. This is necessary when the alpha_inc
724 is nonzero, and also avoids a gcc warning "subscript has type 'char'". */
725 printf ("(unsigned char)");
726 if (pos == Positions::LASTCHAR)
727 printf ("str[len - 1]");
728 else
729 {
730 printf ("str[%d]", pos);
731 if (_alpha_inc[pos])
732 printf ("+%u", _alpha_inc[pos]);
733 }
734 printf ("]");
735}
736
737/* Generates C code for the hash function that returns the
738 proper encoding for each keyword.
739 The hash function has the signature
740 unsigned int <hash> (const char *str, unsigned int len). */
741
742void
743Output::output_hash_function () const
744{
745 /* Output the function's head. */
746 if (option[CPLUSPLUS])
747 printf ("inline ");
748 else if (option[KRC] | option[C] | option[ANSIC])
749 printf ("#ifdef __GNUC__\n"
750 "__inline\n"
751 "#else\n"
752 "#ifdef __cplusplus\n"
753 "inline\n"
754 "#endif\n"
755 "#endif\n");
756
757 if (/* The function does not use the 'str' argument? */
758 _key_positions.get_size() == 0
759 || /* The function uses 'str', but not the 'len' argument? */
760 (option[NOLENGTH]
761 && _key_positions[0] < _min_key_len
762 && _key_positions[_key_positions.get_size() - 1] != Positions::LASTCHAR))
763 /* Pacify lint. */
764 printf ("/*ARGSUSED*/\n");
765
766 if (option[KRC] | option[C] | option[ANSIC])
767 printf ("static ");
768 printf ("unsigned int\n");
769 if (option[CPLUSPLUS])
770 printf ("%s::", option.get_class_name ());
771 printf ("%s ", option.get_hash_name ());
772 printf (option[KRC] ?
773 "(str, len)\n"
774 " register char *str;\n"
|
879 option[NOLENGTH] ? "len" : "hval");
880
881 while (key_pos != Positions::LASTCHAR && key_pos >= _max_key_len)
882 if ((key_pos = iter.next ()) == PositionIterator::EOS)
883 break;
884
885 if (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR)
886 {
887 int i = key_pos;
888 do
889 {
890 if (i > key_pos)
891 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
892 for ( ; i > key_pos; i--)
893 printf (" case %d:\n", i);
894
895 printf (" hval += ");
896 output_asso_values_ref (key_pos);
897 printf (";\n");
898
899 key_pos = iter.next ();
900 }
901 while (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR);
902
903 if (i >= _min_key_len)
904 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
905 for ( ; i >= _min_key_len; i--)
906 printf (" case %d:\n", i);
907 }
908
909 printf (" break;\n"
910 " }\n"
911 " return hval");
912 if (key_pos == Positions::LASTCHAR)
913 {
914 printf (" + ");
915 output_asso_values_ref (Positions::LASTCHAR);
916 }
917 printf (";\n");
918 }
919 }
920 printf ("}\n\n");
921}
922
923/* ------------------------------------------------------------------------- */
924
925/* Prints out a table of keyword lengths, for use with the
926 comparison code in generated function 'in_word_set'.
927 Only called if option[LENTABLE]. */
928
929void
930Output::output_keylength_table () const
931{
932 const int columns = 14;
933 const char * const indent = option[GLOBAL] ? "" : " ";
934
935 printf ("%sstatic %s%s %s[] =\n"
936 "%s {",
937 indent, const_readonly_array,
938 smallest_integral_type (_max_key_len),
939 option.get_lengthtable_name (),
940 indent);
941
942 /* Generate an array of lengths, similar to output_keyword_table. */
943 int index;
944 int column;
945 KeywordExt_List *temp;
946
947 column = 0;
948 for (temp = _head, index = 0; temp; temp = temp->rest())
949 {
950 KeywordExt *keyword = temp->first();
951
952 /* If generating a switch statement, and there is no user defined type,
953 we generate non-duplicates directly in the code. Only duplicates go
954 into the table. */
955 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
956 continue;
957
958 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
959 {
960 /* Some blank entries. */
961 for ( ; index < keyword->_hash_value; index++)
962 {
963 if (index > 0)
964 printf (",");
965 if ((column++ % columns) == 0)
966 printf ("\n%s ", indent);
967 printf ("%3d", 0);
968 }
969 }
970
971 if (index > 0)
972 printf (",");
973 if ((column++ % columns) == 0)
974 printf("\n%s ", indent);
975 printf ("%3d", keyword->_allchars_length);
976 index++;
977
978 /* Deal with duplicates specially. */
979 if (keyword->_duplicate_link) // implies option[DUP]
980 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
981 {
982 printf (",");
983 if ((column++ % columns) == 0)
984 printf("\n%s ", indent);
985 printf ("%3d", links->_allchars_length);
986 index++;
987 }
988 }
989
990 printf ("\n%s };\n", indent);
991 if (option[GLOBAL])
992 printf ("\n");
993}
994
995/* ------------------------------------------------------------------------- */
996
997/* Prints out the string pool, containing the strings of the keyword table.
998 Only called if option[SHAREDLIB]. */
999
1000void
1001Output::output_string_pool () const
1002{
1003 const char * const indent = option[TYPE] || option[GLOBAL] ? "" : " ";
1004 int index;
1005 KeywordExt_List *temp;
1006
1007 printf ("%sstruct %s_t\n"
1008 "%s {\n",
1009 indent, option.get_stringpool_name (), indent);
1010 for (temp = _head, index = 0; temp; temp = temp->rest())
1011 {
1012 KeywordExt *keyword = temp->first();
1013
1014 /* If generating a switch statement, and there is no user defined type,
1015 we generate non-duplicates directly in the code. Only duplicates go
1016 into the table. */
1017 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1018 continue;
1019
1020 if (!option[SWITCH] && !option[DUP])
1021 index = keyword->_hash_value;
1022
1023 printf ("%s char %s_str%d[sizeof(",
1024 indent, option.get_stringpool_name (), index);
1025 output_string (keyword->_allchars, keyword->_allchars_length);
1026 printf (")];\n");
1027
1028 /* Deal with duplicates specially. */
1029 if (keyword->_duplicate_link) // implies option[DUP]
1030 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1031 if (!(links->_allchars_length == keyword->_allchars_length
1032 && memcmp (links->_allchars, keyword->_allchars,
1033 keyword->_allchars_length) == 0))
1034 {
1035 index++;
1036 printf ("%s char %s_str%d[sizeof(",
1037 indent, option.get_stringpool_name (), index);
1038 output_string (links->_allchars, links->_allchars_length);
1039 printf (")];\n");
1040 }
1041
1042 index++;
1043 }
1044 printf ("%s };\n",
1045 indent);
1046
1047 printf ("%sstatic %sstruct %s_t %s_contents =\n"
1048 "%s {\n",
1049 indent, const_readonly_array, option.get_stringpool_name (),
1050 option.get_stringpool_name (), indent);
1051 for (temp = _head, index = 0; temp; temp = temp->rest())
1052 {
1053 KeywordExt *keyword = temp->first();
1054
1055 /* If generating a switch statement, and there is no user defined type,
1056 we generate non-duplicates directly in the code. Only duplicates go
1057 into the table. */
1058 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1059 continue;
1060
1061 if (index > 0)
1062 printf (",\n");
1063
1064 if (!option[SWITCH] && !option[DUP])
1065 index = keyword->_hash_value;
1066
1067 printf ("%s ",
1068 indent);
1069 output_string (keyword->_allchars, keyword->_allchars_length);
1070
1071 /* Deal with duplicates specially. */
1072 if (keyword->_duplicate_link) // implies option[DUP]
1073 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1074 if (!(links->_allchars_length == keyword->_allchars_length
1075 && memcmp (links->_allchars, keyword->_allchars,
1076 keyword->_allchars_length) == 0))
1077 {
1078 index++;
1079 printf (",\n");
1080 printf ("%s ",
1081 indent);
1082 output_string (links->_allchars, links->_allchars_length);
1083 }
1084
1085 index++;
1086 }
1087 if (index > 0)
1088 printf ("\n");
1089 printf ("%s };\n",
1090 indent);
1091 printf ("%s#define %s ((%schar *) &%s_contents)\n",
1092 indent, option.get_stringpool_name (), const_always,
1093 option.get_stringpool_name ());
1094 if (option[GLOBAL])
1095 printf ("\n");
1096}
1097
1098/* ------------------------------------------------------------------------- */
1099
1100static void
1101output_keyword_entry (KeywordExt *temp, int stringpool_index, const char *indent)
1102{
1103 if (option[TYPE])
1104 output_line_directive (temp->_lineno);
1105 printf ("%s ", indent);
1106 if (option[TYPE])
1107 printf ("{");
1108 if (option[SHAREDLIB])
1109 printf("offsetof(struct %s_t, %s_str%d)", option.get_stringpool_name (), option.get_stringpool_name (), stringpool_index);
1110 else
1111 output_string (temp->_allchars, temp->_allchars_length);
1112 if (option[TYPE])
1113 {
1114 if (strlen (temp->_rest) > 0)
1115 printf (",%s", temp->_rest);
1116 printf ("}");
1117 }
1118 if (option[DEBUG])
1119 printf (" /* hash value = %d, index = %d */",
1120 temp->_hash_value, temp->_final_index);
1121}
1122
1123static void
1124output_keyword_blank_entries (int count, const char *indent)
1125{
1126 int columns;
1127 if (option[TYPE])
1128 {
1129 columns = 58 / (4 + (option[SHAREDLIB] ? 2 : option[NULLSTRINGS] ? 8 : 2)
1130 + strlen (option.get_initializer_suffix()));
1131 if (columns == 0)
1132 columns = 1;
1133 }
1134 else
1135 {
1136 columns = (option[SHAREDLIB] ? 9 : option[NULLSTRINGS] ? 4 : 9);
1137 }
1138 int column = 0;
1139 for (int i = 0; i < count; i++)
1140 {
1141 if ((column % columns) == 0)
1142 {
1143 if (i > 0)
1144 printf (",\n");
1145 printf ("%s ", indent);
1146 }
1147 else
1148 {
1149 if (i > 0)
1150 printf (", ");
1151 }
1152 if (option[TYPE])
1153 printf ("{");
1154 if (option[SHAREDLIB])
1155 printf ("-1");
1156 else
1157 {
1158 if (option[NULLSTRINGS])
1159 printf ("(char*)0");
1160 else
1161 printf ("\"\"");
1162 }
1163 if (option[TYPE])
1164 printf ("%s}", option.get_initializer_suffix());
1165 column++;
1166 }
1167}
1168
1169/* Prints out the array containing the keywords for the hash function. */
1170
1171void
1172Output::output_keyword_table () const
1173{
1174 const char *indent = option[GLOBAL] ? "" : " ";
1175 int index;
1176 KeywordExt_List *temp;
1177
1178 printf ("%sstatic ",
1179 indent);
1180 output_const_type (const_readonly_array, _wordlist_eltype);
1181 printf ("%s[] =\n"
1182 "%s {\n",
1183 option.get_wordlist_name (),
1184 indent);
1185
1186 /* Generate an array of reserved words at appropriate locations. */
1187
1188 for (temp = _head, index = 0; temp; temp = temp->rest())
1189 {
1190 KeywordExt *keyword = temp->first();
1191
1192 /* If generating a switch statement, and there is no user defined type,
1193 we generate non-duplicates directly in the code. Only duplicates go
1194 into the table. */
1195 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1196 continue;
1197
1198 if (index > 0)
1199 printf (",\n");
1200
1201 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
1202 {
1203 /* Some blank entries. */
1204 output_keyword_blank_entries (keyword->_hash_value - index, indent);
1205 printf (",\n");
1206 index = keyword->_hash_value;
1207 }
1208
1209 keyword->_final_index = index;
1210
1211 output_keyword_entry (keyword, index, indent);
1212
1213 /* Deal with duplicates specially. */
1214 if (keyword->_duplicate_link) // implies option[DUP]
1215 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1216 {
1217 links->_final_index = ++index;
1218 printf (",\n");
1219 int stringpool_index =
1220 (links->_allchars_length == keyword->_allchars_length
1221 && memcmp (links->_allchars, keyword->_allchars,
1222 keyword->_allchars_length) == 0
1223 ? keyword->_final_index
1224 : links->_final_index);
1225 output_keyword_entry (links, stringpool_index, indent);
1226 }
1227
1228 index++;
1229 }
1230 if (index > 0)
1231 printf ("\n");
1232
1233 printf ("%s };\n\n", indent);
1234}
1235
1236/* ------------------------------------------------------------------------- */
1237
1238/* Generates the large, sparse table that maps hash values into
1239 the smaller, contiguous range of the keyword table. */
1240
1241void
1242Output::output_lookup_array () const
1243{
1244 if (option[DUP])
1245 {
1246 const int DEFAULT_VALUE = -1;
1247
1248 /* Because of the way output_keyword_table works, every duplicate set is
1249 stored contiguously in the wordlist array. */
1250 struct duplicate_entry
1251 {
1252 int hash_value; /* Hash value for this particular duplicate set. */
1253 int index; /* Index into the main keyword storage array. */
1254 int count; /* Number of consecutive duplicates at this index. */
1255 };
1256
1257 duplicate_entry *duplicates = new duplicate_entry[_total_duplicates];
1258 int *lookup_array = new int[_max_hash_value + 1 + 2*_total_duplicates];
1259 int lookup_array_size = _max_hash_value + 1;
1260 duplicate_entry *dup_ptr = &duplicates[0];
1261 int *lookup_ptr = &lookup_array[_max_hash_value + 1 + 2*_total_duplicates];
1262
1263 while (lookup_ptr > lookup_array)
1264 *--lookup_ptr = DEFAULT_VALUE;
1265
1266 /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1267
1268 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
1269 {
1270 int hash_value = temp->first()->_hash_value;
1271 lookup_array[hash_value] = temp->first()->_final_index;
1272 if (option[DEBUG])
1273 fprintf (stderr, "keyword = %.*s, index = %d\n",
1274 temp->first()->_allchars_length, temp->first()->_allchars, temp->first()->_final_index);
1275 if (temp->first()->_duplicate_link)
1276 {
1277 /* Start a duplicate entry. */
1278 dup_ptr->hash_value = hash_value;
1279 dup_ptr->index = temp->first()->_final_index;
1280 dup_ptr->count = 1;
1281
1282 for (KeywordExt *ptr = temp->first()->_duplicate_link; ptr; ptr = ptr->_duplicate_link)
1283 {
1284 dup_ptr->count++;
1285 if (option[DEBUG])
1286 fprintf (stderr,
1287 "static linked keyword = %.*s, index = %d\n",
1288 ptr->_allchars_length, ptr->_allchars, ptr->_final_index);
1289 }
1290 assert (dup_ptr->count >= 2);
1291 dup_ptr++;
1292 }
1293 }
1294
1295 while (dup_ptr > duplicates)
1296 {
1297 dup_ptr--;
1298
1299 if (option[DEBUG])
1300 fprintf (stderr,
1301 "dup_ptr[%td]: hash_value = %d, index = %d, count = %d\n",
1302 dup_ptr - duplicates,
1303 dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1304
1305 int i;
1306 /* Start searching for available space towards the right part
1307 of the lookup array. */
1308 for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1309 if (lookup_array[i] == DEFAULT_VALUE
1310 && lookup_array[i + 1] == DEFAULT_VALUE)
1311 goto found_i;
1312 /* If we didn't find it to the right look to the left instead... */
1313 for (i = dup_ptr->hash_value-1; i >= 0; i--)
1314 if (lookup_array[i] == DEFAULT_VALUE
1315 && lookup_array[i + 1] == DEFAULT_VALUE)
1316 goto found_i;
1317 /* Append to the end of lookup_array. */
1318 i = lookup_array_size;
1319 lookup_array_size += 2;
1320 found_i:
1321 /* Put in an indirection from dup_ptr->_hash_value to i.
1322 At i and i+1 store dup_ptr->_final_index and dup_ptr->count. */
1323 assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1324 lookup_array[dup_ptr->hash_value] = - 1 - _total_keys - i;
1325 lookup_array[i] = - _total_keys + dup_ptr->index;
1326 lookup_array[i + 1] = - dup_ptr->count;
1327 /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1328 }
1329
1330 /* The values of the lookup array are now known. */
1331
1332 int min = INT_MAX;
1333 int max = INT_MIN;
1334 lookup_ptr = lookup_array + lookup_array_size;
1335 while (lookup_ptr > lookup_array)
1336 {
1337 int val = *--lookup_ptr;
1338 if (min > val)
1339 min = val;
1340 if (max < val)
1341 max = val;
1342 }
1343
1344 const char *indent = option[GLOBAL] ? "" : " ";
1345 printf ("%sstatic %s%s lookup[] =\n"
1346 "%s {",
1347 indent, const_readonly_array, smallest_integral_type (min, max),
1348 indent);
1349
1350 int field_width;
1351 /* Calculate maximum number of digits required for MIN..MAX. */
1352 {
1353 field_width = 2;
1354 for (int trunc = max; (trunc /= 10) > 0;)
1355 field_width++;
1356 }
1357 if (min < 0)
1358 {
1359 int neg_field_width = 2;
1360 for (int trunc = -min; (trunc /= 10) > 0;)
1361 neg_field_width++;
1362 neg_field_width++; /* account for the minus sign */
1363 if (field_width < neg_field_width)
1364 field_width = neg_field_width;
1365 }
1366
1367 const int columns = 42 / field_width;
1368 int column;
1369
1370 column = 0;
1371 for (int i = 0; i < lookup_array_size; i++)
1372 {
1373 if (i > 0)
1374 printf (",");
1375 if ((column++ % columns) == 0)
1376 printf("\n%s ", indent);
1377 printf ("%*d", field_width, lookup_array[i]);
1378 }
1379 printf ("\n%s };\n\n", indent);
1380
1381 delete[] duplicates;
1382 delete[] lookup_array;
1383 }
1384}
1385
1386/* ------------------------------------------------------------------------- */
1387
1388/* Generate all pools needed for the lookup function. */
1389
1390void
1391Output::output_lookup_pools () const
1392{
1393 if (option[SWITCH])
1394 {
1395 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1396 output_string_pool ();
1397 }
1398 else
1399 {
1400 output_string_pool ();
1401 }
1402}
1403
1404/* Generate all the tables needed for the lookup function. */
1405
1406void
1407Output::output_lookup_tables () const
1408{
1409 if (option[SWITCH])
1410 {
1411 /* Use the switch in place of lookup table. */
1412 if (option[LENTABLE] && (option[DUP] && _total_duplicates > 0))
1413 output_keylength_table ();
1414 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1415 output_keyword_table ();
1416 }
1417 else
1418 {
1419 /* Use the lookup table, in place of switch. */
1420 if (option[LENTABLE])
1421 output_keylength_table ();
1422 output_keyword_table ();
1423 output_lookup_array ();
1424 }
1425}
1426
1427/* ------------------------------------------------------------------------- */
1428
1429/* Output a single switch case (including duplicates). Advance list. */
1430
1431static KeywordExt_List *
1432output_switch_case (KeywordExt_List *list, int indent, int *jumps_away)
1433{
1434 if (option[DEBUG])
1435 printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1436 indent, "", list->first()->_hash_value, list->first()->_allchars_length, list->first()->_allchars);
1437
1438 if (option[DUP] && list->first()->_duplicate_link)
1439 {
1440 if (option[LENTABLE])
1441 printf ("%*slengthptr = &%s[%d];\n",
1442 indent, "", option.get_lengthtable_name (), list->first()->_final_index);
1443 printf ("%*swordptr = &%s[%d];\n",
1444 indent, "", option.get_wordlist_name (), list->first()->_final_index);
1445
1446 int count = 0;
1447 for (KeywordExt *links = list->first(); links; links = links->_duplicate_link)
1448 count++;
1449
1450 printf ("%*swordendptr = wordptr + %d;\n"
1451 "%*sgoto multicompare;\n",
1452 indent, "", count,
1453 indent, "");
1454 *jumps_away = 1;
1455 }
1456 else
1457 {
1458 if (option[LENTABLE])
1459 {
1460 printf ("%*sif (len == %d)\n"
1461 "%*s {\n",
1462 indent, "", list->first()->_allchars_length,
1463 indent, "");
1464 indent += 4;
1465 }
1466 printf ("%*sresword = ",
1467 indent, "");
1468 if (option[TYPE])
1469 printf ("&%s[%d]", option.get_wordlist_name (), list->first()->_final_index);
1470 else
1471 output_string (list->first()->_allchars, list->first()->_allchars_length);
1472 printf (";\n");
1473 printf ("%*sgoto compare;\n",
1474 indent, "");
1475 if (option[LENTABLE])
1476 {
1477 indent -= 4;
1478 printf ("%*s }\n",
1479 indent, "");
1480 }
1481 else
1482 *jumps_away = 1;
1483 }
1484
1485 return list->rest();
1486}
1487
1488/* Output a total of size cases, grouped into num_switches switch statements,
1489 where 0 < num_switches <= size. */
1490
1491static void
1492output_switches (KeywordExt_List *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1493{
1494 if (option[DEBUG])
1495 printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1496 indent, "", min_hash_value, max_hash_value, size);
1497
1498 if (num_switches > 1)
1499 {
1500 int part1 = num_switches / 2;
1501 int part2 = num_switches - part1;
1502 int size1 = static_cast<int>(static_cast<double>(size) / static_cast<double>(num_switches) * static_cast<double>(part1) + 0.5);
1503 int size2 = size - size1;
1504
1505 KeywordExt_List *temp = list;
1506 for (int count = size1; count > 0; count--)
1507 temp = temp->rest();
1508
1509 printf ("%*sif (key < %d)\n"
1510 "%*s {\n",
1511 indent, "", temp->first()->_hash_value,
1512 indent, "");
1513
1514 output_switches (list, part1, size1, min_hash_value, temp->first()->_hash_value-1, indent+4);
1515
1516 printf ("%*s }\n"
1517 "%*selse\n"
1518 "%*s {\n",
1519 indent, "", indent, "", indent, "");
1520
1521 output_switches (temp, part2, size2, temp->first()->_hash_value, max_hash_value, indent+4);
1522
1523 printf ("%*s }\n",
1524 indent, "");
1525 }
1526 else
1527 {
1528 /* Output a single switch. */
1529 int lowest_case_value = list->first()->_hash_value;
1530 if (size == 1)
1531 {
1532 int jumps_away = 0;
1533 assert (min_hash_value <= lowest_case_value);
1534 assert (lowest_case_value <= max_hash_value);
1535 if (min_hash_value == max_hash_value)
1536 output_switch_case (list, indent, &jumps_away);
1537 else
1538 {
1539 printf ("%*sif (key == %d)\n"
1540 "%*s {\n",
1541 indent, "", lowest_case_value,
1542 indent, "");
1543 output_switch_case (list, indent+4, &jumps_away);
1544 printf ("%*s }\n",
1545 indent, "");
1546 }
1547 }
1548 else
1549 {
1550 if (lowest_case_value == 0)
1551 printf ("%*sswitch (key)\n", indent, "");
1552 else
1553 printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1554 printf ("%*s {\n",
1555 indent, "");
1556 for (; size > 0; size--)
1557 {
1558 int jumps_away = 0;
1559 printf ("%*s case %d:\n",
1560 indent, "", list->first()->_hash_value - lowest_case_value);
1561 list = output_switch_case (list, indent+6, &jumps_away);
1562 if (!jumps_away)
1563 printf ("%*s break;\n",
1564 indent, "");
1565 }
1566 printf ("%*s }\n",
1567 indent, "");
1568 }
1569 }
1570}
1571
1572/* Generates C code to perform the keyword lookup. */
1573
1574void
1575Output::output_lookup_function_body (const Output_Compare& comparison) const
1576{
1577 printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1578 " {\n"
1579 " register int key = %s (str, len);\n\n",
1580 option.get_hash_name ());
1581
1582 if (option[SWITCH])
1583 {
1584 int switch_size = num_hash_values ();
1585 int num_switches = option.get_total_switches ();
1586 if (num_switches > switch_size)
1587 num_switches = switch_size;
1588
1589 printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1590 " {\n");
1591 if (option[DUP] && _total_duplicates > 0)
1592 {
1593 if (option[LENTABLE])
1594 printf (" register %s%s *lengthptr;\n",
1595 const_always, smallest_integral_type (_max_key_len));
1596 printf (" register ");
1597 output_const_type (const_readonly_array, _wordlist_eltype);
1598 printf ("*wordptr;\n");
1599 printf (" register ");
1600 output_const_type (const_readonly_array, _wordlist_eltype);
1601 printf ("*wordendptr;\n");
1602 }
1603 if (option[TYPE])
1604 {
1605 printf (" register ");
1606 output_const_type (const_readonly_array, _struct_tag);
1607 printf ("*resword;\n\n");
1608 }
1609 else
1610 printf (" register %sresword;\n\n",
1611 _struct_tag);
1612
1613 output_switches (_head, num_switches, switch_size, _min_hash_value, _max_hash_value, 10);
1614
1615 printf (" return 0;\n");
1616 if (option[DUP] && _total_duplicates > 0)
1617 {
1618 int indent = 8;
1619 printf ("%*smulticompare:\n"
1620 "%*s while (wordptr < wordendptr)\n"
1621 "%*s {\n",
1622 indent, "", indent, "", indent, "");
1623 if (option[LENTABLE])
1624 {
1625 printf ("%*s if (len == *lengthptr)\n"
1626 "%*s {\n",
1627 indent, "", indent, "");
1628 indent += 4;
1629 }
1630 printf ("%*s register %schar *s = ",
1631 indent, "", const_always);
1632 if (option[TYPE])
1633 printf ("wordptr->%s", option.get_slot_name ());
1634 else
1635 printf ("*wordptr");
1636 if (option[SHAREDLIB])
1637 printf (" + %s",
1638 option.get_stringpool_name ());
1639 printf (";\n\n"
1640 "%*s if (",
1641 indent, "");
1642 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1643 printf (")\n"
1644 "%*s return %s;\n",
1645 indent, "",
1646 option[TYPE] ? "wordptr" : "s");
1647 if (option[LENTABLE])
1648 {
1649 indent -= 4;
1650 printf ("%*s }\n",
1651 indent, "");
1652 }
1653 if (option[LENTABLE])
1654 printf ("%*s lengthptr++;\n",
1655 indent, "");
1656 printf ("%*s wordptr++;\n"
1657 "%*s }\n"
1658 "%*s return 0;\n",
1659 indent, "", indent, "", indent, "");
1660 }
1661 printf (" compare:\n");
1662 if (option[TYPE])
1663 {
1664 printf (" {\n"
1665 " register %schar *s = resword->%s",
1666 const_always, option.get_slot_name ());
1667 if (option[SHAREDLIB])
1668 printf (" + %s",
1669 option.get_stringpool_name ());
1670 printf (";\n\n"
1671 " if (");
1672 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1673 printf (")\n"
1674 " return resword;\n"
1675 " }\n");
1676 }
1677 else
1678 {
1679 printf (" if (");
1680 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1681 printf (")\n"
1682 " return resword;\n");
1683 }
1684 printf (" }\n");
1685 }
1686 else
1687 {
1688 printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n");
1689
1690 if (option[DUP])
1691 {
1692 int indent = 8;
1693 printf ("%*s{\n"
1694 "%*s register int index = lookup[key];\n\n"
1695 "%*s if (index >= 0)\n",
1696 indent, "", indent, "", indent, "");
1697 if (option[LENTABLE])
1698 {
1699 printf ("%*s {\n"
1700 "%*s if (len == %s[index])\n",
1701 indent, "", indent, "", option.get_lengthtable_name ());
1702 indent += 4;
1703 }
1704 printf ("%*s {\n"
1705 "%*s register %schar *s = %s[index]",
1706 indent, "",
1707 indent, "", const_always, option.get_wordlist_name ());
1708 if (option[TYPE])
1709 printf (".%s", option.get_slot_name ());
1710 if (option[SHAREDLIB])
1711 printf (" + %s",
1712 option.get_stringpool_name ());
1713 printf (";\n\n"
1714 "%*s if (",
1715 indent, "");
1716 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1717 printf (")\n"
1718 "%*s return ",
1719 indent, "");
1720 if (option[TYPE])
1721 printf ("&%s[index]", option.get_wordlist_name ());
1722 else
1723 printf ("s");
1724 printf (";\n"
1725 "%*s }\n",
1726 indent, "");
1727 if (option[LENTABLE])
1728 {
1729 indent -= 4;
1730 printf ("%*s }\n", indent, "");
1731 }
1732 if (_total_duplicates > 0)
1733 {
1734 printf ("%*s else if (index < -TOTAL_KEYWORDS)\n"
1735 "%*s {\n"
1736 "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1737 indent, "", indent, "", indent, "");
1738 if (option[LENTABLE])
1739 printf ("%*s register %s%s *lengthptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1740 indent, "", const_always, smallest_integral_type (_max_key_len),
1741 option.get_lengthtable_name ());
1742 printf ("%*s register ",
1743 indent, "");
1744 output_const_type (const_readonly_array, _wordlist_eltype);
1745 printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1746 option.get_wordlist_name ());
1747 printf ("%*s register ",
1748 indent, "");
1749 output_const_type (const_readonly_array, _wordlist_eltype);
1750 printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1751 printf ("%*s while (wordptr < wordendptr)\n"
1752 "%*s {\n",
1753 indent, "", indent, "");
1754 if (option[LENTABLE])
1755 {
1756 printf ("%*s if (len == *lengthptr)\n"
1757 "%*s {\n",
1758 indent, "", indent, "");
1759 indent += 4;
1760 }
1761 printf ("%*s register %schar *s = ",
1762 indent, "", const_always);
1763 if (option[TYPE])
1764 printf ("wordptr->%s", option.get_slot_name ());
1765 else
1766 printf ("*wordptr");
1767 if (option[SHAREDLIB])
1768 printf (" + %s",
1769 option.get_stringpool_name ());
1770 printf (";\n\n"
1771 "%*s if (",
1772 indent, "");
1773 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1774 printf (")\n"
1775 "%*s return %s;\n",
1776 indent, "",
1777 option[TYPE] ? "wordptr" : "s");
1778 if (option[LENTABLE])
1779 {
1780 indent -= 4;
1781 printf ("%*s }\n",
1782 indent, "");
1783 }
1784 if (option[LENTABLE])
1785 printf ("%*s lengthptr++;\n",
1786 indent, "");
1787 printf ("%*s wordptr++;\n"
1788 "%*s }\n"
1789 "%*s }\n",
1790 indent, "", indent, "", indent, "");
1791 }
1792 printf ("%*s}\n",
1793 indent, "");
1794 }
1795 else
1796 {
1797 int indent = 8;
1798 if (option[LENTABLE])
1799 {
1800 printf ("%*sif (len == %s[key])\n",
1801 indent, "", option.get_lengthtable_name ());
1802 indent += 2;
1803 }
1804
1805 if (option[SHAREDLIB])
1806 {
1807 if (!option[LENTABLE])
1808 {
1809 printf ("%*s{\n"
1810 "%*s register int o = %s[key]",
1811 indent, "",
1812 indent, "", option.get_wordlist_name ());
1813 if (option[TYPE])
1814 printf (".%s", option.get_slot_name ());
1815 printf (";\n"
1816 "%*s if (o >= 0)\n"
1817 "%*s {\n",
1818 indent, "",
1819 indent, "");
1820 indent += 4;
1821 printf ("%*s register %schar *s = o",
1822 indent, "", const_always);
1823 }
1824 else
1825 {
1826 /* No need for the (o >= 0) test, because the
1827 (len == lengthtable[key]) test already guarantees that
1828 key points to nonempty table entry. */
1829 printf ("%*s{\n"
1830 "%*s register %schar *s = %s[key]",
1831 indent, "",
1832 indent, "", const_always,
1833 option.get_wordlist_name ());
1834 if (option[TYPE])
1835 printf (".%s", option.get_slot_name ());
1836 }
1837 printf (" + %s",
1838 option.get_stringpool_name ());
1839 }
1840 else
1841 {
1842 printf ("%*s{\n"
1843 "%*s register %schar *s = %s[key]",
1844 indent, "",
1845 indent, "", const_always, option.get_wordlist_name ());
1846 if (option[TYPE])
1847 printf (".%s", option.get_slot_name ());
1848 }
1849
1850 printf (";\n\n"
1851 "%*s if (",
1852 indent, "");
1853 if (!option[SHAREDLIB] && option[NULLSTRINGS])
1854 printf ("s && ");
1855 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1856 printf (")\n"
1857 "%*s return ",
1858 indent, "");
1859 if (option[TYPE])
1860 printf ("&%s[key]", option.get_wordlist_name ());
1861 else
1862 printf ("s");
1863 printf (";\n");
1864 if (option[SHAREDLIB] && !option[LENTABLE])
1865 {
1866 indent -= 4;
1867 printf ("%*s }\n",
1868 indent, "");
1869 }
1870 printf ("%*s}\n",
1871 indent, "");
1872 }
1873 }
1874 printf (" }\n"
1875 " return 0;\n");
1876}
1877
1878/* Generates C code for the lookup function. */
1879
1880void
1881Output::output_lookup_function () const
1882{
1883 /* Output the function's head. */
1884 if (option[KRC] | option[C] | option[ANSIC])
1885 /* GCC 4.3 and above with -std=c99 or -std=gnu99 implements ISO C99
1886 inline semantics, unless -fgnu89-inline is used. It defines a macro
1887 __GNUC_STDC_INLINE__ to indicate this situation. */
1888 printf ("#ifdef __GNUC__\n"
1889 "__inline\n"
1890 "#ifdef __GNUC_STDC_INLINE__\n"
1891 "__attribute__ ((__gnu_inline__))\n"
1892 "#endif\n"
1893 "#endif\n");
1894
1895 printf ("%s%s\n",
1896 const_for_struct, _return_type);
1897 if (option[CPLUSPLUS])
1898 printf ("%s::", option.get_class_name ());
1899 printf ("%s ", option.get_function_name ());
1900 printf (option[KRC] ?
1901 "(str, len)\n"
1902 " register char *str;\n"
| 879 option[NOLENGTH] ? "len" : "hval");
880
881 while (key_pos != Positions::LASTCHAR && key_pos >= _max_key_len)
882 if ((key_pos = iter.next ()) == PositionIterator::EOS)
883 break;
884
885 if (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR)
886 {
887 int i = key_pos;
888 do
889 {
890 if (i > key_pos)
891 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
892 for ( ; i > key_pos; i--)
893 printf (" case %d:\n", i);
894
895 printf (" hval += ");
896 output_asso_values_ref (key_pos);
897 printf (";\n");
898
899 key_pos = iter.next ();
900 }
901 while (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR);
902
903 if (i >= _min_key_len)
904 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
905 for ( ; i >= _min_key_len; i--)
906 printf (" case %d:\n", i);
907 }
908
909 printf (" break;\n"
910 " }\n"
911 " return hval");
912 if (key_pos == Positions::LASTCHAR)
913 {
914 printf (" + ");
915 output_asso_values_ref (Positions::LASTCHAR);
916 }
917 printf (";\n");
918 }
919 }
920 printf ("}\n\n");
921}
922
923/* ------------------------------------------------------------------------- */
924
925/* Prints out a table of keyword lengths, for use with the
926 comparison code in generated function 'in_word_set'.
927 Only called if option[LENTABLE]. */
928
929void
930Output::output_keylength_table () const
931{
932 const int columns = 14;
933 const char * const indent = option[GLOBAL] ? "" : " ";
934
935 printf ("%sstatic %s%s %s[] =\n"
936 "%s {",
937 indent, const_readonly_array,
938 smallest_integral_type (_max_key_len),
939 option.get_lengthtable_name (),
940 indent);
941
942 /* Generate an array of lengths, similar to output_keyword_table. */
943 int index;
944 int column;
945 KeywordExt_List *temp;
946
947 column = 0;
948 for (temp = _head, index = 0; temp; temp = temp->rest())
949 {
950 KeywordExt *keyword = temp->first();
951
952 /* If generating a switch statement, and there is no user defined type,
953 we generate non-duplicates directly in the code. Only duplicates go
954 into the table. */
955 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
956 continue;
957
958 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
959 {
960 /* Some blank entries. */
961 for ( ; index < keyword->_hash_value; index++)
962 {
963 if (index > 0)
964 printf (",");
965 if ((column++ % columns) == 0)
966 printf ("\n%s ", indent);
967 printf ("%3d", 0);
968 }
969 }
970
971 if (index > 0)
972 printf (",");
973 if ((column++ % columns) == 0)
974 printf("\n%s ", indent);
975 printf ("%3d", keyword->_allchars_length);
976 index++;
977
978 /* Deal with duplicates specially. */
979 if (keyword->_duplicate_link) // implies option[DUP]
980 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
981 {
982 printf (",");
983 if ((column++ % columns) == 0)
984 printf("\n%s ", indent);
985 printf ("%3d", links->_allchars_length);
986 index++;
987 }
988 }
989
990 printf ("\n%s };\n", indent);
991 if (option[GLOBAL])
992 printf ("\n");
993}
994
995/* ------------------------------------------------------------------------- */
996
997/* Prints out the string pool, containing the strings of the keyword table.
998 Only called if option[SHAREDLIB]. */
999
1000void
1001Output::output_string_pool () const
1002{
1003 const char * const indent = option[TYPE] || option[GLOBAL] ? "" : " ";
1004 int index;
1005 KeywordExt_List *temp;
1006
1007 printf ("%sstruct %s_t\n"
1008 "%s {\n",
1009 indent, option.get_stringpool_name (), indent);
1010 for (temp = _head, index = 0; temp; temp = temp->rest())
1011 {
1012 KeywordExt *keyword = temp->first();
1013
1014 /* If generating a switch statement, and there is no user defined type,
1015 we generate non-duplicates directly in the code. Only duplicates go
1016 into the table. */
1017 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1018 continue;
1019
1020 if (!option[SWITCH] && !option[DUP])
1021 index = keyword->_hash_value;
1022
1023 printf ("%s char %s_str%d[sizeof(",
1024 indent, option.get_stringpool_name (), index);
1025 output_string (keyword->_allchars, keyword->_allchars_length);
1026 printf (")];\n");
1027
1028 /* Deal with duplicates specially. */
1029 if (keyword->_duplicate_link) // implies option[DUP]
1030 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1031 if (!(links->_allchars_length == keyword->_allchars_length
1032 && memcmp (links->_allchars, keyword->_allchars,
1033 keyword->_allchars_length) == 0))
1034 {
1035 index++;
1036 printf ("%s char %s_str%d[sizeof(",
1037 indent, option.get_stringpool_name (), index);
1038 output_string (links->_allchars, links->_allchars_length);
1039 printf (")];\n");
1040 }
1041
1042 index++;
1043 }
1044 printf ("%s };\n",
1045 indent);
1046
1047 printf ("%sstatic %sstruct %s_t %s_contents =\n"
1048 "%s {\n",
1049 indent, const_readonly_array, option.get_stringpool_name (),
1050 option.get_stringpool_name (), indent);
1051 for (temp = _head, index = 0; temp; temp = temp->rest())
1052 {
1053 KeywordExt *keyword = temp->first();
1054
1055 /* If generating a switch statement, and there is no user defined type,
1056 we generate non-duplicates directly in the code. Only duplicates go
1057 into the table. */
1058 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1059 continue;
1060
1061 if (index > 0)
1062 printf (",\n");
1063
1064 if (!option[SWITCH] && !option[DUP])
1065 index = keyword->_hash_value;
1066
1067 printf ("%s ",
1068 indent);
1069 output_string (keyword->_allchars, keyword->_allchars_length);
1070
1071 /* Deal with duplicates specially. */
1072 if (keyword->_duplicate_link) // implies option[DUP]
1073 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1074 if (!(links->_allchars_length == keyword->_allchars_length
1075 && memcmp (links->_allchars, keyword->_allchars,
1076 keyword->_allchars_length) == 0))
1077 {
1078 index++;
1079 printf (",\n");
1080 printf ("%s ",
1081 indent);
1082 output_string (links->_allchars, links->_allchars_length);
1083 }
1084
1085 index++;
1086 }
1087 if (index > 0)
1088 printf ("\n");
1089 printf ("%s };\n",
1090 indent);
1091 printf ("%s#define %s ((%schar *) &%s_contents)\n",
1092 indent, option.get_stringpool_name (), const_always,
1093 option.get_stringpool_name ());
1094 if (option[GLOBAL])
1095 printf ("\n");
1096}
1097
1098/* ------------------------------------------------------------------------- */
1099
1100static void
1101output_keyword_entry (KeywordExt *temp, int stringpool_index, const char *indent)
1102{
1103 if (option[TYPE])
1104 output_line_directive (temp->_lineno);
1105 printf ("%s ", indent);
1106 if (option[TYPE])
1107 printf ("{");
1108 if (option[SHAREDLIB])
1109 printf("offsetof(struct %s_t, %s_str%d)", option.get_stringpool_name (), option.get_stringpool_name (), stringpool_index);
1110 else
1111 output_string (temp->_allchars, temp->_allchars_length);
1112 if (option[TYPE])
1113 {
1114 if (strlen (temp->_rest) > 0)
1115 printf (",%s", temp->_rest);
1116 printf ("}");
1117 }
1118 if (option[DEBUG])
1119 printf (" /* hash value = %d, index = %d */",
1120 temp->_hash_value, temp->_final_index);
1121}
1122
1123static void
1124output_keyword_blank_entries (int count, const char *indent)
1125{
1126 int columns;
1127 if (option[TYPE])
1128 {
1129 columns = 58 / (4 + (option[SHAREDLIB] ? 2 : option[NULLSTRINGS] ? 8 : 2)
1130 + strlen (option.get_initializer_suffix()));
1131 if (columns == 0)
1132 columns = 1;
1133 }
1134 else
1135 {
1136 columns = (option[SHAREDLIB] ? 9 : option[NULLSTRINGS] ? 4 : 9);
1137 }
1138 int column = 0;
1139 for (int i = 0; i < count; i++)
1140 {
1141 if ((column % columns) == 0)
1142 {
1143 if (i > 0)
1144 printf (",\n");
1145 printf ("%s ", indent);
1146 }
1147 else
1148 {
1149 if (i > 0)
1150 printf (", ");
1151 }
1152 if (option[TYPE])
1153 printf ("{");
1154 if (option[SHAREDLIB])
1155 printf ("-1");
1156 else
1157 {
1158 if (option[NULLSTRINGS])
1159 printf ("(char*)0");
1160 else
1161 printf ("\"\"");
1162 }
1163 if (option[TYPE])
1164 printf ("%s}", option.get_initializer_suffix());
1165 column++;
1166 }
1167}
1168
1169/* Prints out the array containing the keywords for the hash function. */
1170
1171void
1172Output::output_keyword_table () const
1173{
1174 const char *indent = option[GLOBAL] ? "" : " ";
1175 int index;
1176 KeywordExt_List *temp;
1177
1178 printf ("%sstatic ",
1179 indent);
1180 output_const_type (const_readonly_array, _wordlist_eltype);
1181 printf ("%s[] =\n"
1182 "%s {\n",
1183 option.get_wordlist_name (),
1184 indent);
1185
1186 /* Generate an array of reserved words at appropriate locations. */
1187
1188 for (temp = _head, index = 0; temp; temp = temp->rest())
1189 {
1190 KeywordExt *keyword = temp->first();
1191
1192 /* If generating a switch statement, and there is no user defined type,
1193 we generate non-duplicates directly in the code. Only duplicates go
1194 into the table. */
1195 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1196 continue;
1197
1198 if (index > 0)
1199 printf (",\n");
1200
1201 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
1202 {
1203 /* Some blank entries. */
1204 output_keyword_blank_entries (keyword->_hash_value - index, indent);
1205 printf (",\n");
1206 index = keyword->_hash_value;
1207 }
1208
1209 keyword->_final_index = index;
1210
1211 output_keyword_entry (keyword, index, indent);
1212
1213 /* Deal with duplicates specially. */
1214 if (keyword->_duplicate_link) // implies option[DUP]
1215 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1216 {
1217 links->_final_index = ++index;
1218 printf (",\n");
1219 int stringpool_index =
1220 (links->_allchars_length == keyword->_allchars_length
1221 && memcmp (links->_allchars, keyword->_allchars,
1222 keyword->_allchars_length) == 0
1223 ? keyword->_final_index
1224 : links->_final_index);
1225 output_keyword_entry (links, stringpool_index, indent);
1226 }
1227
1228 index++;
1229 }
1230 if (index > 0)
1231 printf ("\n");
1232
1233 printf ("%s };\n\n", indent);
1234}
1235
1236/* ------------------------------------------------------------------------- */
1237
1238/* Generates the large, sparse table that maps hash values into
1239 the smaller, contiguous range of the keyword table. */
1240
1241void
1242Output::output_lookup_array () const
1243{
1244 if (option[DUP])
1245 {
1246 const int DEFAULT_VALUE = -1;
1247
1248 /* Because of the way output_keyword_table works, every duplicate set is
1249 stored contiguously in the wordlist array. */
1250 struct duplicate_entry
1251 {
1252 int hash_value; /* Hash value for this particular duplicate set. */
1253 int index; /* Index into the main keyword storage array. */
1254 int count; /* Number of consecutive duplicates at this index. */
1255 };
1256
1257 duplicate_entry *duplicates = new duplicate_entry[_total_duplicates];
1258 int *lookup_array = new int[_max_hash_value + 1 + 2*_total_duplicates];
1259 int lookup_array_size = _max_hash_value + 1;
1260 duplicate_entry *dup_ptr = &duplicates[0];
1261 int *lookup_ptr = &lookup_array[_max_hash_value + 1 + 2*_total_duplicates];
1262
1263 while (lookup_ptr > lookup_array)
1264 *--lookup_ptr = DEFAULT_VALUE;
1265
1266 /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1267
1268 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
1269 {
1270 int hash_value = temp->first()->_hash_value;
1271 lookup_array[hash_value] = temp->first()->_final_index;
1272 if (option[DEBUG])
1273 fprintf (stderr, "keyword = %.*s, index = %d\n",
1274 temp->first()->_allchars_length, temp->first()->_allchars, temp->first()->_final_index);
1275 if (temp->first()->_duplicate_link)
1276 {
1277 /* Start a duplicate entry. */
1278 dup_ptr->hash_value = hash_value;
1279 dup_ptr->index = temp->first()->_final_index;
1280 dup_ptr->count = 1;
1281
1282 for (KeywordExt *ptr = temp->first()->_duplicate_link; ptr; ptr = ptr->_duplicate_link)
1283 {
1284 dup_ptr->count++;
1285 if (option[DEBUG])
1286 fprintf (stderr,
1287 "static linked keyword = %.*s, index = %d\n",
1288 ptr->_allchars_length, ptr->_allchars, ptr->_final_index);
1289 }
1290 assert (dup_ptr->count >= 2);
1291 dup_ptr++;
1292 }
1293 }
1294
1295 while (dup_ptr > duplicates)
1296 {
1297 dup_ptr--;
1298
1299 if (option[DEBUG])
1300 fprintf (stderr,
1301 "dup_ptr[%td]: hash_value = %d, index = %d, count = %d\n",
1302 dup_ptr - duplicates,
1303 dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1304
1305 int i;
1306 /* Start searching for available space towards the right part
1307 of the lookup array. */
1308 for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1309 if (lookup_array[i] == DEFAULT_VALUE
1310 && lookup_array[i + 1] == DEFAULT_VALUE)
1311 goto found_i;
1312 /* If we didn't find it to the right look to the left instead... */
1313 for (i = dup_ptr->hash_value-1; i >= 0; i--)
1314 if (lookup_array[i] == DEFAULT_VALUE
1315 && lookup_array[i + 1] == DEFAULT_VALUE)
1316 goto found_i;
1317 /* Append to the end of lookup_array. */
1318 i = lookup_array_size;
1319 lookup_array_size += 2;
1320 found_i:
1321 /* Put in an indirection from dup_ptr->_hash_value to i.
1322 At i and i+1 store dup_ptr->_final_index and dup_ptr->count. */
1323 assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1324 lookup_array[dup_ptr->hash_value] = - 1 - _total_keys - i;
1325 lookup_array[i] = - _total_keys + dup_ptr->index;
1326 lookup_array[i + 1] = - dup_ptr->count;
1327 /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1328 }
1329
1330 /* The values of the lookup array are now known. */
1331
1332 int min = INT_MAX;
1333 int max = INT_MIN;
1334 lookup_ptr = lookup_array + lookup_array_size;
1335 while (lookup_ptr > lookup_array)
1336 {
1337 int val = *--lookup_ptr;
1338 if (min > val)
1339 min = val;
1340 if (max < val)
1341 max = val;
1342 }
1343
1344 const char *indent = option[GLOBAL] ? "" : " ";
1345 printf ("%sstatic %s%s lookup[] =\n"
1346 "%s {",
1347 indent, const_readonly_array, smallest_integral_type (min, max),
1348 indent);
1349
1350 int field_width;
1351 /* Calculate maximum number of digits required for MIN..MAX. */
1352 {
1353 field_width = 2;
1354 for (int trunc = max; (trunc /= 10) > 0;)
1355 field_width++;
1356 }
1357 if (min < 0)
1358 {
1359 int neg_field_width = 2;
1360 for (int trunc = -min; (trunc /= 10) > 0;)
1361 neg_field_width++;
1362 neg_field_width++; /* account for the minus sign */
1363 if (field_width < neg_field_width)
1364 field_width = neg_field_width;
1365 }
1366
1367 const int columns = 42 / field_width;
1368 int column;
1369
1370 column = 0;
1371 for (int i = 0; i < lookup_array_size; i++)
1372 {
1373 if (i > 0)
1374 printf (",");
1375 if ((column++ % columns) == 0)
1376 printf("\n%s ", indent);
1377 printf ("%*d", field_width, lookup_array[i]);
1378 }
1379 printf ("\n%s };\n\n", indent);
1380
1381 delete[] duplicates;
1382 delete[] lookup_array;
1383 }
1384}
1385
1386/* ------------------------------------------------------------------------- */
1387
1388/* Generate all pools needed for the lookup function. */
1389
1390void
1391Output::output_lookup_pools () const
1392{
1393 if (option[SWITCH])
1394 {
1395 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1396 output_string_pool ();
1397 }
1398 else
1399 {
1400 output_string_pool ();
1401 }
1402}
1403
1404/* Generate all the tables needed for the lookup function. */
1405
1406void
1407Output::output_lookup_tables () const
1408{
1409 if (option[SWITCH])
1410 {
1411 /* Use the switch in place of lookup table. */
1412 if (option[LENTABLE] && (option[DUP] && _total_duplicates > 0))
1413 output_keylength_table ();
1414 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1415 output_keyword_table ();
1416 }
1417 else
1418 {
1419 /* Use the lookup table, in place of switch. */
1420 if (option[LENTABLE])
1421 output_keylength_table ();
1422 output_keyword_table ();
1423 output_lookup_array ();
1424 }
1425}
1426
1427/* ------------------------------------------------------------------------- */
1428
1429/* Output a single switch case (including duplicates). Advance list. */
1430
1431static KeywordExt_List *
1432output_switch_case (KeywordExt_List *list, int indent, int *jumps_away)
1433{
1434 if (option[DEBUG])
1435 printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1436 indent, "", list->first()->_hash_value, list->first()->_allchars_length, list->first()->_allchars);
1437
1438 if (option[DUP] && list->first()->_duplicate_link)
1439 {
1440 if (option[LENTABLE])
1441 printf ("%*slengthptr = &%s[%d];\n",
1442 indent, "", option.get_lengthtable_name (), list->first()->_final_index);
1443 printf ("%*swordptr = &%s[%d];\n",
1444 indent, "", option.get_wordlist_name (), list->first()->_final_index);
1445
1446 int count = 0;
1447 for (KeywordExt *links = list->first(); links; links = links->_duplicate_link)
1448 count++;
1449
1450 printf ("%*swordendptr = wordptr + %d;\n"
1451 "%*sgoto multicompare;\n",
1452 indent, "", count,
1453 indent, "");
1454 *jumps_away = 1;
1455 }
1456 else
1457 {
1458 if (option[LENTABLE])
1459 {
1460 printf ("%*sif (len == %d)\n"
1461 "%*s {\n",
1462 indent, "", list->first()->_allchars_length,
1463 indent, "");
1464 indent += 4;
1465 }
1466 printf ("%*sresword = ",
1467 indent, "");
1468 if (option[TYPE])
1469 printf ("&%s[%d]", option.get_wordlist_name (), list->first()->_final_index);
1470 else
1471 output_string (list->first()->_allchars, list->first()->_allchars_length);
1472 printf (";\n");
1473 printf ("%*sgoto compare;\n",
1474 indent, "");
1475 if (option[LENTABLE])
1476 {
1477 indent -= 4;
1478 printf ("%*s }\n",
1479 indent, "");
1480 }
1481 else
1482 *jumps_away = 1;
1483 }
1484
1485 return list->rest();
1486}
1487
1488/* Output a total of size cases, grouped into num_switches switch statements,
1489 where 0 < num_switches <= size. */
1490
1491static void
1492output_switches (KeywordExt_List *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1493{
1494 if (option[DEBUG])
1495 printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1496 indent, "", min_hash_value, max_hash_value, size);
1497
1498 if (num_switches > 1)
1499 {
1500 int part1 = num_switches / 2;
1501 int part2 = num_switches - part1;
1502 int size1 = static_cast<int>(static_cast<double>(size) / static_cast<double>(num_switches) * static_cast<double>(part1) + 0.5);
1503 int size2 = size - size1;
1504
1505 KeywordExt_List *temp = list;
1506 for (int count = size1; count > 0; count--)
1507 temp = temp->rest();
1508
1509 printf ("%*sif (key < %d)\n"
1510 "%*s {\n",
1511 indent, "", temp->first()->_hash_value,
1512 indent, "");
1513
1514 output_switches (list, part1, size1, min_hash_value, temp->first()->_hash_value-1, indent+4);
1515
1516 printf ("%*s }\n"
1517 "%*selse\n"
1518 "%*s {\n",
1519 indent, "", indent, "", indent, "");
1520
1521 output_switches (temp, part2, size2, temp->first()->_hash_value, max_hash_value, indent+4);
1522
1523 printf ("%*s }\n",
1524 indent, "");
1525 }
1526 else
1527 {
1528 /* Output a single switch. */
1529 int lowest_case_value = list->first()->_hash_value;
1530 if (size == 1)
1531 {
1532 int jumps_away = 0;
1533 assert (min_hash_value <= lowest_case_value);
1534 assert (lowest_case_value <= max_hash_value);
1535 if (min_hash_value == max_hash_value)
1536 output_switch_case (list, indent, &jumps_away);
1537 else
1538 {
1539 printf ("%*sif (key == %d)\n"
1540 "%*s {\n",
1541 indent, "", lowest_case_value,
1542 indent, "");
1543 output_switch_case (list, indent+4, &jumps_away);
1544 printf ("%*s }\n",
1545 indent, "");
1546 }
1547 }
1548 else
1549 {
1550 if (lowest_case_value == 0)
1551 printf ("%*sswitch (key)\n", indent, "");
1552 else
1553 printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1554 printf ("%*s {\n",
1555 indent, "");
1556 for (; size > 0; size--)
1557 {
1558 int jumps_away = 0;
1559 printf ("%*s case %d:\n",
1560 indent, "", list->first()->_hash_value - lowest_case_value);
1561 list = output_switch_case (list, indent+6, &jumps_away);
1562 if (!jumps_away)
1563 printf ("%*s break;\n",
1564 indent, "");
1565 }
1566 printf ("%*s }\n",
1567 indent, "");
1568 }
1569 }
1570}
1571
1572/* Generates C code to perform the keyword lookup. */
1573
1574void
1575Output::output_lookup_function_body (const Output_Compare& comparison) const
1576{
1577 printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1578 " {\n"
1579 " register int key = %s (str, len);\n\n",
1580 option.get_hash_name ());
1581
1582 if (option[SWITCH])
1583 {
1584 int switch_size = num_hash_values ();
1585 int num_switches = option.get_total_switches ();
1586 if (num_switches > switch_size)
1587 num_switches = switch_size;
1588
1589 printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1590 " {\n");
1591 if (option[DUP] && _total_duplicates > 0)
1592 {
1593 if (option[LENTABLE])
1594 printf (" register %s%s *lengthptr;\n",
1595 const_always, smallest_integral_type (_max_key_len));
1596 printf (" register ");
1597 output_const_type (const_readonly_array, _wordlist_eltype);
1598 printf ("*wordptr;\n");
1599 printf (" register ");
1600 output_const_type (const_readonly_array, _wordlist_eltype);
1601 printf ("*wordendptr;\n");
1602 }
1603 if (option[TYPE])
1604 {
1605 printf (" register ");
1606 output_const_type (const_readonly_array, _struct_tag);
1607 printf ("*resword;\n\n");
1608 }
1609 else
1610 printf (" register %sresword;\n\n",
1611 _struct_tag);
1612
1613 output_switches (_head, num_switches, switch_size, _min_hash_value, _max_hash_value, 10);
1614
1615 printf (" return 0;\n");
1616 if (option[DUP] && _total_duplicates > 0)
1617 {
1618 int indent = 8;
1619 printf ("%*smulticompare:\n"
1620 "%*s while (wordptr < wordendptr)\n"
1621 "%*s {\n",
1622 indent, "", indent, "", indent, "");
1623 if (option[LENTABLE])
1624 {
1625 printf ("%*s if (len == *lengthptr)\n"
1626 "%*s {\n",
1627 indent, "", indent, "");
1628 indent += 4;
1629 }
1630 printf ("%*s register %schar *s = ",
1631 indent, "", const_always);
1632 if (option[TYPE])
1633 printf ("wordptr->%s", option.get_slot_name ());
1634 else
1635 printf ("*wordptr");
1636 if (option[SHAREDLIB])
1637 printf (" + %s",
1638 option.get_stringpool_name ());
1639 printf (";\n\n"
1640 "%*s if (",
1641 indent, "");
1642 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1643 printf (")\n"
1644 "%*s return %s;\n",
1645 indent, "",
1646 option[TYPE] ? "wordptr" : "s");
1647 if (option[LENTABLE])
1648 {
1649 indent -= 4;
1650 printf ("%*s }\n",
1651 indent, "");
1652 }
1653 if (option[LENTABLE])
1654 printf ("%*s lengthptr++;\n",
1655 indent, "");
1656 printf ("%*s wordptr++;\n"
1657 "%*s }\n"
1658 "%*s return 0;\n",
1659 indent, "", indent, "", indent, "");
1660 }
1661 printf (" compare:\n");
1662 if (option[TYPE])
1663 {
1664 printf (" {\n"
1665 " register %schar *s = resword->%s",
1666 const_always, option.get_slot_name ());
1667 if (option[SHAREDLIB])
1668 printf (" + %s",
1669 option.get_stringpool_name ());
1670 printf (";\n\n"
1671 " if (");
1672 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1673 printf (")\n"
1674 " return resword;\n"
1675 " }\n");
1676 }
1677 else
1678 {
1679 printf (" if (");
1680 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1681 printf (")\n"
1682 " return resword;\n");
1683 }
1684 printf (" }\n");
1685 }
1686 else
1687 {
1688 printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n");
1689
1690 if (option[DUP])
1691 {
1692 int indent = 8;
1693 printf ("%*s{\n"
1694 "%*s register int index = lookup[key];\n\n"
1695 "%*s if (index >= 0)\n",
1696 indent, "", indent, "", indent, "");
1697 if (option[LENTABLE])
1698 {
1699 printf ("%*s {\n"
1700 "%*s if (len == %s[index])\n",
1701 indent, "", indent, "", option.get_lengthtable_name ());
1702 indent += 4;
1703 }
1704 printf ("%*s {\n"
1705 "%*s register %schar *s = %s[index]",
1706 indent, "",
1707 indent, "", const_always, option.get_wordlist_name ());
1708 if (option[TYPE])
1709 printf (".%s", option.get_slot_name ());
1710 if (option[SHAREDLIB])
1711 printf (" + %s",
1712 option.get_stringpool_name ());
1713 printf (";\n\n"
1714 "%*s if (",
1715 indent, "");
1716 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1717 printf (")\n"
1718 "%*s return ",
1719 indent, "");
1720 if (option[TYPE])
1721 printf ("&%s[index]", option.get_wordlist_name ());
1722 else
1723 printf ("s");
1724 printf (";\n"
1725 "%*s }\n",
1726 indent, "");
1727 if (option[LENTABLE])
1728 {
1729 indent -= 4;
1730 printf ("%*s }\n", indent, "");
1731 }
1732 if (_total_duplicates > 0)
1733 {
1734 printf ("%*s else if (index < -TOTAL_KEYWORDS)\n"
1735 "%*s {\n"
1736 "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1737 indent, "", indent, "", indent, "");
1738 if (option[LENTABLE])
1739 printf ("%*s register %s%s *lengthptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1740 indent, "", const_always, smallest_integral_type (_max_key_len),
1741 option.get_lengthtable_name ());
1742 printf ("%*s register ",
1743 indent, "");
1744 output_const_type (const_readonly_array, _wordlist_eltype);
1745 printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1746 option.get_wordlist_name ());
1747 printf ("%*s register ",
1748 indent, "");
1749 output_const_type (const_readonly_array, _wordlist_eltype);
1750 printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1751 printf ("%*s while (wordptr < wordendptr)\n"
1752 "%*s {\n",
1753 indent, "", indent, "");
1754 if (option[LENTABLE])
1755 {
1756 printf ("%*s if (len == *lengthptr)\n"
1757 "%*s {\n",
1758 indent, "", indent, "");
1759 indent += 4;
1760 }
1761 printf ("%*s register %schar *s = ",
1762 indent, "", const_always);
1763 if (option[TYPE])
1764 printf ("wordptr->%s", option.get_slot_name ());
1765 else
1766 printf ("*wordptr");
1767 if (option[SHAREDLIB])
1768 printf (" + %s",
1769 option.get_stringpool_name ());
1770 printf (";\n\n"
1771 "%*s if (",
1772 indent, "");
1773 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1774 printf (")\n"
1775 "%*s return %s;\n",
1776 indent, "",
1777 option[TYPE] ? "wordptr" : "s");
1778 if (option[LENTABLE])
1779 {
1780 indent -= 4;
1781 printf ("%*s }\n",
1782 indent, "");
1783 }
1784 if (option[LENTABLE])
1785 printf ("%*s lengthptr++;\n",
1786 indent, "");
1787 printf ("%*s wordptr++;\n"
1788 "%*s }\n"
1789 "%*s }\n",
1790 indent, "", indent, "", indent, "");
1791 }
1792 printf ("%*s}\n",
1793 indent, "");
1794 }
1795 else
1796 {
1797 int indent = 8;
1798 if (option[LENTABLE])
1799 {
1800 printf ("%*sif (len == %s[key])\n",
1801 indent, "", option.get_lengthtable_name ());
1802 indent += 2;
1803 }
1804
1805 if (option[SHAREDLIB])
1806 {
1807 if (!option[LENTABLE])
1808 {
1809 printf ("%*s{\n"
1810 "%*s register int o = %s[key]",
1811 indent, "",
1812 indent, "", option.get_wordlist_name ());
1813 if (option[TYPE])
1814 printf (".%s", option.get_slot_name ());
1815 printf (";\n"
1816 "%*s if (o >= 0)\n"
1817 "%*s {\n",
1818 indent, "",
1819 indent, "");
1820 indent += 4;
1821 printf ("%*s register %schar *s = o",
1822 indent, "", const_always);
1823 }
1824 else
1825 {
1826 /* No need for the (o >= 0) test, because the
1827 (len == lengthtable[key]) test already guarantees that
1828 key points to nonempty table entry. */
1829 printf ("%*s{\n"
1830 "%*s register %schar *s = %s[key]",
1831 indent, "",
1832 indent, "", const_always,
1833 option.get_wordlist_name ());
1834 if (option[TYPE])
1835 printf (".%s", option.get_slot_name ());
1836 }
1837 printf (" + %s",
1838 option.get_stringpool_name ());
1839 }
1840 else
1841 {
1842 printf ("%*s{\n"
1843 "%*s register %schar *s = %s[key]",
1844 indent, "",
1845 indent, "", const_always, option.get_wordlist_name ());
1846 if (option[TYPE])
1847 printf (".%s", option.get_slot_name ());
1848 }
1849
1850 printf (";\n\n"
1851 "%*s if (",
1852 indent, "");
1853 if (!option[SHAREDLIB] && option[NULLSTRINGS])
1854 printf ("s && ");
1855 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1856 printf (")\n"
1857 "%*s return ",
1858 indent, "");
1859 if (option[TYPE])
1860 printf ("&%s[key]", option.get_wordlist_name ());
1861 else
1862 printf ("s");
1863 printf (";\n");
1864 if (option[SHAREDLIB] && !option[LENTABLE])
1865 {
1866 indent -= 4;
1867 printf ("%*s }\n",
1868 indent, "");
1869 }
1870 printf ("%*s}\n",
1871 indent, "");
1872 }
1873 }
1874 printf (" }\n"
1875 " return 0;\n");
1876}
1877
1878/* Generates C code for the lookup function. */
1879
1880void
1881Output::output_lookup_function () const
1882{
1883 /* Output the function's head. */
1884 if (option[KRC] | option[C] | option[ANSIC])
1885 /* GCC 4.3 and above with -std=c99 or -std=gnu99 implements ISO C99
1886 inline semantics, unless -fgnu89-inline is used. It defines a macro
1887 __GNUC_STDC_INLINE__ to indicate this situation. */
1888 printf ("#ifdef __GNUC__\n"
1889 "__inline\n"
1890 "#ifdef __GNUC_STDC_INLINE__\n"
1891 "__attribute__ ((__gnu_inline__))\n"
1892 "#endif\n"
1893 "#endif\n");
1894
1895 printf ("%s%s\n",
1896 const_for_struct, _return_type);
1897 if (option[CPLUSPLUS])
1898 printf ("%s::", option.get_class_name ());
1899 printf ("%s ", option.get_function_name ());
1900 printf (option[KRC] ?
1901 "(str, len)\n"
1902 " register char *str;\n"
|