output.cc revision 259320
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" 775 " register unsigned int len;\n" : 776 option[C] ? 777 "(str, len)\n" 778 " register const char *str;\n" 779 " register unsigned int len;\n" : 780 option[ANSIC] | option[CPLUSPLUS] ? 781 "(register const char *str, register unsigned int len)\n" : 782 ""); 783 784 /* Note that when the hash function is called, it has already been verified 785 that min_key_len <= len <= max_key_len. */ 786 787 /* Output the function's body. */ 788 printf ("{\n"); 789 790 /* First the asso_values array. */ 791 if (_key_positions.get_size() > 0) 792 { 793 printf (" static %s%s asso_values[] =\n" 794 " {", 795 const_readonly_array, 796 smallest_integral_type (_max_hash_value + 1)); 797 798 const int columns = 10; 799 800 /* Calculate maximum number of digits required for MAX_HASH_VALUE. */ 801 int field_width = 2; 802 for (int trunc = _max_hash_value; (trunc /= 10) > 0;) 803 field_width++; 804 805 for (unsigned int count = 0; count < _alpha_size; count++) 806 { 807 if (count > 0) 808 printf (","); 809 if ((count % columns) == 0) 810 printf ("\n "); 811 printf ("%*d", field_width, _asso_values[count]); 812 } 813 814 printf ("\n" 815 " };\n"); 816 } 817 818 if (_key_positions.get_size() == 0) 819 { 820 /* Trivial case: No key positions at all. */ 821 printf (" return %s;\n", 822 option[NOLENGTH] ? "0" : "len"); 823 } 824 else 825 { 826 /* Iterate through the key positions. Remember that Positions::sort() 827 has sorted them in decreasing order, with Positions::LASTCHAR coming 828 last. */ 829 PositionIterator iter = _key_positions.iterator(_max_key_len); 830 int key_pos; 831 832 /* Get the highest key position. */ 833 key_pos = iter.next (); 834 835 if (key_pos == Positions::LASTCHAR || key_pos < _min_key_len) 836 { 837 /* We can perform additional optimizations here: 838 Write it out as a single expression. Note that the values 839 are added as 'int's even though the asso_values array may 840 contain 'unsigned char's or 'unsigned short's. */ 841 842 printf (" return %s", 843 option[NOLENGTH] ? "" : "len + "); 844 845 if (_key_positions.get_size() == 2 846 && _key_positions[0] == 0 847 && _key_positions[1] == Positions::LASTCHAR) 848 /* Optimize special case of "-k 1,$". */ 849 { 850 output_asso_values_ref (Positions::LASTCHAR); 851 printf (" + "); 852 output_asso_values_ref (0); 853 } 854 else 855 { 856 for (; key_pos != Positions::LASTCHAR; ) 857 { 858 output_asso_values_ref (key_pos); 859 if ((key_pos = iter.next ()) != PositionIterator::EOS) 860 printf (" + "); 861 else 862 break; 863 } 864 865 if (key_pos == Positions::LASTCHAR) 866 output_asso_values_ref (Positions::LASTCHAR); 867 } 868 869 printf (";\n"); 870 } 871 else 872 { 873 /* We've got to use the correct, but brute force, technique. */ 874 printf (" register int hval = %s;\n\n" 875 " switch (%s)\n" 876 " {\n" 877 " default:\n", 878 option[NOLENGTH] ? "0" : "len", 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" 1903 " register unsigned int len;\n" : 1904 option[C] ? 1905 "(str, len)\n" 1906 " register const char *str;\n" 1907 " register unsigned int len;\n" : 1908 option[ANSIC] | option[CPLUSPLUS] ? 1909 "(register const char *str, register unsigned int len)\n" : 1910 ""); 1911 1912 /* Output the function's body. */ 1913 printf ("{\n"); 1914 1915 if (option[ENUM] && !option[GLOBAL]) 1916 { 1917 Output_Enum style (" "); 1918 output_constants (style); 1919 } 1920 1921 if (option[SHAREDLIB] && !(option[GLOBAL] || option[TYPE])) 1922 output_lookup_pools (); 1923 if (!option[GLOBAL]) 1924 output_lookup_tables (); 1925 1926 if (option[LENTABLE]) 1927 output_lookup_function_body (Output_Compare_Memcmp ()); 1928 else 1929 { 1930 if (option[COMP]) 1931 output_lookup_function_body (Output_Compare_Strncmp ()); 1932 else 1933 output_lookup_function_body (Output_Compare_Strcmp ()); 1934 } 1935 1936 printf ("}\n"); 1937} 1938 1939/* ------------------------------------------------------------------------- */ 1940 1941/* Generates the hash function and the key word recognizer function 1942 based upon the user's Options. */ 1943 1944void 1945Output::output () 1946{ 1947 compute_min_max (); 1948 1949 if (option[C] | option[ANSIC] | option[CPLUSPLUS]) 1950 { 1951 const_always = "const "; 1952 const_readonly_array = (option[CONST] ? "const " : ""); 1953 const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : ""); 1954 } 1955 else 1956 { 1957 const_always = ""; 1958 const_readonly_array = ""; 1959 const_for_struct = ""; 1960 } 1961 1962 if (!option[TYPE]) 1963 { 1964 _return_type = (const_always[0] ? "const char *" : "char *"); 1965 _struct_tag = (const_always[0] ? "const char *" : "char *"); 1966 } 1967 1968 _wordlist_eltype = (option[SHAREDLIB] && !option[TYPE] ? "int" : _struct_tag); 1969 1970 printf ("/* "); 1971 if (option[KRC]) 1972 printf ("KR-C"); 1973 else if (option[C]) 1974 printf ("C"); 1975 else if (option[ANSIC]) 1976 printf ("ANSI-C"); 1977 else if (option[CPLUSPLUS]) 1978 printf ("C++"); 1979 printf (" code produced by gperf version %s */\n", version_string); 1980 option.print_options (); 1981 printf ("\n"); 1982 if (!option[POSITIONS]) 1983 { 1984 printf ("/* Computed positions: -k'"); 1985 _key_positions.print(); 1986 printf ("' */\n"); 1987 } 1988 printf ("\n"); 1989 1990 if (_charset_dependent 1991 && (_key_positions.get_size() > 0 || option[UPPERLOWER])) 1992 { 1993 /* The generated tables assume that the execution character set is 1994 based on ISO-646, not EBCDIC. */ 1995 printf ("#if !((' ' == 32) && ('!' == 33) && ('\"' == 34) && ('#' == 35) \\\n" 1996 " && ('%%' == 37) && ('&' == 38) && ('\\'' == 39) && ('(' == 40) \\\n" 1997 " && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \\\n" 1998 " && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \\\n" 1999 " && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \\\n" 2000 " && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \\\n" 2001 " && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \\\n" 2002 " && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \\\n" 2003 " && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \\\n" 2004 " && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \\\n" 2005 " && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \\\n" 2006 " && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \\\n" 2007 " && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \\\n" 2008 " && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \\\n" 2009 " && ('Z' == 90) && ('[' == 91) && ('\\\\' == 92) && (']' == 93) \\\n" 2010 " && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \\\n" 2011 " && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \\\n" 2012 " && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \\\n" 2013 " && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \\\n" 2014 " && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \\\n" 2015 " && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \\\n" 2016 " && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \\\n" 2017 " && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126))\n" 2018 "/* The character set is not based on ISO-646. */\n"); 2019 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"); 2020 printf ("#endif\n\n"); 2021 } 2022 2023 if (_verbatim_declarations < _verbatim_declarations_end) 2024 { 2025 output_line_directive (_verbatim_declarations_lineno); 2026 fwrite (_verbatim_declarations, 1, 2027 _verbatim_declarations_end - _verbatim_declarations, stdout); 2028 } 2029 2030 if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */ 2031 { 2032 output_line_directive (_struct_decl_lineno); 2033 printf ("%s\n", _struct_decl); 2034 } 2035 2036 if (option[INCLUDE]) { 2037 printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */ 2038 if (option[SHAREDLIB]) 2039 printf("#include <stddef.h>\n"); /* Declare offsetof() */ 2040 } 2041 2042 if (!option[ENUM]) 2043 { 2044 Output_Defines style; 2045 output_constants (style); 2046 } 2047 else if (option[GLOBAL]) 2048 { 2049 Output_Enum style (""); 2050 output_constants (style); 2051 } 2052 2053 printf ("/* maximum key range = %d, duplicates = %d */\n\n", 2054 _max_hash_value - _min_hash_value + 1, _total_duplicates); 2055 2056 if (option[UPPERLOWER]) 2057 { 2058 #if USE_DOWNCASE_TABLE 2059 output_upperlower_table (); 2060 #endif 2061 2062 if (option[LENTABLE]) 2063 output_upperlower_memcmp (); 2064 else 2065 { 2066 if (option[COMP]) 2067 output_upperlower_strncmp (); 2068 else 2069 output_upperlower_strcmp (); 2070 } 2071 } 2072 2073 if (option[CPLUSPLUS]) 2074 printf ("class %s\n" 2075 "{\n" 2076 "private:\n" 2077 " static inline unsigned int %s (const char *str, unsigned int len);\n" 2078 "public:\n" 2079 " static %s%s%s (const char *str, unsigned int len);\n" 2080 "};\n" 2081 "\n", 2082 option.get_class_name (), option.get_hash_name (), 2083 const_for_struct, _return_type, option.get_function_name ()); 2084 2085 output_hash_function (); 2086 2087 if (option[SHAREDLIB] && (option[GLOBAL] || option[TYPE])) 2088 output_lookup_pools (); 2089 if (option[GLOBAL]) 2090 output_lookup_tables (); 2091 2092 output_lookup_function (); 2093 2094 if (_verbatim_code < _verbatim_code_end) 2095 { 2096 output_line_directive (_verbatim_code_lineno); 2097 fwrite (_verbatim_code, 1, _verbatim_code_end - _verbatim_code, stdout); 2098 } 2099 2100 fflush (stdout); 2101} 2102