output.cc revision 228604
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 ("(int)(long)&((struct %s_t *)0)->%s_str%d", 1110 option.get_stringpool_name (), option.get_stringpool_name (), 1111 stringpool_index); 1112 else 1113 output_string (temp->_allchars, temp->_allchars_length); 1114 if (option[TYPE]) 1115 { 1116 if (strlen (temp->_rest) > 0) 1117 printf (",%s", temp->_rest); 1118 printf ("}"); 1119 } 1120 if (option[DEBUG]) 1121 printf (" /* hash value = %d, index = %d */", 1122 temp->_hash_value, temp->_final_index); 1123} 1124 1125static void 1126output_keyword_blank_entries (int count, const char *indent) 1127{ 1128 int columns; 1129 if (option[TYPE]) 1130 { 1131 columns = 58 / (4 + (option[SHAREDLIB] ? 2 : option[NULLSTRINGS] ? 8 : 2) 1132 + strlen (option.get_initializer_suffix())); 1133 if (columns == 0) 1134 columns = 1; 1135 } 1136 else 1137 { 1138 columns = (option[SHAREDLIB] ? 9 : option[NULLSTRINGS] ? 4 : 9); 1139 } 1140 int column = 0; 1141 for (int i = 0; i < count; i++) 1142 { 1143 if ((column % columns) == 0) 1144 { 1145 if (i > 0) 1146 printf (",\n"); 1147 printf ("%s ", indent); 1148 } 1149 else 1150 { 1151 if (i > 0) 1152 printf (", "); 1153 } 1154 if (option[TYPE]) 1155 printf ("{"); 1156 if (option[SHAREDLIB]) 1157 printf ("-1"); 1158 else 1159 { 1160 if (option[NULLSTRINGS]) 1161 printf ("(char*)0"); 1162 else 1163 printf ("\"\""); 1164 } 1165 if (option[TYPE]) 1166 printf ("%s}", option.get_initializer_suffix()); 1167 column++; 1168 } 1169} 1170 1171/* Prints out the array containing the keywords for the hash function. */ 1172 1173void 1174Output::output_keyword_table () const 1175{ 1176 const char *indent = option[GLOBAL] ? "" : " "; 1177 int index; 1178 KeywordExt_List *temp; 1179 1180 printf ("%sstatic ", 1181 indent); 1182 output_const_type (const_readonly_array, _wordlist_eltype); 1183 printf ("%s[] =\n" 1184 "%s {\n", 1185 option.get_wordlist_name (), 1186 indent); 1187 1188 /* Generate an array of reserved words at appropriate locations. */ 1189 1190 for (temp = _head, index = 0; temp; temp = temp->rest()) 1191 { 1192 KeywordExt *keyword = temp->first(); 1193 1194 /* If generating a switch statement, and there is no user defined type, 1195 we generate non-duplicates directly in the code. Only duplicates go 1196 into the table. */ 1197 if (option[SWITCH] && !option[TYPE] && !keyword->_duplicate_link) 1198 continue; 1199 1200 if (index > 0) 1201 printf (",\n"); 1202 1203 if (index < keyword->_hash_value && !option[SWITCH] && !option[DUP]) 1204 { 1205 /* Some blank entries. */ 1206 output_keyword_blank_entries (keyword->_hash_value - index, indent); 1207 printf (",\n"); 1208 index = keyword->_hash_value; 1209 } 1210 1211 keyword->_final_index = index; 1212 1213 output_keyword_entry (keyword, index, indent); 1214 1215 /* Deal with duplicates specially. */ 1216 if (keyword->_duplicate_link) // implies option[DUP] 1217 for (KeywordExt *links = keyword->_duplicate_link; links; links = links->_duplicate_link) 1218 { 1219 links->_final_index = ++index; 1220 printf (",\n"); 1221 int stringpool_index = 1222 (links->_allchars_length == keyword->_allchars_length 1223 && memcmp (links->_allchars, keyword->_allchars, 1224 keyword->_allchars_length) == 0 1225 ? keyword->_final_index 1226 : links->_final_index); 1227 output_keyword_entry (links, stringpool_index, indent); 1228 } 1229 1230 index++; 1231 } 1232 if (index > 0) 1233 printf ("\n"); 1234 1235 printf ("%s };\n\n", indent); 1236} 1237 1238/* ------------------------------------------------------------------------- */ 1239 1240/* Generates the large, sparse table that maps hash values into 1241 the smaller, contiguous range of the keyword table. */ 1242 1243void 1244Output::output_lookup_array () const 1245{ 1246 if (option[DUP]) 1247 { 1248 const int DEFAULT_VALUE = -1; 1249 1250 /* Because of the way output_keyword_table works, every duplicate set is 1251 stored contiguously in the wordlist array. */ 1252 struct duplicate_entry 1253 { 1254 int hash_value; /* Hash value for this particular duplicate set. */ 1255 int index; /* Index into the main keyword storage array. */ 1256 int count; /* Number of consecutive duplicates at this index. */ 1257 }; 1258 1259 duplicate_entry *duplicates = new duplicate_entry[_total_duplicates]; 1260 int *lookup_array = new int[_max_hash_value + 1 + 2*_total_duplicates]; 1261 int lookup_array_size = _max_hash_value + 1; 1262 duplicate_entry *dup_ptr = &duplicates[0]; 1263 int *lookup_ptr = &lookup_array[_max_hash_value + 1 + 2*_total_duplicates]; 1264 1265 while (lookup_ptr > lookup_array) 1266 *--lookup_ptr = DEFAULT_VALUE; 1267 1268 /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */ 1269 1270 for (KeywordExt_List *temp = _head; temp; temp = temp->rest()) 1271 { 1272 int hash_value = temp->first()->_hash_value; 1273 lookup_array[hash_value] = temp->first()->_final_index; 1274 if (option[DEBUG]) 1275 fprintf (stderr, "keyword = %.*s, index = %d\n", 1276 temp->first()->_allchars_length, temp->first()->_allchars, temp->first()->_final_index); 1277 if (temp->first()->_duplicate_link) 1278 { 1279 /* Start a duplicate entry. */ 1280 dup_ptr->hash_value = hash_value; 1281 dup_ptr->index = temp->first()->_final_index; 1282 dup_ptr->count = 1; 1283 1284 for (KeywordExt *ptr = temp->first()->_duplicate_link; ptr; ptr = ptr->_duplicate_link) 1285 { 1286 dup_ptr->count++; 1287 if (option[DEBUG]) 1288 fprintf (stderr, 1289 "static linked keyword = %.*s, index = %d\n", 1290 ptr->_allchars_length, ptr->_allchars, ptr->_final_index); 1291 } 1292 assert (dup_ptr->count >= 2); 1293 dup_ptr++; 1294 } 1295 } 1296 1297 while (dup_ptr > duplicates) 1298 { 1299 dup_ptr--; 1300 1301 if (option[DEBUG]) 1302 fprintf (stderr, 1303 "dup_ptr[%td]: hash_value = %d, index = %d, count = %d\n", 1304 dup_ptr - duplicates, 1305 dup_ptr->hash_value, dup_ptr->index, dup_ptr->count); 1306 1307 int i; 1308 /* Start searching for available space towards the right part 1309 of the lookup array. */ 1310 for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++) 1311 if (lookup_array[i] == DEFAULT_VALUE 1312 && lookup_array[i + 1] == DEFAULT_VALUE) 1313 goto found_i; 1314 /* If we didn't find it to the right look to the left instead... */ 1315 for (i = dup_ptr->hash_value-1; i >= 0; i--) 1316 if (lookup_array[i] == DEFAULT_VALUE 1317 && lookup_array[i + 1] == DEFAULT_VALUE) 1318 goto found_i; 1319 /* Append to the end of lookup_array. */ 1320 i = lookup_array_size; 1321 lookup_array_size += 2; 1322 found_i: 1323 /* Put in an indirection from dup_ptr->_hash_value to i. 1324 At i and i+1 store dup_ptr->_final_index and dup_ptr->count. */ 1325 assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index); 1326 lookup_array[dup_ptr->hash_value] = - 1 - _total_keys - i; 1327 lookup_array[i] = - _total_keys + dup_ptr->index; 1328 lookup_array[i + 1] = - dup_ptr->count; 1329 /* All these three values are <= -2, distinct from DEFAULT_VALUE. */ 1330 } 1331 1332 /* The values of the lookup array are now known. */ 1333 1334 int min = INT_MAX; 1335 int max = INT_MIN; 1336 lookup_ptr = lookup_array + lookup_array_size; 1337 while (lookup_ptr > lookup_array) 1338 { 1339 int val = *--lookup_ptr; 1340 if (min > val) 1341 min = val; 1342 if (max < val) 1343 max = val; 1344 } 1345 1346 const char *indent = option[GLOBAL] ? "" : " "; 1347 printf ("%sstatic %s%s lookup[] =\n" 1348 "%s {", 1349 indent, const_readonly_array, smallest_integral_type (min, max), 1350 indent); 1351 1352 int field_width; 1353 /* Calculate maximum number of digits required for MIN..MAX. */ 1354 { 1355 field_width = 2; 1356 for (int trunc = max; (trunc /= 10) > 0;) 1357 field_width++; 1358 } 1359 if (min < 0) 1360 { 1361 int neg_field_width = 2; 1362 for (int trunc = -min; (trunc /= 10) > 0;) 1363 neg_field_width++; 1364 neg_field_width++; /* account for the minus sign */ 1365 if (field_width < neg_field_width) 1366 field_width = neg_field_width; 1367 } 1368 1369 const int columns = 42 / field_width; 1370 int column; 1371 1372 column = 0; 1373 for (int i = 0; i < lookup_array_size; i++) 1374 { 1375 if (i > 0) 1376 printf (","); 1377 if ((column++ % columns) == 0) 1378 printf("\n%s ", indent); 1379 printf ("%*d", field_width, lookup_array[i]); 1380 } 1381 printf ("\n%s };\n\n", indent); 1382 1383 delete[] duplicates; 1384 delete[] lookup_array; 1385 } 1386} 1387 1388/* ------------------------------------------------------------------------- */ 1389 1390/* Generate all pools needed for the lookup function. */ 1391 1392void 1393Output::output_lookup_pools () const 1394{ 1395 if (option[SWITCH]) 1396 { 1397 if (option[TYPE] || (option[DUP] && _total_duplicates > 0)) 1398 output_string_pool (); 1399 } 1400 else 1401 { 1402 output_string_pool (); 1403 } 1404} 1405 1406/* Generate all the tables needed for the lookup function. */ 1407 1408void 1409Output::output_lookup_tables () const 1410{ 1411 if (option[SWITCH]) 1412 { 1413 /* Use the switch in place of lookup table. */ 1414 if (option[LENTABLE] && (option[DUP] && _total_duplicates > 0)) 1415 output_keylength_table (); 1416 if (option[TYPE] || (option[DUP] && _total_duplicates > 0)) 1417 output_keyword_table (); 1418 } 1419 else 1420 { 1421 /* Use the lookup table, in place of switch. */ 1422 if (option[LENTABLE]) 1423 output_keylength_table (); 1424 output_keyword_table (); 1425 output_lookup_array (); 1426 } 1427} 1428 1429/* ------------------------------------------------------------------------- */ 1430 1431/* Output a single switch case (including duplicates). Advance list. */ 1432 1433static KeywordExt_List * 1434output_switch_case (KeywordExt_List *list, int indent, int *jumps_away) 1435{ 1436 if (option[DEBUG]) 1437 printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n", 1438 indent, "", list->first()->_hash_value, list->first()->_allchars_length, list->first()->_allchars); 1439 1440 if (option[DUP] && list->first()->_duplicate_link) 1441 { 1442 if (option[LENTABLE]) 1443 printf ("%*slengthptr = &%s[%d];\n", 1444 indent, "", option.get_lengthtable_name (), list->first()->_final_index); 1445 printf ("%*swordptr = &%s[%d];\n", 1446 indent, "", option.get_wordlist_name (), list->first()->_final_index); 1447 1448 int count = 0; 1449 for (KeywordExt *links = list->first(); links; links = links->_duplicate_link) 1450 count++; 1451 1452 printf ("%*swordendptr = wordptr + %d;\n" 1453 "%*sgoto multicompare;\n", 1454 indent, "", count, 1455 indent, ""); 1456 *jumps_away = 1; 1457 } 1458 else 1459 { 1460 if (option[LENTABLE]) 1461 { 1462 printf ("%*sif (len == %d)\n" 1463 "%*s {\n", 1464 indent, "", list->first()->_allchars_length, 1465 indent, ""); 1466 indent += 4; 1467 } 1468 printf ("%*sresword = ", 1469 indent, ""); 1470 if (option[TYPE]) 1471 printf ("&%s[%d]", option.get_wordlist_name (), list->first()->_final_index); 1472 else 1473 output_string (list->first()->_allchars, list->first()->_allchars_length); 1474 printf (";\n"); 1475 printf ("%*sgoto compare;\n", 1476 indent, ""); 1477 if (option[LENTABLE]) 1478 { 1479 indent -= 4; 1480 printf ("%*s }\n", 1481 indent, ""); 1482 } 1483 else 1484 *jumps_away = 1; 1485 } 1486 1487 return list->rest(); 1488} 1489 1490/* Output a total of size cases, grouped into num_switches switch statements, 1491 where 0 < num_switches <= size. */ 1492 1493static void 1494output_switches (KeywordExt_List *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent) 1495{ 1496 if (option[DEBUG]) 1497 printf ("%*s/* know %d <= key <= %d, contains %d cases */\n", 1498 indent, "", min_hash_value, max_hash_value, size); 1499 1500 if (num_switches > 1) 1501 { 1502 int part1 = num_switches / 2; 1503 int part2 = num_switches - part1; 1504 int size1 = static_cast<int>(static_cast<double>(size) / static_cast<double>(num_switches) * static_cast<double>(part1) + 0.5); 1505 int size2 = size - size1; 1506 1507 KeywordExt_List *temp = list; 1508 for (int count = size1; count > 0; count--) 1509 temp = temp->rest(); 1510 1511 printf ("%*sif (key < %d)\n" 1512 "%*s {\n", 1513 indent, "", temp->first()->_hash_value, 1514 indent, ""); 1515 1516 output_switches (list, part1, size1, min_hash_value, temp->first()->_hash_value-1, indent+4); 1517 1518 printf ("%*s }\n" 1519 "%*selse\n" 1520 "%*s {\n", 1521 indent, "", indent, "", indent, ""); 1522 1523 output_switches (temp, part2, size2, temp->first()->_hash_value, max_hash_value, indent+4); 1524 1525 printf ("%*s }\n", 1526 indent, ""); 1527 } 1528 else 1529 { 1530 /* Output a single switch. */ 1531 int lowest_case_value = list->first()->_hash_value; 1532 if (size == 1) 1533 { 1534 int jumps_away = 0; 1535 assert (min_hash_value <= lowest_case_value); 1536 assert (lowest_case_value <= max_hash_value); 1537 if (min_hash_value == max_hash_value) 1538 output_switch_case (list, indent, &jumps_away); 1539 else 1540 { 1541 printf ("%*sif (key == %d)\n" 1542 "%*s {\n", 1543 indent, "", lowest_case_value, 1544 indent, ""); 1545 output_switch_case (list, indent+4, &jumps_away); 1546 printf ("%*s }\n", 1547 indent, ""); 1548 } 1549 } 1550 else 1551 { 1552 if (lowest_case_value == 0) 1553 printf ("%*sswitch (key)\n", indent, ""); 1554 else 1555 printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value); 1556 printf ("%*s {\n", 1557 indent, ""); 1558 for (; size > 0; size--) 1559 { 1560 int jumps_away = 0; 1561 printf ("%*s case %d:\n", 1562 indent, "", list->first()->_hash_value - lowest_case_value); 1563 list = output_switch_case (list, indent+6, &jumps_away); 1564 if (!jumps_away) 1565 printf ("%*s break;\n", 1566 indent, ""); 1567 } 1568 printf ("%*s }\n", 1569 indent, ""); 1570 } 1571 } 1572} 1573 1574/* Generates C code to perform the keyword lookup. */ 1575 1576void 1577Output::output_lookup_function_body (const Output_Compare& comparison) const 1578{ 1579 printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n" 1580 " {\n" 1581 " register int key = %s (str, len);\n\n", 1582 option.get_hash_name ()); 1583 1584 if (option[SWITCH]) 1585 { 1586 int switch_size = num_hash_values (); 1587 int num_switches = option.get_total_switches (); 1588 if (num_switches > switch_size) 1589 num_switches = switch_size; 1590 1591 printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n" 1592 " {\n"); 1593 if (option[DUP] && _total_duplicates > 0) 1594 { 1595 if (option[LENTABLE]) 1596 printf (" register %s%s *lengthptr;\n", 1597 const_always, smallest_integral_type (_max_key_len)); 1598 printf (" register "); 1599 output_const_type (const_readonly_array, _wordlist_eltype); 1600 printf ("*wordptr;\n"); 1601 printf (" register "); 1602 output_const_type (const_readonly_array, _wordlist_eltype); 1603 printf ("*wordendptr;\n"); 1604 } 1605 if (option[TYPE]) 1606 { 1607 printf (" register "); 1608 output_const_type (const_readonly_array, _struct_tag); 1609 printf ("*resword;\n\n"); 1610 } 1611 else 1612 printf (" register %sresword;\n\n", 1613 _struct_tag); 1614 1615 output_switches (_head, num_switches, switch_size, _min_hash_value, _max_hash_value, 10); 1616 1617 printf (" return 0;\n"); 1618 if (option[DUP] && _total_duplicates > 0) 1619 { 1620 int indent = 8; 1621 printf ("%*smulticompare:\n" 1622 "%*s while (wordptr < wordendptr)\n" 1623 "%*s {\n", 1624 indent, "", indent, "", indent, ""); 1625 if (option[LENTABLE]) 1626 { 1627 printf ("%*s if (len == *lengthptr)\n" 1628 "%*s {\n", 1629 indent, "", indent, ""); 1630 indent += 4; 1631 } 1632 printf ("%*s register %schar *s = ", 1633 indent, "", const_always); 1634 if (option[TYPE]) 1635 printf ("wordptr->%s", option.get_slot_name ()); 1636 else 1637 printf ("*wordptr"); 1638 if (option[SHAREDLIB]) 1639 printf (" + %s", 1640 option.get_stringpool_name ()); 1641 printf (";\n\n" 1642 "%*s if (", 1643 indent, ""); 1644 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); 1645 printf (")\n" 1646 "%*s return %s;\n", 1647 indent, "", 1648 option[TYPE] ? "wordptr" : "s"); 1649 if (option[LENTABLE]) 1650 { 1651 indent -= 4; 1652 printf ("%*s }\n", 1653 indent, ""); 1654 } 1655 if (option[LENTABLE]) 1656 printf ("%*s lengthptr++;\n", 1657 indent, ""); 1658 printf ("%*s wordptr++;\n" 1659 "%*s }\n" 1660 "%*s return 0;\n", 1661 indent, "", indent, "", indent, ""); 1662 } 1663 printf (" compare:\n"); 1664 if (option[TYPE]) 1665 { 1666 printf (" {\n" 1667 " register %schar *s = resword->%s", 1668 const_always, option.get_slot_name ()); 1669 if (option[SHAREDLIB]) 1670 printf (" + %s", 1671 option.get_stringpool_name ()); 1672 printf (";\n\n" 1673 " if ("); 1674 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); 1675 printf (")\n" 1676 " return resword;\n" 1677 " }\n"); 1678 } 1679 else 1680 { 1681 printf (" if ("); 1682 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword")); 1683 printf (")\n" 1684 " return resword;\n"); 1685 } 1686 printf (" }\n"); 1687 } 1688 else 1689 { 1690 printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n"); 1691 1692 if (option[DUP]) 1693 { 1694 int indent = 8; 1695 printf ("%*s{\n" 1696 "%*s register int index = lookup[key];\n\n" 1697 "%*s if (index >= 0)\n", 1698 indent, "", indent, "", indent, ""); 1699 if (option[LENTABLE]) 1700 { 1701 printf ("%*s {\n" 1702 "%*s if (len == %s[index])\n", 1703 indent, "", indent, "", option.get_lengthtable_name ()); 1704 indent += 4; 1705 } 1706 printf ("%*s {\n" 1707 "%*s register %schar *s = %s[index]", 1708 indent, "", 1709 indent, "", const_always, option.get_wordlist_name ()); 1710 if (option[TYPE]) 1711 printf (".%s", option.get_slot_name ()); 1712 if (option[SHAREDLIB]) 1713 printf (" + %s", 1714 option.get_stringpool_name ()); 1715 printf (";\n\n" 1716 "%*s if (", 1717 indent, ""); 1718 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); 1719 printf (")\n" 1720 "%*s return ", 1721 indent, ""); 1722 if (option[TYPE]) 1723 printf ("&%s[index]", option.get_wordlist_name ()); 1724 else 1725 printf ("s"); 1726 printf (";\n" 1727 "%*s }\n", 1728 indent, ""); 1729 if (option[LENTABLE]) 1730 { 1731 indent -= 4; 1732 printf ("%*s }\n", indent, ""); 1733 } 1734 if (_total_duplicates > 0) 1735 { 1736 printf ("%*s else if (index < -TOTAL_KEYWORDS)\n" 1737 "%*s {\n" 1738 "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n", 1739 indent, "", indent, "", indent, ""); 1740 if (option[LENTABLE]) 1741 printf ("%*s register %s%s *lengthptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n", 1742 indent, "", const_always, smallest_integral_type (_max_key_len), 1743 option.get_lengthtable_name ()); 1744 printf ("%*s register ", 1745 indent, ""); 1746 output_const_type (const_readonly_array, _wordlist_eltype); 1747 printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n", 1748 option.get_wordlist_name ()); 1749 printf ("%*s register ", 1750 indent, ""); 1751 output_const_type (const_readonly_array, _wordlist_eltype); 1752 printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n"); 1753 printf ("%*s while (wordptr < wordendptr)\n" 1754 "%*s {\n", 1755 indent, "", indent, ""); 1756 if (option[LENTABLE]) 1757 { 1758 printf ("%*s if (len == *lengthptr)\n" 1759 "%*s {\n", 1760 indent, "", indent, ""); 1761 indent += 4; 1762 } 1763 printf ("%*s register %schar *s = ", 1764 indent, "", const_always); 1765 if (option[TYPE]) 1766 printf ("wordptr->%s", option.get_slot_name ()); 1767 else 1768 printf ("*wordptr"); 1769 if (option[SHAREDLIB]) 1770 printf (" + %s", 1771 option.get_stringpool_name ()); 1772 printf (";\n\n" 1773 "%*s if (", 1774 indent, ""); 1775 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); 1776 printf (")\n" 1777 "%*s return %s;\n", 1778 indent, "", 1779 option[TYPE] ? "wordptr" : "s"); 1780 if (option[LENTABLE]) 1781 { 1782 indent -= 4; 1783 printf ("%*s }\n", 1784 indent, ""); 1785 } 1786 if (option[LENTABLE]) 1787 printf ("%*s lengthptr++;\n", 1788 indent, ""); 1789 printf ("%*s wordptr++;\n" 1790 "%*s }\n" 1791 "%*s }\n", 1792 indent, "", indent, "", indent, ""); 1793 } 1794 printf ("%*s}\n", 1795 indent, ""); 1796 } 1797 else 1798 { 1799 int indent = 8; 1800 if (option[LENTABLE]) 1801 { 1802 printf ("%*sif (len == %s[key])\n", 1803 indent, "", option.get_lengthtable_name ()); 1804 indent += 2; 1805 } 1806 1807 if (option[SHAREDLIB]) 1808 { 1809 if (!option[LENTABLE]) 1810 { 1811 printf ("%*s{\n" 1812 "%*s register int o = %s[key]", 1813 indent, "", 1814 indent, "", option.get_wordlist_name ()); 1815 if (option[TYPE]) 1816 printf (".%s", option.get_slot_name ()); 1817 printf (";\n" 1818 "%*s if (o >= 0)\n" 1819 "%*s {\n", 1820 indent, "", 1821 indent, ""); 1822 indent += 4; 1823 printf ("%*s register %schar *s = o", 1824 indent, "", const_always); 1825 } 1826 else 1827 { 1828 /* No need for the (o >= 0) test, because the 1829 (len == lengthtable[key]) test already guarantees that 1830 key points to nonempty table entry. */ 1831 printf ("%*s{\n" 1832 "%*s register %schar *s = %s[key]", 1833 indent, "", 1834 indent, "", const_always, 1835 option.get_wordlist_name ()); 1836 if (option[TYPE]) 1837 printf (".%s", option.get_slot_name ()); 1838 } 1839 printf (" + %s", 1840 option.get_stringpool_name ()); 1841 } 1842 else 1843 { 1844 printf ("%*s{\n" 1845 "%*s register %schar *s = %s[key]", 1846 indent, "", 1847 indent, "", const_always, option.get_wordlist_name ()); 1848 if (option[TYPE]) 1849 printf (".%s", option.get_slot_name ()); 1850 } 1851 1852 printf (";\n\n" 1853 "%*s if (", 1854 indent, ""); 1855 if (!option[SHAREDLIB] && option[NULLSTRINGS]) 1856 printf ("s && "); 1857 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); 1858 printf (")\n" 1859 "%*s return ", 1860 indent, ""); 1861 if (option[TYPE]) 1862 printf ("&%s[key]", option.get_wordlist_name ()); 1863 else 1864 printf ("s"); 1865 printf (";\n"); 1866 if (option[SHAREDLIB] && !option[LENTABLE]) 1867 { 1868 indent -= 4; 1869 printf ("%*s }\n", 1870 indent, ""); 1871 } 1872 printf ("%*s}\n", 1873 indent, ""); 1874 } 1875 } 1876 printf (" }\n" 1877 " return 0;\n"); 1878} 1879 1880/* Generates C code for the lookup function. */ 1881 1882void 1883Output::output_lookup_function () const 1884{ 1885 /* Output the function's head. */ 1886 if (option[KRC] | option[C] | option[ANSIC]) 1887 /* GCC 4.3 and above with -std=c99 or -std=gnu99 implements ISO C99 1888 inline semantics, unless -fgnu89-inline is used. It defines a macro 1889 __GNUC_STDC_INLINE__ to indicate this situation. */ 1890 printf ("#ifdef __GNUC__\n" 1891 "__inline\n" 1892 "#ifdef __GNUC_STDC_INLINE__\n" 1893 "__attribute__ ((__gnu_inline__))\n" 1894 "#endif\n" 1895 "#endif\n"); 1896 1897 printf ("%s%s\n", 1898 const_for_struct, _return_type); 1899 if (option[CPLUSPLUS]) 1900 printf ("%s::", option.get_class_name ()); 1901 printf ("%s ", option.get_function_name ()); 1902 printf (option[KRC] ? 1903 "(str, len)\n" 1904 " register char *str;\n" 1905 " register unsigned int len;\n" : 1906 option[C] ? 1907 "(str, len)\n" 1908 " register const char *str;\n" 1909 " register unsigned int len;\n" : 1910 option[ANSIC] | option[CPLUSPLUS] ? 1911 "(register const char *str, register unsigned int len)\n" : 1912 ""); 1913 1914 /* Output the function's body. */ 1915 printf ("{\n"); 1916 1917 if (option[ENUM] && !option[GLOBAL]) 1918 { 1919 Output_Enum style (" "); 1920 output_constants (style); 1921 } 1922 1923 if (option[SHAREDLIB] && !(option[GLOBAL] || option[TYPE])) 1924 output_lookup_pools (); 1925 if (!option[GLOBAL]) 1926 output_lookup_tables (); 1927 1928 if (option[LENTABLE]) 1929 output_lookup_function_body (Output_Compare_Memcmp ()); 1930 else 1931 { 1932 if (option[COMP]) 1933 output_lookup_function_body (Output_Compare_Strncmp ()); 1934 else 1935 output_lookup_function_body (Output_Compare_Strcmp ()); 1936 } 1937 1938 printf ("}\n"); 1939} 1940 1941/* ------------------------------------------------------------------------- */ 1942 1943/* Generates the hash function and the key word recognizer function 1944 based upon the user's Options. */ 1945 1946void 1947Output::output () 1948{ 1949 compute_min_max (); 1950 1951 if (option[C] | option[ANSIC] | option[CPLUSPLUS]) 1952 { 1953 const_always = "const "; 1954 const_readonly_array = (option[CONST] ? "const " : ""); 1955 const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : ""); 1956 } 1957 else 1958 { 1959 const_always = ""; 1960 const_readonly_array = ""; 1961 const_for_struct = ""; 1962 } 1963 1964 if (!option[TYPE]) 1965 { 1966 _return_type = (const_always[0] ? "const char *" : "char *"); 1967 _struct_tag = (const_always[0] ? "const char *" : "char *"); 1968 } 1969 1970 _wordlist_eltype = (option[SHAREDLIB] && !option[TYPE] ? "int" : _struct_tag); 1971 1972 printf ("/* "); 1973 if (option[KRC]) 1974 printf ("KR-C"); 1975 else if (option[C]) 1976 printf ("C"); 1977 else if (option[ANSIC]) 1978 printf ("ANSI-C"); 1979 else if (option[CPLUSPLUS]) 1980 printf ("C++"); 1981 printf (" code produced by gperf version %s */\n", version_string); 1982 option.print_options (); 1983 printf ("\n"); 1984 if (!option[POSITIONS]) 1985 { 1986 printf ("/* Computed positions: -k'"); 1987 _key_positions.print(); 1988 printf ("' */\n"); 1989 } 1990 printf ("\n"); 1991 1992 if (_charset_dependent 1993 && (_key_positions.get_size() > 0 || option[UPPERLOWER])) 1994 { 1995 /* The generated tables assume that the execution character set is 1996 based on ISO-646, not EBCDIC. */ 1997 printf ("#if !((' ' == 32) && ('!' == 33) && ('\"' == 34) && ('#' == 35) \\\n" 1998 " && ('%%' == 37) && ('&' == 38) && ('\\'' == 39) && ('(' == 40) \\\n" 1999 " && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \\\n" 2000 " && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \\\n" 2001 " && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \\\n" 2002 " && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \\\n" 2003 " && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \\\n" 2004 " && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \\\n" 2005 " && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \\\n" 2006 " && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \\\n" 2007 " && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \\\n" 2008 " && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \\\n" 2009 " && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \\\n" 2010 " && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \\\n" 2011 " && ('Z' == 90) && ('[' == 91) && ('\\\\' == 92) && (']' == 93) \\\n" 2012 " && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \\\n" 2013 " && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \\\n" 2014 " && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \\\n" 2015 " && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \\\n" 2016 " && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \\\n" 2017 " && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \\\n" 2018 " && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \\\n" 2019 " && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126))\n" 2020 "/* The character set is not based on ISO-646. */\n"); 2021 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"); 2022 printf ("#endif\n\n"); 2023 } 2024 2025 if (_verbatim_declarations < _verbatim_declarations_end) 2026 { 2027 output_line_directive (_verbatim_declarations_lineno); 2028 fwrite (_verbatim_declarations, 1, 2029 _verbatim_declarations_end - _verbatim_declarations, stdout); 2030 } 2031 2032 if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */ 2033 { 2034 output_line_directive (_struct_decl_lineno); 2035 printf ("%s\n", _struct_decl); 2036 } 2037 2038 if (option[INCLUDE]) 2039 printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */ 2040 2041 if (!option[ENUM]) 2042 { 2043 Output_Defines style; 2044 output_constants (style); 2045 } 2046 else if (option[GLOBAL]) 2047 { 2048 Output_Enum style (""); 2049 output_constants (style); 2050 } 2051 2052 printf ("/* maximum key range = %d, duplicates = %d */\n\n", 2053 _max_hash_value - _min_hash_value + 1, _total_duplicates); 2054 2055 if (option[UPPERLOWER]) 2056 { 2057 #if USE_DOWNCASE_TABLE 2058 output_upperlower_table (); 2059 #endif 2060 2061 if (option[LENTABLE]) 2062 output_upperlower_memcmp (); 2063 else 2064 { 2065 if (option[COMP]) 2066 output_upperlower_strncmp (); 2067 else 2068 output_upperlower_strcmp (); 2069 } 2070 } 2071 2072 if (option[CPLUSPLUS]) 2073 printf ("class %s\n" 2074 "{\n" 2075 "private:\n" 2076 " static inline unsigned int %s (const char *str, unsigned int len);\n" 2077 "public:\n" 2078 " static %s%s%s (const char *str, unsigned int len);\n" 2079 "};\n" 2080 "\n", 2081 option.get_class_name (), option.get_hash_name (), 2082 const_for_struct, _return_type, option.get_function_name ()); 2083 2084 output_hash_function (); 2085 2086 if (option[SHAREDLIB] && (option[GLOBAL] || option[TYPE])) 2087 output_lookup_pools (); 2088 if (option[GLOBAL]) 2089 output_lookup_tables (); 2090 2091 output_lookup_function (); 2092 2093 if (_verbatim_code < _verbatim_code_end) 2094 { 2095 output_line_directive (_verbatim_code_lineno); 2096 fwrite (_verbatim_code, 1, _verbatim_code_end - _verbatim_code, stdout); 2097 } 2098 2099 fflush (stdout); 2100} 2101