home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / cperf-2.1 / src / keylist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-11-11  |  33.7 KB  |  1,034 lines
  1. /* Routines for building, ordering, and printing the keyword list.
  2.    Copyright (C) 1989 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
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <assert.h>
  22. #include <stdio.h>
  23. #include "options.h"
  24. #include "readline.h"
  25. #include "keylist.h"
  26. #include "hashtable.h"
  27. #include "stderr.h"
  28. #ifdef sparc
  29. #include <alloca.h>
  30. #endif
  31.  
  32. /* Current release version. */
  33. extern char *version_string;
  34.  
  35. /* See comments in perfect.cc. */
  36. extern int occurrences[ALPHABET_SIZE]; 
  37.  
  38. /* Ditto. */
  39. extern int asso_values[ALPHABET_SIZE];
  40.  
  41. /* Used in function reorder, below. */
  42. static bool determined[ALPHABET_SIZE]; 
  43.  
  44. /* Default type for generated code. */
  45. static char *default_array_type = "char *";
  46.  
  47. /* Generated function ``in_word_set'' default return type. */
  48. static char *default_return_type = "char *";
  49.  
  50. /* Largest positive integer value. */
  51. #define MAX_INT ((~(unsigned)0)>>1)
  52.  
  53. /* Most negative integer value. */
  54. #define NEG_MAX_INT ((~(unsigned)0)^((~(unsigned)0)>>1))
  55.  
  56. /* Maximum value an unsigned char can take. */
  57. #define MAX_UNSIGNED_CHAR 256
  58.  
  59. /* Maximum value an unsigned short can take. */
  60. #define MAX_UNSIGNED_SHORT 65536
  61.  
  62. /* Make the hash table 5 times larger than the number of keyword entries. */
  63. #define TABLE_MULTIPLE 5
  64.  
  65. /* Efficiently returns the least power of two greater than or equal to X! */
  66. #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
  67.  
  68. /* How wide the printed field width must be to contain the maximum hash value. */
  69. static int field_width = 2;
  70.  
  71. /* Globally visible KEY_LIST object. */
  72.  
  73. KEY_LIST key_list;
  74.  
  75. /* Gathers the input stream into a buffer until one of two things occur:
  76.  
  77.    1. We read a '%' followed by a '%'
  78.    2. We read a '%' followed by a '}'
  79.  
  80.    The first symbolizes the beginning of the keyword list proper,
  81.    The second symbolizes the end of the C source code to be generated
  82.    verbatim in the output file.
  83.  
  84.    I assume that the keys are separated from the optional preceding struct
  85.    declaration by a consecutive % followed by either % or } starting in 
  86.    the first column. The code below uses an expandible buffer to scan off 
  87.    and return a pointer to all the code (if any) appearing before the delimiter. */
  88.  
  89. static char *
  90. get_special_input (delimiter)
  91.      char delimiter;
  92. { 
  93.   char *xmalloc ();
  94.   int size  = 80;
  95.   char *buf = xmalloc (size);
  96.   int c, i;
  97.  
  98.   for (i = 0; (c = getchar ()) != EOF; i++)
  99.     {
  100.       if (c == '%')
  101.         {
  102.           if ((c = getchar ()) == delimiter)
  103.             {
  104.         
  105.               while ((c = getchar ()) != '\n')
  106.                 ; /* Discard newline. */
  107.               
  108.               if (i == 0)
  109.                 return "";
  110.               else
  111.                 {
  112.                   buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
  113.                   return buf;
  114.                 }
  115.             }
  116.           else
  117.             ungetc (c, stdin);
  118.         }
  119.       else if (i >= size) /* Yikes, time to grow the buffer! */
  120.         { 
  121.           char *temp = xmalloc (size *= 2);
  122.           int j;
  123.           
  124.           for (j = 0; j < i; j++)
  125.             temp[j] = buf[j];
  126.           
  127.           free (buf);
  128.           buf = temp;
  129.         }
  130.       buf[i] = c;
  131.     }
  132.   
  133.   return NULL;        /* Problem here. */
  134. }
  135.  
  136. /* Stores any C text that must be included verbatim into the 
  137.    generated code output. */
  138.  
  139. static char *
  140. save_include_src ()
  141. {
  142.   int c;
  143.   
  144.   if ((c = getchar ()) != '%')
  145.     {
  146.       ungetc (c, stdin);
  147.       return "";
  148.     }
  149.   else if ((c = getchar ()) != '{')
  150.     report_error ("internal error, %c != '{' on line %d in file %s%a", c, __LINE__, __FILE__);
  151.     /*NOT REACHED*/
  152.   else 
  153.     return get_special_input ('}');
  154. }
  155.  
  156. /* strcspn - find length of initial segment of s consisting entirely
  157.    of characters not from reject (borrowed from Henry Spencer's
  158.    ANSI string package). */
  159.  
  160. static int
  161. strcspn (s, reject)
  162.      char *s;
  163.      char *reject;
  164. {
  165.   char *scan;
  166.   char *rej_scan;
  167.   int   count = 0;
  168.  
  169.   for (scan = s; *scan; scan++) 
  170.     {
  171.  
  172.       for (rej_scan = reject; *rej_scan;) 
  173.         if (*scan == *rej_scan++)
  174.           return count;
  175.  
  176.       count++;
  177.     }
  178.  
  179.   return count;
  180. }
  181.  
  182. /* Determines from the input file whether the user wants to build a table
  183.    from a user-defined struct, or whether the user is content to simply
  184.    use the default array of keys. */
  185.  
  186. static char *
  187. get_array_type ()
  188. {
  189.   return get_special_input ('%');
  190. }  
  191.   
  192. /* Sets up the Return_Type, the Struct_Tag type and the Array_Type
  193.    based upon various user Options. */
  194.  
  195. static void 
  196. set_output_types ()
  197. {
  198.   char *xmalloc ();
  199.   
  200.   if (OPTION_ENABLED (option, TYPE) && !(key_list.array_type = get_array_type ()))
  201.     return;                     /* Something's wrong, bug we'll catch it later on.... */
  202.   else if (OPTION_ENABLED (option, TYPE))        /* Yow, we've got a user-defined type... */
  203.     {    
  204.       int struct_tag_length = strcspn (key_list.array_type, "{\n\0");
  205.       
  206.       if (OPTION_ENABLED (option, POINTER))      /* And it must return a pointer... */
  207.         {    
  208.           key_list.return_type = xmalloc (struct_tag_length + 2);
  209.           strncpy (key_list.return_type, key_list.array_type, struct_tag_length);
  210.           key_list.return_type[struct_tag_length] = '\0';
  211.           strcat (key_list.return_type, "*");
  212.         }
  213.       
  214.       key_list.struct_tag = (char *) xmalloc (struct_tag_length + 1);
  215.       strncpy (key_list.struct_tag, key_list.array_type, struct_tag_length);
  216.       key_list.struct_tag[struct_tag_length] = '\0';
  217.     }  
  218.   else if (OPTION_ENABLED (option, POINTER))     /* Return a char *. */
  219.     key_list.return_type = default_array_type;
  220. }
  221.  
  222. /* Reads in all keys from standard input and creates a linked list pointed
  223.    to by Head.  This list is then quickly checked for ``links,'' i.e.,
  224.    unhashable elements possessing identical key sets and lengths. */
  225.  
  226. void 
  227. read_keys ()
  228. {
  229.   char     *ptr;
  230.   
  231.   key_list.include_src = save_include_src ();
  232.   set_output_types ();
  233.  
  234.   /* Oops, problem with the input file. */  
  235.   if (! (ptr = read_line ())) 
  236.     report_error ("No words in input file, did you forget\
  237.  to prepend %s or use -t accidentally?\n%a", "%%");
  238.  
  239.   /* Read in all the keywords from the input file. */
  240.   else 
  241.     {                      
  242.       LIST_NODE *temp, *trail;
  243.       char *delimiter = GET_DELIMITER (option); 
  244.  
  245.       for (temp = key_list.head = make_list_node (ptr, strcspn (ptr, delimiter));
  246.            (ptr = read_line ()) && strcmp (ptr, "%%");
  247.            key_list.total_keys++, temp = temp->next)
  248.         temp->next = make_list_node (ptr, strcspn (ptr, delimiter));
  249.       
  250.       /* See if any additional C code is included at end of this file. */
  251.       if (ptr)
  252.         key_list.additional_code = TRUE;
  253.       {
  254.         /* If this becomes TRUE we've got a link. */
  255.         bool       link = FALSE;  
  256.  
  257.         /* Make large hash table for efficiency. */
  258.         int table_size = (key_list.list_len = key_list.total_keys) * TABLE_MULTIPLE;
  259.         
  260.         /* By allocating the memory here we save on dynamic allocation overhead. 
  261.            Table must be a power of 2 for the hash function scheme to work. */
  262.         LIST_NODE **table = (LIST_NODE **) alloca (POW (table_size) * sizeof (LIST_NODE *));
  263.  
  264.         hash_table_init (table, table_size);
  265.  
  266.         /* Test whether there are any links and also set the maximum length of
  267.           an identifier in the keyword list. */
  268.       
  269.         for (temp = key_list.head, trail = NULL; temp; temp = temp->next)
  270.           {
  271.             LIST_NODE *ptr = retrieve (temp, OPTION_ENABLED (option, NOLENGTH));
  272.           
  273.             /* Check for links.  We deal with these by building an equivalence class
  274.               of all duplicate values (i.e., links) so that only 1 keyword is
  275.                 representative of the entire collection.  This *greatly* simplifies
  276.                   processing during later stages of the program. */
  277.  
  278.             if (ptr)              
  279.               {                   
  280.                 key_list.list_len--;
  281.                 trail->next = temp->next;
  282.                 temp->link  = ptr->link;
  283.                 ptr->link   = temp;
  284.                 link        = TRUE;
  285.  
  286.                 /* Complain if user hasn't enabled the duplicate option. */
  287.                 if (!OPTION_ENABLED (option, DUP))
  288.                   fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n", 
  289.                   temp->key, ptr->key, temp->char_set);
  290.                 else if (OPTION_ENABLED (option, DEBUG))
  291.                   fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n", 
  292.                   temp->key, ptr->key, temp->char_set);
  293.               }
  294.             else
  295.               trail = temp;
  296.             
  297.             /* Update minimum and maximum keyword length, if needed. */
  298.             if (temp->length > key_list.max_key_len) 
  299.               key_list.max_key_len = temp->length;
  300.             if (temp->length < key_list.min_key_len) 
  301.               key_list.min_key_len = temp->length;
  302.           }
  303.  
  304.         /* Free up the dynamic memory used in the hash table. */
  305.         hash_table_destroy ();
  306.  
  307.         /* Exit program if links exists and option[DUP] not set, since we can't continue safely. */
  308.         if (link) 
  309.           report_error (OPTION_ENABLED (option, DUP)
  310.                         ? "Some input keys have identical hash values, examine output carefully...\n"
  311.                         : "Some input keys have identical hash values,\ntry different key positions or use option -D.\n%a");
  312.       }
  313.       if (OPTION_ENABLED (option, ALLCHARS))
  314.         SET_CHARSET_SIZE (option, key_list.max_key_len);
  315.     }
  316. }
  317.  
  318. /* Recursively merges two sorted lists together to form one sorted list. The
  319.    ordering criteria is by frequency of occurrence of elements in the key set
  320.    or by the hash value.  This is a kludge, but permits nice sharing of
  321.    almost identical code without incurring the overhead of a function
  322.    call comparison. */
  323.   
  324. static LIST_NODE *
  325. merge (list1, list2)
  326.      LIST_NODE *list1;
  327.      LIST_NODE *list2;
  328. {
  329.   if (!list1)
  330.     return list2;
  331.   else if (!list2)
  332.     return list1;
  333.   else if (key_list.occurrence_sort && list1->occurrence < list2->occurrence
  334.            || key_list.hash_sort && list1->hash_value > list2->hash_value)
  335.     {
  336.       list2->next = merge (list2->next, list1);
  337.       return list2;
  338.     }
  339.   else
  340.     {
  341.       list1->next = merge (list1->next, list2);
  342.       return list1;
  343.     }
  344. }
  345.  
  346. /* Applies the merge sort algorithm to recursively sort the key list by
  347.    frequency of occurrence of elements in the key set. */
  348.   
  349. static LIST_NODE *
  350. merge_sort (head)
  351.      LIST_NODE *head;
  352. { 
  353.   if (!head || !head->next)
  354.     return head;
  355.   else
  356.     {
  357.       LIST_NODE *middle = head;
  358.       LIST_NODE *temp   = head->next->next;
  359.     
  360.       while (temp)
  361.         {
  362.           temp   = temp->next;
  363.           middle = middle->next;
  364.           if (temp)
  365.             temp = temp->next;
  366.         } 
  367.     
  368.       temp         = middle->next;
  369.       middle->next = NULL;
  370.       return merge (merge_sort (head), merge_sort (temp));
  371.     }   
  372. }
  373.  
  374. /* Returns the frequency of occurrence of elements in the key set. */
  375.  
  376. static int 
  377. get_occurrence (ptr)
  378.      LIST_NODE *ptr;
  379. {
  380.   int   value = 0;
  381.   char *temp;
  382.  
  383.   for (temp = ptr->char_set; *temp; temp++)
  384.     value += occurrences[*temp];
  385.   
  386.   return value;
  387. }
  388.  
  389. /* Enables the index location of all key set elements that are now 
  390.    determined. */
  391.   
  392. static void 
  393. set_determined (ptr)
  394.      LIST_NODE *ptr;
  395. {
  396.   char *temp;
  397.   
  398.   for (temp = ptr->char_set; *temp; temp++)
  399.     determined[*temp] = TRUE;
  400.   
  401. }
  402.  
  403. /* Returns TRUE if PTR's key set is already completely determined. */
  404.  
  405. static bool 
  406. already_determined (ptr)
  407.      LIST_NODE *ptr;
  408. {
  409.   bool  is_determined = TRUE;
  410.   char *temp;
  411.  
  412.   for (temp = ptr->char_set; is_determined && *temp; temp++)
  413.     is_determined = determined[*temp];
  414.   
  415.   return is_determined;
  416. }
  417.  
  418. /* Reorders the table by first sorting the list so that frequently occuring 
  419.    keys appear first, and then the list is reorded so that keys whose values 
  420.    are already determined will be placed towards the front of the list.  This
  421.    helps prune the search time by handling inevitable collisions early in the
  422.    search process.  See Cichelli's paper from Jan 1980 JACM for details.... */
  423.  
  424. void 
  425. reorder ()
  426. {
  427.   LIST_NODE *ptr;
  428.  
  429.   for (ptr = key_list.head; ptr; ptr = ptr->next)
  430.     ptr->occurrence = get_occurrence (ptr);
  431.   
  432.   key_list.hash_sort       = FALSE;
  433.   key_list.occurrence_sort = TRUE;
  434.   
  435.   for (ptr = key_list.head = merge_sort (key_list.head); ptr->next; ptr = ptr->next)
  436.     {
  437.       set_determined (ptr);
  438.     
  439.       if (already_determined (ptr->next))
  440.         continue;
  441.       else
  442.         {
  443.           LIST_NODE *trail_ptr = ptr->next;
  444.           LIST_NODE *run_ptr   = trail_ptr->next;
  445.       
  446.           for (; run_ptr; run_ptr = trail_ptr->next)
  447.             {
  448.         
  449.               if (already_determined (run_ptr))
  450.                 {
  451.                   trail_ptr->next = run_ptr->next;
  452.                   run_ptr->next   = ptr->next;
  453.                   ptr = ptr->next = run_ptr;
  454.                 }
  455.               else
  456.                 trail_ptr = run_ptr;
  457.             }
  458.         }
  459.     }     
  460. }
  461.  
  462. /* Determines the maximum and minimum hash values.  One notable feature is 
  463.    Ira Pohl's optimal algorithm to calculate both the maximum and minimum
  464.    items in a list in O(3n/2) time (faster than the O (2n) method). 
  465.    Returns the maximum hash value encountered. */
  466.   
  467. static int 
  468. print_min_max ()
  469. {
  470.   int          min_hash_value;
  471.   int          max_hash_value;
  472.   LIST_NODE   *temp;
  473.   
  474.   if (ODD (key_list.list_len)) /* Pre-process first item, list now has an even length. */
  475.     {              
  476.       min_hash_value  = max_hash_value = key_list.head->hash_value;
  477.       temp            = key_list.head->next;
  478.     }
  479.   else /* List is already even length, no extra work necessary. */
  480.     {                      
  481.       min_hash_value = MAX_INT;
  482.       max_hash_value = NEG_MAX_INT;
  483.       temp           = key_list.head;
  484.     }
  485.   
  486.   for ( ; temp; temp = temp->next) /* Find max and min in optimal o(3n/2) time. */
  487.     { 
  488.       static int i;
  489.       int key_2, key_1 = temp->hash_value;
  490.       temp  = temp->next;
  491.       key_2 = temp->hash_value;
  492.       i++;
  493.       
  494.       if (key_1 < key_2)
  495.         {
  496.           if (key_1 < min_hash_value)
  497.             min_hash_value = key_1;
  498.           if (key_2 > max_hash_value)
  499.             max_hash_value = key_2;
  500.         }
  501.       else
  502.         {
  503.           if (key_2 < min_hash_value)
  504.             min_hash_value = key_2;
  505.           if (key_1 > max_hash_value)
  506.             max_hash_value = key_1;
  507.         }
  508.   }
  509.   
  510.   printf ("\n#define MIN_WORD_LENGTH %d\n#define MAX_WORD_LENGTH %d\
  511. \n#define MIN_HASH_VALUE %d\n#define MAX_HASH_VALUE %d\
  512. \n/*\n%5d keywords\n%5d is the maximum key range\n*/\n\n",
  513.           key_list.min_key_len == MAX_INT ? key_list.max_key_len : key_list.min_key_len,
  514.           key_list.max_key_len, min_hash_value, max_hash_value,
  515.           key_list.total_keys, (max_hash_value - min_hash_value + 1));
  516.   return max_hash_value;
  517. }
  518.  
  519. /* Generates the output using a C switch.  This trades increased search
  520.    time for decreased table space (potentially *much* less space for
  521.    sparse tables). It the user has specified their own struct in the
  522.    keyword file *and* they enable the POINTER option we have extra work to
  523.    do.  The solution here is to maintain a local static array of user
  524.    defined struct's, as with the Print_Lookup_Function.  Then we use for
  525.    switch statements to perform a strcmp or strncmp, returning 0 if the str 
  526.    fails to match, and otherwise returning a pointer to appropriate index
  527.    location in the local static array. */
  528.  
  529. static void 
  530. print_switch ()
  531. {
  532.   char      *comp_buffer;
  533.   LIST_NODE *curr                     = key_list.head;
  534.   int        pointer_and_type_enabled = OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE);
  535.   int        total_switches           = GET_TOTAL_SWITCHES (option);
  536.   int        switch_size              = keyword_list_length () / total_switches;
  537.  
  538.   if (pointer_and_type_enabled)
  539.     {
  540.       comp_buffer = (char *) alloca (strlen ("*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)")
  541.                                      + 2 * strlen (GET_KEY_NAME (option)) + 1);
  542.       sprintf (comp_buffer, OPTION_ENABLED (option, COMP)
  543.                ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
  544.                : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)",
  545.                GET_KEY_NAME (option), GET_KEY_NAME (option));
  546.     }
  547.   else
  548.     comp_buffer = OPTION_ENABLED (option, COMP) 
  549.       ? "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)" 
  550.       : "*str == *resword && !strcmp (str + 1, resword + 1)";
  551.  
  552.   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n\
  553.       register int key = %s (str, len);\n\n\
  554.       if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n        {\n", GET_HASH_NAME (option));
  555.   
  556.   /* Properly deal with user's who request multiple switch statements. */
  557.  
  558.   while (curr)
  559.     {
  560.       LIST_NODE *temp              = curr;
  561.       int        lowest_case_value = curr->hash_value;
  562.       int        number_of_cases   = 0;
  563.  
  564.       /* Figure out a good cut point to end this switch. */
  565.  
  566.       for (; temp && ++number_of_cases < switch_size; temp = temp->next)
  567.         if (temp->next && temp->hash_value == temp->next->hash_value)
  568.           while (temp->next && temp->hash_value == temp->next->hash_value)
  569.             temp = temp->next;
  570.  
  571.       if (temp)
  572.         printf ("          if (key <= %d)\n            {\n", temp->hash_value);
  573.       else
  574.         printf ("            {\n");
  575.  
  576.       /* Output each keyword as part of a switch statement indexed by hash value. */
  577.       
  578.       if (OPTION_ENABLED (option, POINTER) || OPTION_ENABLED (option, DUP))
  579.         {
  580.           int i = 0;
  581.  
  582.           printf ("              %s%s *resword; %s\n\n",
  583.                   OPTION_ENABLED (option, CONST) ? "const " : "",
  584.                   pointer_and_type_enabled ? key_list.struct_tag : "char", 
  585.                   OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP) ? "int key_len;" : "");
  586.           printf ("              switch (key - %d)\n                {\n", lowest_case_value);
  587.  
  588.           for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
  589.             {
  590.               printf ("                case %*d:", field_width, temp->hash_value - lowest_case_value);
  591.               if (OPTION_ENABLED (option, DEBUG))
  592.                 printf (" /* hash value = %4d, keyword = \"%s\" */", temp->hash_value, temp->key);
  593.               putchar ('\n');
  594.  
  595.               /* Handle `natural links,' i.e., those that occur statically. */
  596.  
  597.               if (temp->link)
  598.                 {
  599.                   LIST_NODE *links;
  600.  
  601.                   for (links = temp; links; links = links->link)
  602.                     {
  603.                       if (pointer_and_type_enabled)
  604.                         printf ("                  resword = &wordlist[%d];\n", links->index);
  605.                       else
  606.                         printf ("                  resword = \"%s\";\n", links->key); 
  607.                       printf ("                  if (%s) return resword;\n", comp_buffer);
  608.                     }
  609.                 }
  610.               /* Handle unresolved duplicate hash values.  These are guaranteed
  611.                 to be adjacent since we sorted the keyword list by increasing
  612.                   hash values. */
  613.               if (temp->next && temp->hash_value == temp->next->hash_value)
  614.                 {
  615.  
  616.                   for ( ; temp->next && temp->hash_value == temp->next->hash_value;
  617.                        temp = temp->next)
  618.                     {
  619.                       if (pointer_and_type_enabled)
  620.                         printf ("                  resword = &wordlist[%d];\n", temp->index);
  621.                       else
  622.                         printf ("                  resword = \"%s\";\n", temp->key);
  623.                       printf ("                  if (%s) return resword;\n", comp_buffer);
  624.                     }
  625.                   if (pointer_and_type_enabled)
  626.                     printf ("                  resword = &wordlist[%d];\n", temp->index);
  627.                   else
  628.                     printf ("                  resword = \"%s\";\n", temp->key);
  629.                   printf ("                  return %s ? resword : 0;\n", comp_buffer);
  630.                 }
  631.               else if (temp->link)
  632.                 printf ("                  return 0;\n");
  633.               else
  634.                 {
  635.                   if (pointer_and_type_enabled)
  636.                     printf ("                  resword = &wordlist[%d];", temp->index);
  637.                   else 
  638.                     printf ("                  resword = \"%s\";", temp->key);
  639.                   if (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP))
  640.                     printf (" key_len = %d;", temp->length);
  641.                   printf (" break;\n");
  642.                 }
  643.             }
  644.           printf ("                default: return 0;\n                }\n");
  645.           printf (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP)
  646.                   ? "              if (len == key_len && %s)\n                return resword;\n"
  647.                   : "              if (%s)\n                return resword;\n", comp_buffer);
  648.           printf ("              return 0;\n            }\n");
  649.           curr = temp;
  650.         }
  651.       else                          /* Nothing special required here. */
  652.         {                        
  653.           int i = 0;
  654.           printf ("              char *s;\n\n              switch (key - %d)\n                {\n",
  655.                   lowest_case_value);
  656.       
  657.           for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
  658.             if (OPTION_ENABLED (option, LENTABLE))
  659.               printf ("                case %*d: if (len == %d) s = \"%s\"; else return 0; break;\n",
  660.                       field_width, temp->hash_value - lowest_case_value, 
  661.                       temp->length, temp->key);
  662.             else
  663.               printf ("                case %*d: s = \"%s\"; break;\n",
  664.                       field_width, temp->hash_value - lowest_case_value, temp->key);
  665.                       
  666.           printf ("                default: return 0;\n                }\n              ");
  667.           printf ("return *s == *str && !%s;\n            }\n",
  668.                   OPTION_ENABLED (option, COMP) 
  669.                   ? "strncmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)");
  670.           curr = temp;
  671.         }
  672.     }
  673.   printf ("         }\n    }\n  return 0;\n}\n");
  674. }
  675.  
  676. /* Prints out a table of keyword lengths, for use with the 
  677.    comparison code in generated function ``in_word_set.'' */
  678.  
  679. static void 
  680. print_keylength_table ()
  681. {
  682.   int        max_column = 15;
  683.   int        index      = 0;
  684.   int        column     = 0;
  685.   char      *indent     = OPTION_ENABLED (option, GLOBAL) ? "" : "  ";
  686.   LIST_NODE *temp;
  687.  
  688.   if (!OPTION_ENABLED (option, DUP) && !OPTION_ENABLED (option, SWITCH)) 
  689.     {
  690.       printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n    ",
  691.               indent, OPTION_ENABLED (option, CONST) ? "const " : "",
  692.               key_list.max_key_len < MAX_UNSIGNED_CHAR ? "char" :
  693.               (key_list.max_key_len < MAX_UNSIGNED_SHORT ? "short" : "long"),
  694.               indent, indent);
  695.   
  696.       for (temp = key_list.head; temp; temp = temp->next, index++)
  697.         {
  698.     
  699.           if (index < temp->hash_value)
  700.             {
  701.       
  702.               for ( ; index < temp->hash_value; index++)
  703.                 printf ("%3d%s", 0, ++column % (max_column - 1) ? "," : ",\n    ");
  704.             }
  705.     
  706.           printf ("%3d%s", temp->length, ++column % (max_column - 1 ) ? "," : ",\n    ");
  707.         }
  708.   
  709.       printf ("\n%s%s};\n\n", indent, indent);
  710.     }
  711. }
  712.  
  713. /* Prints out the array containing the key words for the Perfect
  714.    hash function. */
  715.   
  716. static void 
  717. print_keyword_table ()
  718. {
  719.   char      *l_brace      = *key_list.head->rest ? "{" : "";
  720.   char      *r_brace      = *key_list.head->rest ? "}," : "";
  721.   int        doing_switch = OPTION_ENABLED (option, SWITCH);
  722.   char      *indent       = OPTION_ENABLED (option, GLOBAL) ? "" : "  ";
  723.   int        index        = 0;
  724.   LIST_NODE *temp;
  725.  
  726.   printf ("\n%sstatic %s%s wordlist[] =\n%s%s{\n", 
  727.           indent, OPTION_ENABLED (option, CONST) ? "const " : "",
  728.           key_list.struct_tag, indent, indent);
  729.   
  730.   /* Generate an array of reserved words at appropriate locations. */
  731.   
  732.     for (temp = key_list.head; temp; temp = temp->next, index++)
  733.         {
  734.             temp->index = index;
  735.  
  736.             if (!doing_switch && index < temp->hash_value)
  737.                 {
  738.                     int column;
  739.  
  740.                     printf ("      ");
  741.       
  742.                     for (column = 1; index < temp->hash_value; index++, column++)
  743.                         printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n      ");
  744.       
  745.                     if (column % 10)
  746.                         printf ("\n");
  747.                     else 
  748.                         {
  749.                             printf ("%s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
  750.                             continue;
  751.                         }
  752.                 }
  753.  
  754.             printf ("      %s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
  755.  
  756.             /* Deal with links specially. */
  757.             if (temp->link)
  758.                 {
  759.                     LIST_NODE *links;
  760.  
  761.                     for (links = temp->link; links; links = links->link)
  762.                         {
  763.                             links->index = ++index;
  764.                             printf ("      %s\"%s\", %s%s\n", l_brace, links->key, links->rest, r_brace);
  765.                         }
  766.                 }
  767.  
  768.         }
  769.  
  770.   printf ("%s%s};\n\n", indent, indent);
  771. }
  772.  
  773. /* Generates C code for the hash function that returns the
  774.    proper encoding for each key word. */
  775.  
  776. static void 
  777. print_hash_function (max_hash_value)
  778.      int max_hash_value;
  779. {
  780.   int max_column = 10;
  781.   int count       = max_hash_value;
  782.  
  783.   /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
  784.  
  785.   while ((count /= 10) > 0)
  786.     field_width++;
  787.  
  788.   if (OPTION_ENABLED (option, GNU))
  789.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  790.   
  791.   printf (OPTION_ENABLED (option, ANSI) 
  792.           ? "static int\n%s (register const char *str, register int len)\n{\n  static %sunsigned %s hash_table[] =\n    {"
  793.           : "static int\n%s (str, len)\n     register char *str;\n     register unsigned int  len;\n{\n  static %sunsigned %s hash_table[] =\n    {",
  794.           GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "",
  795.           max_hash_value < MAX_UNSIGNED_CHAR 
  796.           ? "char" : (max_hash_value < MAX_UNSIGNED_SHORT ? "short" : "int"));
  797.   
  798.   for (count = 0; count < ALPHABET_SIZE; ++count)
  799.     {
  800.       if (!(count % max_column))
  801.         printf ("\n    ");
  802.       
  803.       printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value);
  804.     }
  805.   
  806.   /* Optimize special case of ``-k 1,$'' */
  807.   if (OPTION_ENABLED (option, DEFAULTCHARS)) 
  808.     printf ("\n    };\n  return %s + hash_table[str[len - 1]] + hash_table[str[0]];\n}\n\n",
  809.             OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
  810.   else
  811.     {
  812.       int key_pos;
  813.  
  814.       RESET (option);
  815.  
  816.       /* Get first (also highest) key position. */
  817.       key_pos = GET (option); 
  818.       
  819.       /* We can perform additional optimizations here. */
  820.       if (!OPTION_ENABLED (option, ALLCHARS) && key_pos <= key_list.min_key_len) 
  821.         { 
  822.           printf ("\n  };\n  return %s", OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
  823.           
  824.           for ( ; key_pos != EOS && key_pos != WORD_END; key_pos = GET (option))
  825.             printf (" + hash_table[str[%d]]", key_pos - 1);
  826.            
  827.           printf ("%s;\n}\n\n", key_pos == WORD_END ? " + hash_table[str[len - 1]]" : "");
  828.         }
  829.  
  830.       /* We've got to use the correct, but brute force, technique. */
  831.       else 
  832.         {                    
  833.           printf ("\n    };\n  register int hval = %s;\n\n  switch (%s)\n    {\n      default:\n",
  834.                   OPTION_ENABLED (option, NOLENGTH) 
  835.                   ? "0" : "len", OPTION_ENABLED (option, NOLENGTH) ? "len" : "hval");
  836.           
  837.           /* User wants *all* characters considered in hash. */
  838.           if (OPTION_ENABLED (option, ALLCHARS)) 
  839.             { 
  840.               int i;
  841.  
  842.               for (i = key_list.max_key_len; i > 0; i--)
  843.                 printf ("      case %d:\n        hval += hash_table[str[%d]];\n", i, i - 1);
  844.               
  845.               printf ("    }\n  return hval;\n}\n\n");
  846.             }
  847.           else /* do the hard part... */
  848.             {                
  849.               count = key_pos + 1;
  850.               
  851.               do
  852.                 {
  853.                   
  854.                   while (--count > key_pos)
  855.                     printf ("      case %d:\n", count);
  856.                   
  857.                   printf ("      case %d:\n        hval += hash_table[str[%d]];\n", 
  858.                           key_pos, key_pos - 1);
  859.                 }
  860.               while ((key_pos = GET (option)) != EOS && key_pos != WORD_END);
  861.               
  862.               printf ("    }\n  return hval%s ;\n}\n\n", key_pos == WORD_END 
  863.                       ? " + hash_table[str[len - 1]]" : "");
  864.           }
  865.       }
  866.   }
  867. }
  868.  
  869. /* Generates C code to perform the keyword lookup. */
  870.  
  871. static void 
  872. print_lookup_function ()
  873. { 
  874.   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n\
  875.       register int key = %s (str, len);\n\n\
  876.       if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n        {\n\
  877.           register %schar *s = wordlist[key]", 
  878.           GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "");
  879.   if (key_list.array_type != default_array_type)
  880.     printf (".%s", GET_KEY_NAME (option));
  881.  
  882.   printf (";\n\n          if (%s*s == *str && !%s)\n            return %s",
  883.           OPTION_ENABLED (option, LENTABLE) ? "len == lengthtable[key]\n              && " : "",
  884.           OPTION_ENABLED (option, COMP) ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
  885.           OPTION_ENABLED (option, TYPE) && OPTION_ENABLED (option, POINTER) ? "&wordlist[key]" : "s");
  886.   printf (";\n        }\n    }\n  return 0;\n}\n");
  887. }
  888.  
  889. /* Generates the hash function and the key word recognizer function
  890.    based upon the user's Options. */
  891.  
  892. void 
  893. print_output ()
  894. {
  895.   int global_table = OPTION_ENABLED (option, GLOBAL);
  896.  
  897.   printf ("%s\n", key_list.include_src);
  898.   
  899.   /* Potentially output type declaration now, reference it later on.... */
  900.   if (OPTION_ENABLED (option, TYPE) && !OPTION_ENABLED (option, NOTYPE)) 
  901.     printf ("%s;\n", key_list.array_type);
  902.   
  903.   print_hash_function (print_min_max ());
  904.   
  905.   if (global_table)
  906.     if (OPTION_ENABLED (option, SWITCH))
  907.       {
  908.         if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
  909.           print_keylength_table ();
  910.         if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE))
  911.           print_keyword_table ();
  912.       }
  913.     else
  914.       {
  915.         if (OPTION_ENABLED (option, LENTABLE))
  916.           print_keylength_table ();
  917.         print_keyword_table ();
  918.       }
  919.   /* Use the inline keyword to remove function overhead. */
  920.   if (OPTION_ENABLED (option, GNU)) 
  921.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  922.   
  923.   /* Use ANSI function prototypes. */
  924.   printf (OPTION_ENABLED (option, ANSI)
  925.           ? "%s%s\n%s (register const char *str, register int len)\n{\n"
  926.           : "%s%s\n%s (str, len)\n     register char *str;\n     register unsigned int len;\n{\n", 
  927.             OPTION_ENABLED (option, CONST) ? "const " : "", 
  928.             key_list.return_type, GET_FUNCTION_NAME (option));
  929.   
  930.   /* Use the switch in place of lookup table. */
  931.   if (OPTION_ENABLED (option, SWITCH))
  932.     {               
  933.       if (!global_table)
  934.         {
  935.           if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
  936.             print_keylength_table ();
  937.           if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE)) 
  938.             print_keyword_table ();
  939.         }
  940.       print_switch ();
  941.     }
  942.   else                /* Use the lookup table, in place of switch. */
  943.     {           
  944.       if (!global_table)
  945.         {
  946.           if (OPTION_ENABLED (option, LENTABLE))
  947.             print_keylength_table ();
  948.           print_keyword_table ();
  949.         }
  950.       print_lookup_function ();
  951.     }
  952.  
  953.   if (key_list.additional_code)
  954.     {
  955.       int c;
  956.  
  957.       while ((c = getchar ()) != EOF)
  958.         putchar (c);
  959.     }
  960.   fflush (stdout);
  961. }
  962.  
  963. /* Sorts the keys by hash value. */
  964.  
  965. void 
  966. sort ()
  967. { 
  968.   key_list.hash_sort       = TRUE;
  969.   key_list.occurrence_sort = FALSE;
  970.   
  971.   key_list.head = merge_sort (key_list.head);
  972. }
  973.  
  974. /* Dumps the key list to stderr stream. */
  975.  
  976. static void 
  977. dump () 
  978. {      
  979.   LIST_NODE *ptr;
  980.  
  981.   fprintf (stderr, "\nList contents are:\n(hash value, key length, index, key set, key):\n");
  982.   
  983.   for (ptr = key_list.head; ptr; ptr = ptr->next)
  984.     fprintf (stderr, "%7d,%7d,%6d, %s, %s\n",
  985.              ptr->hash_value, ptr->length, ptr->index,
  986.              ptr->char_set, ptr->key);
  987. }
  988.  
  989. /* Simple-minded constructor action here... */
  990.  
  991. void
  992. key_list_init ()
  993. {   
  994.   key_list.total_keys      = 1;
  995.   key_list.max_key_len     = NEG_MAX_INT;
  996.   key_list.min_key_len     = MAX_INT;
  997.   key_list.return_type     = default_return_type;
  998.   key_list.array_type      = key_list.struct_tag  = default_array_type;
  999.   key_list.head            = NULL;
  1000.   key_list.additional_code = FALSE;
  1001. }
  1002.  
  1003. /* Returns the length of entire key list. */
  1004.  
  1005. int 
  1006. keyword_list_length () 
  1007. { 
  1008.   return key_list.list_len;
  1009. }
  1010.  
  1011. /* Returns length of longest key read. */
  1012.  
  1013. int 
  1014. max_key_length ()
  1015. { 
  1016.   return key_list.max_key_len;
  1017. }
  1018.  
  1019. /* DESTRUCTOR dumps diagnostics during debugging. */
  1020.  
  1021. void
  1022. key_list_destroy () 
  1023. { 
  1024.   if (OPTION_ENABLED (option, DEBUG))
  1025.     {
  1026.       fprintf (stderr, "\nDumping key list information:\ntotal unique keywords = %d\
  1027. \ntotal keywords = %d\nmaximum key length = %d.\n", 
  1028.                     key_list.list_len, key_list.total_keys, key_list.max_key_len);
  1029.       dump ();
  1030.       fprintf (stderr, "End dumping list.\n\n");
  1031.     }
  1032. }
  1033.  
  1034.