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   if (option[KRC] || option[C] || option [ANSIC] || option[CPLUSPLUS])
1039     printf (option[KRC] ?
1040               "(str, len)\n"
1041               "     register char *str;\n"
1042               "     register unsigned int len;\n" :
1043             option[C] ?
1044               "(str, len)\n"
1045               "     register const char *str;\n"
1046               "     register unsigned int len;\n" :
1047               "(register const char *str, register unsigned int len)\n");
1048
1049   /* Note that when the hash function is called, it has already been verified
1050      that  min_key_len <= len <= max_key_len. */
1051
1052   /* Output the function's body. */
1053   printf ("{\n");
1054
1055   /* First the asso_values array. */
1056   printf ("  static %s%s asso_values[] =\n"
1057           "    {",
1058           const_readonly_array,
1059           smallest_integral_type (max_hash_value + 1));
1060
1061   for (int count = 0; count < ALPHA_SIZE; count++)
1062     {
1063       if (count > 0)
1064         printf (",");
1065       if (!(count % max_column))
1066         printf ("\n     ");
1067       printf ("%*d", field_width,
1068               occurrences[count] ? asso_values[count] : max_hash_value + 1);
1069     }
1070
1071   printf ("\n"
1072           "    };\n");
1073
1074   /* Optimize special case of ``-k 1,$'' */
1075   if (option[DEFAULTCHARS])
1076     printf ("  return %sasso_values[%sstr[len - 1]] + asso_values[%sstr[0]];\n",
1077             option[NOLENGTH] ? "" : "len + ",
1078             char_to_index, char_to_index);
1079   else
1080     {
1081       int key_pos;
1082
1083       option.reset ();
1084
1085       /* Get first (also highest) key position. */
1086       key_pos = option.get ();
1087
1088       if (!option[ALLCHARS] && (key_pos == WORD_END || key_pos <= min_key_len))
1089         {
1090           /* We can perform additional optimizations here:
1091              Write it out as a single expression. Note that the values
1092              are added as `int's even though the asso_values array may
1093              contain `unsigned char's or `unsigned short's. */
1094
1095           printf ("  return %s",
1096                   option[NOLENGTH] ? "" : "len + ");
1097
1098           for (; key_pos != WORD_END; )
1099             {
1100               printf ("asso_values[%sstr[%d]]", char_to_index, key_pos - 1);
1101               if ((key_pos = option.get ()) != EOS)
1102                 printf (" + ");
1103               else
1104                 break;
1105             }
1106
1107           if (key_pos == WORD_END)
1108             printf ("asso_values[%sstr[len - 1]]", char_to_index);
1109
1110           printf (";\n");
1111         }
1112       else
1113         {
1114           /* We've got to use the correct, but brute force, technique. */
1115           printf ("  register int hval = %s;\n\n"
1116                   "  switch (%s)\n"
1117                   "    {\n"
1118                   "      default:\n",
1119                   option[NOLENGTH] ? "0" : "len",
1120                   option[NOLENGTH] ? "len" : "hval");
1121
1122           /* User wants *all* characters considered in hash. */
1123           if (option[ALLCHARS])
1124             {
1125               for (int i = max_key_len; i > 0; i--)
1126                 printf ("      case %d:\n"
1127                         "        hval += asso_values[%sstr[%d]];\n",
1128                         i, char_to_index, i - 1);
1129
1130               printf ("        break;\n"
1131                       "    }\n"
1132                       "  return hval;\n");
1133             }
1134           else                  /* do the hard part... */
1135             {
1136               while (key_pos != WORD_END && key_pos > max_key_len)
1137                 if ((key_pos = option.get ()) == EOS)
1138                   break;
1139
1140               if (key_pos != EOS && key_pos != WORD_END)
1141                 {
1142                   int i = key_pos;
1143                   do
1144                     {
1145                       for ( ; i >= key_pos; i--)
1146                         printf ("      case %d:\n", i);
1147
1148                       printf ("        hval += asso_values[%sstr[%d]];\n",
1149                               char_to_index, key_pos - 1);
1150
1151                       key_pos = option.get ();
1152                     }
1153                   while (key_pos != EOS && key_pos != WORD_END);
1154
1155                   for ( ; i >= min_key_len; i--)
1156                     printf ("      case %d:\n", i);
1157                 }
1158
1159               printf ("        break;\n"
1160                       "    }\n"
1161                       "  return hval");
1162               if (key_pos == WORD_END)
1163                 printf (" + asso_values[%sstr[len - 1]]", char_to_index);
1164               printf (";\n");
1165             }
1166         }
1167     }
1168   printf ("}\n\n");
1169 }
1170
1171 /* ------------------------------------------------------------------------- */
1172
1173 /* Prints out a table of keyword lengths, for use with the
1174    comparison code in generated function ``in_word_set''. */
1175
1176 void
1177 Key_List::output_keylength_table (void)
1178 {
1179   T (Trace t ("Key_List::output_keylength_table");)
1180   const int  columns = 14;
1181   int        index;
1182   int        column;
1183   const char *indent    = option[GLOBAL] ? "" : "  ";
1184   List_Node *temp;
1185
1186   printf ("%sstatic %s%s lengthtable[] =\n%s  {",
1187           indent, const_readonly_array,
1188           smallest_integral_type (max_key_len),
1189           indent);
1190
1191   /* Generate an array of lengths, similar to output_keyword_table. */
1192
1193   column = 0;
1194   for (temp = head, index = 0; temp; temp = temp->next)
1195     {
1196       if (option[SWITCH] && !option[TYPE]
1197           && !(temp->link
1198                || (temp->next && temp->hash_value == temp->next->hash_value)))
1199         continue;
1200
1201       if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1202         {
1203           /* Some blank entries. */
1204           for ( ; index < temp->hash_value; index++)
1205             {
1206               if (index > 0)
1207                 printf (",");
1208               if ((column++ % columns) == 0)
1209                 printf ("\n%s   ", indent);
1210               printf ("%3d", 0);
1211             }
1212         }
1213
1214       if (index > 0)
1215         printf (",");
1216       if ((column++ % columns) == 0)
1217         printf("\n%s   ", indent);
1218       printf ("%3d", temp->key_length);
1219
1220       /* Deal with links specially. */
1221       if (temp->link) // implies option[DUP]
1222         for (List_Node *links = temp->link; links; links = links->link)
1223           {
1224             ++index;
1225             printf (",");
1226             if ((column++ % columns) == 0)
1227               printf("\n%s   ", indent);
1228             printf ("%3d", links->key_length);
1229           }
1230
1231       index++;
1232     }
1233
1234   printf ("\n%s  };\n", indent);
1235   if (option[GLOBAL])
1236     printf ("\n");
1237 }
1238
1239 /* ------------------------------------------------------------------------- */
1240
1241 static void
1242 output_keyword_entry (List_Node *temp, const char *indent)
1243 {
1244   printf ("%s    ", indent);
1245   if (option[TYPE])
1246     printf ("{");
1247   output_string (temp->key, temp->key_length);
1248   if (option[TYPE])
1249     {
1250       if (strlen (temp->rest) > 0)
1251         printf (",%s", temp->rest);
1252       printf ("}");
1253     }
1254   if (option[DEBUG])
1255     printf (" /* hash value = %d, index = %d */",
1256             temp->hash_value, temp->index);
1257 }
1258
1259 static void
1260 output_keyword_blank_entries (int count, const char *indent)
1261 {
1262   int columns;
1263   if (option[TYPE])
1264     {
1265       columns = 58 / (6 + strlen (option.get_initializer_suffix()));
1266       if (columns == 0)
1267         columns = 1;
1268     }
1269   else
1270     {
1271       columns = 9;
1272     }
1273   int column = 0;
1274   for (int i = 0; i < count; i++)
1275     {
1276       if ((column % columns) == 0)
1277         {
1278           if (i > 0)
1279             printf (",\n");
1280           printf ("%s    ", indent);
1281         }
1282       else
1283         {
1284           if (i > 0)
1285             printf (", ");
1286         }
1287       if (option[TYPE])
1288         printf ("{\"\"%s}", option.get_initializer_suffix());
1289       else
1290         printf ("\"\"");
1291       column++;
1292     }
1293 }
1294
1295 /* Prints out the array containing the key words for the hash function. */
1296
1297 void
1298 Key_List::output_keyword_table (void)
1299 {
1300   T (Trace t ("Key_List::output_keyword_table");)
1301   const char *indent  = option[GLOBAL] ? "" : "  ";
1302   int         index;
1303   List_Node  *temp;
1304
1305   printf ("%sstatic ",
1306           indent);
1307   output_const_type (const_readonly_array, struct_tag);
1308   printf ("%s[] =\n"
1309           "%s  {\n",
1310           option.get_wordlist_name (),
1311           indent);
1312
1313   /* Generate an array of reserved words at appropriate locations. */
1314
1315   for (temp = head, index = 0; temp; temp = temp->next)
1316     {
1317       if (option[SWITCH] && !option[TYPE]
1318           && !(temp->link
1319                || (temp->next && temp->hash_value == temp->next->hash_value)))
1320         continue;
1321
1322       if (index > 0)
1323         printf (",\n");
1324
1325       if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1326         {
1327           /* Some blank entries. */
1328           output_keyword_blank_entries (temp->hash_value - index, indent);
1329           printf (",\n");
1330           index = temp->hash_value;
1331         }
1332
1333       temp->index = index;
1334
1335       output_keyword_entry (temp, indent);
1336
1337       /* Deal with links specially. */
1338       if (temp->link) // implies option[DUP]
1339         for (List_Node *links = temp->link; links; links = links->link)
1340           {
1341             links->index = ++index;
1342             printf (",\n");
1343             output_keyword_entry (links, indent);
1344           }
1345
1346       index++;
1347     }
1348   if (index > 0)
1349     printf ("\n");
1350
1351   printf ("%s  };\n\n", indent);
1352 }
1353
1354 /* ------------------------------------------------------------------------- */
1355
1356 /* Generates the large, sparse table that maps hash values into
1357    the smaller, contiguous range of the keyword table. */
1358
1359 void
1360 Key_List::output_lookup_array (void)
1361 {
1362   T (Trace t ("Key_List::output_lookup_array");)
1363   if (option[DUP])
1364     {
1365       const int DEFAULT_VALUE = -1;
1366
1367       /* Because of the way output_keyword_table works, every duplicate set is
1368          stored contiguously in the wordlist array. */
1369       struct duplicate_entry
1370         {
1371           int hash_value;  /* Hash value for this particular duplicate set. */
1372           int index;       /* Index into the main keyword storage array. */
1373           int count;       /* Number of consecutive duplicates at this index. */
1374         };
1375
1376 #if LARGE_STACK_ARRAYS
1377       duplicate_entry duplicates[total_duplicates];
1378       int lookup_array[max_hash_value + 1 + 2*total_duplicates];
1379 #else
1380       // Note: we don't use new, because that invokes a custom operator new.
1381       duplicate_entry *duplicates = (duplicate_entry *)
1382         malloc (total_duplicates * sizeof(duplicate_entry) + 1);
1383       int *lookup_array = (int *)
1384         malloc ((max_hash_value + 1 + 2*total_duplicates) * sizeof(int));
1385       if (duplicates == NULL || lookup_array == NULL)
1386         abort();
1387 #endif
1388       int lookup_array_size = max_hash_value + 1;
1389       duplicate_entry *dup_ptr = &duplicates[0];
1390       int *lookup_ptr = &lookup_array[max_hash_value + 1 + 2*total_duplicates];
1391
1392       while (lookup_ptr > lookup_array)
1393         *--lookup_ptr = DEFAULT_VALUE;
1394
1395       /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1396
1397       for (List_Node *temp = head; temp; temp = temp->next)
1398         {
1399           int hash_value = temp->hash_value;
1400           lookup_array[hash_value] = temp->index;
1401           if (option[DEBUG])
1402             fprintf (stderr, "keyword = %.*s, index = %d\n",
1403                      temp->key_length, temp->key, temp->index);
1404           if (temp->link
1405               || (temp->next && hash_value == temp->next->hash_value))
1406             {
1407               /* Start a duplicate entry. */
1408               dup_ptr->hash_value = hash_value;
1409               dup_ptr->index      = temp->index;
1410               dup_ptr->count      = 1;
1411
1412               for (;;)
1413                 {
1414                   for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
1415                     {
1416                       dup_ptr->count++;
1417                       if (option[DEBUG])
1418                         fprintf (stderr,
1419                                  "static linked keyword = %.*s, index = %d\n",
1420                                  ptr->key_length, ptr->key, ptr->index);
1421                     }
1422
1423                   if (!(temp->next && hash_value == temp->next->hash_value))
1424                     break;
1425
1426                   temp = temp->next;
1427
1428                   dup_ptr->count++;
1429                   if (option[DEBUG])
1430                     fprintf (stderr, "dynamic linked keyword = %.*s, index = %d\n",
1431                              temp->key_length, temp->key, temp->index);
1432                 }
1433               assert (dup_ptr->count >= 2);
1434               dup_ptr++;
1435             }
1436         }
1437
1438       while (dup_ptr > duplicates)
1439         {
1440           dup_ptr--;
1441
1442           if (option[DEBUG])
1443             fprintf (stderr,
1444                      "dup_ptr[%td]: hash_value = %d, index = %d, count = %d\n",
1445                      dup_ptr - duplicates,
1446                      dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1447
1448           int i;
1449           /* Start searching for available space towards the right part
1450              of the lookup array. */
1451           for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1452             if (lookup_array[i] == DEFAULT_VALUE
1453                 && lookup_array[i + 1] == DEFAULT_VALUE)
1454               goto found_i;
1455           /* If we didn't find it to the right look to the left instead... */
1456           for (i = dup_ptr->hash_value-1; i >= 0; i--)
1457             if (lookup_array[i] == DEFAULT_VALUE
1458                 && lookup_array[i + 1] == DEFAULT_VALUE)
1459               goto found_i;
1460           /* Append to the end of lookup_array. */
1461           i = lookup_array_size;
1462           lookup_array_size += 2;
1463         found_i:
1464           /* Put in an indirection from dup_ptr->hash_value to i.
1465              At i and i+1 store dup_ptr->index and dup_ptr->count. */
1466           assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1467           lookup_array[dup_ptr->hash_value] = - 1 - total_keys - i;
1468           lookup_array[i] = - total_keys + dup_ptr->index;
1469           lookup_array[i + 1] = - dup_ptr->count;
1470           /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1471         }
1472
1473       /* The values of the lookup array are now known. */
1474
1475       int min = INT_MAX;
1476       int max = INT_MIN;
1477       lookup_ptr = lookup_array + lookup_array_size;
1478       while (lookup_ptr > lookup_array)
1479         {
1480           int val = *--lookup_ptr;
1481           if (min > val)
1482             min = val;
1483           if (max < val)
1484             max = val;
1485         }
1486
1487       const char *indent = option[GLOBAL] ? "" : "  ";
1488       printf ("%sstatic %s%s lookup[] =\n"
1489               "%s  {",
1490               indent, const_readonly_array, smallest_integral_type (min, max),
1491               indent);
1492
1493       int field_width;
1494       /* Calculate maximum number of digits required for MIN..MAX. */
1495       {
1496         field_width = 2;
1497         for (int trunc = max; (trunc /= 10) > 0;)
1498           field_width++;
1499       }
1500       if (min < 0)
1501         {
1502           int neg_field_width = 2;
1503           for (int trunc = -min; (trunc /= 10) > 0;)
1504             neg_field_width++;
1505           neg_field_width++; /* account for the minus sign */
1506           if (field_width < neg_field_width)
1507             field_width = neg_field_width;
1508         }
1509
1510       const int columns = 42 / field_width;
1511       int column;
1512
1513       column = 0;
1514       for (int i = 0; i < lookup_array_size; i++)
1515         {
1516           if (i > 0)
1517             printf (",");
1518           if ((column++ % columns) == 0)
1519             printf("\n%s   ", indent);
1520           printf ("%*d", field_width, lookup_array[i]);
1521         }
1522       printf ("\n%s  };\n\n", indent);
1523
1524 #if !LARGE_STACK_ARRAYS
1525       free ((char *) duplicates);
1526       free ((char *) lookup_array);
1527 #endif
1528     }
1529 }
1530
1531 /* ------------------------------------------------------------------------- */
1532
1533 /* Generate all the tables needed for the lookup function. */
1534
1535 void
1536 Key_List::output_lookup_tables (void)
1537 {
1538   T (Trace t ("Key_List::output_lookup_tables");)
1539
1540   if (option[SWITCH])
1541     {
1542       /* Use the switch in place of lookup table. */
1543       if (option[LENTABLE] && (option[DUP] && total_duplicates > 0))
1544         output_keylength_table ();
1545       if (option[TYPE] || (option[DUP] && total_duplicates > 0))
1546         output_keyword_table ();
1547     }
1548   else
1549     {
1550       /* Use the lookup table, in place of switch. */
1551       if (option[LENTABLE])
1552         output_keylength_table ();
1553       output_keyword_table ();
1554       output_lookup_array ();
1555     }
1556 }
1557
1558 /* ------------------------------------------------------------------------- */
1559
1560 /* Output a single switch case (including duplicates). Advance list. */
1561
1562 static List_Node *
1563 output_switch_case (List_Node *list, int indent, int *jumps_away)
1564 {
1565   T (Trace t ("output_switch_case");)
1566
1567   if (option[DEBUG])
1568     printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1569             indent, "", list->hash_value, list->key_length, list->key);
1570
1571   if (option[DUP]
1572       && (list->link
1573           || (list->next && list->hash_value == list->next->hash_value)))
1574     {
1575       if (option[LENTABLE])
1576         printf ("%*slengthptr = &lengthtable[%d];\n",
1577                 indent, "", list->index);
1578       printf ("%*swordptr = &%s[%d];\n",
1579               indent, "", option.get_wordlist_name (), list->index);
1580
1581       int count = 0;
1582       for (List_Node *temp = list; ; temp = temp->next)
1583         {
1584           for (List_Node *links = temp; links; links = links->link)
1585             count++;
1586           if (!(temp->next && temp->hash_value == temp->next->hash_value))
1587             break;
1588         }
1589
1590       printf ("%*swordendptr = wordptr + %d;\n"
1591               "%*sgoto multicompare;\n",
1592               indent, "", count,
1593               indent, "");
1594       *jumps_away = 1;
1595     }
1596   else
1597     {
1598       if (option[LENTABLE])
1599         {
1600           printf ("%*sif (len == %d)\n"
1601                   "%*s  {\n",
1602                   indent, "", list->key_length,
1603                   indent, "");
1604           indent += 4;
1605         }
1606       printf ("%*sresword = ",
1607               indent, "");
1608       if (option[TYPE])
1609         printf ("&%s[%d]", option.get_wordlist_name (), list->index);
1610       else
1611         output_string (list->key, list->key_length);
1612       printf (";\n");
1613       printf ("%*sgoto compare;\n",
1614               indent, "");
1615       if (option[LENTABLE])
1616         {
1617           indent -= 4;
1618           printf ("%*s  }\n",
1619                   indent, "");
1620         }
1621       else
1622         *jumps_away = 1;
1623     }
1624
1625   while (list->next && list->hash_value == list->next->hash_value)
1626     list = list->next;
1627   list = list->next;
1628   return list;
1629 }
1630
1631 /* Output a total of size cases, grouped into num_switches switch statements,
1632    where 0 < num_switches <= size. */
1633
1634 static void
1635 output_switches (List_Node *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1636 {
1637   T (Trace t ("output_switches");)
1638
1639   if (option[DEBUG])
1640     printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1641             indent, "", min_hash_value, max_hash_value, size);
1642
1643   if (num_switches > 1)
1644     {
1645       int part1 = num_switches / 2;
1646       int part2 = num_switches - part1;
1647       int size1 = (int)((double)size / (double)num_switches * (double)part1 + 0.5);
1648       int size2 = size - size1;
1649
1650       List_Node *temp = list;
1651       for (int count = size1; count > 0; count--)
1652         {
1653           while (temp->hash_value == temp->next->hash_value)
1654             temp = temp->next;
1655           temp = temp->next;
1656         }
1657
1658       printf ("%*sif (key < %d)\n"
1659               "%*s  {\n",
1660               indent, "", temp->hash_value,
1661               indent, "");
1662
1663       output_switches (list, part1, size1, min_hash_value, temp->hash_value-1, indent+4);
1664
1665       printf ("%*s  }\n"
1666               "%*selse\n"
1667               "%*s  {\n",
1668               indent, "", indent, "", indent, "");
1669
1670       output_switches (temp, part2, size2, temp->hash_value, max_hash_value, indent+4);
1671
1672       printf ("%*s  }\n",
1673               indent, "");
1674     }
1675   else
1676     {
1677       /* Output a single switch. */
1678       int lowest_case_value = list->hash_value;
1679       if (size == 1)
1680         {
1681           int jumps_away = 0;
1682           assert (min_hash_value <= lowest_case_value);
1683           assert (lowest_case_value <= max_hash_value);
1684           if (min_hash_value == max_hash_value)
1685             output_switch_case (list, indent, &jumps_away);
1686           else
1687             {
1688               printf ("%*sif (key == %d)\n"
1689                       "%*s  {\n",
1690                       indent, "", lowest_case_value,
1691                       indent, "");
1692               output_switch_case (list, indent+4, &jumps_away);
1693               printf ("%*s  }\n",
1694                       indent, "");
1695             }
1696         }
1697       else
1698         {
1699           if (lowest_case_value == 0)
1700             printf ("%*sswitch (key)\n", indent, "");
1701           else
1702             printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1703           printf ("%*s  {\n",
1704                   indent, "");
1705           for (; size > 0; size--)
1706             {
1707               int jumps_away = 0;
1708               printf ("%*s    case %d:\n",
1709                       indent, "", list->hash_value - lowest_case_value);
1710               list = output_switch_case (list, indent+6, &jumps_away);
1711               if (!jumps_away)
1712                 printf ("%*s      break;\n",
1713                         indent, "");
1714             }
1715           printf ("%*s  }\n",
1716                   indent, "");
1717         }
1718     }
1719 }
1720
1721 /* Generates C code to perform the keyword lookup. */
1722
1723 void
1724 Key_List::output_lookup_function_body (const Output_Compare& comparison)
1725 {
1726   T (Trace t ("Key_List::output_lookup_function_body");)
1727
1728   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1729           "    {\n"
1730           "      register int key = %s (str, len);\n\n",
1731           option.get_hash_name ());
1732
1733   if (option[SWITCH])
1734     {
1735       int switch_size = num_hash_values ();
1736       int num_switches = option.get_total_switches ();
1737       if (num_switches > switch_size)
1738         num_switches = switch_size;
1739
1740       printf ("      if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1741               "        {\n");
1742       if (option[DUP])
1743         {
1744           if (option[LENTABLE])
1745             printf ("          register %s%s *lengthptr;\n",
1746                     const_always, smallest_integral_type (max_key_len));
1747           printf ("          register ");
1748           output_const_type (const_readonly_array, struct_tag);
1749           printf ("*wordptr;\n");
1750           printf ("          register ");
1751           output_const_type (const_readonly_array, struct_tag);
1752           printf ("*wordendptr;\n");
1753         }
1754       if (option[TYPE])
1755         {
1756           printf ("          register ");
1757           output_const_type (const_readonly_array, struct_tag);
1758           printf ("*resword;\n\n");
1759         }
1760       else
1761         printf ("          register %sresword;\n\n",
1762                 struct_tag);
1763
1764       output_switches (head, num_switches, switch_size, min_hash_value, max_hash_value, 10);
1765
1766       if (option[DUP])
1767         {
1768           int indent = 8;
1769           printf ("%*s  return 0;\n"
1770                   "%*smulticompare:\n"
1771                   "%*s  while (wordptr < wordendptr)\n"
1772                   "%*s    {\n",
1773                   indent, "", indent, "", indent, "", indent, "");
1774           if (option[LENTABLE])
1775             {
1776               printf ("%*s      if (len == *lengthptr)\n"
1777                       "%*s        {\n",
1778                       indent, "", indent, "");
1779               indent += 4;
1780             }
1781           printf ("%*s      register %schar *s = ",
1782                   indent, "", const_always);
1783           if (option[TYPE])
1784             printf ("wordptr->%s", option.get_key_name ());
1785           else
1786             printf ("*wordptr");
1787           printf (";\n\n"
1788                   "%*s      if (",
1789                   indent, "");
1790           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1791           printf (")\n"
1792                   "%*s        return %s;\n",
1793                   indent, "",
1794                   option[TYPE] ? "wordptr" : "s");
1795           if (option[LENTABLE])
1796             {
1797               indent -= 4;
1798               printf ("%*s        }\n",
1799                       indent, "");
1800             }
1801           if (option[LENTABLE])
1802             printf ("%*s      lengthptr++;\n",
1803                     indent, "");
1804           printf ("%*s      wordptr++;\n"
1805                   "%*s    }\n",
1806                   indent, "", indent, "");
1807         }
1808       printf ("          return 0;\n"
1809               "        compare:\n");
1810       if (option[TYPE])
1811         {
1812           printf ("          {\n"
1813                   "            register %schar *s = resword->%s;\n\n"
1814                   "            if (",
1815                   const_always, option.get_key_name ());
1816           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1817           printf (")\n"
1818                   "              return resword;\n"
1819                   "          }\n");
1820         }
1821       else
1822         {
1823           printf ("          if (");
1824           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1825           printf (")\n"
1826                   "            return resword;\n");
1827         }
1828       printf ("        }\n");
1829     }
1830   else
1831     {
1832       printf ("      if (key <= MAX_HASH_VALUE && key >= 0)\n");
1833
1834       if (option[DUP])
1835         {
1836           int indent = 8;
1837           printf ("%*s{\n"
1838                   "%*s  register int index = lookup[key];\n\n"
1839                   "%*s  if (index >= 0)\n",
1840                   indent, "", indent, "", indent, "");
1841           if (option[LENTABLE])
1842             {
1843               printf ("%*s    {\n"
1844                       "%*s      if (len == lengthtable[index])\n",
1845                       indent, "", indent, "");
1846               indent += 4;
1847             }
1848           printf ("%*s    {\n"
1849                   "%*s      register %schar *s = %s[index]",
1850                   indent, "",
1851                   indent, "", const_always, option.get_wordlist_name ());
1852           if (option[TYPE])
1853             printf (".%s", option.get_key_name ());
1854           printf (";\n\n"
1855                   "%*s      if (",
1856                   indent, "");
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[index]", option.get_wordlist_name ());
1863           else
1864             printf ("s");
1865           printf (";\n"
1866                   "%*s    }\n",
1867                   indent, "");
1868           if (option[LENTABLE])
1869             {
1870               indent -= 4;
1871               printf ("%*s    }\n", indent, "");
1872             }
1873           if (total_duplicates > 0)
1874             {
1875               printf ("%*s  else if (index < -TOTAL_KEYWORDS)\n"
1876                       "%*s    {\n"
1877                       "%*s      register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1878                       indent, "", indent, "", indent, "");
1879               if (option[LENTABLE])
1880                 printf ("%*s      register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n",
1881                         indent, "", const_always, smallest_integral_type (max_key_len));
1882               printf ("%*s      register ",
1883                       indent, "");
1884               output_const_type (const_readonly_array, struct_tag);
1885               printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1886                       option.get_wordlist_name ());
1887               printf ("%*s      register ",
1888                       indent, "");
1889               output_const_type (const_readonly_array, struct_tag);
1890               printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1891               printf ("%*s      while (wordptr < wordendptr)\n"
1892                       "%*s        {\n",
1893                       indent, "", indent, "");
1894               if (option[LENTABLE])
1895                 {
1896                   printf ("%*s          if (len == *lengthptr)\n"
1897                           "%*s            {\n",
1898                           indent, "", indent, "");
1899                   indent += 4;
1900                 }
1901               printf ("%*s          register %schar *s = ",
1902                       indent, "", const_always);
1903               if (option[TYPE])
1904                 printf ("wordptr->%s", option.get_key_name ());
1905               else
1906                 printf ("*wordptr");
1907               printf (";\n\n"
1908                       "%*s          if (",
1909                       indent, "");
1910               comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1911               printf (")\n"
1912                       "%*s            return %s;\n",
1913                       indent, "",
1914                       option[TYPE] ? "wordptr" : "s");
1915               if (option[LENTABLE])
1916                 {
1917                   indent -= 4;
1918                   printf ("%*s            }\n",
1919                           indent, "");
1920                 }
1921               if (option[LENTABLE])
1922                 printf ("%*s          lengthptr++;\n",
1923                         indent, "");
1924               printf ("%*s          wordptr++;\n"
1925                       "%*s        }\n"
1926                       "%*s    }\n",
1927                       indent, "", indent, "", indent, "");
1928             }
1929           printf ("%*s}\n",
1930                   indent, "");
1931         }
1932       else
1933         {
1934           int indent = 8;
1935           if (option[LENTABLE])
1936             {
1937               printf ("%*sif (len == lengthtable[key])\n",
1938                       indent, "");
1939               indent += 2;
1940             }
1941
1942           printf ("%*s{\n"
1943                   "%*s  register %schar *s = %s[key]",
1944                   indent, "",
1945                   indent, "", const_always, option.get_wordlist_name ());
1946
1947           if (option[TYPE])
1948             printf (".%s", option.get_key_name ());
1949
1950           printf (";\n\n"
1951                   "%*s  if (",
1952                   indent, "");
1953           comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1954           printf (")\n"
1955                   "%*s    return ",
1956                   indent, "");
1957           if (option[TYPE])
1958             printf ("&%s[key]", option.get_wordlist_name ());
1959           else
1960             printf ("s");
1961           printf (";\n"
1962                   "%*s}\n",
1963                   indent, "");
1964         }
1965     }
1966   printf ("    }\n"
1967           "  return 0;\n");
1968 }
1969
1970 /* Generates C code for the lookup function. */
1971
1972 void
1973 Key_List::output_lookup_function (void)
1974 {
1975   T (Trace t ("Key_List::output_lookup_function");)
1976
1977   /* Output the function's head. */
1978   if (option[KRC] | option[C] | option[ANSIC])
1979     printf ("#ifdef __GNUC__\n"
1980             "__inline\n"
1981             "#endif\n");
1982
1983   printf ("%s%s\n",
1984           const_for_struct, return_type);
1985   if (option[CPLUSPLUS])
1986     printf ("%s::", option.get_class_name ());
1987   printf ("%s ", option.get_function_name ());
1988   if (option[KRC] || option[C] || option[ANSIC] || option[CPLUSPLUS])
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             "(register const char *str, register unsigned int len)\n");
1998
1999   /* Output the function's body. */
2000   printf ("{\n");
2001
2002   if (option[ENUM] && !option[GLOBAL])
2003     {
2004       Output_Enum style ("  ");
2005       output_constants (style);
2006     }
2007
2008   if (!option[GLOBAL])
2009     output_lookup_tables ();
2010
2011   if (option[LENTABLE])
2012     output_lookup_function_body (Output_Compare_Memcmp ());
2013   else
2014     {
2015       if (option[COMP])
2016         output_lookup_function_body (Output_Compare_Strncmp ());
2017       else
2018         output_lookup_function_body (Output_Compare_Strcmp ());
2019     }
2020
2021   printf ("}\n");
2022 }
2023
2024 /* ------------------------------------------------------------------------- */
2025
2026 /* Generates the hash function and the key word recognizer function
2027    based upon the user's Options. */
2028
2029 void
2030 Key_List::output (void)
2031 {
2032   T (Trace t ("Key_List::output");)
2033
2034   compute_min_max ();
2035
2036   if (option[C] | option[ANSIC] | option[CPLUSPLUS])
2037     {
2038       const_always = "const ";
2039       const_readonly_array = (option[CONST] ? "const " : "");
2040       const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : "");
2041     }
2042   else
2043     {
2044       const_always = "";
2045       const_readonly_array = "";
2046       const_for_struct = "";
2047     }
2048
2049   if (!option[TYPE])
2050     {
2051       return_type = (const_always[0] ? "const char *" : "char *");
2052       struct_tag = (const_always[0] ? "const char *" : "char *");
2053     }
2054
2055   char_to_index = (option[SEVENBIT] ? "" : "(unsigned char)");
2056
2057   printf ("/* ");
2058   if (option[KRC])
2059     printf ("KR-C");
2060   else if (option[C])
2061     printf ("C");
2062   else if (option[ANSIC])
2063     printf ("ANSI-C");
2064   else if (option[CPLUSPLUS])
2065     printf ("C++");
2066   printf (" code produced by gperf version %s */\n", version_string);
2067   Options::print_options ();
2068
2069   printf ("%s\n", include_src);
2070
2071   if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
2072     printf ("%s;\n", array_type);
2073
2074   if (option[INCLUDE])
2075     printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */
2076
2077   if (!option[ENUM])
2078     {
2079       Output_Defines style;
2080       output_constants (style);
2081     }
2082   else if (option[GLOBAL])
2083     {
2084       Output_Enum style ("");
2085       output_constants (style);
2086     }
2087
2088   printf ("/* maximum key range = %d, duplicates = %d */\n\n",
2089           max_hash_value - min_hash_value + 1, total_duplicates);
2090
2091   if (option[CPLUSPLUS])
2092     printf ("class %s\n"
2093             "{\n"
2094             "private:\n"
2095             "  static inline unsigned int %s (const char *str, unsigned int len);\n"
2096             "public:\n"
2097             "  static %s%s%s (const char *str, unsigned int len);\n"
2098             "};\n"
2099             "\n",
2100             option.get_class_name (), option.get_hash_name (),
2101             const_for_struct, return_type, option.get_function_name ());
2102
2103   output_hash_function ();
2104
2105   if (option[GLOBAL])
2106     output_lookup_tables ();
2107
2108   output_lookup_function ();
2109
2110   if (additional_code)
2111     for (int c; (c = getchar ()) != EOF; putchar (c))
2112       ;
2113
2114   fflush (stdout);
2115 }
2116
2117 /* ========================= End of Output routines ========================= */
2118
2119 /* Sorts the keys by hash value. */
2120
2121 void
2122 Key_List::sort (void)
2123 {
2124   T (Trace t ("Key_List::sort");)
2125   hash_sort       = 1;
2126   occurrence_sort = 0;
2127
2128   head = merge_sort (head);
2129 }
2130
2131 /* Dumps the key list to stderr stream. */
2132
2133 void
2134 Key_List::dump ()
2135 {
2136   T (Trace t ("Key_List::dump");)
2137   int field_width = option.get_max_keysig_size ();
2138
2139   fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
2140            field_width, "char_set");
2141
2142   for (List_Node *ptr = head; ptr; ptr = ptr->next)
2143     fprintf (stderr, "%11d,%11d,%6d, %*.*s, %.*s\n",
2144              ptr->hash_value, ptr->key_length, ptr->index,
2145              field_width, ptr->char_set_length, ptr->char_set,
2146              ptr->key_length, ptr->key);
2147 }
2148
2149 /* Simple-minded constructor action here... */
2150
2151 Key_List::Key_List (void)
2152 {
2153   T (Trace t ("Key_List::Key_List");)
2154   total_keys       = 1;
2155   max_key_len      = INT_MIN;
2156   min_key_len      = INT_MAX;
2157   array_type       = 0;
2158   return_type      = 0;
2159   struct_tag       = 0;
2160   head             = 0;
2161   total_duplicates = 0;
2162   additional_code  = 0;
2163 }
2164
2165 /* Returns the length of entire key list. */
2166
2167 int
2168 Key_List::keyword_list_length (void)
2169 {
2170   T (Trace t ("Key_List::keyword_list_length");)
2171   return list_len;
2172 }
2173
2174 /* Returns length of longest key read. */
2175
2176 int
2177 Key_List::max_key_length (void)
2178 {
2179   T (Trace t ("Key_List::max_key_length");)
2180   return max_key_len;
2181 }
2182