aboutsummaryrefslogtreecommitdiffstats
path: root/src/keylist.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/keylist.c')
-rw-r--r--src/keylist.c1033
1 files changed, 0 insertions, 1033 deletions
diff --git a/src/keylist.c b/src/keylist.c
deleted file mode 100644
index f92d97549694..000000000000
--- a/src/keylist.c
+++ /dev/null
@@ -1,1033 +0,0 @@
-/* Routines for building, ordering, and printing the keyword list.
- Copyright (C) 1989 Free Software Foundation, Inc.
- written by Douglas C. Schmidt (schmidt@ics.uci.edu)
-
-This file is part of GNU GPERF.
-
-GNU GPERF is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 1, or (at your option)
-any later version.
-
-GNU GPERF is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU GPERF; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
-
-#include <assert.h>
-#include <stdio.h>
-#include "options.h"
-#include "readline.h"
-#include "keylist.h"
-#include "hashtable.h"
-#include "stderr.h"
-#ifdef sparc
-#include <alloca.h>
-#endif
-
-/* Current release version. */
-extern char *version_string;
-
-/* See comments in perfect.cc. */
-extern int occurrences[ALPHABET_SIZE];
-
-/* Ditto. */
-extern int asso_values[ALPHABET_SIZE];
-
-/* Used in function reorder, below. */
-static bool determined[ALPHABET_SIZE];
-
-/* Default type for generated code. */
-static char *default_array_type = "char *";
-
-/* Generated function ``in_word_set'' default return type. */
-static char *default_return_type = "char *";
-
-/* Largest positive integer value. */
-#define MAX_INT ((~(unsigned)0)>>1)
-
-/* Most negative integer value. */
-#define NEG_MAX_INT ((~(unsigned)0)^((~(unsigned)0)>>1))
-
-/* Maximum value an unsigned char can take. */
-#define MAX_UNSIGNED_CHAR 256
-
-/* Maximum value an unsigned short can take. */
-#define MAX_UNSIGNED_SHORT 65536
-
-/* Make the hash table 5 times larger than the number of keyword entries. */
-#define TABLE_MULTIPLE 5
-
-/* Efficiently returns the least power of two greater than or equal to X! */
-#define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
-
-/* How wide the printed field width must be to contain the maximum hash value. */
-static int field_width = 2;
-
-/* Globally visible KEY_LIST object. */
-
-KEY_LIST key_list;
-
-/* Gathers the input stream into a buffer until one of two things occur:
-
- 1. We read a '%' followed by a '%'
- 2. We read a '%' followed by a '}'
-
- The first symbolizes the beginning of the keyword list proper,
- The second symbolizes the end of the C source code to be generated
- verbatim in the output file.
-
- I assume that the keys are separated from the optional preceding struct
- declaration by a consecutive % followed by either % or } starting in
- the first column. The code below uses an expandible buffer to scan off
- and return a pointer to all the code (if any) appearing before the delimiter. */
-
-static char *
-get_special_input (delimiter)
- char delimiter;
-{
- char *xmalloc ();
- int size = 80;
- char *buf = xmalloc (size);
- int c, i;
-
- for (i = 0; (c = getchar ()) != EOF; i++)
- {
- if (c == '%')
- {
- if ((c = getchar ()) == delimiter)
- {
-
- while ((c = getchar ()) != '\n')
- ; /* Discard newline. */
-
- if (i == 0)
- return "";
- else
- {
- buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
- return buf;
- }
- }
- else
- ungetc (c, stdin);
- }
- else if (i >= size) /* Yikes, time to grow the buffer! */
- {
- char *temp = xmalloc (size *= 2);
- int j;
-
- for (j = 0; j < i; j++)
- temp[j] = buf[j];
-
- free (buf);
- buf = temp;
- }
- buf[i] = c;
- }
-
- return NULL; /* Problem here. */
-}
-
-/* Stores any C text that must be included verbatim into the
- generated code output. */
-
-static char *
-save_include_src ()
-{
- int c;
-
- if ((c = getchar ()) != '%')
- {
- ungetc (c, stdin);
- return "";
- }
- else if ((c = getchar ()) != '{')
- report_error ("internal error, %c != '{' on line %d in file %s%a", c, __LINE__, __FILE__);
- /*NOT REACHED*/
- else
- return get_special_input ('}');
-}
-
-/* strcspn - find length of initial segment of s consisting entirely
- of characters not from reject (borrowed from Henry Spencer's
- ANSI string package). */
-
-static int
-strcspn (s, reject)
- char *s;
- char *reject;
-{
- char *scan;
- char *rej_scan;
- int count = 0;
-
- for (scan = s; *scan; scan++)
- {
-
- for (rej_scan = reject; *rej_scan;)
- if (*scan == *rej_scan++)
- return count;
-
- count++;
- }
-
- return count;
-}
-
-/* Determines from the input file whether the user wants to build a table
- from a user-defined struct, or whether the user is content to simply
- use the default array of keys. */
-
-static char *
-get_array_type ()
-{
- return get_special_input ('%');
-}
-
-/* Sets up the Return_Type, the Struct_Tag type and the Array_Type
- based upon various user Options. */
-
-static void
-set_output_types ()
-{
- char *xmalloc ();
-
- if (OPTION_ENABLED (option, TYPE) && !(key_list.array_type = get_array_type ()))
- return; /* Something's wrong, bug we'll catch it later on.... */
- else if (OPTION_ENABLED (option, TYPE)) /* Yow, we've got a user-defined type... */
- {
- int struct_tag_length = strcspn (key_list.array_type, "{\n\0");
-
- if (OPTION_ENABLED (option, POINTER)) /* And it must return a pointer... */
- {
- key_list.return_type = xmalloc (struct_tag_length + 2);
- strncpy (key_list.return_type, key_list.array_type, struct_tag_length);
- key_list.return_type[struct_tag_length] = '\0';
- strcat (key_list.return_type, "*");
- }
-
- key_list.struct_tag = (char *) xmalloc (struct_tag_length + 1);
- strncpy (key_list.struct_tag, key_list.array_type, struct_tag_length);
- key_list.struct_tag[struct_tag_length] = '\0';
- }
- else if (OPTION_ENABLED (option, POINTER)) /* Return a char *. */
- key_list.return_type = default_array_type;
-}
-
-/* Reads in all keys from standard input and creates a linked list pointed
- to by Head. This list is then quickly checked for ``links,'' i.e.,
- unhashable elements possessing identical key sets and lengths. */
-
-void
-read_keys ()
-{
- char *ptr;
-
- key_list.include_src = save_include_src ();
- set_output_types ();
-
- /* Oops, problem with the input file. */
- if (! (ptr = read_line ()))
- report_error ("No words in input file, did you forget\
- to prepend %s or use -t accidentally?\n%a", "%%");
-
- /* Read in all the keywords from the input file. */
- else
- {
- LIST_NODE *temp, *trail;
- char *delimiter = GET_DELIMITER (option);
-
- for (temp = key_list.head = make_list_node (ptr, strcspn (ptr, delimiter));
- (ptr = read_line ()) && strcmp (ptr, "%%");
- key_list.total_keys++, temp = temp->next)
- temp->next = make_list_node (ptr, strcspn (ptr, delimiter));
-
- /* See if any additional C code is included at end of this file. */
- if (ptr)
- key_list.additional_code = TRUE;
- {
- /* If this becomes TRUE we've got a link. */
- bool link = FALSE;
-
- /* Make large hash table for efficiency. */
- int table_size = (key_list.list_len = key_list.total_keys) * TABLE_MULTIPLE;
-
- /* By allocating the memory here we save on dynamic allocation overhead.
- Table must be a power of 2 for the hash function scheme to work. */
- LIST_NODE **table = (LIST_NODE **) alloca (POW (table_size) * sizeof (LIST_NODE *));
-
- hash_table_init (table, table_size);
-
- /* Test whether there are any links and also set the maximum length of
- an identifier in the keyword list. */
-
- for (temp = key_list.head, trail = NULL; temp; temp = temp->next)
- {
- LIST_NODE *ptr = retrieve (temp, OPTION_ENABLED (option, NOLENGTH));
-
- /* Check for links. We deal with these by building an equivalence class
- of all duplicate values (i.e., links) so that only 1 keyword is
- representative of the entire collection. This *greatly* simplifies
- processing during later stages of the program. */
-
- if (ptr)
- {
- key_list.list_len--;
- trail->next = temp->next;
- temp->link = ptr->link;
- ptr->link = temp;
- link = TRUE;
-
- /* Complain if user hasn't enabled the duplicate option. */
- if (!OPTION_ENABLED (option, DUP))
- fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n",
- temp->key, ptr->key, temp->char_set);
- else if (OPTION_ENABLED (option, DEBUG))
- fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n",
- temp->key, ptr->key, temp->char_set);
- }
- else
- trail = temp;
-
- /* Update minimum and maximum keyword length, if needed. */
- if (temp->length > key_list.max_key_len)
- key_list.max_key_len = temp->length;
- if (temp->length < key_list.min_key_len)
- key_list.min_key_len = temp->length;
- }
-
- /* Free up the dynamic memory used in the hash table. */
- hash_table_destroy ();
-
- /* Exit program if links exists and option[DUP] not set, since we can't continue safely. */
- if (link)
- report_error (OPTION_ENABLED (option, DUP)
- ? "Some input keys have identical hash values, examine output carefully...\n"
- : "Some input keys have identical hash values,\ntry different key positions or use option -D.\n%a");
- }
- if (OPTION_ENABLED (option, ALLCHARS))
- SET_CHARSET_SIZE (option, key_list.max_key_len);
- }
-}
-
-/* Recursively merges two sorted lists together to form one sorted list. The
- ordering criteria is by frequency of occurrence of elements in the key set
- or by the hash value. This is a kludge, but permits nice sharing of
- almost identical code without incurring the overhead of a function
- call comparison. */
-
-static LIST_NODE *
-merge (list1, list2)
- LIST_NODE *list1;
- LIST_NODE *list2;
-{
- if (!list1)
- return list2;
- else if (!list2)
- return list1;
- else if (key_list.occurrence_sort && list1->occurrence < list2->occurrence
- || key_list.hash_sort && list1->hash_value > list2->hash_value)
- {
- list2->next = merge (list2->next, list1);
- return list2;
- }
- else
- {
- list1->next = merge (list1->next, list2);
- return list1;
- }
-}
-
-/* Applies the merge sort algorithm to recursively sort the key list by
- frequency of occurrence of elements in the key set. */
-
-static LIST_NODE *
-merge_sort (head)
- LIST_NODE *head;
-{
- if (!head || !head->next)
- return head;
- else
- {
- LIST_NODE *middle = head;
- LIST_NODE *temp = head->next->next;
-
- while (temp)
- {
- temp = temp->next;
- middle = middle->next;
- if (temp)
- temp = temp->next;
- }
-
- temp = middle->next;
- middle->next = NULL;
- return merge (merge_sort (head), merge_sort (temp));
- }
-}
-
-/* Returns the frequency of occurrence of elements in the key set. */
-
-static int
-get_occurrence (ptr)
- LIST_NODE *ptr;
-{
- int value = 0;
- char *temp;
-
- for (temp = ptr->char_set; *temp; temp++)
- value += occurrences[*temp];
-
- return value;
-}
-
-/* Enables the index location of all key set elements that are now
- determined. */
-
-static void
-set_determined (ptr)
- LIST_NODE *ptr;
-{
- char *temp;
-
- for (temp = ptr->char_set; *temp; temp++)
- determined[*temp] = TRUE;
-
-}
-
-/* Returns TRUE if PTR's key set is already completely determined. */
-
-static bool
-already_determined (ptr)
- LIST_NODE *ptr;
-{
- bool is_determined = TRUE;
- char *temp;
-
- for (temp = ptr->char_set; is_determined && *temp; temp++)
- is_determined = determined[*temp];
-
- return is_determined;
-}
-
-/* Reorders the table by first sorting the list so that frequently occuring
- keys appear first, and then the list is reorded so that keys whose values
- are already determined will be placed towards the front of the list. This
- helps prune the search time by handling inevitable collisions early in the
- search process. See Cichelli's paper from Jan 1980 JACM for details.... */
-
-void
-reorder ()
-{
- LIST_NODE *ptr;
-
- for (ptr = key_list.head; ptr; ptr = ptr->next)
- ptr->occurrence = get_occurrence (ptr);
-
- key_list.hash_sort = FALSE;
- key_list.occurrence_sort = TRUE;
-
- for (ptr = key_list.head = merge_sort (key_list.head); ptr->next; ptr = ptr->next)
- {
- set_determined (ptr);
-
- if (already_determined (ptr->next))
- continue;
- else
- {
- LIST_NODE *trail_ptr = ptr->next;
- LIST_NODE *run_ptr = trail_ptr->next;
-
- for (; run_ptr; run_ptr = trail_ptr->next)
- {
-
- if (already_determined (run_ptr))
- {
- trail_ptr->next = run_ptr->next;
- run_ptr->next = ptr->next;
- ptr = ptr->next = run_ptr;
- }
- else
- trail_ptr = run_ptr;
- }
- }
- }
-}
-
-/* Determines the maximum and minimum hash values. One notable feature is
- Ira Pohl's optimal algorithm to calculate both the maximum and minimum
- items in a list in O(3n/2) time (faster than the O (2n) method).
- Returns the maximum hash value encountered. */
-
-static int
-print_min_max ()
-{
- int min_hash_value;
- int max_hash_value;
- LIST_NODE *temp;
-
- if (ODD (key_list.list_len)) /* Pre-process first item, list now has an even length. */
- {
- min_hash_value = max_hash_value = key_list.head->hash_value;
- temp = key_list.head->next;
- }
- else /* List is already even length, no extra work necessary. */
- {
- min_hash_value = MAX_INT;
- max_hash_value = NEG_MAX_INT;
- temp = key_list.head;
- }
-
- for ( ; temp; temp = temp->next) /* Find max and min in optimal o(3n/2) time. */
- {
- static int i;
- int key_2, key_1 = temp->hash_value;
- temp = temp->next;
- key_2 = temp->hash_value;
- i++;
-
- if (key_1 < key_2)
- {
- if (key_1 < min_hash_value)
- min_hash_value = key_1;
- if (key_2 > max_hash_value)
- max_hash_value = key_2;
- }
- else
- {
- if (key_2 < min_hash_value)
- min_hash_value = key_2;
- if (key_1 > max_hash_value)
- max_hash_value = key_1;
- }
- }
-
- printf ("\n#define MIN_WORD_LENGTH %d\n#define MAX_WORD_LENGTH %d\
-\n#define MIN_HASH_VALUE %d\n#define MAX_HASH_VALUE %d\
-\n/*\n%5d keywords\n%5d is the maximum key range\n*/\n\n",
- key_list.min_key_len == MAX_INT ? key_list.max_key_len : key_list.min_key_len,
- key_list.max_key_len, min_hash_value, max_hash_value,
- key_list.total_keys, (max_hash_value - min_hash_value + 1));
- return max_hash_value;
-}
-
-/* Generates the output using a C switch. This trades increased search
- time for decreased table space (potentially *much* less space for
- sparse tables). It the user has specified their own struct in the
- keyword file *and* they enable the POINTER option we have extra work to
- do. The solution here is to maintain a local static array of user
- defined struct's, as with the Print_Lookup_Function. Then we use for
- switch statements to perform a strcmp or strncmp, returning 0 if the str
- fails to match, and otherwise returning a pointer to appropriate index
- location in the local static array. */
-
-static void
-print_switch ()
-{
- char *comp_buffer;
- LIST_NODE *curr = key_list.head;
- int pointer_and_type_enabled = OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE);
- int total_switches = GET_TOTAL_SWITCHES (option);
- int switch_size = keyword_list_length () / total_switches;
-
- if (pointer_and_type_enabled)
- {
- comp_buffer = (char *) alloca (strlen ("*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)")
- + 2 * strlen (GET_KEY_NAME (option)) + 1);
- sprintf (comp_buffer, OPTION_ENABLED (option, COMP)
- ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
- : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)",
- GET_KEY_NAME (option), GET_KEY_NAME (option));
- }
- else
- comp_buffer = OPTION_ENABLED (option, COMP)
- ? "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)"
- : "*str == *resword && !strcmp (str + 1, resword + 1)";
-
- printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n\
- register int key = %s (str, len);\n\n\
- if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n {\n", GET_HASH_NAME (option));
-
- /* Properly deal with user's who request multiple switch statements. */
-
- while (curr)
- {
- LIST_NODE *temp = curr;
- int lowest_case_value = curr->hash_value;
- int number_of_cases = 0;
-
- /* Figure out a good cut point to end this switch. */
-
- for (; temp && ++number_of_cases < switch_size; temp = temp->next)
- if (temp->next && temp->hash_value == temp->next->hash_value)
- while (temp->next && temp->hash_value == temp->next->hash_value)
- temp = temp->next;
-
- if (temp)
- printf (" if (key <= %d)\n {\n", temp->hash_value);
- else
- printf (" {\n");
-
- /* Output each keyword as part of a switch statement indexed by hash value. */
-
- if (OPTION_ENABLED (option, POINTER) || OPTION_ENABLED (option, DUP))
- {
- int i = 0;
-
- printf (" %s%s *resword; %s\n\n",
- OPTION_ENABLED (option, CONST) ? "const " : "",
- pointer_and_type_enabled ? key_list.struct_tag : "char",
- OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP) ? "int key_len;" : "");
- printf (" switch (key - %d)\n {\n", lowest_case_value);
-
- for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
- {
- printf (" case %*d:", field_width, temp->hash_value - lowest_case_value);
- if (OPTION_ENABLED (option, DEBUG))
- printf (" /* hash value = %4d, keyword = \"%s\" */", temp->hash_value, temp->key);
- putchar ('\n');
-
- /* Handle `natural links,' i.e., those that occur statically. */
-
- if (temp->link)
- {
- LIST_NODE *links;
-
- for (links = temp; links; links = links->link)
- {
- if (pointer_and_type_enabled)
- printf (" resword = &wordlist[%d];\n", links->index);
- else
- printf (" resword = \"%s\";\n", links->key);
- printf (" if (%s) return resword;\n", comp_buffer);
- }
- }
- /* Handle unresolved duplicate hash values. These are guaranteed
- to be adjacent since we sorted the keyword list by increasing
- hash values. */
- if (temp->next && temp->hash_value == temp->next->hash_value)
- {
-
- for ( ; temp->next && temp->hash_value == temp->next->hash_value;
- temp = temp->next)
- {
- if (pointer_and_type_enabled)
- printf (" resword = &wordlist[%d];\n", temp->index);
- else
- printf (" resword = \"%s\";\n", temp->key);
- printf (" if (%s) return resword;\n", comp_buffer);
- }
- if (pointer_and_type_enabled)
- printf (" resword = &wordlist[%d];\n", temp->index);
- else
- printf (" resword = \"%s\";\n", temp->key);
- printf (" return %s ? resword : 0;\n", comp_buffer);
- }
- else if (temp->link)
- printf (" return 0;\n");
- else
- {
- if (pointer_and_type_enabled)
- printf (" resword = &wordlist[%d];", temp->index);
- else
- printf (" resword = \"%s\";", temp->key);
- if (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP))
- printf (" key_len = %d;", temp->length);
- printf (" break;\n");
- }
- }
- printf (" default: return 0;\n }\n");
- printf (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP)
- ? " if (len == key_len && %s)\n return resword;\n"
- : " if (%s)\n return resword;\n", comp_buffer);
- printf (" return 0;\n }\n");
- curr = temp;
- }
- else /* Nothing special required here. */
- {
- int i = 0;
- printf (" char *s;\n\n switch (key - %d)\n {\n",
- lowest_case_value);
-
- for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
- if (OPTION_ENABLED (option, LENTABLE))
- printf (" case %*d: if (len == %d) s = \"%s\"; else return 0; break;\n",
- field_width, temp->hash_value - lowest_case_value,
- temp->length, temp->key);
- else
- printf (" case %*d: s = \"%s\"; break;\n",
- field_width, temp->hash_value - lowest_case_value, temp->key);
-
- printf (" default: return 0;\n }\n ");
- printf ("return *s == *str && !%s;\n }\n",
- OPTION_ENABLED (option, COMP)
- ? "strncmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)");
- curr = temp;
- }
- }
- printf (" }\n }\n return 0;\n}\n");
-}
-
-/* Prints out a table of keyword lengths, for use with the
- comparison code in generated function ``in_word_set.'' */
-
-static void
-print_keylength_table ()
-{
- int max_column = 15;
- int index = 0;
- int column = 0;
- char *indent = OPTION_ENABLED (option, GLOBAL) ? "" : " ";
- LIST_NODE *temp;
-
- if (!OPTION_ENABLED (option, DUP) && !OPTION_ENABLED (option, SWITCH))
- {
- printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n ",
- indent, OPTION_ENABLED (option, CONST) ? "const " : "",
- key_list.max_key_len < MAX_UNSIGNED_CHAR ? "char" :
- (key_list.max_key_len < MAX_UNSIGNED_SHORT ? "short" : "long"),
- indent, indent);
-
- for (temp = key_list.head; temp; temp = temp->next, index++)
- {
-
- if (index < temp->hash_value)
- {
-
- for ( ; index < temp->hash_value; index++)
- printf ("%3d%s", 0, ++column % (max_column - 1) ? "," : ",\n ");
- }
-
- printf ("%3d%s", temp->length, ++column % (max_column - 1 ) ? "," : ",\n ");
- }
-
- printf ("\n%s%s};\n\n", indent, indent);
- }
-}
-
-/* Prints out the array containing the key words for the Perfect
- hash function. */
-
-static void
-print_keyword_table ()
-{
- char *l_brace = *key_list.head->rest ? "{" : "";
- char *r_brace = *key_list.head->rest ? "}," : "";
- int doing_switch = OPTION_ENABLED (option, SWITCH);
- char *indent = OPTION_ENABLED (option, GLOBAL) ? "" : " ";
- int index = 0;
- LIST_NODE *temp;
-
- printf ("\n%sstatic %s%s wordlist[] =\n%s%s{\n",
- indent, OPTION_ENABLED (option, CONST) ? "const " : "",
- key_list.struct_tag, indent, indent);
-
- /* Generate an array of reserved words at appropriate locations. */
-
- for (temp = key_list.head; temp; temp = temp->next, index++)
- {
- temp->index = index;
-
- if (!doing_switch && index < temp->hash_value)
- {
- int column;
-
- printf (" ");
-
- for (column = 1; index < temp->hash_value; index++, column++)
- printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n ");
-
- if (column % 10)
- printf ("\n");
- else
- {
- printf ("%s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
- continue;
- }
- }
-
- printf (" %s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
-
- /* Deal with links specially. */
- if (temp->link)
- {
- LIST_NODE *links;
-
- for (links = temp->link; links; links = links->link)
- {
- links->index = ++index;
- printf (" %s\"%s\", %s%s\n", l_brace, links->key, links->rest, r_brace);
- }
- }
-
- }
-
- printf ("%s%s};\n\n", indent, indent);
-}
-
-/* Generates C code for the hash function that returns the
- proper encoding for each key word. */
-
-static void
-print_hash_function (max_hash_value)
- int max_hash_value;
-{
- int max_column = 10;
- int count = max_hash_value;
-
- /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
-
- while ((count /= 10) > 0)
- field_width++;
-
- if (OPTION_ENABLED (option, GNU))
- printf ("#ifdef __GNUC__\ninline\n#endif\n");
-
- printf (OPTION_ENABLED (option, ANSI)
- ? "static int\n%s (register const char *str, register int len)\n{\n static %sunsigned %s hash_table[] =\n {"
- : "static int\n%s (str, len)\n register char *str;\n register unsigned int len;\n{\n static %sunsigned %s hash_table[] =\n {",
- GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "",
- max_hash_value < MAX_UNSIGNED_CHAR
- ? "char" : (max_hash_value < MAX_UNSIGNED_SHORT ? "short" : "int"));
-
- for (count = 0; count < ALPHABET_SIZE; ++count)
- {
- if (!(count % max_column))
- printf ("\n ");
-
- printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value);
- }
-
- /* Optimize special case of ``-k 1,$'' */
- if (OPTION_ENABLED (option, DEFAULTCHARS))
- printf ("\n };\n return %s + hash_table[str[len - 1]] + hash_table[str[0]];\n}\n\n",
- OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
- else
- {
- int key_pos;
-
- RESET (option);
-
- /* Get first (also highest) key position. */
- key_pos = GET (option);
-
- /* We can perform additional optimizations here. */
- if (!OPTION_ENABLED (option, ALLCHARS) && key_pos <= key_list.min_key_len)
- {
- printf ("\n };\n return %s", OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
-
- for ( ; key_pos != EOS && key_pos != WORD_END; key_pos = GET (option))
- printf (" + hash_table[str[%d]]", key_pos - 1);
-
- printf ("%s;\n}\n\n", key_pos == WORD_END ? " + hash_table[str[len - 1]]" : "");
- }
-
- /* We've got to use the correct, but brute force, technique. */
- else
- {
- printf ("\n };\n register int hval = %s;\n\n switch (%s)\n {\n default:\n",
- OPTION_ENABLED (option, NOLENGTH)
- ? "0" : "len", OPTION_ENABLED (option, NOLENGTH) ? "len" : "hval");
-
- /* User wants *all* characters considered in hash. */
- if (OPTION_ENABLED (option, ALLCHARS))
- {
- int i;
-
- for (i = key_list.max_key_len; i > 0; i--)
- printf (" case %d:\n hval += hash_table[str[%d]];\n", i, i - 1);
-
- printf (" }\n return hval;\n}\n\n");
- }
- else /* do the hard part... */
- {
- count = key_pos + 1;
-
- do
- {
-
- while (--count > key_pos)
- printf (" case %d:\n", count);
-
- printf (" case %d:\n hval += hash_table[str[%d]];\n",
- key_pos, key_pos - 1);
- }
- while ((key_pos = GET (option)) != EOS && key_pos != WORD_END);
-
- printf (" }\n return hval%s ;\n}\n\n", key_pos == WORD_END
- ? " + hash_table[str[len - 1]]" : "");
- }
- }
- }
-}
-
-/* Generates C code to perform the keyword lookup. */
-
-static void
-print_lookup_function ()
-{
- printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n\
- register int key = %s (str, len);\n\n\
- if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n {\n\
- register %schar *s = wordlist[key]",
- GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "");
- if (key_list.array_type != default_array_type)
- printf (".%s", GET_KEY_NAME (option));
-
- printf (";\n\n if (%s*s == *str && !%s)\n return %s",
- OPTION_ENABLED (option, LENTABLE) ? "len == lengthtable[key]\n && " : "",
- OPTION_ENABLED (option, COMP) ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
- OPTION_ENABLED (option, TYPE) && OPTION_ENABLED (option, POINTER) ? "&wordlist[key]" : "s");
- printf (";\n }\n }\n return 0;\n}\n");
-}
-
-/* Generates the hash function and the key word recognizer function
- based upon the user's Options. */
-
-void
-print_output ()
-{
- int global_table = OPTION_ENABLED (option, GLOBAL);
-
- printf ("%s\n", key_list.include_src);
-
- /* Potentially output type declaration now, reference it later on.... */
- if (OPTION_ENABLED (option, TYPE) && !OPTION_ENABLED (option, NOTYPE))
- printf ("%s;\n", key_list.array_type);
-
- print_hash_function (print_min_max ());
-
- if (global_table)
- if (OPTION_ENABLED (option, SWITCH))
- {
- if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
- print_keylength_table ();
- if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE))
- print_keyword_table ();
- }
- else
- {
- if (OPTION_ENABLED (option, LENTABLE))
- print_keylength_table ();
- print_keyword_table ();
- }
- /* Use the inline keyword to remove function overhead. */
- if (OPTION_ENABLED (option, GNU))
- printf ("#ifdef __GNUC__\ninline\n#endif\n");
-
- /* Use ANSI function prototypes. */
- printf (OPTION_ENABLED (option, ANSI)
- ? "%s%s\n%s (register const char *str, register int len)\n{\n"
- : "%s%s\n%s (str, len)\n register char *str;\n register unsigned int len;\n{\n",
- OPTION_ENABLED (option, CONST) ? "const " : "",
- key_list.return_type, GET_FUNCTION_NAME (option));
-
- /* Use the switch in place of lookup table. */
- if (OPTION_ENABLED (option, SWITCH))
- {
- if (!global_table)
- {
- if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
- print_keylength_table ();
- if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE))
- print_keyword_table ();
- }
- print_switch ();
- }
- else /* Use the lookup table, in place of switch. */
- {
- if (!global_table)
- {
- if (OPTION_ENABLED (option, LENTABLE))
- print_keylength_table ();
- print_keyword_table ();
- }
- print_lookup_function ();
- }
-
- if (key_list.additional_code)
- {
- int c;
-
- while ((c = getchar ()) != EOF)
- putchar (c);
- }
- fflush (stdout);
-}
-
-/* Sorts the keys by hash value. */
-
-void
-sort ()
-{
- key_list.hash_sort = TRUE;
- key_list.occurrence_sort = FALSE;
-
- key_list.head = merge_sort (key_list.head);
-}
-
-/* Dumps the key list to stderr stream. */
-
-static void
-dump ()
-{
- LIST_NODE *ptr;
-
- fprintf (stderr, "\nList contents are:\n(hash value, key length, index, key set, key):\n");
-
- for (ptr = key_list.head; ptr; ptr = ptr->next)
- fprintf (stderr, "%7d,%7d,%6d, %s, %s\n",
- ptr->hash_value, ptr->length, ptr->index,
- ptr->char_set, ptr->key);
-}
-
-/* Simple-minded constructor action here... */
-
-void
-key_list_init ()
-{
- key_list.total_keys = 1;
- key_list.max_key_len = NEG_MAX_INT;
- key_list.min_key_len = MAX_INT;
- key_list.return_type = default_return_type;
- key_list.array_type = key_list.struct_tag = default_array_type;
- key_list.head = NULL;
- key_list.additional_code = FALSE;
-}
-
-/* Returns the length of entire key list. */
-
-int
-keyword_list_length ()
-{
- return key_list.list_len;
-}
-
-/* Returns length of longest key read. */
-
-int
-max_key_length ()
-{
- return key_list.max_key_len;
-}
-
-/* DESTRUCTOR dumps diagnostics during debugging. */
-
-void
-key_list_destroy ()
-{
- if (OPTION_ENABLED (option, DEBUG))
- {
- fprintf (stderr, "\nDumping key list information:\ntotal unique keywords = %d\
-\ntotal keywords = %d\nmaximum key length = %d.\n",
- key_list.list_len, key_list.total_keys, key_list.max_key_len);
- dump ();
- fprintf (stderr, "End dumping list.\n\n");
- }
-}
-