?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add gperf 3.0.1.
[dragonfly.git] / contrib / gperf-3.0.1 / src / output.cc
blobf6935059f9eb692429954c4559730da77eeaa986
1 /* Output routines.
2 Copyright (C) 1989-1998, 2000, 2002-2003 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 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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. */
35 static const char *const_always;
36
37 /* The "const " qualifier, for read-only arrays. */
38 static const char *const_readonly_array;
39
40 /* The "const " qualifier, for the array type. */
41 static const char *const_for_struct;
42
43 /* Returns the smallest unsigned C type capable of holding integers
44 up to N. */
45
46 static const char *
47 smallest_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
57 static const char *
58 smallest_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 */
79 Output::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
113 void
114 Output::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
131 int
132 Output::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
146 struct 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
157 struct 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
166 void Output_Defines::output_start ()
167 {
168 printf ("\n");
169 }
170
171 void Output_Defines::output_item (const char *name, int value)
172 {
173 printf ("#define %s %d\n", name, value);
174 }
175
176 void Output_Defines::output_end ()
177 {
178 }
179
180 /* This class outputs an enumeration using 'enum'. */
181
182 struct 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 () {}
190 private:
191 const char *_indentation;
192 bool _pending_comma;
193 };
194
195 void Output_Enum::output_start ()
196 {
197 printf ("%senum\n"
198 "%s {\n",
199 _indentation, _indentation);
200 _pending_comma = false;
201 }
202
203 void 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
211 void 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
220 void
221 Output::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
246 static void
247 output_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
272 static void
273 output_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
322 static void
323 output_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
382 static void
383 output_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
445 static void
446 output_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 type and a const specifier (i.e. "const " or "").
476 The output is terminated with a space. */
477
478 static void
479 output_const_type (const char *const_string, const char *type_string)
480 {
481 if (type_string[strlen(type_string)-1] == '*')
482 /* For pointer types, put the 'const' after the type. */
483 printf ("%s %s", type_string, const_string);
484 else
485 /* For scalar or struct types, put the 'const' before the type. */
486 printf ("%s%s ", const_string, type_string);
487 }
488
489 /* ----------------------- Output_Expr and subclasses ----------------------- */
490
491 /* This class outputs a general expression. */
492
493 struct Output_Expr
494 {
495 virtual void output_expr () const = 0;
496 Output_Expr () {}
497 virtual ~Output_Expr () {}
498 };
499
500 /* This class outputs an expression formed by a single string. */
501
502 struct Output_Expr1 : public Output_Expr
503 {
504 virtual void output_expr () const;
505 Output_Expr1 (const char *piece1) : _p1 (piece1) {}
506 virtual ~Output_Expr1 () {}
507 private:
508 const char *_p1;
509 };
510
511 void Output_Expr1::output_expr () const
512 {
513 printf ("%s", _p1);
514 }
515
516 #if 0 /* unused */
517
518 /* This class outputs an expression formed by the concatenation of two
519 strings. */
520
521 struct Output_Expr2 : public Output_Expr
522 {
523 virtual void output_expr () const;
524 Output_Expr2 (const char *piece1, const char *piece2)
525 : _p1 (piece1), _p2 (piece2) {}
526 virtual ~Output_Expr2 () {}
527 private:
528 const char *_p1;
529 const char *_p2;
530 };
531
532 void Output_Expr2::output_expr () const
533 {
534 printf ("%s%s", _p1, _p2);
535 }
536
537 #endif
538
539 /* --------------------- Output_Compare and subclasses --------------------- */
540
541 /* This class outputs a comparison expression. */
542
543 struct Output_Compare
544 {
545 /* Outputs the comparison expression.
546 expr1 outputs a simple expression of type 'const char *' referring to
547 the string being looked up. expr2 outputs a simple expression of type
548 'const char *' referring to the constant string stored in the gperf
549 generated hash table. */
550 virtual void output_comparison (const Output_Expr& expr1,
551 const Output_Expr& expr2) const = 0;
552 /* Outputs the comparison expression for the first byte.
553 Returns true if the this comparison is complete. */
554 bool output_firstchar_comparison (const Output_Expr& expr1,
555 const Output_Expr& expr2) const;
556 Output_Compare () {}
557 virtual ~Output_Compare () {}
558 };
559
560 bool Output_Compare::output_firstchar_comparison (const Output_Expr& expr1,
561 const Output_Expr& expr2) const
562 {
563 /* First, we emit a comparison of the first byte of the two strings.
564 This catches most cases where the string being looked up is not in the
565 hash table but happens to have the same hash code as an element of the
566 hash table. */
567 if (option[UPPERLOWER])
568 {
569 /* Incomplete comparison, just for speedup. */
570 printf ("(((unsigned char)*");
571 expr1.output_expr ();
572 printf (" ^ (unsigned char)*");
573 expr2.output_expr ();
574 printf (") & ~32) == 0");
575 return false;
576 }
577 else
578 {
579 /* Complete comparison. */
580 printf ("*");
581 expr1.output_expr ();
582 printf (" == *");
583 expr2.output_expr ();
584 return true;
585 }
586 }
587
588 /* This class outputs a comparison using strcmp. */
589
590 struct Output_Compare_Strcmp : public Output_Compare
591 {
592 virtual void output_comparison (const Output_Expr& expr1,
593 const Output_Expr& expr2) const;
594 Output_Compare_Strcmp () {}
595 virtual ~Output_Compare_Strcmp () {}
596 };
597
598 void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
599 const Output_Expr& expr2) const
600 {
601 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
602 printf (" && !");
603 if (option[UPPERLOWER])
604 printf ("gperf_case_");
605 printf ("strcmp (");
606 if (firstchar_done)
607 {
608 expr1.output_expr ();
609 printf (" + 1, ");
610 expr2.output_expr ();
611 printf (" + 1");
612 }
613 else
614 {
615 expr1.output_expr ();
616 printf (", ");
617 expr2.output_expr ();
618 }
619 printf (")");
620 }
621
622 /* This class outputs a comparison using strncmp.
623 Note that the length of expr1 will be available through the local variable
624 'len'. */
625
626 struct Output_Compare_Strncmp : public Output_Compare
627 {
628 virtual void output_comparison (const Output_Expr& expr1,
629 const Output_Expr& expr2) const;
630 Output_Compare_Strncmp () {}
631 virtual ~Output_Compare_Strncmp () {}
632 };
633
634 void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
635 const Output_Expr& expr2) const
636 {
637 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
638 printf (" && !");
639 if (option[UPPERLOWER])
640 printf ("gperf_case_");
641 printf ("strncmp (");
642 if (firstchar_done)
643 {
644 expr1.output_expr ();
645 printf (" + 1, ");
646 expr2.output_expr ();
647 printf (" + 1, len - 1");
648 }
649 else
650 {
651 expr1.output_expr ();
652 printf (", ");
653 expr2.output_expr ();
654 printf (", len");
655 }
656 printf (") && ");
657 expr2.output_expr ();
658 printf ("[len] == '\\0'");
659 }
660
661 /* This class outputs a comparison using memcmp.
662 Note that the length of expr1 (available through the local variable 'len')
663 must be verified to be equal to the length of expr2 prior to this
664 comparison. */
665
666 struct Output_Compare_Memcmp : public Output_Compare
667 {
668 virtual void output_comparison (const Output_Expr& expr1,
669 const Output_Expr& expr2) const;
670 Output_Compare_Memcmp () {}
671 virtual ~Output_Compare_Memcmp () {}
672 };
673
674 void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
675 const Output_Expr& expr2) const
676 {
677 bool firstchar_done = output_firstchar_comparison (expr1, expr2);
678 printf (" && !");
679 if (option[UPPERLOWER])
680 printf ("gperf_case_");
681 printf ("memcmp (");
682 if (firstchar_done)
683 {
684 expr1.output_expr ();
685 printf (" + 1, ");
686 expr2.output_expr ();
687 printf (" + 1, len - 1");
688 }
689 else
690 {
691 expr1.output_expr ();
692 printf (", ");
693 expr2.output_expr ();
694 printf (", len");
695 }
696 printf (")");
697 }
698
699 /* ------------------------------------------------------------------------- */
700
701 /* Generates a C expression for an asso_values[] reference. */
702
703 void
704 Output::output_asso_values_ref (int pos) const
705 {
706 printf ("asso_values[");
707 /* Always cast to unsigned char. This is necessary when the alpha_inc
708 is nonzero, and also avoids a gcc warning "subscript has type 'char'". */
709 printf ("(unsigned char)");
710 if (pos == Positions::LASTCHAR)
711 printf ("str[len - 1]");
712 else
713 {
714 printf ("str[%d]", pos);
715 if (_alpha_inc[pos])
716 printf ("+%u", _alpha_inc[pos]);
717 }
718 printf ("]");
719 }
720
721 /* Generates C code for the hash function that returns the
722 proper encoding for each keyword.
723 The hash function has the signature
724 unsigned int <hash> (const char *str, unsigned int len). */
725
726 void
727 Output::output_hash_function () const
728 {
729 /* Output the function's head. */
730 if (option[CPLUSPLUS])
731 printf ("inline ");
732 else if (option[KRC] | option[C] | option[ANSIC])
733 printf ("#ifdef __GNUC__\n"
734 "__inline\n"
735 "#else\n"
736 "#ifdef __cplusplus\n"
737 "inline\n"
738 "#endif\n"
739 "#endif\n");
740
741 if (/* The function does not use the 'str' argument? */
742 _key_positions.get_size() == 0
743 || /* The function uses 'str', but not the 'len' argument? */
744 (option[NOLENGTH]
745 && _key_positions[0] < _min_key_len
746 && _key_positions[_key_positions.get_size() - 1] != Positions::LASTCHAR))
747 /* Pacify lint. */
748 printf ("/*ARGSUSED*/\n");
749
750 if (option[KRC] | option[C] | option[ANSIC])
751 printf ("static ");
752 printf ("unsigned int\n");
753 if (option[CPLUSPLUS])
754 printf ("%s::", option.get_class_name ());
755 printf ("%s ", option.get_hash_name ());
756 printf (option[KRC] ?
757 "(str, len)\n"
758 " register char *str;\n"
759 " register unsigned int len;\n" :
760 option[C] ?
761 "(str, len)\n"
762 " register const char *str;\n"
763 " register unsigned int len;\n" :
764 option[ANSIC] | option[CPLUSPLUS] ?
765 "(register const char *str, register unsigned int len)\n" :
766 "");
767
768 /* Note that when the hash function is called, it has already been verified
769 that min_key_len <= len <= max_key_len. */
770
771 /* Output the function's body. */
772 printf ("{\n");
773
774 /* First the asso_values array. */
775 if (_key_positions.get_size() > 0)
776 {
777 printf (" static %s%s asso_values[] =\n"
778 " {",
779 const_readonly_array,
780 smallest_integral_type (_max_hash_value + 1));
781
782 const int columns = 10;
783
784 /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
785 int field_width = 2;
786 for (int trunc = _max_hash_value; (trunc /= 10) > 0;)
787 field_width++;
788
789 for (unsigned int count = 0; count < _alpha_size; count++)
790 {
791 if (count > 0)
792 printf (",");
793 if ((count % columns) == 0)
794 printf ("\n ");
795 printf ("%*d", field_width, _asso_values[count]);
796 }
797
798 printf ("\n"
799 " };\n");
800 }
801
802 if (_key_positions.get_size() == 0)
803 {
804 /* Trivial case: No key positions at all. */
805 printf (" return %s;\n",
806 option[NOLENGTH] ? "0" : "len");
807 }
808 else
809 {
810 /* Iterate through the key positions. Remember that Positions::sort()
811 has sorted them in decreasing order, with Positions::LASTCHAR coming
812 last. */
813 PositionIterator iter = _key_positions.iterator(_max_key_len);
814 int key_pos;
815
816 /* Get the highest key position. */
817 key_pos = iter.next ();
818
819 if (key_pos == Positions::LASTCHAR || key_pos < _min_key_len)
820 {
821 /* We can perform additional optimizations here:
822 Write it out as a single expression. Note that the values
823 are added as 'int's even though the asso_values array may
824 contain 'unsigned char's or 'unsigned short's. */
825
826 printf (" return %s",
827 option[NOLENGTH] ? "" : "len + ");
828
829 if (_key_positions.get_size() == 2
830 && _key_positions[0] == 0
831 && _key_positions[1] == Positions::LASTCHAR)
832 /* Optimize special case of "-k 1,$". */
833 {
834 output_asso_values_ref (Positions::LASTCHAR);
835 printf (" + ");
836 output_asso_values_ref (0);
837 }
838 else
839 {
840 for (; key_pos != Positions::LASTCHAR; )
841 {
842 output_asso_values_ref (key_pos);
843 if ((key_pos = iter.next ()) != PositionIterator::EOS)
844 printf (" + ");
845 else
846 break;
847 }
848
849 if (key_pos == Positions::LASTCHAR)
850 output_asso_values_ref (Positions::LASTCHAR);
851 }
852
853 printf (";\n");
854 }
855 else
856 {
857 /* We've got to use the correct, but brute force, technique. */
858 printf (" register int hval = %s;\n\n"
859 " switch (%s)\n"
860 " {\n"
861 " default:\n",
862 option[NOLENGTH] ? "0" : "len",
863 option[NOLENGTH] ? "len" : "hval");
864
865 while (key_pos != Positions::LASTCHAR && key_pos >= _max_key_len)
866 if ((key_pos = iter.next ()) == PositionIterator::EOS)
867 break;
868
869 if (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR)
870 {
871 int i = key_pos;
872 do
873 {
874 if (i > key_pos)
875 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
876 for ( ; i > key_pos; i--)
877 printf (" case %d:\n", i);
878
879 printf (" hval += ");
880 output_asso_values_ref (key_pos);
881 printf (";\n");
882
883 key_pos = iter.next ();
884 }
885 while (key_pos != PositionIterator::EOS && key_pos != Positions::LASTCHAR);
886
887 if (i >= _min_key_len)
888 printf (" /*FALLTHROUGH*/\n"); /* Pacify lint. */
889 for ( ; i >= _min_key_len; i--)
890 printf (" case %d:\n", i);
891 }
892
893 printf (" break;\n"
894 " }\n"
895 " return hval");
896 if (key_pos == Positions::LASTCHAR)
897 {
898 printf (" + ");
899 output_asso_values_ref (Positions::LASTCHAR);
900 }
901 printf (";\n");
902 }
903 }
904 printf ("}\n\n");
905 }
906
907 /* ------------------------------------------------------------------------- */
908
909 /* Prints out a table of keyword lengths, for use with the
910 comparison code in generated function 'in_word_set'.
911 Only called if option[LENTABLE]. */
912
913 void
914 Output::output_keylength_table () const
915 {
916 const int columns = 14;
917 const char * const indent = option[GLOBAL] ? "" : " ";
918
919 printf ("%sstatic %s%s lengthtable[] =\n%s {",
920 indent, const_readonly_array,
921 smallest_integral_type (_max_key_len),
922 indent);
923
924 /* Generate an array of lengths, similar to output_keyword_table. */
925 int index;
926 int column;
927 KeywordExt_List *temp;
928
929 column = 0;
930 for (temp = _head, index = 0; temp; temp = temp->rest())
931 {
932 KeywordExt *keyword = temp->first();
933
934 /* If generating a switch statement, and there is no user defined type,
935 we generate non-duplicates directly in the code. Only duplicates go
936 into the table. */
937 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
938 continue;
939
940 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
941 {
942 /* Some blank entries. */
943 for ( ; index < keyword->_hash_value; index++)
944 {
945 if (index > 0)
946 printf (",");
947 if ((column++ % columns) == 0)
948 printf ("\n%s ", indent);
949 printf ("%3d", 0);
950 }
951 }
952
953 if (index > 0)
954 printf (",");
955 if ((column++ % columns) == 0)
956 printf("\n%s ", indent);
957 printf ("%3d", keyword->_allchars_length);
958 index++;
959
960 /* Deal with duplicates specially. */
961 if (keyword->_duplicate_link) // implies option[DUP]
962 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
963 {
964 printf (",");
965 if ((column++ % columns) == 0)
966 printf("\n%s ", indent);
967 printf ("%3d", links->_allchars_length);
968 index++;
969 }
970 }
971
972 printf ("\n%s };\n", indent);
973 if (option[GLOBAL])
974 printf ("\n");
975 }
976
977 /* ------------------------------------------------------------------------- */
978
979 /* Prints out the string pool, containing the strings of the keyword table.
980 Only called if option[SHAREDLIB]. */
981
982 void
983 Output::output_string_pool () const
984 {
985 const char * const indent = option[TYPE] || option[GLOBAL] ? "" : " ";
986 int index;
987 KeywordExt_List *temp;
988
989 printf ("%sstruct %s_t\n"
990 "%s {\n",
991 indent, option.get_stringpool_name (), indent);
992 for (temp = _head, index = 0; temp; temp = temp->rest())
993 {
994 KeywordExt *keyword = temp->first();
995
996 /* If generating a switch statement, and there is no user defined type,
997 we generate non-duplicates directly in the code. Only duplicates go
998 into the table. */
999 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1000 continue;
1001
1002 if (!option[SWITCH] && !option[DUP])
1003 index = keyword->_hash_value;
1004
1005 printf ("%s char %s_str%d[sizeof(",
1006 indent, option.get_stringpool_name (), index);
1007 output_string (keyword->_allchars, keyword->_allchars_length);
1008 printf (")];\n");
1009
1010 /* Deal with duplicates specially. */
1011 if (keyword->_duplicate_link) // implies option[DUP]
1012 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1013 if (!(links->_allchars_length == keyword->_allchars_length
1014 && memcmp (links->_allchars, keyword->_allchars,
1015 keyword->_allchars_length) == 0))
1016 {
1017 index++;
1018 printf ("%s char %s_str%d[sizeof(",
1019 indent, option.get_stringpool_name (), index);
1020 output_string (links->_allchars, links->_allchars_length);
1021 printf (")];\n");
1022 }
1023
1024 index++;
1025 }
1026 printf ("%s };\n",
1027 indent);
1028
1029 printf ("%sstatic %sstruct %s_t %s_contents =\n"
1030 "%s {\n",
1031 indent, const_readonly_array, option.get_stringpool_name (),
1032 option.get_stringpool_name (), indent);
1033 for (temp = _head, index = 0; temp; temp = temp->rest())
1034 {
1035 KeywordExt *keyword = temp->first();
1036
1037 /* If generating a switch statement, and there is no user defined type,
1038 we generate non-duplicates directly in the code. Only duplicates go
1039 into the table. */
1040 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1041 continue;
1042
1043 if (index > 0)
1044 printf (",\n");
1045
1046 if (!option[SWITCH] && !option[DUP])
1047 index = keyword->_hash_value;
1048
1049 printf ("%s ",
1050 indent);
1051 output_string (keyword->_allchars, keyword->_allchars_length);
1052
1053 /* Deal with duplicates specially. */
1054 if (keyword->_duplicate_link) // implies option[DUP]
1055 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1056 if (!(links->_allchars_length == keyword->_allchars_length
1057 && memcmp (links->_allchars, keyword->_allchars,
1058 keyword->_allchars_length) == 0))
1059 {
1060 index++;
1061 printf (",\n");
1062 printf ("%s ",
1063 indent);
1064 output_string (links->_allchars, links->_allchars_length);
1065 }
1066
1067 index++;
1068 }
1069 if (index > 0)
1070 printf ("\n");
1071 printf ("%s };\n",
1072 indent);
1073 printf ("%s#define %s ((%schar *) &%s_contents)\n",
1074 indent, option.get_stringpool_name (), const_always,
1075 option.get_stringpool_name ());
1076 if (option[GLOBAL])
1077 printf ("\n");
1078 }
1079
1080 /* ------------------------------------------------------------------------- */
1081
1082 static void
1083 output_keyword_entry (KeywordExt *temp, int stringpool_index, const char *indent)
1084 {
1085 if (option[TYPE] && option.get_input_file_name ())
1086 printf ("#line %u \"%s\"\n",
1087 temp->_lineno, option.get_input_file_name ());
1088 printf ("%s ", indent);
1089 if (option[TYPE])
1090 printf ("{");
1091 if (option[SHAREDLIB])
1092 printf ("(int)(long)&((struct %s_t *)0)->%s_str%d",
1093 option.get_stringpool_name (), option.get_stringpool_name (),
1094 stringpool_index);
1095 else
1096 output_string (temp->_allchars, temp->_allchars_length);
1097 if (option[TYPE])
1098 {
1099 if (strlen (temp->_rest) > 0)
1100 printf (",%s", temp->_rest);
1101 printf ("}");
1102 }
1103 if (option[DEBUG])
1104 printf (" /* hash value = %d, index = %d */",
1105 temp->_hash_value, temp->_final_index);
1106 }
1107
1108 static void
1109 output_keyword_blank_entries (int count, const char *indent)
1110 {
1111 int columns;
1112 if (option[TYPE])
1113 {
1114 columns = 58 / (4 + (option[SHAREDLIB] ? 2 : option[NULLSTRINGS] ? 8 : 2)
1115 + strlen (option.get_initializer_suffix()));
1116 if (columns == 0)
1117 columns = 1;
1118 }
1119 else
1120 {
1121 columns = (option[SHAREDLIB] ? 9 : option[NULLSTRINGS] ? 4 : 9);
1122 }
1123 int column = 0;
1124 for (int i = 0; i < count; i++)
1125 {
1126 if ((column % columns) == 0)
1127 {
1128 if (i > 0)
1129 printf (",\n");
1130 printf ("%s ", indent);
1131 }
1132 else
1133 {
1134 if (i > 0)
1135 printf (", ");
1136 }
1137 if (option[TYPE])
1138 printf ("{");
1139 if (option[SHAREDLIB])
1140 printf ("-1");
1141 else
1142 {
1143 if (option[NULLSTRINGS])
1144 printf ("(char*)0");
1145 else
1146 printf ("\"\"");
1147 }
1148 if (option[TYPE])
1149 printf ("%s}", option.get_initializer_suffix());
1150 column++;
1151 }
1152 }
1153
1154 /* Prints out the array containing the keywords for the hash function. */
1155
1156 void
1157 Output::output_keyword_table () const
1158 {
1159 const char *indent = option[GLOBAL] ? "" : " ";
1160 int index;
1161 KeywordExt_List *temp;
1162
1163 printf ("%sstatic ",
1164 indent);
1165 output_const_type (const_readonly_array, _wordlist_eltype);
1166 printf ("%s[] =\n"
1167 "%s {\n",
1168 option.get_wordlist_name (),
1169 indent);
1170
1171 /* Generate an array of reserved words at appropriate locations. */
1172
1173 for (temp = _head, index = 0; temp; temp = temp->rest())
1174 {
1175 KeywordExt *keyword = temp->first();
1176
1177 /* If generating a switch statement, and there is no user defined type,
1178 we generate non-duplicates directly in the code. Only duplicates go
1179 into the table. */
1180 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link)
1181 continue;
1182
1183 if (index > 0)
1184 printf (",\n");
1185
1186 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP])
1187 {
1188 /* Some blank entries. */
1189 output_keyword_blank_entries (keyword->_hash_value - index, indent);
1190 printf (",\n");
1191 index = keyword->_hash_value;
1192 }
1193
1194 keyword->_final_index = index;
1195
1196 output_keyword_entry (keyword, index, indent);
1197
1198 /* Deal with duplicates specially. */
1199 if (keyword->_duplicate_link) // implies option[DUP]
1200 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link)
1201 {
1202 links->_final_index = ++index;
1203 printf (",\n");
1204 int stringpool_index =
1205 (links->_allchars_length == keyword->_allchars_length
1206 && memcmp (links->_allchars, keyword->_allchars,
1207 keyword->_allchars_length) == 0
1208 ? keyword->_final_index
1209 : links->_final_index);
1210 output_keyword_entry (links, stringpool_index, indent);
1211 }
1212
1213 index++;
1214 }
1215 if (index > 0)
1216 printf ("\n");
1217
1218 printf ("%s };\n\n", indent);
1219 }
1220
1221 /* ------------------------------------------------------------------------- */
1222
1223 /* Generates the large, sparse table that maps hash values into
1224 the smaller, contiguous range of the keyword table. */
1225
1226 void
1227 Output::output_lookup_array () const
1228 {
1229 if (option[DUP])
1230 {
1231 const int DEFAULT_VALUE = -1;
1232
1233 /* Because of the way output_keyword_table works, every duplicate set is
1234 stored contiguously in the wordlist array. */
1235 struct duplicate_entry
1236 {
1237 int hash_value; /* Hash value for this particular duplicate set. */
1238 int index; /* Index into the main keyword storage array. */
1239 int count; /* Number of consecutive duplicates at this index. */
1240 };
1241
1242 duplicate_entry *duplicates = new duplicate_entry[_total_duplicates];
1243 int *lookup_array = new int[_max_hash_value + 1 + 2*_total_duplicates];
1244 int lookup_array_size = _max_hash_value + 1;
1245 duplicate_entry *dup_ptr = &duplicates[0];
1246 int *lookup_ptr = &lookup_array[_max_hash_value + 1 + 2*_total_duplicates];
1247
1248 while (lookup_ptr > lookup_array)
1249 *--lookup_ptr = DEFAULT_VALUE;
1250
1251 /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1252
1253 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
1254 {
1255 int hash_value = temp->first()->_hash_value;
1256 lookup_array[hash_value] = temp->first()->_final_index;
1257 if (option[DEBUG])
1258 fprintf (stderr, "keyword = %.*s, index = %d\n",
1259 temp->first()->_allchars_length, temp->first()->_allchars, temp->first()->_final_index);
1260 if (temp->first()->_duplicate_link)
1261 {
1262 /* Start a duplicate entry. */
1263 dup_ptr->hash_value = hash_value;
1264 dup_ptr->index = temp->first()->_final_index;
1265 dup_ptr->count = 1;
1266
1267 for (KeywordExt *ptr = temp->first()->_duplicate_link; ptr; ptr = ptr->_duplicate_link)
1268 {
1269 dup_ptr->count++;
1270 if (option[DEBUG])
1271 fprintf (stderr,
1272 "static linked keyword = %.*s, index = %d\n",
1273 ptr->_allchars_length, ptr->_allchars, ptr->_final_index);
1274 }
1275 assert (dup_ptr->count >= 2);
1276 dup_ptr++;
1277 }
1278 }
1279
1280 while (dup_ptr > duplicates)
1281 {
1282 dup_ptr--;
1283
1284 if (option[DEBUG])
1285 fprintf (stderr,
1286 "dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n",
1287 dup_ptr - duplicates,
1288 dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1289
1290 int i;
1291 /* Start searching for available space towards the right part
1292 of the lookup array. */
1293 for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1294 if (lookup_array[i] == DEFAULT_VALUE
1295 && lookup_array[i + 1] == DEFAULT_VALUE)
1296 goto found_i;
1297 /* If we didn't find it to the right look to the left instead... */
1298 for (i = dup_ptr->hash_value-1; i >= 0; i--)
1299 if (lookup_array[i] == DEFAULT_VALUE
1300 && lookup_array[i + 1] == DEFAULT_VALUE)
1301 goto found_i;
1302 /* Append to the end of lookup_array. */
1303 i = lookup_array_size;
1304 lookup_array_size += 2;
1305 found_i:
1306 /* Put in an indirection from dup_ptr->_hash_value to i.
1307 At i and i+1 store dup_ptr->_final_index and dup_ptr->count. */
1308 assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1309 lookup_array[dup_ptr->hash_value] = - 1 - _total_keys - i;
1310 lookup_array[i] = - _total_keys + dup_ptr->index;
1311 lookup_array[i + 1] = - dup_ptr->count;
1312 /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1313 }
1314
1315 /* The values of the lookup array are now known. */
1316
1317 int min = INT_MAX;
1318 int max = INT_MIN;
1319 lookup_ptr = lookup_array + lookup_array_size;
1320 while (lookup_ptr > lookup_array)
1321 {
1322 int val = *--lookup_ptr;
1323 if (min > val)
1324 min = val;
1325 if (max < val)
1326 max = val;
1327 }
1328
1329 const char *indent = option[GLOBAL] ? "" : " ";
1330 printf ("%sstatic %s%s lookup[] =\n"
1331 "%s {",
1332 indent, const_readonly_array, smallest_integral_type (min, max),
1333 indent);
1334
1335 int field_width;
1336 /* Calculate maximum number of digits required for MIN..MAX. */
1337 {
1338 field_width = 2;
1339 for (int trunc = max; (trunc /= 10) > 0;)
1340 field_width++;
1341 }
1342 if (min < 0)
1343 {
1344 int neg_field_width = 2;
1345 for (int trunc = -min; (trunc /= 10) > 0;)
1346 neg_field_width++;
1347 neg_field_width++; /* account for the minus sign */
1348 if (field_width < neg_field_width)
1349 field_width = neg_field_width;
1350 }
1351
1352 const int columns = 42 / field_width;
1353 int column;
1354
1355 column = 0;
1356 for (int i = 0; i < lookup_array_size; i++)
1357 {
1358 if (i > 0)
1359 printf (",");
1360 if ((column++ % columns) == 0)
1361 printf("\n%s ", indent);
1362 printf ("%*d", field_width, lookup_array[i]);
1363 }
1364 printf ("\n%s };\n\n", indent);
1365
1366 delete[] duplicates;
1367 delete[] lookup_array;
1368 }
1369 }
1370
1371 /* ------------------------------------------------------------------------- */
1372
1373 /* Generate all pools needed for the lookup function. */
1374
1375 void
1376 Output::output_lookup_pools () const
1377 {
1378 if (option[SWITCH])
1379 {
1380 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1381 output_string_pool ();
1382 }
1383 else
1384 {
1385 output_string_pool ();
1386 }
1387 }
1388
1389 /* Generate all the tables needed for the lookup function. */
1390
1391 void
1392 Output::output_lookup_tables () const
1393 {
1394 if (option[SWITCH])
1395 {
1396 /* Use the switch in place of lookup table. */
1397 if (option[LENTABLE] && (option[DUP] && _total_duplicates > 0))
1398 output_keylength_table ();
1399 if (option[TYPE] || (option[DUP] && _total_duplicates > 0))
1400 output_keyword_table ();
1401 }
1402 else
1403 {
1404 /* Use the lookup table, in place of switch. */
1405 if (option[LENTABLE])
1406 output_keylength_table ();
1407 output_keyword_table ();
1408 output_lookup_array ();
1409 }
1410 }
1411
1412 /* ------------------------------------------------------------------------- */
1413
1414 /* Output a single switch case (including duplicates). Advance list. */
1415
1416 static KeywordExt_List *
1417 output_switch_case (KeywordExt_List *list, int indent, int *jumps_away)
1418 {
1419 if (option[DEBUG])
1420 printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1421 indent, "", list->first()->_hash_value, list->first()->_allchars_length, list->first()->_allchars);
1422
1423 if (option[DUP] && list->first()->_duplicate_link)
1424 {
1425 if (option[LENTABLE])
1426 printf ("%*slengthptr = &lengthtable[%d];\n",
1427 indent, "", list->first()->_final_index);
1428 printf ("%*swordptr = &%s[%d];\n",
1429 indent, "", option.get_wordlist_name (), list->first()->_final_index);
1430
1431 int count = 0;
1432 for (KeywordExt *links = list->first(); links; links = links->_duplicate_link)
1433 count++;
1434
1435 printf ("%*swordendptr = wordptr + %d;\n"
1436 "%*sgoto multicompare;\n",
1437 indent, "", count,
1438 indent, "");
1439 *jumps_away = 1;
1440 }
1441 else
1442 {
1443 if (option[LENTABLE])
1444 {
1445 printf ("%*sif (len == %d)\n"
1446 "%*s {\n",
1447 indent, "", list->first()->_allchars_length,
1448 indent, "");
1449 indent += 4;
1450 }
1451 printf ("%*sresword = ",
1452 indent, "");
1453 if (option[TYPE])
1454 printf ("&%s[%d]", option.get_wordlist_name (), list->first()->_final_index);
1455 else
1456 output_string (list->first()->_allchars, list->first()->_allchars_length);
1457 printf (";\n");
1458 printf ("%*sgoto compare;\n",
1459 indent, "");
1460 if (option[LENTABLE])
1461 {
1462 indent -= 4;
1463 printf ("%*s }\n",
1464 indent, "");
1465 }
1466 else
1467 *jumps_away = 1;
1468 }
1469
1470 return list->rest();
1471 }
1472
1473 /* Output a total of size cases, grouped into num_switches switch statements,
1474 where 0 < num_switches <= size. */
1475
1476 static void
1477 output_switches (KeywordExt_List *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1478 {
1479 if (option[DEBUG])
1480 printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1481 indent, "", min_hash_value, max_hash_value, size);
1482
1483 if (num_switches > 1)
1484 {
1485 int part1 = num_switches / 2;
1486 int part2 = num_switches - part1;
1487 int size1 = static_cast<int>(static_cast<double>(size) / static_cast<double>(num_switches) * static_cast<double>(part1) + 0.5);
1488 int size2 = size - size1;
1489
1490 KeywordExt_List *temp = list;
1491 for (int count = size1; count > 0; count--)
1492 temp = temp->rest();
1493
1494 printf ("%*sif (key < %d)\n"
1495 "%*s {\n",
1496 indent, "", temp->first()->_hash_value,
1497 indent, "");
1498
1499 output_switches (list, part1, size1, min_hash_value, temp->first()->_hash_value-1, indent+4);
1500
1501 printf ("%*s }\n"
1502 "%*selse\n"
1503 "%*s {\n",
1504 indent, "", indent, "", indent, "");
1505
1506 output_switches (temp, part2, size2, temp->first()->_hash_value, max_hash_value, indent+4);
1507
1508 printf ("%*s }\n",
1509 indent, "");
1510 }
1511 else
1512 {
1513 /* Output a single switch. */
1514 int lowest_case_value = list->first()->_hash_value;
1515 if (size == 1)
1516 {
1517 int jumps_away = 0;
1518 assert (min_hash_value <= lowest_case_value);
1519 assert (lowest_case_value <= max_hash_value);
1520 if (min_hash_value == max_hash_value)
1521 output_switch_case (list, indent, &jumps_away);
1522 else
1523 {
1524 printf ("%*sif (key == %d)\n"
1525 "%*s {\n",
1526 indent, "", lowest_case_value,
1527 indent, "");
1528 output_switch_case (list, indent+4, &jumps_away);
1529 printf ("%*s }\n",
1530 indent, "");
1531 }
1532 }
1533 else
1534 {
1535 if (lowest_case_value == 0)
1536 printf ("%*sswitch (key)\n", indent, "");
1537 else
1538 printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1539 printf ("%*s {\n",
1540 indent, "");
1541 for (; size > 0; size--)
1542 {
1543 int jumps_away = 0;
1544 printf ("%*s case %d:\n",
1545 indent, "", list->first()->_hash_value - lowest_case_value);
1546 list = output_switch_case (list, indent+6, &jumps_away);
1547 if (!jumps_away)
1548 printf ("%*s break;\n",
1549 indent, "");
1550 }
1551 printf ("%*s }\n",
1552 indent, "");
1553 }
1554 }
1555 }
1556
1557 /* Generates C code to perform the keyword lookup. */
1558
1559 void
1560 Output::output_lookup_function_body (const Output_Compare& comparison) const
1561 {
1562 printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1563 " {\n"
1564 " register int key = %s (str, len);\n\n",
1565 option.get_hash_name ());
1566
1567 if (option[SWITCH])
1568 {
1569 int switch_size = num_hash_values ();
1570 int num_switches = option.get_total_switches ();
1571 if (num_switches > switch_size)
1572 num_switches = switch_size;
1573
1574 printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1575 " {\n");
1576 if (option[DUP] && _total_duplicates > 0)
1577 {
1578 if (option[LENTABLE])
1579 printf (" register %s%s *lengthptr;\n",
1580 const_always, smallest_integral_type (_max_key_len));
1581 printf (" register ");
1582 output_const_type (const_readonly_array, _wordlist_eltype);
1583 printf ("*wordptr;\n");
1584 printf (" register ");
1585 output_const_type (const_readonly_array, _wordlist_eltype);
1586 printf ("*wordendptr;\n");
1587 }
1588 if (option[TYPE])
1589 {
1590 printf (" register ");
1591 output_const_type (const_readonly_array, _struct_tag);
1592 printf ("*resword;\n\n");
1593 }
1594 else
1595 printf (" register %sresword;\n\n",
1596 _struct_tag);
1597
1598 output_switches (_head, num_switches, switch_size, _min_hash_value, _max_hash_value, 10);
1599
1600 printf (" return 0;\n");
1601 if (option[DUP] && _total_duplicates > 0)
1602 {
1603 int indent = 8;
1604 printf ("%*smulticompare:\n"
1605 "%*s while (wordptr < wordendptr)\n"
1606 "%*s {\n",
1607 indent, "", indent, "", indent, "");
1608 if (option[LENTABLE])
1609 {
1610 printf ("%*s if (len == *lengthptr)\n"
1611 "%*s {\n",
1612 indent, "", indent, "");
1613 indent += 4;
1614 }
1615 printf ("%*s register %schar *s = ",
1616 indent, "", const_always);
1617 if (option[TYPE])
1618 printf ("wordptr->%s", option.get_slot_name ());
1619 else
1620 printf ("*wordptr");
1621 if (option[SHAREDLIB])
1622 printf (" + %s",
1623 option.get_stringpool_name ());
1624 printf (";\n\n"
1625 "%*s if (",
1626 indent, "");
1627 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1628 printf (")\n"
1629 "%*s return %s;\n",
1630 indent, "",
1631 option[TYPE] ? "wordptr" : "s");
1632 if (option[LENTABLE])
1633 {
1634 indent -= 4;
1635 printf ("%*s }\n",
1636 indent, "");
1637 }
1638 if (option[LENTABLE])
1639 printf ("%*s lengthptr++;\n",
1640 indent, "");
1641 printf ("%*s wordptr++;\n"
1642 "%*s }\n"
1643 "%*s return 0;\n",
1644 indent, "", indent, "", indent, "");
1645 }
1646 printf (" compare:\n");
1647 if (option[TYPE])
1648 {
1649 printf (" {\n"
1650 " register %schar *s = resword->%s",
1651 const_always, option.get_slot_name ());
1652 if (option[SHAREDLIB])
1653 printf (" + %s",
1654 option.get_stringpool_name ());
1655 printf (";\n\n"
1656 " if (");
1657 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1658 printf (")\n"
1659 " return resword;\n"
1660 " }\n");
1661 }
1662 else
1663 {
1664 printf (" if (");
1665 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1666 printf (")\n"
1667 " return resword;\n");
1668 }
1669 printf (" }\n");
1670 }
1671 else
1672 {
1673 printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n");
1674
1675 if (option[DUP])
1676 {
1677 int indent = 8;
1678 printf ("%*s{\n"
1679 "%*s register int index = lookup[key];\n\n"
1680 "%*s if (index >= 0)\n",
1681 indent, "", indent, "", indent, "");
1682 if (option[LENTABLE])
1683 {
1684 printf ("%*s {\n"
1685 "%*s if (len == lengthtable[index])\n",
1686 indent, "", indent, "");
1687 indent += 4;
1688 }
1689 printf ("%*s {\n"
1690 "%*s register %schar *s = %s[index]",
1691 indent, "",
1692 indent, "", const_always, option.get_wordlist_name ());
1693 if (option[TYPE])
1694 printf (".%s", option.get_slot_name ());
1695 if (option[SHAREDLIB])
1696 printf (" + %s",
1697 option.get_stringpool_name ());
1698 printf (";\n\n"
1699 "%*s if (",
1700 indent, "");
1701 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1702 printf (")\n"
1703 "%*s return ",
1704 indent, "");
1705 if (option[TYPE])
1706 printf ("&%s[index]", option.get_wordlist_name ());
1707 else
1708 printf ("s");
1709 printf (";\n"
1710 "%*s }\n",
1711 indent, "");
1712 if (option[LENTABLE])
1713 {
1714 indent -= 4;
1715 printf ("%*s }\n", indent, "");
1716 }
1717 if (_total_duplicates > 0)
1718 {
1719 printf ("%*s else if (index < -TOTAL_KEYWORDS)\n"
1720 "%*s {\n"
1721 "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1722 indent, "", indent, "", indent, "");
1723 if (option[LENTABLE])
1724 printf ("%*s register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n",
1725 indent, "", const_always, smallest_integral_type (_max_key_len));
1726 printf ("%*s register ",
1727 indent, "");
1728 output_const_type (const_readonly_array, _wordlist_eltype);
1729 printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1730 option.get_wordlist_name ());
1731 printf ("%*s register ",
1732 indent, "");
1733 output_const_type (const_readonly_array, _wordlist_eltype);
1734 printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1735 printf ("%*s while (wordptr < wordendptr)\n"
1736 "%*s {\n",
1737 indent, "", indent, "");
1738 if (option[LENTABLE])
1739 {
1740 printf ("%*s if (len == *lengthptr)\n"
1741 "%*s {\n",
1742 indent, "", indent, "");
1743 indent += 4;
1744 }
1745 printf ("%*s register %schar *s = ",
1746 indent, "", const_always);
1747 if (option[TYPE])
1748 printf ("wordptr->%s", option.get_slot_name ());
1749 else
1750 printf ("*wordptr");
1751 if (option[SHAREDLIB])
1752 printf (" + %s",
1753 option.get_stringpool_name ());
1754 printf (";\n\n"
1755 "%*s if (",
1756 indent, "");
1757 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1758 printf (")\n"
1759 "%*s return %s;\n",
1760 indent, "",
1761 option[TYPE] ? "wordptr" : "s");
1762 if (option[LENTABLE])
1763 {
1764 indent -= 4;
1765 printf ("%*s }\n",
1766 indent, "");
1767 }
1768 if (option[LENTABLE])
1769 printf ("%*s lengthptr++;\n",
1770 indent, "");
1771 printf ("%*s wordptr++;\n"
1772 "%*s }\n"
1773 "%*s }\n",
1774 indent, "", indent, "", indent, "");
1775 }
1776 printf ("%*s}\n",
1777 indent, "");
1778 }
1779 else
1780 {
1781 int indent = 8;
1782 if (option[LENTABLE])
1783 {
1784 printf ("%*sif (len == lengthtable[key])\n",
1785 indent, "");
1786 indent += 2;
1787 }
1788
1789 if (option[SHAREDLIB])
1790 {
1791 if (!option[LENTABLE])
1792 {
1793 printf ("%*s{\n"
1794 "%*s register int o = %s[key]",
1795 indent, "",
1796 indent, "", option.get_wordlist_name ());
1797 if (option[TYPE])
1798 printf (".%s", option.get_slot_name ());
1799 printf (";\n"
1800 "%*s if (o >= 0)\n"
1801 "%*s {\n",
1802 indent, "",
1803 indent, "");
1804 indent += 4;
1805 printf ("%*s register %schar *s = o",
1806 indent, "", const_always);
1807 }
1808 else
1809 {
1810 /* No need for the (o >= 0) test, because the
1811 (len == lengthtable[key]) test already guarantees that
1812 key points to nonempty table entry. */
1813 printf ("%*s{\n"
1814 "%*s register %schar *s = %s[key]",
1815 indent, "",
1816 indent, "", const_always,
1817 option.get_wordlist_name ());
1818 if (option[TYPE])
1819 printf (".%s", option.get_slot_name ());
1820 }
1821 printf (" + %s",
1822 option.get_stringpool_name ());
1823 }
1824 else
1825 {
1826 printf ("%*s{\n"
1827 "%*s register %schar *s = %s[key]",
1828 indent, "",
1829 indent, "", const_always, option.get_wordlist_name ());
1830 if (option[TYPE])
1831 printf (".%s", option.get_slot_name ());
1832 }
1833
1834 printf (";\n\n"
1835 "%*s if (",
1836 indent, "");
1837 if (!option[SHAREDLIB] && option[NULLSTRINGS])
1838 printf ("s && ");
1839 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1840 printf (")\n"
1841 "%*s return ",
1842 indent, "");
1843 if (option[TYPE])
1844 printf ("&%s[key]", option.get_wordlist_name ());
1845 else
1846 printf ("s");
1847 printf (";\n");
1848 if (option[SHAREDLIB] && !option[LENTABLE])
1849 {
1850 indent -= 4;
1851 printf ("%*s }\n",
1852 indent, "");
1853 }
1854 printf ("%*s}\n",
1855 indent, "");
1856 }
1857 }
1858 printf (" }\n"
1859 " return 0;\n");
1860 }
1861
1862 /* Generates C code for the lookup function. */
1863
1864 void
1865 Output::output_lookup_function () const
1866 {
1867 /* Output the function's head. */
1868 if (option[KRC] | option[C] | option[ANSIC])
1869 printf ("#ifdef __GNUC__\n"
1870 "__inline\n"
1871 "#endif\n");
1872
1873 printf ("%s%s\n",
1874 const_for_struct, _return_type);
1875 if (option[CPLUSPLUS])
1876 printf ("%s::", option.get_class_name ());
1877 printf ("%s ", option.get_function_name ());
1878 printf (option[KRC] ?
1879 "(str, len)\n"
1880 " register char *str;\n"
1881 " register unsigned int len;\n" :
1882 option[C] ?
1883 "(str, len)\n"
1884 " register const char *str;\n"
1885 " register unsigned int len;\n" :
1886 option[ANSIC] | option[CPLUSPLUS] ?
1887 "(register const char *str, register unsigned int len)\n" :
1888 "");
1889
1890 /* Output the function's body. */
1891 printf ("{\n");
1892
1893 if (option[ENUM] && !option[GLOBAL])
1894 {
1895 Output_Enum style (" ");
1896 output_constants (style);
1897 }
1898
1899 if (option[SHAREDLIB] && !(option[GLOBAL] || option[TYPE]))
1900 output_lookup_pools ();
1901 if (!option[GLOBAL])
1902 output_lookup_tables ();
1903
1904 if (option[LENTABLE])
1905 output_lookup_function_body (Output_Compare_Memcmp ());
1906 else
1907 {
1908 if (option[COMP])
1909 output_lookup_function_body (Output_Compare_Strncmp ());
1910 else
1911 output_lookup_function_body (Output_Compare_Strcmp ());
1912 }
1913
1914 printf ("}\n");
1915 }
1916
1917 /* ------------------------------------------------------------------------- */
1918
1919 /* Generates the hash function and the key word recognizer function
1920 based upon the user's Options. */
1921
1922 void
1923 Output::output ()
1924 {
1925 compute_min_max ();
1926
1927 if (option[C] | option[ANSIC] | option[CPLUSPLUS])
1928 {
1929 const_always = "const ";
1930 const_readonly_array = (option[CONST] ? "const " : "");
1931 const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : "");
1932 }
1933 else
1934 {
1935 const_always = "";
1936 const_readonly_array = "";
1937 const_for_struct = "";
1938 }
1939
1940 if (!option[TYPE])
1941 {
1942 _return_type = (const_always[0] ? "const char *" : "char *");
1943 _struct_tag = (const_always[0] ? "const char *" : "char *");
1944 }
1945
1946 _wordlist_eltype = (option[SHAREDLIB] && !option[TYPE] ? "int" : _struct_tag);
1947
1948 printf ("/* ");
1949 if (option[KRC])
1950 printf ("KR-C");
1951 else if (option[C])
1952 printf ("C");
1953 else if (option[ANSIC])
1954 printf ("ANSI-C");
1955 else if (option[CPLUSPLUS])
1956 printf ("C++");
1957 printf (" code produced by gperf version %s */\n", version_string);
1958 option.print_options ();
1959 printf ("\n");
1960 if (!option[POSITIONS])
1961 {
1962 printf ("/* Computed positions: -k'");
1963 _key_positions.print();
1964 printf ("' */\n");
1965 }
1966 printf ("\n");
1967
1968 if (_charset_dependent
1969 && (_key_positions.get_size() > 0 || option[UPPERLOWER]))
1970 {
1971 /* The generated tables assume that the execution character set is
1972 based on ISO-646, not EBCDIC. */
1973 printf ("#if !((' ' == 32) && ('!' == 33) && ('\"' == 34) && ('#' == 35) \\\n"
1974 " && ('%%' == 37) && ('&' == 38) && ('\\'' == 39) && ('(' == 40) \\\n"
1975 " && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \\\n"
1976 " && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \\\n"
1977 " && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \\\n"
1978 " && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \\\n"
1979 " && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \\\n"
1980 " && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \\\n"
1981 " && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \\\n"
1982 " && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \\\n"
1983 " && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \\\n"
1984 " && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \\\n"
1985 " && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \\\n"
1986 " && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \\\n"
1987 " && ('Z' == 90) && ('[' == 91) && ('\\\\' == 92) && (']' == 93) \\\n"
1988 " && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \\\n"
1989 " && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \\\n"
1990 " && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \\\n"
1991 " && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \\\n"
1992 " && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \\\n"
1993 " && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \\\n"
1994 " && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \\\n"
1995 " && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126))\n"
1996 "/* The character set is not based on ISO-646. */\n");
1997 printf ("%s \"gperf generated tables don't work with this execution character set. Please report a bug to <bug-gnu-gperf@gnu.org>.\"\n", option[KRC] || option[C] ? "error" : "#error");
1998 printf ("#endif\n\n");
1999 }
2000
2001 if (_verbatim_declarations < _verbatim_declarations_end)
2002 {
2003 if (option.get_input_file_name ())
2004 printf ("#line %u \"%s\"\n",
2005 _verbatim_declarations_lineno, option.get_input_file_name ());
2006 fwrite (_verbatim_declarations, 1,
2007 _verbatim_declarations_end - _verbatim_declarations, stdout);
2008 }
2009
2010 if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
2011 {
2012 if (option.get_input_file_name ())
2013 printf ("#line %u \"%s\"\n",
2014 _struct_decl_lineno, option.get_input_file_name ());
2015 printf ("%s\n", _struct_decl);
2016 }
2017
2018 if (option[INCLUDE])
2019 printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */
2020
2021 if (!option[ENUM])
2022 {
2023 Output_Defines style;
2024 output_constants (style);
2025 }
2026 else if (option[GLOBAL])
2027 {
2028 Output_Enum style ("");
2029 output_constants (style);
2030 }
2031
2032 printf ("/* maximum key range = %d, duplicates = %d */\n\n",
2033 _max_hash_value - _min_hash_value + 1, _total_duplicates);
2034
2035 if (option[UPPERLOWER])
2036 {
2037 #if USE_DOWNCASE_TABLE
2038 output_upperlower_table ();
2039 #endif
2040
2041 if (option[LENTABLE])
2042 output_upperlower_memcmp ();
2043 else
2044 {
2045 if (option[COMP])
2046 output_upperlower_strncmp ();
2047 else
2048 output_upperlower_strcmp ();
2049 }
2050 }
2051
2052 if (option[CPLUSPLUS])
2053 printf ("class %s\n"
2054 "{\n"
2055 "private:\n"
2056 " static inline unsigned int %s (const char *str, unsigned int len);\n"
2057 "public:\n"
2058 " static %s%s%s (const char *str, unsigned int len);\n"
2059 "};\n"
2060 "\n",
2061 option.get_class_name (), option.get_hash_name (),
2062 const_for_struct, _return_type, option.get_function_name ());
2063
2064 output_hash_function ();
2065
2066 if (option[SHAREDLIB] && (option[GLOBAL] || option[TYPE]))
2067 output_lookup_pools ();
2068 if (option[GLOBAL])
2069 output_lookup_tables ();
2070
2071 output_lookup_function ();
2072
2073 if (_verbatim_code < _verbatim_code_end)
2074 {
2075 if (option.get_input_file_name ())
2076 printf ("#line %u \"%s\"\n",
2077 _verbatim_code_lineno, option.get_input_file_name ());
2078 fwrite (_verbatim_code, 1, _verbatim_code_end - _verbatim_code, stdout);
2079 }
2080
2081 fflush (stdout);
2082 }
DragonFly BSD