contrib/gperf/src/key-list.cc

   1 /* Routines for building, ordering, and printing the keyword list.
   2    Copyright (C) 1989-1998, 2000 Free Software Foundation, Inc.
   3    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
   4
   5 This file is part of GNU GPERF.
   6
   7 GNU GPERF is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 1, or (at your option)
  10 any later version.
  11
  12 GNU GPERF is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU GPERF; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA.  */
  20
  21 #include <stdio.h>
  22 #include <string.h> /* declares strncpy(), strchr() */
  23 #include <stdlib.h> /* declares malloc(), free(), abs(), exit(), abort() */
  24 #include <ctype.h>  /* declares isprint() */
  25 #include <assert.h> /* defines assert() */
  26 #include <limits.h> /* defines SCHAR_MAX etc. */
  27 #include "options.h"
  28 #include "read-line.h"
  29 #include "hash-table.h"
  30 #include "key-list.h"
  31 #include "trace.h"
  32 #include "version.h"
  33
  34 /* Make the hash table 8 times larger than the number of keyword entries. */
  35 static const int TABLE_MULTIPLE     = 10;
  36
  37 /* Efficiently returns the least power of two greater than or equal to X! */
  38 #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
  39
  40 int Key_List::determined[MAX_ALPHA_SIZE];
  41
  42 /* Destructor dumps diagnostics during debugging. */
  43
  44 Key_List::~Key_List (void)
  45 {
  46   T (Trace t ("Key_List::~Key_List");)
  47   if (option[DEBUG])
  48     {
  49       fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d"
  50                "\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n",
  51                list_len, total_keys, total_duplicates, max_key_len);
  52       dump ();
  53       fprintf (stderr, "End dumping list.\n\n");
  54     }
  55 }
  56
  57 /* Gathers the input stream into a buffer until one of two things occur:
  58
  59    1. We read a '%' followed by a '%'
  60    2. We read a '%' followed by a '}'
  61
  62    The first symbolizes the beginning of the keyword list proper,
  63    The second symbolizes the end of the C source code to be generated
  64    verbatim in the output file.
  65
  66    I assume that the keys are separated from the optional preceding struct
  67    declaration by a consecutive % followed by either % or } starting in
  68    the first column. The code below uses an expandible buffer to scan off
  69    and return a pointer to all the code (if any) appearing before the delimiter. */
  70
  71 const char *
  72 Key_List::get_special_input (char delimiter)
  73 {
  74   T (Trace t ("Key_List::get_special_input");)
  75   int size  = 80;
  76   char *buf = new char[size];
  77   int c, i;
  78
  79   for (i = 0; (c = getchar ()) != EOF; i++)
  80     {
  81       if (c == '%')
  82         {
  83           if ((c = getchar ()) == delimiter)
  84             {
  85
  86               while ((c = getchar ()) != '\n')
  87                 ; /* discard newline */
  88
  89               if (i == 0)
  90                 return "";
  91               else
  92                 {
  93                   buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
  94                   return buf;
  95                 }
  96             }
  97           else
  98             buf[i++] = '%';
  99         }
 100       else if (i >= size) /* Yikes, time to grow the buffer! */
 101         {
 102           char *temp = new char[size *= 2];
 103           int j;
 104
 105           for (j = 0; j < i; j++)
 106             temp[j] = buf[j];
 107
 108           buf = temp;
 109         }
 110       buf[i] = c;
 111     }
 112
 113   return 0;        /* Problem here. */
 114 }
 115
 116 /* Stores any C text that must be included verbatim into the
 117    generated code output. */
 118
 119 const char *
 120 Key_List::save_include_src (void)
 121 {
 122   T (Trace t ("Key_List::save_include_src");)
 123   int c;
 124
 125   if ((c = getchar ()) != '%')
 126     ungetc (c, stdin);
 127   else if ((c = getchar ()) != '{')
 128     {
 129       fprintf (stderr, "internal error, %c != '{' on line %d in file %s", c, __LINE__, __FILE__);
 130       exit (1);
 131     }
 132   else
 133     return get_special_input ('}');
 134   return "";
 135 }
 136
 137 /* Determines from the input file whether the user wants to build a table
 138    from a user-defined struct, or whether the user is content to simply
 139    use the default array of keys. */
 140
 141 const char *
 142 Key_List::get_array_type (void)
 143 {
 144   T (Trace t ("Key_List::get_array_type");)
 145   return get_special_input ('%');
 146 }
 147
 148 /* strcspn - find length of initial segment of S consisting entirely
 149    of characters not from REJECT (borrowed from Henry Spencer's
 150    ANSI string package, when GNU libc comes out I'll replace this...). */
 151
 152 #ifndef strcspn
 153 inline int
 154 Key_List::strcspn (const char *s, const char *reject)
 155 {
 156   T (Trace t ("Key_List::strcspn");)
 157   const char *scan;
 158   const char *rej_scan;
 159   int   count = 0;
 160
 161   for (scan = s; *scan; scan++)
 162     {
 163
 164       for (rej_scan = reject; *rej_scan; rej_scan++)
 165         if (*scan == *rej_scan)
 166           return count;
 167
 168       count++;
 169     }
 170
 171   return count;
 172 }
 173 #endif
 174
 175 /* Sets up the Return_Type, the Struct_Tag type and the Array_Type
 176    based upon various user Options. */
 177
 178 void
 179 Key_List::set_output_types (void)
 180 {
 181   T (Trace t ("Key_List::set_output_types");)
 182   if (option[TYPE])
 183     {
 184       array_type = get_array_type ();
 185       if (!array_type)
 186         /* Something's wrong, but we'll catch it later on, in read_keys()... */
 187         return;
 188       /* Yow, we've got a user-defined type... */
 189       int i = strcspn (array_type, "{\n\0");
 190       /* Remove trailing whitespace. */
 191       while (i > 0 && strchr (" \t", array_type[i-1]))
 192         i--;
 193       int struct_tag_length = i;
 194
 195       /* Set `struct_tag' to a naked "struct something". */
 196       char *structtag = new char[struct_tag_length + 1];
 197       strncpy (structtag, array_type, struct_tag_length);
 198       structtag[struct_tag_length] = '\0';
 199       struct_tag = structtag;
 200
 201       /* The return type of the lookup function is "struct something *".
 202          No "const" here, because if !option[CONST], some user code might want
 203          to modify the structure. */
 204       char *rettype = new char[struct_tag_length + 3];
 205       strncpy (rettype, array_type, struct_tag_length);
 206       rettype[struct_tag_length] = ' ';
 207       rettype[struct_tag_length + 1] = '*';
 208       rettype[struct_tag_length + 2] = '\0';
 209       return_type = rettype;
 210     }
 211 }
 212
 213 /* Extracts a key from an input line and creates a new List_Node for it. */
 214
 215 static List_Node *
 216 parse_line (const char *line, const char *delimiters)
 217 {
 218   if (*line == '"')
 219     {
 220       /* Parse a string in ANSI C syntax. */
 221       char *key = new char[strlen(line)];
 222       char *kp = key;
 223       const char *lp = line + 1;
 224
 225       for (; *lp;)
 226         {
 227           char c = *lp;
 228
 229           if (c == '\0')
 230             {
 231               fprintf (stderr, "unterminated string: %s\n", line);
 232               exit (1);
 233             }
 234           else if (c == '\\')
 235             {
 236               c = *++lp;
 237               switch (c)
 238                 {
 239                 case '0': case '1': case '2': case '3':
 240                 case '4': case '5': case '6': case '7':
 241                   {
 242                     int code = 0;
 243                     int count = 0;
 244                     while (count < 3 && *lp >= '0' && *lp <= '7')
 245                       {
 246                         code = (code << 3) + (*lp - '0');
 247                         lp++;
 248                         count++;
 249                       }
 250                     if (code > UCHAR_MAX)
 251                       fprintf (stderr, "octal escape out of range: %s\n", line);
 252                     *kp = (char) code;
 253                     break;
 254                   }
 255                 case 'x':
 256                   {
 257                     int code = 0;
 258                     int count = 0;
 259                     lp++;
 260                     while ((*lp >= '0' && *lp <= '9')
 261                            || (*lp >= 'A' && *lp <= 'F')
 262                            || (*lp >= 'a' && *lp <= 'f'))
 263                       {
 264                         code = (code << 4)
 265                                + (*lp >= 'A' && *lp <= 'F' ? *lp - 'A' + 10 :
 266                                   *lp >= 'a' && *lp <= 'f' ? *lp - 'a' + 10 :
 267                                   *lp - '0');
 268                         lp++;
 269                         count++;
 270                       }
 271                     if (count == 0)
 272                       fprintf (stderr, "hexadecimal escape without any hex digits: %s\n", line);
 273                     if (code > UCHAR_MAX)
 274                       fprintf (stderr, "hexadecimal escape out of range: %s\n", line);
 275                     *kp = (char) code;
 276                     break;
 277                   }
 278                 case '\\': case '\'': case '"':
 279                   *kp = c;
 280                   lp++;
 281                   break;
 282                 case 'n':
 283                   *kp = '\n';
 284                   lp++;
 285                   break;
 286                 case 't':
 287                   *kp = '\t';
 288                   lp++;
 289                   break;
 290                 case 'r':
 291                   *kp = '\r';
 292                   lp++;
 293                   break;
 294                 case 'f':
 295                   *kp = '\f';
 296                   lp++;
 297                   break;
 298                 case 'b':
 299                   *kp = '\b';
 300                   lp++;
 301                   break;
 302                 case 'a':
 303                   *kp = '\a';
 304                   lp++;
 305                   break;
 306                 case 'v':
 307                   *kp = '\v';
 308                   lp++;
 309                   break;
 310                 default:
 311                   fprintf (stderr, "invalid escape sequence in string: %s\n", line);
 312                   exit (1);
 313                 }
 314             }
 315           else if (c == '"')
 316             break;
 317           else
 318             {
 319               *kp = c;
 320               lp++;
 321             }
 322           kp++;
 323         }
 324       lp++;
 325       if (*lp != '\0')
 326         {
 327           if (strchr (delimiters, *lp) == NULL)
 328             {
 329               fprintf (stderr, "string not followed by delimiter: %s\n", line);
 330               exit (1);
 331             }
 332           lp++;
 333         }
 334       return new List_Node (key, kp - key, option[TYPE] ? lp : "");
 335     }
 336   else
 337     {
 338       /* Not a string. Look for the delimiter. */
 339       int len = strcspn (line, delimiters);
 340       const char *rest;
 341
 342       if (line[len] == '\0')
 343         rest = "";
 344       else
 345         /* Skip the first delimiter. */
 346         rest = &line[len + 1];
 347       return new List_Node (line, len, option[TYPE] ? rest : "");
 348     }
 349 }
 350
 351 /* Reads in all keys from standard input and creates a linked list pointed
 352    to by Head.  This list is then quickly checked for ``links,'' i.e.,
 353    unhashable elements possessing identical key sets and lengths. */
 354
 355 void
 356 Key_List::read_keys (void)
 357 {
 358   T (Trace t ("Key_List::read_keys");)
 359   char *ptr;
 360
 361   include_src = save_include_src ();
 362   set_output_types ();
 363
 364   /* Oops, problem with the input file. */
 365   if (! (ptr = Read_Line::get_line ()))
 366     {
 367       fprintf (stderr, "No words in input file, did you forget to prepend %s or use -t accidentally?\n", "%%");
 368       exit (1);
 369     }
 370
 371   /* Read in all the keywords from the input file. */
 372   else
 373     {
 374       const char *delimiter = option.get_delimiter ();
 375       List_Node  *temp, *trail = 0;
 376
 377       head = parse_line (ptr, delimiter);
 378
 379       for (temp = head;
 380            (ptr = Read_Line::get_line ()) && strcmp (ptr, "%%");
 381            temp = temp->next)
 382         {
 383           temp->next = parse_line (ptr, delimiter);
 384           total_keys++;
 385         }
 386
 387       /* See if any additional C code is included at end of this file. */
 388       if (ptr)
 389         additional_code = 1;
 390
 391       /* Hash table this number of times larger than keyword number. */
 392       int table_size = (list_len = total_keys) * TABLE_MULTIPLE;
 393
 394 #if LARGE_STACK_ARRAYS
 395       /* By allocating the memory here we save on dynamic allocation overhead.
 396          Table must be a power of 2 for the hash function scheme to work. */
 397       List_Node *table[POW (table_size)];
 398 #else
 399       // Note: we don't use new, because that invokes a custom operator new.
 400       int malloc_size = POW (table_size) * sizeof(List_Node*);
 401       if (malloc_size == 0) malloc_size = 1;
 402       List_Node **table = (List_Node**)malloc(malloc_size);
 403       if (table == NULL)
 404         abort ();
 405 #endif
 406
 407       /* Make large hash table for efficiency. */
 408       Hash_Table found_link (table, table_size, option[NOLENGTH]);
 409
 410       /* Test whether there are any links and also set the maximum length of
 411         an identifier in the keyword list. */
 412
 413       for (temp = head; temp; temp = temp->next)
 414         {
 415           List_Node *ptr = found_link.insert (temp);
 416
 417           /* Check for links.  We deal with these by building an equivalence class
 418              of all duplicate values (i.e., links) so that only 1 keyword is
 419              representative of the entire collection.  This *greatly* simplifies
 420              processing during later stages of the program. */
 421
 422           if (ptr)
 423             {
 424               total_duplicates++;
 425               list_len--;
 426               trail->next = temp->next;
 427               temp->link  = ptr->link;
 428               ptr->link   = temp;
 429
 430               /* Complain if user hasn't enabled the duplicate option. */
 431               if (!option[DUP] || option[DEBUG])
 432                 fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"%.*s\".\n",
 433                                  temp->key_length, temp->key,
 434                                  ptr->key_length, ptr->key,
 435                                  temp->char_set_length, temp->char_set);
 436             }
 437           else
 438             trail = temp;
 439
 440           /* Update minimum and maximum keyword length, if needed. */
 441           if (max_key_len < temp->key_length)
 442             max_key_len = temp->key_length;
 443           if (min_key_len > temp->key_length)
 444             min_key_len = temp->key_length;
 445         }
 446
 447 #if !LARGE_STACK_ARRAYS
 448       free ((char *) table);
 449 #endif
 450
 451       /* Exit program if links exists and option[DUP] not set, since we can't continue */
 452       if (total_duplicates)
 453         {
 454           if (option[DUP])
 455             fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n",
 456                              total_duplicates);
 457           else
 458             {
 459               fprintf (stderr, "%d input keys have identical hash values,\ntry different key positions or use option -D.\n",
 460                                total_duplicates);
 461               exit (1);
 462             }
 463         }
 464       /* Exit program if an empty string is used as key, since the comparison
 465          expressions don't work correctly for looking up an empty string. */
 466       if (min_key_len == 0)
 467         {
 468           fprintf (stderr, "Empty input key is not allowed.\nTo recognize an empty input key, your code should check for\nlen == 0 before calling the gperf generated lookup function.\n");
 469           exit (1);
 470         }
 471       if (option[ALLCHARS])
 472         option.set_keysig_size (max_key_len);
 473     }
 474 }
 475
 476 /* Recursively merges two sorted lists together to form one sorted list. The
 477    ordering criteria is by frequency of occurrence of elements in the key set
 478    or by the hash value.  This is a kludge, but permits nice sharing of
 479    almost identical code without incurring the overhead of a function
 480    call comparison. */
 481
 482 List_Node *
 483 Key_List::merge (List_Node *list1, List_Node *list2)
 484 {
 485   T (Trace t ("Key_List::merge");)
 486   List_Node *result;
 487   List_Node **resultp = &result;
 488   for (;;)
 489     {
 490       if (!list1)
 491         {
 492           *resultp = list2;
 493           break;
 494         }
 495       if (!list2)
 496         {
 497           *resultp = list1;
 498           break;
 499         }
 500       if (occurrence_sort && list1->occurrence < list2->occurrence
 501           || hash_sort && list1->hash_value > list2->hash_value)
 502         {
 503           *resultp = list2;
 504           resultp = &list2->next; list2 = list1; list1 = *resultp;
 505         }
 506       else
 507         {
 508           *resultp = list1;
 509           resultp = &list1->next; list1 = *resultp;
 510         }
 511     }
 512   return result;
 513 }
 514
 515 /* Applies the merge sort algorithm to recursively sort the key list by
 516    frequency of occurrence of elements in the key set. */
 517
 518 List_Node *
 519 Key_List::merge_sort (List_Node *head)
 520 {
 521   T (Trace t ("Key_List::merge_sort");)
 522   if (!head || !head->next)
 523     return head;
 524   else
 525     {
 526       List_Node *middle = head;
 527       List_Node *temp   = head->next->next;
 528
 529       while (temp)
 530         {
 531           temp   = temp->next;
 532           middle = middle->next;
 533           if (temp)
 534             temp = temp->next;
 535         }
 536
 537       temp         = middle->next;
 538       middle->next = 0;
 539       return merge (merge_sort (head), merge_sort (temp));
 540     }
 541 }
 542
 543 /* Returns the frequency of occurrence of elements in the key set. */
 544
 545 inline int
 546 Key_List::get_occurrence (List_Node *ptr)
 547 {
 548   T (Trace t ("Key_List::get_occurrence");)
 549   int value = 0;
 550
 551   const char *p = ptr->char_set;
 552   unsigned int i = ptr->char_set_length;
 553   for (; i > 0; p++, i--)
 554     value += occurrences[(unsigned char)(*p)];
 555
 556   return value;
 557 }
 558
 559 /* Enables the index location of all key set elements that are now
 560    determined. */
 561
 562 inline void
 563 Key_List::set_determined (List_Node *ptr)
 564 {
 565   T (Trace t ("Key_List::set_determined");)
 566
 567   const char *p = ptr->char_set;
 568   unsigned int i = ptr->char_set_length;
 569   for (; i > 0; p++, i--)
 570     determined[(unsigned char)(*p)] = 1;
 571 }
 572
 573 /* Returns TRUE if PTR's key set is already completely determined. */
 574
 575 inline int
 576 Key_List::already_determined (List_Node *ptr)
 577 {
 578   T (Trace t ("Key_List::already_determined");)
 579   int is_determined = 1;
 580
 581   const char *p = ptr->char_set;
 582   unsigned int i = ptr->char_set_length;
 583   for (; is_determined && i > 0; p++, i--)
 584     is_determined = determined[(unsigned char)(*p)];
 585
 586   return is_determined;
 587 }
 588
 589 /* Reorders the table by first sorting the list so that frequently occuring
 590    keys appear first, and then the list is reorded so that keys whose values
 591    are already determined will be placed towards the front of the list.  This
 592    helps prune the search time by handling inevitable collisions early in the
 593    search process.  See Cichelli's paper from Jan 1980 JACM for details.... */
 594
 595 void
 596 Key_List::reorder (void)
 597 {
 598   T (Trace t ("Key_List::reorder");)
 599   List_Node *ptr;
 600   for (ptr = head; ptr; ptr = ptr->next)
 601     ptr->occurrence = get_occurrence (ptr);
 602
 603   hash_sort = 0;
 604   occurrence_sort = 1;
 605
 606   for (ptr = head = merge_sort (head); ptr->next; ptr = ptr->next)
 607     {
 608       set_determined (ptr);
 609
 610       if (already_determined (ptr->next))
 611         continue;
 612       else
 613         {
 614           List_Node *trail_ptr = ptr->next;
 615           List_Node *run_ptr   = trail_ptr->next;
 616
 617           for (; run_ptr; run_ptr = trail_ptr->next)
 618             {
 619
 620               if (already_determined (run_ptr))
 621                 {
 622                   trail_ptr->next = run_ptr->next;
 623                   run_ptr->next   = ptr->next;
 624                   ptr = ptr->next = run_ptr;
 625                 }
 626               else
 627                 trail_ptr = run_ptr;
 628             }
 629         }
 630     }
 631 }
 632
 633 /* ============================ Output routines ============================ */
 634
 635 /* The "const " qualifier. */
 636 static const char *const_always;
 637
 638 /* The "const " qualifier, for read-only arrays. */
 639 static const char *const_readonly_array;
 640
 641 /* The "const " qualifier, for the array type. */
 642 static const char *const_for_struct;
 643
 644 /* Returns the smallest unsigned C type capable of holding integers up to N. */
 645
 646 static const char *
 647 smallest_integral_type (int n)
 648 {
 649   if (n <= UCHAR_MAX) return "unsigned char";
 650   if (n <= USHRT_MAX) return "unsigned short";
 651   return "unsigned int";
 652 }
 653
 654 /* Returns the smallest signed C type capable of holding integers
 655    from MIN to MAX. */
 656
 657 static const char *
 658 smallest_integral_type (int min, int max)
 659 {
 660   if (option[ANSIC] | option[CPLUSPLUS])
 661     if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char";
 662   if (min >= SHRT_MIN && max <= SHRT_MAX) return "short";
 663   return "int";
 664 }
 665
 666 /* A cast from `char' to a valid array index. */
 667 static const char *char_to_index;
 668
 669 /* ------------------------------------------------------------------------- */
 670
 671 /* Computes the maximum and minimum hash values.  Since the
 672    list is already sorted by hash value all we need to do is
 673    find the final item! */
 674
 675 void
 676 Key_List::compute_min_max (void)
 677 {
 678   T (Trace t ("Key_List::compute_min_max");)
 679   List_Node *temp;
 680   for (temp = head; temp->next; temp = temp->next)
 681     ;
 682
 683   min_hash_value = head->hash_value;
 684   max_hash_value = temp->hash_value;
 685 }
 686
 687 /* ------------------------------------------------------------------------- */
 688
 689 /* Returns the number of different hash values. */
 690
 691 int
 692 Key_List::num_hash_values (void)
 693 {
 694   T (Trace t ("Key_List::num_hash_values");)
 695   int count = 1;
 696   List_Node *temp;
 697   int value;
 698
 699   for (temp = head, value = temp->hash_value; temp->next; )
 700     {
 701       temp = temp->next;
 702       if (value != temp->hash_value)
 703         {
 704           value = temp->hash_value;
 705           count++;
 706         }
 707     }
 708   return count;
 709 }
 710
 711 /* -------------------- Output_Constants and subclasses -------------------- */
 712
 713 /* This class outputs an enumeration defining some constants. */
 714
 715 struct Output_Constants
 716 {
 717   virtual void output_start () = 0;
 718   virtual void output_item (const char *name, int value) = 0;
 719   virtual void output_end () = 0;
 720   Output_Constants () {}
 721   virtual ~Output_Constants () {}
 722 };
 723
 724 /* This class outputs an enumeration in #define syntax. */
 725
 726 struct Output_Defines : public Output_Constants
 727 {
 728   virtual void output_start ();
 729   virtual void output_item (const char *name, int value);
 730   virtual void output_end ();
 731   Output_Defines () {}
 732   virtual ~Output_Defines () {}
 733 };
 734
 735 void Output_Defines::output_start ()
 736 {
 737   T (Trace t ("Output_Defines::output_start");)
 738   printf ("\n");
 739 }
 740
 741 void Output_Defines::output_item (const char *name, int value)
 742 {
 743   T (Trace t ("Output_Defines::output_item");)
 744   printf ("#define %s %d\n", name, value);
 745 }
 746
 747 void Output_Defines::output_end ()
 748 {
 749   T (Trace t ("Output_Defines::output_end");)
 750 }
 751
 752 /* This class outputs an enumeration using `enum'. */
 753
 754 struct Output_Enum : public Output_Constants
 755 {
 756   virtual void output_start ();
 757   virtual void output_item (const char *name, int value);
 758   virtual void output_end ();
 759   Output_Enum (const char *indent) : indentation (indent) {}
 760   virtual ~Output_Enum () {}
 761 private:
 762   const char *indentation;
 763   int pending_comma;
 764 };
 765
 766 void Output_Enum::output_start ()
 767 {
 768   T (Trace t ("Output_Enum::output_start");)
 769   printf ("%senum\n"
 770           "%s  {\n",
 771           indentation, indentation);
 772   pending_comma = 0;
 773 }
 774
 775 void Output_Enum::output_item (const char *name, int value)
 776 {
 777   T (Trace t ("Output_Enum::output_item");)
 778   if (pending_comma)
 779     printf (",\n");
 780   printf ("%s    %s = %d", indentation, name, value);
 781   pending_comma = 1;
 782 }
 783
 784 void Output_Enum::output_end ()
 785 {
 786   T (Trace t ("Output_Enum::output_end");)
 787   if (pending_comma)
 788     printf ("\n");
 789   printf ("%s  };\n\n", indentation);
 790 }
 791
 792 /* Outputs the maximum and minimum hash values etc. */
 793
 794 void
 795 Key_List::output_constants (struct Output_Constants& style)
 796 {
 797   T (Trace t ("Key_List::output_constants");)
 798
 799   style.output_start ();
 800   style.output_item ("TOTAL_KEYWORDS", total_keys);
 801   style.output_item ("MIN_WORD_LENGTH", min_key_len);
 802   style.output_item ("MAX_WORD_LENGTH", max_key_len);
 803   style.output_item ("MIN_HASH_VALUE", min_hash_value);
 804   style.output_item ("MAX_HASH_VALUE", max_hash_value);
 805   style.output_end ();
 806 }
 807
 808 /* ------------------------------------------------------------------------- */
 809
 810 /* Outputs a keyword, as a string: enclosed in double quotes, escaping
 811    backslashes, double quote and unprintable characters. */
 812
 813 static void
 814 output_string (const char *key, int len)
 815 {
 816   T (Trace t ("output_string");)
 817
 818   putchar ('"');
 819   for (; len > 0; len--)
 820     {
 821       unsigned char c = (unsigned char) *key++;
 822       if (isprint (c))
 823         {
 824           if (c == '"' || c == '\\')
 825             putchar ('\\');
 826           putchar (c);
 827         }
 828       else
 829         {
 830           /* Use octal escapes, not hexadecimal escapes, because some old
 831              C compilers didn't understand hexadecimal escapes, and because
 832              hexadecimal escapes are not limited to 2 digits, thus needing
 833              special care if the following character happens to be a digit. */
 834           putchar ('\\');
 835           putchar ('0' + ((c >> 6) & 7));
 836           putchar ('0' + ((c >> 3) & 7));
 837           putchar ('0' + (c & 7));
 838         }
 839     }
 840   putchar ('"');
 841 }
 842
 843 /* ------------------------------------------------------------------------- */
 844
 845 /* Outputs a type and a const specifier.
 846    The output is terminated with a space. */
 847
 848 static void
 849 output_const_type (const char *const_string, const char *type_string)
 850 {
 851   if (type_string[strlen(type_string)-1] == '*')
 852     printf ("%s %s", type_string, const_string);
 853   else
 854     printf ("%s%s ", const_string, type_string);
 855 }
 856
 857 /* ----------------------- Output_Expr and subclasses ----------------------- */
 858
 859 /* This class outputs a general expression. */
 860
 861 struct Output_Expr
 862 {
 863   virtual void output_expr () const = 0;
 864   Output_Expr () {}
 865   virtual ~Output_Expr () {}
 866 };
 867
 868 /* This class outputs an expression formed by a single string. */
 869
 870 struct Output_Expr1 : public Output_Expr
 871 {
 872   virtual void output_expr () const;
 873   Output_Expr1 (const char *piece1) : p1 (piece1) {}
 874   virtual ~Output_Expr1 () {}
 875 private:
 876   const char *p1;
 877 };
 878
 879 void Output_Expr1::output_expr () const
 880 {
 881   T (Trace t ("Output_Expr1::output_expr");)
 882   printf ("%s", p1);
 883 }
 884
 885 #if 0 /* unused */
 886
 887 /* This class outputs an expression formed by the concatenation of two
 888    strings. */
 889
 890 struct Output_Expr2 : public Output_Expr
 891 {
 892   virtual void output_expr () const;
 893   Output_Expr2 (const char *piece1, const char *piece2)
 894     : p1 (piece1), p2 (piece2) {}
 895   virtual ~Output_Expr2 () {}
 896 private:
 897   const char *p1;
 898   const char *p2;
 899 };
 900
 901 void Output_Expr2::output_expr () const
 902 {
 903   T (Trace t ("Output_Expr2::output_expr");)
 904   printf ("%s%s", p1, p2);
 905 }
 906
 907 #endif
 908
 909 /* --------------------- Output_Compare and subclasses --------------------- */
 910
 911 /* This class outputs a comparison expression. */
 912
 913 struct Output_Compare
 914 {
 915   virtual void output_comparison (const Output_Expr& expr1,
 916                                   const Output_Expr& expr2) const = 0;
 917   Output_Compare () {}
 918   virtual ~Output_Compare () {}
 919 };
 920
 921 /* This class outputs a comparison using strcmp. */
 922
 923 struct Output_Compare_Strcmp : public Output_Compare
 924 {
 925   virtual void output_comparison (const Output_Expr& expr1,
 926                                   const Output_Expr& expr2) const;
 927   Output_Compare_Strcmp () {}
 928   virtual ~Output_Compare_Strcmp () {}
 929 };
 930
 931 void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
 932                                                const Output_Expr& expr2) const
 933 {
 934   T (Trace t ("Output_Compare_Strcmp::output_comparison");)
 935   printf ("*");
 936   expr1.output_expr ();
 937   printf (" == *");
 938   expr2.output_expr ();
 939   printf (" && !strcmp (");
 940   expr1.output_expr ();
 941   printf (" + 1, ");
 942   expr2.output_expr ();
 943   printf (" + 1)");
 944 }
 945
 946 /* This class outputs a comparison using strncmp.
 947    Note that the length of expr1 will be available through the local variable
 948    `len'. */
 949
 950 struct Output_Compare_Strncmp : public Output_Compare
 951 {
 952   virtual void output_comparison (const Output_Expr& expr1,
 953                                   const Output_Expr& expr2) const;
 954   Output_Compare_Strncmp () {}
 955   virtual ~Output_Compare_Strncmp () {}
 956 };
 957
 958 void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
 959                                                 const Output_Expr& expr2) const
 960 {
 961   T (Trace t ("Output_Compare_Strncmp::output_comparison");)
 962   printf ("*");
 963   expr1.output_expr ();
 964   printf (" == *");
 965   expr2.output_expr ();
 966   printf (" && !strncmp (");
 967   expr1.output_expr ();
 968   printf (" + 1, ");
 969   expr2.output_expr ();
 970   printf (" + 1, len - 1) && ");
 971   expr2.output_expr ();
 972   printf ("[len] == '\\0'");
 973 }
 974
 975 /* This class outputs a comparison using memcmp.
 976    Note that the length of expr1 (available through the local variable `len')
 977    must be verified to be equal to the length of expr2 prior to this
 978    comparison. */
 979
 980 struct Output_Compare_Memcmp : public Output_Compare
 981 {
 982   virtual void output_comparison (const Output_Expr& expr1,
 983                                   const Output_Expr& expr2) const;
 984   Output_Compare_Memcmp () {}
 985   virtual ~Output_Compare_Memcmp () {}
 986 };
 987
 988 void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
 989                                                const Output_Expr& expr2) const
 990 {
 991   T (Trace t ("Output_Compare_Memcmp::output_comparison");)
 992   printf ("*");
 993   expr1.output_expr ();
 994   printf (" == *");
 995   expr2.output_expr ();
 996   printf (" && !memcmp (");
 997   expr1.output_expr ();
 998   printf (" + 1, ");
 999   expr2.output_expr ();
1000   printf (" + 1, len - 1)");
1001 }
1002
1003 /* ------------------------------------------------------------------------- */
1004
1005 /* Generates C code for the hash function that returns the
1006    proper encoding for each key word. */
1007
1008 void
1009 Key_List::output_hash_function (void)
1010 {
1011   T (Trace t ("Key_List::output_hash_function");)
1012   const int max_column  = 10;
1013   int field_width;
1014
1015   /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
1016   field_width = 2;
1017   for (int trunc = max_hash_value; (trunc /= 10) > 0;)
1018     field_width++;
1019
1020   /* Output the function's head. */
1021   if (option[CPLUSPLUS])
1022     printf ("inline ");
1023   else if (option[KRC] | option[C] | option[ANSIC])
1024     printf ("#ifdef __GNUC__\n"
1025             "__inline\n"
1026             "#else\n"
1027             "#ifdef __cplusplus\n"
1028             "inline\n"
1029             "#endif\n"
1030             "#endif\n");
1031
1032   if (option[KRC] | option[C] | option[ANSIC])
1033     printf ("static ");
1034   printf ("unsigned int\n");
1035   if (option[CPLUSPLUS])
1036     printf ("%s::", option.get_class_name ());
1037   printf ("%s ", option.get_hash_name ());
1038   printf (option[KRC] ?
1039                  "(str, len)\n"
1040             "     register char *str;\n"
1041             "     register unsigned int len;\n" :
1042           option[C] ?
1043                  "(str, len)\n"
1044             "     register const char *str;\n"
1045             "     register unsigned int len;\n" :
1046           option[ANSIC] | option[CPLUSPLUS] ?
1047                  "(register const char *str, register unsigned int len)\n" :
1048           "");
1049
1050   /* Note that when the hash function is called, it has already been verified
1051      that  min_key_len <= len <= max_key_len. */
1052
1053   /* Output the function's body. */
1054   printf ("{\n");
1055
1056   /* First the asso_values array. */
1057   printf ("  static %s%s asso_values[] =\n"
1058           "    {",
1059           const_readonly_array,
1060           smallest_integral_type (max_hash_value + 1));
1061
1062   for (int count = 0; count < ALPHA_SIZE; count++)
1063     {
1064       if (count > 0)
1065         printf (",");
1066       if (!(count % max_column))
1067         printf ("\n     ");
1068       printf ("%*d", field_width,
1069               occurrences[count] ? asso_values[count] : max_hash_value + 1);
1070     }
1071
1072   printf ("\n"
1073           "    };\n");
1074
1075   /* Optimize special case of ``-k 1,$'' */
1076   if (option[DEFAULTCHARS])
1077     printf ("  return %sasso_values[%sstr[len - 1]] + asso_values[%sstr[0]];\n",
1078             option[NOLENGTH] ? "" : "len + ",
1079             char_to_index, char_to_index);
1080   else
1081     {
1082       int key_pos;
1083
1084       option.reset ();
1085
1086       /* Get first (also highest) key position. */
1087       key_pos = option.get ();
1088
1089       if (!option[ALLCHARS] && (key_pos == WORD_END || key_pos <= min_key_len))
1090         {
1091           /* We can perform additional optimizations here:
1092              Write it out as a single expression. Note that the values
1093              are added as `int's even though the asso_values array may
1094              contain `unsigned char's or `unsigned short's. */
1095
1096           printf ("  return %s",
1097                   option[NOLENGTH] ? "" : "len + ");
1098
1099           for (; key_pos != WORD_END; )
1100             {
1101               printf ("asso_values[%sstr[%d]]", char_to_index, key_pos - 1);
1102               if ((key_pos = option.get ()) != EOS)
1103                 printf (" + ");
1104               else
1105                 break;
1106             }
1107
1108           if (key_pos == WORD_END)
1109             printf ("asso_values[%sstr[len - 1]]", char_to_index);
1110
1111           printf (";\n");
1112         }
1113       else
1114         {
1115           /* We've got to use the correct, but brute force, technique. */
1116           printf ("  register int hval = %s;\n\n"
1117                   "  switch (%s)\n"
1118                   "    {\n"
1119                   "      default:\n",
1120                   option[NOLENGTH] ? "0" : "len",
1121                   option[NOLENGTH] ? "len" : "hval");
1122
1123           /* User wants *all* characters considered in hash. */
1124           if (option[ALLCHARS])
1125             {
1126               for (int i = max_key_len; i > 0; i--)
1127                 printf ("      case %d:\n"
1128                         "        hval += asso_values[%sstr[%d]];\n",
1129                         i, char_to_index, i - 1);
1130
1131               printf ("        break;\n"
1132                       "    }\n"
1133                       "  return hval;\n");
1134             }
1135           else                  /* do the hard part... */
1136             {
1137               while (key_pos != WORD_END && key_pos > max_key_len)
1138                 if ((key_pos = option.get ()) == EOS)
1139                   break;
1140
1141               if (key_pos != EOS && key_pos != WORD_END)
1142                 {
1143                   int i = key_pos;
1144                   do
1145                     {
1146                       for ( ; i >= key_pos; i--)
1147                         printf ("      case %d:\n", i);
1148
1149                       printf ("        hval += asso_values[%sstr[%d]];\n",
1150                               char_to_index, key_pos - 1);
1151
1152                       key_pos = option.get ();
1153                     }
1154                   while (key_pos != EOS && key_pos != WORD_END);
1155
1156                   for ( ; i >= min_key_len; i--)
1157                     printf ("      case %d:\n", i);
1158                 }
1159
1160               printf ("        break;\n"
1161                       "    }\n"
1162                       "  return hval");
1163               if (key_pos == WORD_END)
1164                 printf (" + asso_values[%sstr[len - 1]]", char_to_index);
1165               printf (";\n");
1166             }
1167         }
1168     }
1169   printf ("}\n\n");
1170 }
1171
1172 /* ------------------------------------------------------------------------- */
1173
1174 /* Prints out a table of keyword lengths, for use with the
1175    comparison code in generated function ``in_word_set''. */
1176
1177 void
1178 Key_List::output_keylength_table (void)
1179 {
1180   T (Trace t ("Key_List::output_keylength_table");)
1181   const int  columns = 14;
1182   int        index;
1183   int        column;
1184   const char *indent    = option[GLOBAL] ? "" : "  ";
1185   List_Node *temp;
1186
1187   printf ("%sstatic %s%s lengthtable[] =\n%s  {",
1188           indent, const_readonly_array,
1189           smallest_integral_type (max_key_len),
1190           indent);
1191
1192   /* Generate an array of lengths, similar to output_keyword_table. */
1193
1194   column = 0;
1195   for (temp = head, index = 0; temp; temp = temp->next)
1196     {
1197       if (option[SWITCH] && !option[TYPE]
1198           && !(temp->link
1199                || (temp->next && temp->hash_value == temp->next->hash_value)))
1200         continue;
1201
1202       if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1203         {
1204           /* Some blank entries. */
1205           for ( ; index < temp->hash_value; index++)
1206             {
1207               if (index > 0)
1208                 printf (",");
1209               if ((column++ % columns) == 0)
1210                 printf ("\n%s   ", indent);
1211               printf ("%3d", 0);
1212             }
1213         }
1214
1215       if (index > 0)
1216         printf (",");
1217       if ((column++ % columns) == 0)
1218         printf("\n%s   ", indent);
1219       printf ("%3d", temp->key_length);
1220
1221       /* Deal with links specially. */
1222       if (temp->link) // implies option[DUP]
1223         for (List_Node *links = temp->link; links; links = links->link)
1224           {
1225             ++index;
1226             printf (",");
1227             if ((column++ % columns) == 0)
1228               printf("\n%s   ", indent);
1229             printf ("%3d", links->key_length);
1230           }
1231
1232       index++;
1233     }
1234
1235   printf ("\n%s  };\n", indent);
1236   if (option[GLOBAL])
1237     printf ("\n");
1238 }
1239
1240 /* ------------------------------------------------------------------------- */
1241
1242 static void
1243 output_keyword_entry (List_Node *temp, const char *indent)
1244 {
1245   printf ("%s    ", indent);
1246   if (option[TYPE])
1247     printf ("{");
1248   output_string (temp->key, temp->key_length);
1249   if (option[TYPE])
1250     {
1251       if (strlen (temp->rest) > 0)
1252         printf (",%s", temp->rest);
1253       printf ("}");
1254     }
1255   if (option[DEBUG])
1256     printf (" /* hash value = %d, index = %d */",
1257             temp->hash_value, temp->index);
1258 }
1259
1260 static void
1261 output_keyword_blank_entries (int count, const char *indent)
1262 {
1263   int columns;
1264   if (option[TYPE])
1265     {
1266       columns = 58 / (6 + strlen (option.get_initializer_suffix()));
1267       if (columns == 0)
1268         columns = 1;
1269     }
1270   else
1271     {
1272       columns = 9;
1273     }
1274   int column = 0;
1275   for (int i = 0; i < count; i++)
1276     {
1277       if ((column % columns) == 0)
1278         {
1279           if (i > 0)
1280             printf (",\n");
1281           printf ("%s    ", indent);
1282         }
1283       else
1284         {
1285           if (i > 0)
1286             printf (", ");
1287         }
1288       if (option[TYPE])
1289         printf ("{\"\"%s}", option.get_initializer_suffix());
1290       else
1291         printf ("\"\"");
1292       column++;
1293     }
1294 }
1295
1296 /* Prints out the array containing the key words for the hash function. */
1297
1298 void
1299 Key_List::output_keyword_table (void)
1300 {
1301   T (Trace t ("Key_List::output_keyword_table");)
1302   const char *indent  = option[GLOBAL] ? "" : "  ";
1303   int         index;
1304   List_Node  *temp;
1305
1306   printf ("%sstatic ",
1307           indent);
1308   output_const_type (const_readonly_array, struct_tag);
1309   printf ("%s[] =\n"
1310           "%s  {\n",
1311           option.get_wordlist_name (),
1312           indent);
1313
1314   /* Generate an array of reserved words at appropriate locations. */
1315
1316   for (temp = head, index = 0; temp; temp = temp->next)
1317     {
1318       if (option[SWITCH] && !option[TYPE]
1319           && !(temp->link
1320                || (temp->next && temp->hash_value == temp->next->hash_value)))
1321         continue;
1322
1323       if (index > 0)
1324         printf (",\n");
1325
1326       if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1327         {
1328           /* Some blank entries. */
1329           output_keyword_blank_entries (temp->hash_value - index, indent);
1330           printf (",\n");
1331           index = temp->hash_value;
1332         }
1333
1334       temp->index = index;
1335
1336       output_keyword_entry (temp, indent);
1337
1338       /* Deal with links specially. */
1339       if (temp->link) // implies option[DUP]
1340         for (List_Node *links = temp->link; links; links = links->link)
1341           {
1342             links->index = ++index;
1343             printf (",\n");
1344             output_keyword_entry (links, indent);
1345           }
1346
1347       index++;
1348     }
1349   if (index > 0)
1350     printf ("\n");
1351
1352   printf ("%s  };\n\n", indent);
1353 }
1354
1355 /* ------------------------------------------------------------------------- */
1356
1357 /* Generates the large, sparse table that maps hash values into
1358    the smaller, contiguous range of the keyword table. */
1359
1360 void
1361 Key_List::output_lookup_array (void)
1362 {
1363   T (Trace t ("Key_List::output_lookup_array");)
1364   if (option[DUP])
1365     {
1366       const int DEFAULT_VALUE = -1;
1367
1368       /* Because of the way output_keyword_table works, every duplicate set is
1369          stored contiguously in the wordlist array. */
1370       struct duplicate_entry
1371         {
1372           int hash_value;  /* Hash value for this particular duplicate set. */
1373           int index;       /* Index into the main keyword storage array. */
1374           int count;       /* Number of consecutive duplicates at this index. */
1375         };
1376
1377 #if LARGE_STACK_ARRAYS
1378       duplicate_entry duplicates[total_duplicates];
1379       int lookup_array[max_hash_value + 1 + 2*total_duplicates];
1380 #else
1381       // Note: we don't use new, because that invokes a custom operator new.
1382       duplicate_entry *duplicates = (duplicate_entry *)
1383         malloc (total_duplicates * sizeof(duplicate_entry) + 1);
1384       int *lookup_array = (int *)
1385         malloc ((max_hash_value + 1 + 2*total_duplicates) * sizeof(int));
1386       if (duplicates == NULL || lookup_array == NULL)
1387         abort();
1388 #endif
1389       int lookup_array_size = max_hash_value + 1;
1390       duplicate_entry *dup_ptr = &duplicates[0];
1391       int *lookup_ptr = &lookup_array[max_hash_value + 1 + 2*total_duplicates];
1392
1393       while (lookup_ptr > lookup_array)
1394         *--lookup_ptr = DEFAULT_VALUE;
1395
1396       /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1397
1398       for (List_Node *temp = head; temp; temp = temp->next)
1399         {
1400           int hash_value = temp->hash_value;
1401           lookup_array[hash_value] = temp->index;
1402           if (option[DEBUG])
1403             fprintf (stderr, "keyword = %.*s, index = %d\n",
1404                      temp->key_length, temp->key, temp->index);
1405           if (temp->link
1406               || (temp->next && hash_value == temp->next->hash_value))
1407             {
1408               /* Start a duplicate entry. */
1409               dup_ptr->hash_value = hash_value;
1410               dup_ptr->index      = temp->index;
1411               dup_ptr->count      = 1;
1412
1413               for (;;)
1414                 {
1415                   for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
1416                     {
1417                       dup_ptr->count++;
1418                       if (option[DEBUG])
1419                         fprintf (stderr,
1420                                  "static linked keyword = %.*s, index = %d\n",
1421                                  ptr->key_length, ptr->key, ptr->index);
1422                     }
1423
1424                   if (!(temp->next && hash_value == temp->next->hash_value))
1425                     break;
1426
1427                   temp = temp->next;
1428
1429                   dup_ptr->count++;
1430                   if (option[DEBUG])
1431                     fprintf (stderr, "dynamic linked keyword = %.*s, index = %d\n",
1432                              temp->key_length, temp->key, temp->index);
1433                 }
1434               assert (dup_ptr->count >= 2);
1435               dup_ptr++;
1436             }
1437         }
1438
1439       while (dup_ptr > duplicates)
1440         {
1441           dup_ptr--;
1442
1443           if (option[DEBUG])
1444             fprintf (stderr,
1445                      "dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n",
1446                      dup_ptr - duplicates,
1447                      dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1448
1449           int i;
1450           /* Start searching for available space towards the right part
1451              of the lookup array. */
1452           for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1453             if (lookup_array[i] == DEFAULT_VALUE
1454                 && lookup_array[i + 1] == DEFAULT_VALUE)
1455               goto found_i;
1456           /* If we didn't find it to the right look to the left instead... */
1457           for (i = dup_ptr->hash_value-1; i >= 0; i--)
1458             if (lookup_array[i] == DEFAULT_VALUE
1459                 && lookup_array[i + 1] == DEFAULT_VALUE)
1460               goto found_i;
1461           /* Append to the end of lookup_array. */
1462           i = lookup_array_size;
1463           lookup_array_size += 2;
1464         found_i:
1465           /* Put in an indirection from dup_ptr->hash_value to i.
1466              At i and i+1 store dup_ptr->index and dup_ptr->count. */
1467           assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1468           lookup_array[dup_ptr->hash_value] = - 1 - total_keys - i;
1469           lookup_array[i] = - total_keys + dup_ptr->index;
1470           lookup_array[i + 1] = - dup_ptr->count;
1471           /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1472         }
1473
1474       /* The values of the lookup array are now known. */
1475
1476       int min = INT_MAX;
1477       int max = INT_MIN;
1478       lookup_ptr = lookup_array + lookup_array_size;
1479       while (lookup_ptr > lookup_array)
1480         {
1481           int val = *--lookup_ptr;
1482           if (min > val)
1483             min = val;
1484           if (max < val)
1485             max = val;
1486         }
1487
1488       const char *indent = option[GLOBAL] ? "" : "  ";
1489       printf ("%sstatic %s%s lookup[] =\n"
1490               "%s  {",
1491               indent, const_readonly_array, smallest_integral_type (min, max),
1492               indent);
1493
1494       int field_width;
1495       /* Calculate maximum number of digits required for MIN..MAX. */
1496       {
1497         field_width = 2;
1498         for (int trunc = max; (trunc /= 10) > 0;)
1499           field_width++;
1500       }
1501       if (min < 0)
1502         {
1503           int neg_field_width = 2;
1504           for (int trunc = -min; (trunc /= 10) > 0;)
1505             neg_field_width++;
1506           neg_field_width++; /* account for the minus sign */
1507           if (field_width < neg_field_width)
1508             field_width = neg_field_width;
1509         }
1510
1511       const int columns = 42 / field_width;
1512       int column;
1513
1514       column = 0;
1515       for (int i = 0; i < lookup_array_size; i++)
1516         {
1517           if (i > 0)
1518             printf (",");
1519           if ((column++ % columns) == 0)
1520             printf("\n%s   ", indent);
1521           printf ("%*d", field_width, lookup_array[i]);
1522         }
1523       printf ("\n%s  };\n\n", indent);
1524
1525 #if !LARGE_STACK_ARRAYS
1526       free ((char *) duplicates);
1527       free ((char *) lookup_array);
1528 #endif
1529     }
1530 }
1531
1532 /* ------------------------------------------------------------------------- */
1533
1534 /* Generate all the tables needed for the lookup function. */
1535
1536 void
1537 Key_List::output_lookup_tables (void)
1538 {
1539   T (Trace t ("Key_List::output_lookup_tables");)
1540
1541   if (option[SWITCH])
1542     {
1543       /* Use the switch in place of lookup table. */
1544       if (option[LENTABLE] && (option[DUP] && total_duplicates > 0))
1545         output_keylength_table ();
1546       if (option[TYPE] || (option[DUP] && total_duplicates > 0))
1547         output_keyword_table ();
1548     }
1549   else
1550     {
1551       /* Use the lookup table, in place of switch. */
1552       if (option[LENTABLE])
1553         output_keylength_table ();
1554       output_keyword_table ();
1555       output_lookup_array ();
1556     }
1557 }
1558
1559 /* ------------------------------------------------------------------------- */
1560
1561 /* Output a single switch case (including duplicates). Advance list. */
1562
1563 static List_Node *
1564 output_switch_case (List_Node *list, int indent, int *jumps_away)
1565 {
1566   T (Trace t ("output_switch_case");)
1567
1568   if (option[DEBUG])
1569     printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1570             indent, "", list->hash_value, list->key_length, list->key);
1571
1572   if (option[DUP]
1573       && (list->link
1574           || (list->next && list->hash_value == list->next->hash_value)))
1575     {
1576       if (option[LENTABLE])
1577         printf ("%*slengthptr = &lengthtable[%d];\n",
1578                 indent, "", list->index);
1579       printf ("%*swordptr = &%s[%d];\n",
1580               indent, "", option.get_wordlist_name (), list->index);
1581
1582       int count = 0;
1583       for (List_Node *temp = list; ; temp = temp->next)
1584         {
1585           for (List_Node *links = temp; links; links = links->link)
1586             count++;
1587           if (!(temp->next && temp->hash_value == temp->next->hash_value))
1588             break;
1589         }
1590
1591       printf ("%*swordendptr = wordptr + %d;\n"
1592               "%*sgoto multicompare;\n",
1593               indent, "", count,
1594               indent, "");
1595       *jumps_away = 1;
1596     }
1597   else
1598     {
1599       if (option[LENTABLE])
1600         {
1601           printf ("%*sif (len == %d)\n"
1602                   "%*s  {\n",
1603                   indent, "", list->key_length,
1604                   indent, "");
1605           indent += 4;
1606         }
1607       printf ("%*sresword = ",
1608               indent, "");
1609       if (option[TYPE])
1610         printf ("&%s[%d]", option.get_wordlist_name (), list->index);
1611       else
1612         output_string (list->key, list->key_length);
1613       printf (";\n");
1614       printf ("%*sgoto compare;\n",
1615               indent, "");
1616       if (option[LENTABLE])
1617         {
1618           indent -= 4;
1619           printf ("%*s  }\n",
1620                   indent, "");
1621         }
1622       else
1623         *jumps_away = 1;
1624     }
1625
1626   while (list->next && list->hash_value == list->next->hash_value)
1627     list = list->next;
1628   list = list->next;
1629   return list;
1630 }
1631
1632 /* Output a total of size cases, grouped into num_switches switch statements,
1633    where 0 < num_switches <= size. */
1634
1635 static void
1636 output_switches (List_Node *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1637 {
1638   T (Trace t ("output_switches");)
1639
1640   if (option[DEBUG])
1641     printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1642             indent, "", min_hash_value, max_hash_value, size);
1643
1644   if (num_switches > 1)
1645     {
1646       int part1 = num_switches / 2;
1647       int part2 = num_switches - part1;
1648       int size1 = (int)((double)size / (double)num_switches * (double)part1 + 0.5);
1649       int size2 = size - size1;
1650
1651       List_Node *temp = list;
1652       for (int count = size1; count > 0; count--)
1653         {
1654           while (temp->hash_value == temp->next->hash_value)
1655             temp = temp->next;
1656           temp = temp->next;
1657         }
1658
1659       printf ("%*sif (key < %d)\n"
1660               "%*s  {\n",
1661               indent, "", temp->hash_value,
1662               indent, "");
1663
1664       output_switches (list, part1, size1, min_hash_value, temp->hash_value-1, indent+4);
1665
1666       printf ("%*s  }\n"
1667               "%*selse\n"
1668               "%*s  {\n",
1669               indent, "", indent, "", indent, "");
1670
1671       output_switches (temp, part2, size2, temp->hash_value, max_hash_value, indent+4);
1672
1673       printf ("%*s  }\n",
1674               indent, "");
1675     }
1676   else
1677     {
1678       /* Output a single switch. */
1679       int lowest_case_value = list->hash_value;
1680       if (size == 1)
1681         {
1682           int jumps_away = 0;
1683           assert (min_hash_value <= lowest_case_value);
1684           assert (lowest_case_value <= max_hash_value);
1685           if (min_hash_value == max_hash_value)
1686             output_switch_case (list, indent, &jumps_away);
1687           else
1688             {
1689               printf ("%*sif (key == %d)\n"
1690                       "%*s  {\n",
1691                       indent, "", lowest_case_value,
1692                       indent, "");
1693               output_switch_case (list, indent+4, &jumps_away);
1694               printf ("%*s  }\n",
1695                       indent, "");
1696             }
1697         }
1698       else
1699         {
1700           if (lowest_case_value == 0)
1701             printf ("%*sswitch (key)\n", indent, "");
1702           else
1703             printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1704           printf ("%*s  {\n",
1705                   indent, "");
1706           for (; size > 0; size--)
1707             {
1708               int jumps_away = 0;
1709               printf ("%*s    case %d:\n",
1710                       indent, "", list->hash_value - lowest_case_value);
1711               list = output_switch_case (list, indent+6, &jumps_away);
1712               if (!jumps_away)
1713                 printf ("%*s      break;\n",
1714                         indent, "");
1715             }
1716           printf ("%*s  }\n",
1717                   indent, "");
1718         }
1719     }
1720 }
1721
1722 /* Generates C code to perform the keyword lookup. */
1723
1724 void
1725 Key_List::output_lookup_function_body (const Output_Compare& comparison)
1726 {
1727   T (Trace t ("Key_List::output_lookup_function_body");)
1728
1729   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1730           "    {\n"
1731           "      register int key = %s (str, len);\n\n",
1732           option.get_hash_name ());
1733
1734   if (option[SWITCH])
1735     {
1736       int switch_size = num_hash_values ();
1737       int num_switches = option.get_total_switches ();
1738       if (num_switches > switch_size)
1739         num_switches = switch_size;
1740
1741       printf ("      if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1742               "        {\n");
1743       if (option[DUP])
1744         {
1745           if (option[LENTABLE])
1746             printf ("          register %s%s *lengthptr;\n",
1747                     const_always, smallest_integral_type (max_key_len));
1748           printf ("          register ");
1749           output_const_type (const_readonly_array, struct_tag);
1750           printf ("*wordptr;\n");
1751           printf ("          register ");
1752           output_const_type (const_readonly_array, struct_tag);
1753           printf ("*wordendptr;\n");
1754         }
1755       if (option[TYPE])
1756         {
1757           printf ("          register ");
1758           output_const_type (const_readonly_array, struct_tag);
1759           printf ("*resword;\n\n");
1760         }
1761       else
1762         printf ("          register %sresword;\n\n",
1763                 struct_tag);
1764
1765       output_switches (head, num_switches, switch_size, min_hash_value, max_hash_value, 10);
1766
1767       if (option[DUP])
1768         {
1769           int indent = 8;
1770           printf ("%*s  return 0;\n"
1771                   "%*smulticompare:\n"
1772                   "%*s  while (wordptr < wordendptr)\n"
1773                   "%*s    {\n",
1774                   indent, "", indent, "", indent, "", indent, "");
1775           if (option[LENTABLE])
1776             {
1777               printf ("%*s      if (len == *lengthptr)\n"
1778                       "%*s        {\n",
1779                       indent, "", indent, "");
1780               indent += 4;
1781             }
1782           printf ("%*s      register %schar *s = ",
1783                   indent, "", const_always);
1784           if (option[TYPE])
1785             printf ("wordptr->%s", option.get_key_name ());
1786           else
1787             printf ("*wordptr");
1788           printf (";\n\n"
1789                   "%*s      if (",
1790                   indent, "");
1791           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1792           printf (")\n"
1793                   "%*s        return %s;\n",
1794                   indent, "",
1795                   option[TYPE] ? "wordptr" : "s");
1796           if (option[LENTABLE])
1797             {
1798               indent -= 4;
1799               printf ("%*s        }\n",
1800                       indent, "");
1801             }
1802           if (option[LENTABLE])
1803             printf ("%*s      lengthptr++;\n",
1804                     indent, "");
1805           printf ("%*s      wordptr++;\n"
1806                   "%*s    }\n",
1807                   indent, "", indent, "");
1808         }
1809       printf ("          return 0;\n"
1810               "        compare:\n");
1811       if (option[TYPE])
1812         {
1813           printf ("          {\n"
1814                   "            register %schar *s = resword->%s;\n\n"
1815                   "            if (",
1816                   const_always, option.get_key_name ());
1817           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1818           printf (")\n"
1819                   "              return resword;\n"
1820                   "          }\n");
1821         }
1822       else
1823         {
1824           printf ("          if (");
1825           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1826           printf (")\n"
1827                   "            return resword;\n");
1828         }
1829       printf ("        }\n");
1830     }
1831   else
1832     {
1833       printf ("      if (key <= MAX_HASH_VALUE && key >= 0)\n");
1834
1835       if (option[DUP])
1836         {
1837           int indent = 8;
1838           printf ("%*s{\n"
1839                   "%*s  register int index = lookup[key];\n\n"
1840                   "%*s  if (index >= 0)\n",
1841                   indent, "", indent, "", indent, "");
1842           if (option[LENTABLE])
1843             {
1844               printf ("%*s    {\n"
1845                       "%*s      if (len == lengthtable[index])\n",
1846                       indent, "", indent, "");
1847               indent += 4;
1848             }
1849           printf ("%*s    {\n"
1850                   "%*s      register %schar *s = %s[index]",
1851                   indent, "",
1852                   indent, "", const_always, option.get_wordlist_name ());
1853           if (option[TYPE])
1854             printf (".%s", option.get_key_name ());
1855           printf (";\n\n"
1856                   "%*s      if (",
1857                   indent, "");
1858           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1859           printf (")\n"
1860                   "%*s        return ",
1861                   indent, "");
1862           if (option[TYPE])
1863             printf ("&%s[index]", option.get_wordlist_name ());
1864           else
1865             printf ("s");
1866           printf (";\n"
1867                   "%*s    }\n",
1868                   indent, "");
1869           if (option[LENTABLE])
1870             {
1871               indent -= 4;
1872               printf ("%*s    }\n", indent, "");
1873             }
1874           if (total_duplicates > 0)
1875             {
1876               printf ("%*s  else if (index < -TOTAL_KEYWORDS)\n"
1877                       "%*s    {\n"
1878                       "%*s      register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1879                       indent, "", indent, "", indent, "");
1880               if (option[LENTABLE])
1881                 printf ("%*s      register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n",
1882                         indent, "", const_always, smallest_integral_type (max_key_len));
1883               printf ("%*s      register ",
1884                       indent, "");
1885               output_const_type (const_readonly_array, struct_tag);
1886               printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1887                       option.get_wordlist_name ());
1888               printf ("%*s      register ",
1889                       indent, "");
1890               output_const_type (const_readonly_array, struct_tag);
1891               printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1892               printf ("%*s      while (wordptr < wordendptr)\n"
1893                       "%*s        {\n",
1894                       indent, "", indent, "");
1895               if (option[LENTABLE])
1896                 {
1897                   printf ("%*s          if (len == *lengthptr)\n"
1898                           "%*s            {\n",
1899                           indent, "", indent, "");
1900                   indent += 4;
1901                 }
1902               printf ("%*s          register %schar *s = ",
1903                       indent, "", const_always);
1904               if (option[TYPE])
1905                 printf ("wordptr->%s", option.get_key_name ());
1906               else
1907                 printf ("*wordptr");
1908               printf (";\n\n"
1909                       "%*s          if (",
1910                       indent, "");
1911               comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1912               printf (")\n"
1913                       "%*s            return %s;\n",
1914                       indent, "",
1915                       option[TYPE] ? "wordptr" : "s");
1916               if (option[LENTABLE])
1917                 {
1918                   indent -= 4;
1919                   printf ("%*s            }\n",
1920                           indent, "");
1921                 }
1922               if (option[LENTABLE])
1923                 printf ("%*s          lengthptr++;\n",
1924                         indent, "");
1925               printf ("%*s          wordptr++;\n"
1926                       "%*s        }\n"
1927                       "%*s    }\n",
1928                       indent, "", indent, "", indent, "");
1929             }
1930           printf ("%*s}\n",
1931                   indent, "");
1932         }
1933       else
1934         {
1935           int indent = 8;
1936           if (option[LENTABLE])
1937             {
1938               printf ("%*sif (len == lengthtable[key])\n",
1939                       indent, "");
1940               indent += 2;
1941             }
1942
1943           printf ("%*s{\n"
1944                   "%*s  register %schar *s = %s[key]",
1945                   indent, "",
1946                   indent, "", const_always, option.get_wordlist_name ());
1947
1948           if (option[TYPE])
1949             printf (".%s", option.get_key_name ());
1950
1951           printf (";\n\n"
1952                   "%*s  if (",
1953                   indent, "");
1954           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1955           printf (")\n"
1956                   "%*s    return ",
1957                   indent, "");
1958           if (option[TYPE])
1959             printf ("&%s[key]", option.get_wordlist_name ());
1960           else
1961             printf ("s");
1962           printf (";\n"
1963                   "%*s}\n",
1964                   indent, "");
1965         }
1966     }
1967   printf ("    }\n"
1968           "  return 0;\n");
1969 }
1970
1971 /* Generates C code for the lookup function. */
1972
1973 void
1974 Key_List::output_lookup_function (void)
1975 {
1976   T (Trace t ("Key_List::output_lookup_function");)
1977
1978   /* Output the function's head. */
1979   if (option[KRC] | option[C] | option[ANSIC])
1980     printf ("#ifdef __GNUC__\n"
1981             "__inline\n"
1982             "#endif\n");
1983
1984   printf ("%s%s\n",
1985           const_for_struct, return_type);
1986   if (option[CPLUSPLUS])
1987     printf ("%s::", option.get_class_name ());
1988   printf ("%s ", option.get_function_name ());
1989   printf (option[KRC] ?
1990                  "(str, len)\n"
1991             "     register char *str;\n"
1992             "     register unsigned int len;\n" :
1993           option[C] ?
1994                  "(str, len)\n"
1995             "     register const char *str;\n"
1996             "     register unsigned int len;\n" :
1997           option[ANSIC] | option[CPLUSPLUS] ?
1998                  "(register const char *str, register unsigned int len)\n" :
1999           "");
2000
2001   /* Output the function's body. */
2002   printf ("{\n");
2003
2004   if (option[ENUM] && !option[GLOBAL])
2005     {
2006       Output_Enum style ("  ");
2007       output_constants (style);
2008     }
2009
2010   if (!option[GLOBAL])
2011     output_lookup_tables ();
2012
2013   if (option[LENTABLE])
2014     output_lookup_function_body (Output_Compare_Memcmp ());
2015   else
2016     {
2017       if (option[COMP])
2018         output_lookup_function_body (Output_Compare_Strncmp ());
2019       else
2020         output_lookup_function_body (Output_Compare_Strcmp ());
2021     }
2022
2023   printf ("}\n");
2024 }
2025
2026 /* ------------------------------------------------------------------------- */
2027
2028 /* Generates the hash function and the key word recognizer function
2029    based upon the user's Options. */
2030
2031 void
2032 Key_List::output (void)
2033 {
2034   T (Trace t ("Key_List::output");)
2035
2036   compute_min_max ();
2037
2038   if (option[C] | option[ANSIC] | option[CPLUSPLUS])
2039     {
2040       const_always = "const ";
2041       const_readonly_array = (option[CONST] ? "const " : "");
2042       const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : "");
2043     }
2044   else
2045     {
2046       const_always = "";
2047       const_readonly_array = "";
2048       const_for_struct = "";
2049     }
2050
2051   if (!option[TYPE])
2052     {
2053       return_type = (const_always[0] ? "const char *" : "char *");
2054       struct_tag = (const_always[0] ? "const char *" : "char *");
2055     }
2056
2057   char_to_index = (option[SEVENBIT] ? "" : "(unsigned char)");
2058
2059   printf ("/* ");
2060   if (option[KRC])
2061     printf ("KR-C");
2062   else if (option[C])
2063     printf ("C");
2064   else if (option[ANSIC])
2065     printf ("ANSI-C");
2066   else if (option[CPLUSPLUS])
2067     printf ("C++");
2068   printf (" code produced by gperf version %s */\n", version_string);
2069   Options::print_options ();
2070
2071   printf ("%s\n", include_src);
2072
2073   if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
2074     printf ("%s;\n", array_type);
2075
2076   if (option[INCLUDE])
2077     printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */
2078
2079   if (!option[ENUM])
2080     {
2081       Output_Defines style;
2082       output_constants (style);
2083     }
2084   else if (option[GLOBAL])
2085     {
2086       Output_Enum style ("");
2087       output_constants (style);
2088     }
2089
2090   printf ("/* maximum key range = %d, duplicates = %d */\n\n",
2091           max_hash_value - min_hash_value + 1, total_duplicates);
2092
2093   if (option[CPLUSPLUS])
2094     printf ("class %s\n"
2095             "{\n"
2096             "private:\n"
2097             "  static inline unsigned int %s (const char *str, unsigned int len);\n"
2098             "public:\n"
2099             "  static %s%s%s (const char *str, unsigned int len);\n"
2100             "};\n"
2101             "\n",
2102             option.get_class_name (), option.get_hash_name (),
2103             const_for_struct, return_type, option.get_function_name ());
2104
2105   output_hash_function ();
2106
2107   if (option[GLOBAL])
2108     output_lookup_tables ();
2109
2110   output_lookup_function ();
2111
2112   if (additional_code)
2113     for (int c; (c = getchar ()) != EOF; putchar (c))
2114       ;
2115
2116   fflush (stdout);
2117 }
2118
2119 /* ========================= End of Output routines ========================= */
2120
2121 /* Sorts the keys by hash value. */
2122
2123 void
2124 Key_List::sort (void)
2125 {
2126   T (Trace t ("Key_List::sort");)
2127   hash_sort       = 1;
2128   occurrence_sort = 0;
2129
2130   head = merge_sort (head);
2131 }
2132
2133 /* Dumps the key list to stderr stream. */
2134
2135 void
2136 Key_List::dump ()
2137 {
2138   T (Trace t ("Key_List::dump");)
2139   int field_width = option.get_max_keysig_size ();
2140
2141   fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
2142            field_width, "char_set");
2143
2144   for (List_Node *ptr = head; ptr; ptr = ptr->next)
2145     fprintf (stderr, "%11d,%11d,%6d, %*.*s, %.*s\n",
2146              ptr->hash_value, ptr->key_length, ptr->index,
2147              field_width, ptr->char_set_length, ptr->char_set,
2148              ptr->key_length, ptr->key);
2149 }
2150
2151 /* Simple-minded constructor action here... */
2152
2153 Key_List::Key_List (void)
2154 {
2155   T (Trace t ("Key_List::Key_List");)
2156   total_keys       = 1;
2157   max_key_len      = INT_MIN;
2158   min_key_len      = INT_MAX;
2159   array_type       = 0;
2160   return_type      = 0;
2161   struct_tag       = 0;
2162   head             = 0;
2163   total_duplicates = 0;
2164   additional_code  = 0;
2165 }
2166
2167 /* Returns the length of entire key list. */
2168
2169 int
2170 Key_List::keyword_list_length (void)
2171 {
2172   T (Trace t ("Key_List::keyword_list_length");)
2173   return list_len;
2174 }
2175
2176 /* Returns length of longest key read. */
2177
2178 int
2179 Key_List::max_key_length (void)
2180 {
2181   T (Trace t ("Key_List::max_key_length");)
2182   return max_key_len;
2183 }
2184