diff options
Diffstat (limited to 'contrib/gperf/src/key-list.cc')
| -rw-r--r-- | contrib/gperf/src/key-list.cc | 2184 |
1 files changed, 0 insertions, 2184 deletions
diff --git a/contrib/gperf/src/key-list.cc b/contrib/gperf/src/key-list.cc deleted file mode 100644 index 1c941a4535796..0000000000000 --- a/contrib/gperf/src/key-list.cc +++ /dev/null @@ -1,2184 +0,0 @@ -/* Routines for building, ordering, and printing the keyword list. - Copyright (C) 1989-1998, 2000 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, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ - -#include <stdio.h> -#include <string.h> /* declares strncpy(), strchr() */ -#include <stdlib.h> /* declares malloc(), free(), abs(), exit(), abort() */ -#include <ctype.h> /* declares isprint() */ -#include <assert.h> /* defines assert() */ -#include <limits.h> /* defines SCHAR_MAX etc. */ -#include "options.h" -#include "read-line.h" -#include "hash-table.h" -#include "key-list.h" -#include "trace.h" -#include "version.h" - -/* Make the hash table 8 times larger than the number of keyword entries. */ -static const int TABLE_MULTIPLE = 10; - -/* 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))) - -int Key_List::determined[MAX_ALPHA_SIZE]; - -/* Destructor dumps diagnostics during debugging. */ - -Key_List::~Key_List (void) -{ - T (Trace t ("Key_List::~Key_List");) - if (option[DEBUG]) - { - fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d" - "\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n", - list_len, total_keys, total_duplicates, max_key_len); - dump (); - fprintf (stderr, "End dumping list.\n\n"); - } -} - -/* 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. */ - -const char * -Key_List::get_special_input (char delimiter) -{ - T (Trace t ("Key_List::get_special_input");) - int size = 80; - char *buf = new char[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 - buf[i++] = '%'; - } - else if (i >= size) /* Yikes, time to grow the buffer! */ - { - char *temp = new char[size *= 2]; - int j; - - for (j = 0; j < i; j++) - temp[j] = buf[j]; - - buf = temp; - } - buf[i] = c; - } - - return 0; /* Problem here. */ -} - -/* Stores any C text that must be included verbatim into the - generated code output. */ - -const char * -Key_List::save_include_src (void) -{ - T (Trace t ("Key_List::save_include_src");) - int c; - - if ((c = getchar ()) != '%') - ungetc (c, stdin); - else if ((c = getchar ()) != '{') - { - fprintf (stderr, "internal error, %c != '{' on line %d in file %s", c, __LINE__, __FILE__); - exit (1); - } - else - return get_special_input ('}'); - return ""; -} - -/* 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. */ - -const char * -Key_List::get_array_type (void) -{ - T (Trace t ("Key_List::get_array_type");) - 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, when GNU libc comes out I'll replace this...). */ - -#ifndef strcspn -inline int -Key_List::strcspn (const char *s, const char *reject) -{ - T (Trace t ("Key_List::strcspn");) - const char *scan; - const char *rej_scan; - int count = 0; - - for (scan = s; *scan; scan++) - { - - for (rej_scan = reject; *rej_scan; rej_scan++) - if (*scan == *rej_scan) - return count; - - count++; - } - - return count; -} -#endif - -/* Sets up the Return_Type, the Struct_Tag type and the Array_Type - based upon various user Options. */ - -void -Key_List::set_output_types (void) -{ - T (Trace t ("Key_List::set_output_types");) - if (option[TYPE]) - { - array_type = get_array_type (); - if (!array_type) - /* Something's wrong, but we'll catch it later on, in read_keys()... */ - return; - /* Yow, we've got a user-defined type... */ - int i = strcspn (array_type, "{\n\0"); - /* Remove trailing whitespace. */ - while (i > 0 && strchr (" \t", array_type[i-1])) - i--; - int struct_tag_length = i; - - /* Set `struct_tag' to a naked "struct something". */ - char *structtag = new char[struct_tag_length + 1]; - strncpy (structtag, array_type, struct_tag_length); - structtag[struct_tag_length] = '\0'; - struct_tag = structtag; - - /* The return type of the lookup function is "struct something *". - No "const" here, because if !option[CONST], some user code might want - to modify the structure. */ - char *rettype = new char[struct_tag_length + 3]; - strncpy (rettype, array_type, struct_tag_length); - rettype[struct_tag_length] = ' '; - rettype[struct_tag_length + 1] = '*'; - rettype[struct_tag_length + 2] = '\0'; - return_type = rettype; - } -} - -/* Extracts a key from an input line and creates a new List_Node for it. */ - -static List_Node * -parse_line (const char *line, const char *delimiters) -{ - if (*line == '"') - { - /* Parse a string in ANSI C syntax. */ - char *key = new char[strlen(line)]; - char *kp = key; - const char *lp = line + 1; - - for (; *lp;) - { - char c = *lp; - - if (c == '\0') - { - fprintf (stderr, "unterminated string: %s\n", line); - exit (1); - } - else if (c == '\\') - { - c = *++lp; - switch (c) - { - case '0': case '1': case '2': case '3': - case '4': case '5': case '6': case '7': - { - int code = 0; - int count = 0; - while (count < 3 && *lp >= '0' && *lp <= '7') - { - code = (code << 3) + (*lp - '0'); - lp++; - count++; - } - if (code > UCHAR_MAX) - fprintf (stderr, "octal escape out of range: %s\n", line); - *kp = (char) code; - break; - } - case 'x': - { - int code = 0; - int count = 0; - lp++; - while ((*lp >= '0' && *lp <= '9') - || (*lp >= 'A' && *lp <= 'F') - || (*lp >= 'a' && *lp <= 'f')) - { - code = (code << 4) - + (*lp >= 'A' && *lp <= 'F' ? *lp - 'A' + 10 : - *lp >= 'a' && *lp <= 'f' ? *lp - 'a' + 10 : - *lp - '0'); - lp++; - count++; - } - if (count == 0) - fprintf (stderr, "hexadecimal escape without any hex digits: %s\n", line); - if (code > UCHAR_MAX) - fprintf (stderr, "hexadecimal escape out of range: %s\n", line); - *kp = (char) code; - break; - } - case '\\': case '\'': case '"': - *kp = c; - lp++; - break; - case 'n': - *kp = '\n'; - lp++; - break; - case 't': - *kp = '\t'; - lp++; - break; - case 'r': - *kp = '\r'; - lp++; - break; - case 'f': - *kp = '\f'; - lp++; - break; - case 'b': - *kp = '\b'; - lp++; - break; - case 'a': - *kp = '\a'; - lp++; - break; - case 'v': - *kp = '\v'; - lp++; - break; - default: - fprintf (stderr, "invalid escape sequence in string: %s\n", line); - exit (1); - } - } - else if (c == '"') - break; - else - { - *kp = c; - lp++; - } - kp++; - } - lp++; - if (*lp != '\0') - { - if (strchr (delimiters, *lp) == NULL) - { - fprintf (stderr, "string not followed by delimiter: %s\n", line); - exit (1); - } - lp++; - } - return new List_Node (key, kp - key, option[TYPE] ? lp : ""); - } - else - { - /* Not a string. Look for the delimiter. */ - int len = strcspn (line, delimiters); - const char *rest; - - if (line[len] == '\0') - rest = ""; - else - /* Skip the first delimiter. */ - rest = &line[len + 1]; - return new List_Node (line, len, option[TYPE] ? rest : ""); - } -} - -/* 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 -Key_List::read_keys (void) -{ - T (Trace t ("Key_List::read_keys");) - char *ptr; - - include_src = save_include_src (); - set_output_types (); - - /* Oops, problem with the input file. */ - if (! (ptr = Read_Line::get_line ())) - { - fprintf (stderr, "No words in input file, did you forget to prepend %s or use -t accidentally?\n", "%%"); - exit (1); - } - - /* Read in all the keywords from the input file. */ - else - { - const char *delimiter = option.get_delimiter (); - List_Node *temp, *trail = 0; - - head = parse_line (ptr, delimiter); - - for (temp = head; - (ptr = Read_Line::get_line ()) && strcmp (ptr, "%%"); - temp = temp->next) - { - temp->next = parse_line (ptr, delimiter); - total_keys++; - } - - /* See if any additional C code is included at end of this file. */ - if (ptr) - additional_code = 1; - - /* Hash table this number of times larger than keyword number. */ - int table_size = (list_len = total_keys) * TABLE_MULTIPLE; - -#if LARGE_STACK_ARRAYS - /* 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[POW (table_size)]; -#else - // Note: we don't use new, because that invokes a custom operator new. - int malloc_size = POW (table_size) * sizeof(List_Node*); - if (malloc_size == 0) malloc_size = 1; - List_Node **table = (List_Node**)malloc(malloc_size); - if (table == NULL) - abort (); -#endif - - /* Make large hash table for efficiency. */ - Hash_Table found_link (table, table_size, option[NOLENGTH]); - - /* Test whether there are any links and also set the maximum length of - an identifier in the keyword list. */ - - for (temp = head; temp; temp = temp->next) - { - List_Node *ptr = found_link.insert (temp); - - /* 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) - { - total_duplicates++; - list_len--; - trail->next = temp->next; - temp->link = ptr->link; - ptr->link = temp; - - /* Complain if user hasn't enabled the duplicate option. */ - if (!option[DUP] || option[DEBUG]) - fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"%.*s\".\n", - temp->key_length, temp->key, - ptr->key_length, ptr->key, - temp->char_set_length, temp->char_set); - } - else - trail = temp; - - /* Update minimum and maximum keyword length, if needed. */ - if (max_key_len < temp->key_length) - max_key_len = temp->key_length; - if (min_key_len > temp->key_length) - min_key_len = temp->key_length; - } - -#if !LARGE_STACK_ARRAYS - free ((char *) table); -#endif - - /* Exit program if links exists and option[DUP] not set, since we can't continue */ - if (total_duplicates) - { - if (option[DUP]) - fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n", - total_duplicates); - else - { - fprintf (stderr, "%d input keys have identical hash values,\ntry different key positions or use option -D.\n", - total_duplicates); - exit (1); - } - } - /* Exit program if an empty string is used as key, since the comparison - expressions don't work correctly for looking up an empty string. */ - if (min_key_len == 0) - { - 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"); - exit (1); - } - if (option[ALLCHARS]) - option.set_keysig_size (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. */ - -List_Node * -Key_List::merge (List_Node *list1, List_Node *list2) -{ - T (Trace t ("Key_List::merge");) - List_Node *result; - List_Node **resultp = &result; - for (;;) - { - if (!list1) - { - *resultp = list2; - break; - } - if (!list2) - { - *resultp = list1; - break; - } - if (occurrence_sort && list1->occurrence < list2->occurrence - || hash_sort && list1->hash_value > list2->hash_value) - { - *resultp = list2; - resultp = &list2->next; list2 = list1; list1 = *resultp; - } - else - { - *resultp = list1; - resultp = &list1->next; list1 = *resultp; - } - } - return result; -} - -/* Applies the merge sort algorithm to recursively sort the key list by - frequency of occurrence of elements in the key set. */ - -List_Node * -Key_List::merge_sort (List_Node *head) -{ - T (Trace t ("Key_List::merge_sort");) - 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 = 0; - return merge (merge_sort (head), merge_sort (temp)); - } -} - -/* Returns the frequency of occurrence of elements in the key set. */ - -inline int -Key_List::get_occurrence (List_Node *ptr) -{ - T (Trace t ("Key_List::get_occurrence");) - int value = 0; - - const char *p = ptr->char_set; - unsigned int i = ptr->char_set_length; - for (; i > 0; p++, i--) - value += occurrences[(unsigned char)(*p)]; - - return value; -} - -/* Enables the index location of all key set elements that are now - determined. */ - -inline void -Key_List::set_determined (List_Node *ptr) -{ - T (Trace t ("Key_List::set_determined");) - - const char *p = ptr->char_set; - unsigned int i = ptr->char_set_length; - for (; i > 0; p++, i--) - determined[(unsigned char)(*p)] = 1; -} - -/* Returns TRUE if PTR's key set is already completely determined. */ - -inline int -Key_List::already_determined (List_Node *ptr) -{ - T (Trace t ("Key_List::already_determined");) - int is_determined = 1; - - const char *p = ptr->char_set; - unsigned int i = ptr->char_set_length; - for (; is_determined && i > 0; p++, i--) - is_determined = determined[(unsigned char)(*p)]; - - 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 -Key_List::reorder (void) -{ - T (Trace t ("Key_List::reorder");) - List_Node *ptr; - for (ptr = head; ptr; ptr = ptr->next) - ptr->occurrence = get_occurrence (ptr); - - hash_sort = 0; - occurrence_sort = 1; - - for (ptr = head = merge_sort (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; - } - } - } -} - -/* ============================ Output routines ============================ */ - -/* The "const " qualifier. */ -static const char *const_always; - -/* The "const " qualifier, for read-only arrays. */ -static const char *const_readonly_array; - -/* The "const " qualifier, for the array type. */ -static const char *const_for_struct; - -/* Returns the smallest unsigned C type capable of holding integers up to N. */ - -static const char * -smallest_integral_type (int n) -{ - if (n <= UCHAR_MAX) return "unsigned char"; - if (n <= USHRT_MAX) return "unsigned short"; - return "unsigned int"; -} - -/* Returns the smallest signed C type capable of holding integers - from MIN to MAX. */ - -static const char * -smallest_integral_type (int min, int max) -{ - if (option[ANSIC] | option[CPLUSPLUS]) - if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char"; - if (min >= SHRT_MIN && max <= SHRT_MAX) return "short"; - return "int"; -} - -/* A cast from `char' to a valid array index. */ -static const char *char_to_index; - -/* ------------------------------------------------------------------------- */ - -/* Computes the maximum and minimum hash values. Since the - list is already sorted by hash value all we need to do is - find the final item! */ - -void -Key_List::compute_min_max (void) -{ - T (Trace t ("Key_List::compute_min_max");) - List_Node *temp; - for (temp = head; temp->next; temp = temp->next) - ; - - min_hash_value = head->hash_value; - max_hash_value = temp->hash_value; -} - -/* ------------------------------------------------------------------------- */ - -/* Returns the number of different hash values. */ - -int -Key_List::num_hash_values (void) -{ - T (Trace t ("Key_List::num_hash_values");) - int count = 1; - List_Node *temp; - int value; - - for (temp = head, value = temp->hash_value; temp->next; ) - { - temp = temp->next; - if (value != temp->hash_value) - { - value = temp->hash_value; - count++; - } - } - return count; -} - -/* -------------------- Output_Constants and subclasses -------------------- */ - -/* This class outputs an enumeration defining some constants. */ - -struct Output_Constants -{ - virtual void output_start () = 0; - virtual void output_item (const char *name, int value) = 0; - virtual void output_end () = 0; - Output_Constants () {} - virtual ~Output_Constants () {} -}; - -/* This class outputs an enumeration in #define syntax. */ - -struct Output_Defines : public Output_Constants -{ - virtual void output_start (); - virtual void output_item (const char *name, int value); - virtual void output_end (); - Output_Defines () {} - virtual ~Output_Defines () {} -}; - -void Output_Defines::output_start () -{ - T (Trace t ("Output_Defines::output_start");) - printf ("\n"); -} - -void Output_Defines::output_item (const char *name, int value) -{ - T (Trace t ("Output_Defines::output_item");) - printf ("#define %s %d\n", name, value); -} - -void Output_Defines::output_end () -{ - T (Trace t ("Output_Defines::output_end");) -} - -/* This class outputs an enumeration using `enum'. */ - -struct Output_Enum : public Output_Constants -{ - virtual void output_start (); - virtual void output_item (const char *name, int value); - virtual void output_end (); - Output_Enum (const char *indent) : indentation (indent) {} - virtual ~Output_Enum () {} -private: - const char *indentation; - int pending_comma; -}; - -void Output_Enum::output_start () -{ - T (Trace t ("Output_Enum::output_start");) - printf ("%senum\n" - "%s {\n", - indentation, indentation); - pending_comma = 0; -} - -void Output_Enum::output_item (const char *name, int value) -{ - T (Trace t ("Output_Enum::output_item");) - if (pending_comma) - printf (",\n"); - printf ("%s %s = %d", indentation, name, value); - pending_comma = 1; -} - -void Output_Enum::output_end () -{ - T (Trace t ("Output_Enum::output_end");) - if (pending_comma) - printf ("\n"); - printf ("%s };\n\n", indentation); -} - -/* Outputs the maximum and minimum hash values etc. */ - -void -Key_List::output_constants (struct Output_Constants& style) -{ - T (Trace t ("Key_List::output_constants");) - - style.output_start (); - style.output_item ("TOTAL_KEYWORDS", total_keys); - style.output_item ("MIN_WORD_LENGTH", min_key_len); - style.output_item ("MAX_WORD_LENGTH", max_key_len); - style.output_item ("MIN_HASH_VALUE", min_hash_value); - style.output_item ("MAX_HASH_VALUE", max_hash_value); - style.output_end (); -} - -/* ------------------------------------------------------------------------- */ - -/* Outputs a keyword, as a string: enclosed in double quotes, escaping - backslashes, double quote and unprintable characters. */ - -static void -output_string (const char *key, int len) -{ - T (Trace t ("output_string");) - - putchar ('"'); - for (; len > 0; len--) - { - unsigned char c = (unsigned char) *key++; - if (isprint (c)) - { - if (c == '"' || c == '\\') - putchar ('\\'); - putchar (c); - } - else - { - /* Use octal escapes, not hexadecimal escapes, because some old - C compilers didn't understand hexadecimal escapes, and because - hexadecimal escapes are not limited to 2 digits, thus needing - special care if the following character happens to be a digit. */ - putchar ('\\'); - putchar ('0' + ((c >> 6) & 7)); - putchar ('0' + ((c >> 3) & 7)); - putchar ('0' + (c & 7)); - } - } - putchar ('"'); -} - -/* ------------------------------------------------------------------------- */ - -/* Outputs a type and a const specifier. - The output is terminated with a space. */ - -static void -output_const_type (const char *const_string, const char *type_string) -{ - if (type_string[strlen(type_string)-1] == '*') - printf ("%s %s", type_string, const_string); - else - printf ("%s%s ", const_string, type_string); -} - -/* ----------------------- Output_Expr and subclasses ----------------------- */ - -/* This class outputs a general expression. */ - -struct Output_Expr -{ - virtual void output_expr () const = 0; - Output_Expr () {} - virtual ~Output_Expr () {} -}; - -/* This class outputs an expression formed by a single string. */ - -struct Output_Expr1 : public Output_Expr -{ - virtual void output_expr () const; - Output_Expr1 (const char *piece1) : p1 (piece1) {} - virtual ~Output_Expr1 () {} -private: - const char *p1; -}; - -void Output_Expr1::output_expr () const -{ - T (Trace t ("Output_Expr1::output_expr");) - printf ("%s", p1); -} - -#if 0 /* unused */ - -/* This class outputs an expression formed by the concatenation of two - strings. */ - -struct Output_Expr2 : public Output_Expr -{ - virtual void output_expr () const; - Output_Expr2 (const char *piece1, const char *piece2) - : p1 (piece1), p2 (piece2) {} - virtual ~Output_Expr2 () {} -private: - const char *p1; - const char *p2; -}; - -void Output_Expr2::output_expr () const -{ - T (Trace t ("Output_Expr2::output_expr");) - printf ("%s%s", p1, p2); -} - -#endif - -/* --------------------- Output_Compare and subclasses --------------------- */ - -/* This class outputs a comparison expression. */ - -struct Output_Compare -{ - virtual void output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const = 0; - Output_Compare () {} - virtual ~Output_Compare () {} -}; - -/* This class outputs a comparison using strcmp. */ - -struct Output_Compare_Strcmp : public Output_Compare -{ - virtual void output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const; - Output_Compare_Strcmp () {} - virtual ~Output_Compare_Strcmp () {} -}; - -void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const -{ - T (Trace t ("Output_Compare_Strcmp::output_comparison");) - printf ("*"); - expr1.output_expr (); - printf (" == *"); - expr2.output_expr (); - printf (" && !strcmp ("); - expr1.output_expr (); - printf (" + 1, "); - expr2.output_expr (); - printf (" + 1)"); -} - -/* This class outputs a comparison using strncmp. - Note that the length of expr1 will be available through the local variable - `len'. */ - -struct Output_Compare_Strncmp : public Output_Compare -{ - virtual void output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const; - Output_Compare_Strncmp () {} - virtual ~Output_Compare_Strncmp () {} -}; - -void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const -{ - T (Trace t ("Output_Compare_Strncmp::output_comparison");) - printf ("*"); - expr1.output_expr (); - printf (" == *"); - expr2.output_expr (); - printf (" && !strncmp ("); - expr1.output_expr (); - printf (" + 1, "); - expr2.output_expr (); - printf (" + 1, len - 1) && "); - expr2.output_expr (); - printf ("[len] == '\\0'"); -} - -/* This class outputs a comparison using memcmp. - Note that the length of expr1 (available through the local variable `len') - must be verified to be equal to the length of expr2 prior to this - comparison. */ - -struct Output_Compare_Memcmp : public Output_Compare -{ - virtual void output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const; - Output_Compare_Memcmp () {} - virtual ~Output_Compare_Memcmp () {} -}; - -void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1, - const Output_Expr& expr2) const -{ - T (Trace t ("Output_Compare_Memcmp::output_comparison");) - printf ("*"); - expr1.output_expr (); - printf (" == *"); - expr2.output_expr (); - printf (" && !memcmp ("); - expr1.output_expr (); - printf (" + 1, "); - expr2.output_expr (); - printf (" + 1, len - 1)"); -} - -/* ------------------------------------------------------------------------- */ - -/* Generates C code for the hash function that returns the - proper encoding for each key word. */ - -void -Key_List::output_hash_function (void) -{ - T (Trace t ("Key_List::output_hash_function");) - const int max_column = 10; - int field_width; - - /* Calculate maximum number of digits required for MAX_HASH_VALUE. */ - field_width = 2; - for (int trunc = max_hash_value; (trunc /= 10) > 0;) - field_width++; - - /* Output the function's head. */ - if (option[CPLUSPLUS]) - printf ("inline "); - else if (option[KRC] | option[C] | option[ANSIC]) - printf ("#ifdef __GNUC__\n" - "__inline\n" - "#else\n" - "#ifdef __cplusplus\n" - "inline\n" - "#endif\n" - "#endif\n"); - - if (option[KRC] | option[C] | option[ANSIC]) - printf ("static "); - printf ("unsigned int\n"); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - printf ("%s ", option.get_hash_name ()); - printf (option[KRC] ? - "(str, len)\n" - " register char *str;\n" - " register unsigned int len;\n" : - option[C] ? - "(str, len)\n" - " register const char *str;\n" - " register unsigned int len;\n" : - option[ANSIC] | option[CPLUSPLUS] ? - "(register const char *str, register unsigned int len)\n" : - ""); - - /* Note that when the hash function is called, it has already been verified - that min_key_len <= len <= max_key_len. */ - - /* Output the function's body. */ - printf ("{\n"); - - /* First the asso_values array. */ - printf (" static %s%s asso_values[] =\n" - " {", - const_readonly_array, - smallest_integral_type (max_hash_value + 1)); - - for (int count = 0; count < ALPHA_SIZE; count++) - { - if (count > 0) - printf (","); - if (!(count % max_column)) - printf ("\n "); - printf ("%*d", field_width, - occurrences[count] ? asso_values[count] : max_hash_value + 1); - } - - printf ("\n" - " };\n"); - - /* Optimize special case of ``-k 1,$'' */ - if (option[DEFAULTCHARS]) - printf (" return %sasso_values[%sstr[len - 1]] + asso_values[%sstr[0]];\n", - option[NOLENGTH] ? "" : "len + ", - char_to_index, char_to_index); - else - { - int key_pos; - - option.reset (); - - /* Get first (also highest) key position. */ - key_pos = option.get (); - - if (!option[ALLCHARS] && (key_pos == WORD_END || key_pos <= min_key_len)) - { - /* We can perform additional optimizations here: - Write it out as a single expression. Note that the values - are added as `int's even though the asso_values array may - contain `unsigned char's or `unsigned short's. */ - - printf (" return %s", - option[NOLENGTH] ? "" : "len + "); - - for (; key_pos != WORD_END; ) - { - printf ("asso_values[%sstr[%d]]", char_to_index, key_pos - 1); - if ((key_pos = option.get ()) != EOS) - printf (" + "); - else - break; - } - - if (key_pos == WORD_END) - printf ("asso_values[%sstr[len - 1]]", char_to_index); - - printf (";\n"); - } - else - { - /* We've got to use the correct, but brute force, technique. */ - printf (" register int hval = %s;\n\n" - " switch (%s)\n" - " {\n" - " default:\n", - option[NOLENGTH] ? "0" : "len", - option[NOLENGTH] ? "len" : "hval"); - - /* User wants *all* characters considered in hash. */ - if (option[ALLCHARS]) - { - for (int i = max_key_len; i > 0; i--) - printf (" case %d:\n" - " hval += asso_values[%sstr[%d]];\n", - i, char_to_index, i - 1); - - printf (" break;\n" - " }\n" - " return hval;\n"); - } - else /* do the hard part... */ - { - while (key_pos != WORD_END && key_pos > max_key_len) - if ((key_pos = option.get ()) == EOS) - break; - - if (key_pos != EOS && key_pos != WORD_END) - { - int i = key_pos; - do - { - for ( ; i >= key_pos; i--) - printf (" case %d:\n", i); - - printf (" hval += asso_values[%sstr[%d]];\n", - char_to_index, key_pos - 1); - - key_pos = option.get (); - } - while (key_pos != EOS && key_pos != WORD_END); - - for ( ; i >= min_key_len; i--) - printf (" case %d:\n", i); - } - - printf (" break;\n" - " }\n" - " return hval"); - if (key_pos == WORD_END) - printf (" + asso_values[%sstr[len - 1]]", char_to_index); - printf (";\n"); - } - } - } - printf ("}\n\n"); -} - -/* ------------------------------------------------------------------------- */ - -/* Prints out a table of keyword lengths, for use with the - comparison code in generated function ``in_word_set''. */ - -void -Key_List::output_keylength_table (void) -{ - T (Trace t ("Key_List::output_keylength_table");) - const int columns = 14; - int index; - int column; - const char *indent = option[GLOBAL] ? "" : " "; - List_Node *temp; - - printf ("%sstatic %s%s lengthtable[] =\n%s {", - indent, const_readonly_array, - smallest_integral_type (max_key_len), - indent); - - /* Generate an array of lengths, similar to output_keyword_table. */ - - column = 0; - for (temp = head, index = 0; temp; temp = temp->next) - { - if (option[SWITCH] && !option[TYPE] - && !(temp->link - || (temp->next && temp->hash_value == temp->next->hash_value))) - continue; - - if (index < temp->hash_value && !option[SWITCH] && !option[DUP]) - { - /* Some blank entries. */ - for ( ; index < temp->hash_value; index++) - { - if (index > 0) - printf (","); - if ((column++ % columns) == 0) - printf ("\n%s ", indent); - printf ("%3d", 0); - } - } - - if (index > 0) - printf (","); - if ((column++ % columns) == 0) - printf("\n%s ", indent); - printf ("%3d", temp->key_length); - - /* Deal with links specially. */ - if (temp->link) // implies option[DUP] - for (List_Node *links = temp->link; links; links = links->link) - { - ++index; - printf (","); - if ((column++ % columns) == 0) - printf("\n%s ", indent); - printf ("%3d", links->key_length); - } - - index++; - } - - printf ("\n%s };\n", indent); - if (option[GLOBAL]) - printf ("\n"); -} - -/* ------------------------------------------------------------------------- */ - -static void -output_keyword_entry (List_Node *temp, const char *indent) -{ - printf ("%s ", indent); - if (option[TYPE]) - printf ("{"); - output_string (temp->key, temp->key_length); - if (option[TYPE]) - { - if (strlen (temp->rest) > 0) - printf (",%s", temp->rest); - printf ("}"); - } - if (option[DEBUG]) - printf (" /* hash value = %d, index = %d */", - temp->hash_value, temp->index); -} - -static void -output_keyword_blank_entries (int count, const char *indent) -{ - int columns; - if (option[TYPE]) - { - columns = 58 / (6 + strlen (option.get_initializer_suffix())); - if (columns == 0) - columns = 1; - } - else - { - columns = 9; - } - int column = 0; - for (int i = 0; i < count; i++) - { - if ((column % columns) == 0) - { - if (i > 0) - printf (",\n"); - printf ("%s ", indent); - } - else - { - if (i > 0) - printf (", "); - } - if (option[TYPE]) - printf ("{\"\"%s}", option.get_initializer_suffix()); - else - printf ("\"\""); - column++; - } -} - -/* Prints out the array containing the key words for the hash function. */ - -void -Key_List::output_keyword_table (void) -{ - T (Trace t ("Key_List::output_keyword_table");) - const char *indent = option[GLOBAL] ? "" : " "; - int index; - List_Node *temp; - - printf ("%sstatic ", - indent); - output_const_type (const_readonly_array, struct_tag); - printf ("%s[] =\n" - "%s {\n", - option.get_wordlist_name (), - indent); - - /* Generate an array of reserved words at appropriate locations. */ - - for (temp = head, index = 0; temp; temp = temp->next) - { - if (option[SWITCH] && !option[TYPE] - && !(temp->link - || (temp->next && temp->hash_value == temp->next->hash_value))) - continue; - - if (index > 0) - printf (",\n"); - - if (index < temp->hash_value && !option[SWITCH] && !option[DUP]) - { - /* Some blank entries. */ - output_keyword_blank_entries (temp->hash_value - index, indent); - printf (",\n"); - index = temp->hash_value; - } - - temp->index = index; - - output_keyword_entry (temp, indent); - - /* Deal with links specially. */ - if (temp->link) // implies option[DUP] - for (List_Node *links = temp->link; links; links = links->link) - { - links->index = ++index; - printf (",\n"); - output_keyword_entry (links, indent); - } - - index++; - } - if (index > 0) - printf ("\n"); - - printf ("%s };\n\n", indent); -} - -/* ------------------------------------------------------------------------- */ - -/* Generates the large, sparse table that maps hash values into - the smaller, contiguous range of the keyword table. */ - -void -Key_List::output_lookup_array (void) -{ - T (Trace t ("Key_List::output_lookup_array");) - if (option[DUP]) - { - const int DEFAULT_VALUE = -1; - - /* Because of the way output_keyword_table works, every duplicate set is - stored contiguously in the wordlist array. */ - struct duplicate_entry - { - int hash_value; /* Hash value for this particular duplicate set. */ - int index; /* Index into the main keyword storage array. */ - int count; /* Number of consecutive duplicates at this index. */ - }; - -#if LARGE_STACK_ARRAYS - duplicate_entry duplicates[total_duplicates]; - int lookup_array[max_hash_value + 1 + 2*total_duplicates]; -#else - // Note: we don't use new, because that invokes a custom operator new. - duplicate_entry *duplicates = (duplicate_entry *) - malloc (total_duplicates * sizeof(duplicate_entry) + 1); - int *lookup_array = (int *) - malloc ((max_hash_value + 1 + 2*total_duplicates) * sizeof(int)); - if (duplicates == NULL || lookup_array == NULL) - abort(); -#endif - int lookup_array_size = max_hash_value + 1; - duplicate_entry *dup_ptr = &duplicates[0]; - int *lookup_ptr = &lookup_array[max_hash_value + 1 + 2*total_duplicates]; - - while (lookup_ptr > lookup_array) - *--lookup_ptr = DEFAULT_VALUE; - - /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */ - - for (List_Node *temp = head; temp; temp = temp->next) - { - int hash_value = temp->hash_value; - lookup_array[hash_value] = temp->index; - if (option[DEBUG]) - fprintf (stderr, "keyword = %.*s, index = %d\n", - temp->key_length, temp->key, temp->index); - if (temp->link - || (temp->next && hash_value == temp->next->hash_value)) - { - /* Start a duplicate entry. */ - dup_ptr->hash_value = hash_value; - dup_ptr->index = temp->index; - dup_ptr->count = 1; - - for (;;) - { - for (List_Node *ptr = temp->link; ptr; ptr = ptr->link) - { - dup_ptr->count++; - if (option[DEBUG]) - fprintf (stderr, - "static linked keyword = %.*s, index = %d\n", - ptr->key_length, ptr->key, ptr->index); - } - - if (!(temp->next && hash_value == temp->next->hash_value)) - break; - - temp = temp->next; - - dup_ptr->count++; - if (option[DEBUG]) - fprintf (stderr, "dynamic linked keyword = %.*s, index = %d\n", - temp->key_length, temp->key, temp->index); - } - assert (dup_ptr->count >= 2); - dup_ptr++; - } - } - - while (dup_ptr > duplicates) - { - dup_ptr--; - - if (option[DEBUG]) - fprintf (stderr, - "dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n", - dup_ptr - duplicates, - dup_ptr->hash_value, dup_ptr->index, dup_ptr->count); - - int i; - /* Start searching for available space towards the right part - of the lookup array. */ - for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++) - if (lookup_array[i] == DEFAULT_VALUE - && lookup_array[i + 1] == DEFAULT_VALUE) - goto found_i; - /* If we didn't find it to the right look to the left instead... */ - for (i = dup_ptr->hash_value-1; i >= 0; i--) - if (lookup_array[i] == DEFAULT_VALUE - && lookup_array[i + 1] == DEFAULT_VALUE) - goto found_i; - /* Append to the end of lookup_array. */ - i = lookup_array_size; - lookup_array_size += 2; - found_i: - /* Put in an indirection from dup_ptr->hash_value to i. - At i and i+1 store dup_ptr->index and dup_ptr->count. */ - assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index); - lookup_array[dup_ptr->hash_value] = - 1 - total_keys - i; - lookup_array[i] = - total_keys + dup_ptr->index; - lookup_array[i + 1] = - dup_ptr->count; - /* All these three values are <= -2, distinct from DEFAULT_VALUE. */ - } - - /* The values of the lookup array are now known. */ - - int min = INT_MAX; - int max = INT_MIN; - lookup_ptr = lookup_array + lookup_array_size; - while (lookup_ptr > lookup_array) - { - int val = *--lookup_ptr; - if (min > val) - min = val; - if (max < val) - max = val; - } - - const char *indent = option[GLOBAL] ? "" : " "; - printf ("%sstatic %s%s lookup[] =\n" - "%s {", - indent, const_readonly_array, smallest_integral_type (min, max), - indent); - - int field_width; - /* Calculate maximum number of digits required for MIN..MAX. */ - { - field_width = 2; - for (int trunc = max; (trunc /= 10) > 0;) - field_width++; - } - if (min < 0) - { - int neg_field_width = 2; - for (int trunc = -min; (trunc /= 10) > 0;) - neg_field_width++; - neg_field_width++; /* account for the minus sign */ - if (field_width < neg_field_width) - field_width = neg_field_width; - } - - const int columns = 42 / field_width; - int column; - - column = 0; - for (int i = 0; i < lookup_array_size; i++) - { - if (i > 0) - printf (","); - if ((column++ % columns) == 0) - printf("\n%s ", indent); - printf ("%*d", field_width, lookup_array[i]); - } - printf ("\n%s };\n\n", indent); - -#if !LARGE_STACK_ARRAYS - free ((char *) duplicates); - free ((char *) lookup_array); -#endif - } -} - -/* ------------------------------------------------------------------------- */ - -/* Generate all the tables needed for the lookup function. */ - -void -Key_List::output_lookup_tables (void) -{ - T (Trace t ("Key_List::output_lookup_tables");) - - if (option[SWITCH]) - { - /* Use the switch in place of lookup table. */ - if (option[LENTABLE] && (option[DUP] && total_duplicates > 0)) - output_keylength_table (); - if (option[TYPE] || (option[DUP] && total_duplicates > 0)) - output_keyword_table (); - } - else - { - /* Use the lookup table, in place of switch. */ - if (option[LENTABLE]) - output_keylength_table (); - output_keyword_table (); - output_lookup_array (); - } -} - -/* ------------------------------------------------------------------------- */ - -/* Output a single switch case (including duplicates). Advance list. */ - -static List_Node * -output_switch_case (List_Node *list, int indent, int *jumps_away) -{ - T (Trace t ("output_switch_case");) - - if (option[DEBUG]) - printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n", - indent, "", list->hash_value, list->key_length, list->key); - - if (option[DUP] - && (list->link - || (list->next && list->hash_value == list->next->hash_value))) - { - if (option[LENTABLE]) - printf ("%*slengthptr = &lengthtable[%d];\n", - indent, "", list->index); - printf ("%*swordptr = &%s[%d];\n", - indent, "", option.get_wordlist_name (), list->index); - - int count = 0; - for (List_Node *temp = list; ; temp = temp->next) - { - for (List_Node *links = temp; links; links = links->link) - count++; - if (!(temp->next && temp->hash_value == temp->next->hash_value)) - break; - } - - printf ("%*swordendptr = wordptr + %d;\n" - "%*sgoto multicompare;\n", - indent, "", count, - indent, ""); - *jumps_away = 1; - } - else - { - if (option[LENTABLE]) - { - printf ("%*sif (len == %d)\n" - "%*s {\n", - indent, "", list->key_length, - indent, ""); - indent += 4; - } - printf ("%*sresword = ", - indent, ""); - if (option[TYPE]) - printf ("&%s[%d]", option.get_wordlist_name (), list->index); - else - output_string (list->key, list->key_length); - printf (";\n"); - printf ("%*sgoto compare;\n", - indent, ""); - if (option[LENTABLE]) - { - indent -= 4; - printf ("%*s }\n", - indent, ""); - } - else - *jumps_away = 1; - } - - while (list->next && list->hash_value == list->next->hash_value) - list = list->next; - list = list->next; - return list; -} - -/* Output a total of size cases, grouped into num_switches switch statements, - where 0 < num_switches <= size. */ - -static void -output_switches (List_Node *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent) -{ - T (Trace t ("output_switches");) - - if (option[DEBUG]) - printf ("%*s/* know %d <= key <= %d, contains %d cases */\n", - indent, "", min_hash_value, max_hash_value, size); - - if (num_switches > 1) - { - int part1 = num_switches / 2; - int part2 = num_switches - part1; - int size1 = (int)((double)size / (double)num_switches * (double)part1 + 0.5); - int size2 = size - size1; - - List_Node *temp = list; - for (int count = size1; count > 0; count--) - { - while (temp->hash_value == temp->next->hash_value) - temp = temp->next; - temp = temp->next; - } - - printf ("%*sif (key < %d)\n" - "%*s {\n", - indent, "", temp->hash_value, - indent, ""); - - output_switches (list, part1, size1, min_hash_value, temp->hash_value-1, indent+4); - - printf ("%*s }\n" - "%*selse\n" - "%*s {\n", - indent, "", indent, "", indent, ""); - - output_switches (temp, part2, size2, temp->hash_value, max_hash_value, indent+4); - - printf ("%*s }\n", - indent, ""); - } - else - { - /* Output a single switch. */ - int lowest_case_value = list->hash_value; - if (size == 1) - { - int jumps_away = 0; - assert (min_hash_value <= lowest_case_value); - assert (lowest_case_value <= max_hash_value); - if (min_hash_value == max_hash_value) - output_switch_case (list, indent, &jumps_away); - else - { - printf ("%*sif (key == %d)\n" - "%*s {\n", - indent, "", lowest_case_value, - indent, ""); - output_switch_case (list, indent+4, &jumps_away); - printf ("%*s }\n", - indent, ""); - } - } - else - { - if (lowest_case_value == 0) - printf ("%*sswitch (key)\n", indent, ""); - else - printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value); - printf ("%*s {\n", - indent, ""); - for (; size > 0; size--) - { - int jumps_away = 0; - printf ("%*s case %d:\n", - indent, "", list->hash_value - lowest_case_value); - list = output_switch_case (list, indent+6, &jumps_away); - if (!jumps_away) - printf ("%*s break;\n", - indent, ""); - } - printf ("%*s }\n", - indent, ""); - } - } -} - -/* Generates C code to perform the keyword lookup. */ - -void -Key_List::output_lookup_function_body (const Output_Compare& comparison) -{ - T (Trace t ("Key_List::output_lookup_function_body");) - - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n" - " {\n" - " register int key = %s (str, len);\n\n", - option.get_hash_name ()); - - if (option[SWITCH]) - { - int switch_size = num_hash_values (); - int num_switches = option.get_total_switches (); - if (num_switches > switch_size) - num_switches = switch_size; - - printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n" - " {\n"); - if (option[DUP]) - { - if (option[LENTABLE]) - printf (" register %s%s *lengthptr;\n", - const_always, smallest_integral_type (max_key_len)); - printf (" register "); - output_const_type (const_readonly_array, struct_tag); - printf ("*wordptr;\n"); - printf (" register "); - output_const_type (const_readonly_array, struct_tag); - printf ("*wordendptr;\n"); - } - if (option[TYPE]) - { - printf (" register "); - output_const_type (const_readonly_array, struct_tag); - printf ("*resword;\n\n"); - } - else - printf (" register %sresword;\n\n", - struct_tag); - - output_switches (head, num_switches, switch_size, min_hash_value, max_hash_value, 10); - - if (option[DUP]) - { - int indent = 8; - printf ("%*s return 0;\n" - "%*smulticompare:\n" - "%*s while (wordptr < wordendptr)\n" - "%*s {\n", - indent, "", indent, "", indent, "", indent, ""); - if (option[LENTABLE]) - { - printf ("%*s if (len == *lengthptr)\n" - "%*s {\n", - indent, "", indent, ""); - indent += 4; - } - printf ("%*s register %schar *s = ", - indent, "", const_always); - if (option[TYPE]) - printf ("wordptr->%s", option.get_key_name ()); - else - printf ("*wordptr"); - printf (";\n\n" - "%*s if (", - indent, ""); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); - printf (")\n" - "%*s return %s;\n", - indent, "", - option[TYPE] ? "wordptr" : "s"); - if (option[LENTABLE]) - { - indent -= 4; - printf ("%*s }\n", - indent, ""); - } - if (option[LENTABLE]) - printf ("%*s lengthptr++;\n", - indent, ""); - printf ("%*s wordptr++;\n" - "%*s }\n", - indent, "", indent, ""); - } - printf (" return 0;\n" - " compare:\n"); - if (option[TYPE]) - { - printf (" {\n" - " register %schar *s = resword->%s;\n\n" - " if (", - const_always, option.get_key_name ()); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); - printf (")\n" - " return resword;\n" - " }\n"); - } - else - { - printf (" if ("); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword")); - printf (")\n" - " return resword;\n"); - } - printf (" }\n"); - } - else - { - printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n"); - - if (option[DUP]) - { - int indent = 8; - printf ("%*s{\n" - "%*s register int index = lookup[key];\n\n" - "%*s if (index >= 0)\n", - indent, "", indent, "", indent, ""); - if (option[LENTABLE]) - { - printf ("%*s {\n" - "%*s if (len == lengthtable[index])\n", - indent, "", indent, ""); - indent += 4; - } - printf ("%*s {\n" - "%*s register %schar *s = %s[index]", - indent, "", - indent, "", const_always, option.get_wordlist_name ()); - if (option[TYPE]) - printf (".%s", option.get_key_name ()); - printf (";\n\n" - "%*s if (", - indent, ""); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); - printf (")\n" - "%*s return ", - indent, ""); - if (option[TYPE]) - printf ("&%s[index]", option.get_wordlist_name ()); - else - printf ("s"); - printf (";\n" - "%*s }\n", - indent, ""); - if (option[LENTABLE]) - { - indent -= 4; - printf ("%*s }\n", indent, ""); - } - if (total_duplicates > 0) - { - printf ("%*s else if (index < -TOTAL_KEYWORDS)\n" - "%*s {\n" - "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n", - indent, "", indent, "", indent, ""); - if (option[LENTABLE]) - printf ("%*s register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n", - indent, "", const_always, smallest_integral_type (max_key_len)); - printf ("%*s register ", - indent, ""); - output_const_type (const_readonly_array, struct_tag); - printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n", - option.get_wordlist_name ()); - printf ("%*s register ", - indent, ""); - output_const_type (const_readonly_array, struct_tag); - printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n"); - printf ("%*s while (wordptr < wordendptr)\n" - "%*s {\n", - indent, "", indent, ""); - if (option[LENTABLE]) - { - printf ("%*s if (len == *lengthptr)\n" - "%*s {\n", - indent, "", indent, ""); - indent += 4; - } - printf ("%*s register %schar *s = ", - indent, "", const_always); - if (option[TYPE]) - printf ("wordptr->%s", option.get_key_name ()); - else - printf ("*wordptr"); - printf (";\n\n" - "%*s if (", - indent, ""); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); - printf (")\n" - "%*s return %s;\n", - indent, "", - option[TYPE] ? "wordptr" : "s"); - if (option[LENTABLE]) - { - indent -= 4; - printf ("%*s }\n", - indent, ""); - } - if (option[LENTABLE]) - printf ("%*s lengthptr++;\n", - indent, ""); - printf ("%*s wordptr++;\n" - "%*s }\n" - "%*s }\n", - indent, "", indent, "", indent, ""); - } - printf ("%*s}\n", - indent, ""); - } - else - { - int indent = 8; - if (option[LENTABLE]) - { - printf ("%*sif (len == lengthtable[key])\n", - indent, ""); - indent += 2; - } - - printf ("%*s{\n" - "%*s register %schar *s = %s[key]", - indent, "", - indent, "", const_always, option.get_wordlist_name ()); - - if (option[TYPE]) - printf (".%s", option.get_key_name ()); - - printf (";\n\n" - "%*s if (", - indent, ""); - comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s")); - printf (")\n" - "%*s return ", - indent, ""); - if (option[TYPE]) - printf ("&%s[key]", option.get_wordlist_name ()); - else - printf ("s"); - printf (";\n" - "%*s}\n", - indent, ""); - } - } - printf (" }\n" - " return 0;\n"); -} - -/* Generates C code for the lookup function. */ - -void -Key_List::output_lookup_function (void) -{ - T (Trace t ("Key_List::output_lookup_function");) - - /* Output the function's head. */ - if (option[KRC] | option[C] | option[ANSIC]) - printf ("#ifdef __GNUC__\n" - "__inline\n" - "#endif\n"); - - printf ("%s%s\n", - const_for_struct, return_type); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - printf ("%s ", option.get_function_name ()); - printf (option[KRC] ? - "(str, len)\n" - " register char *str;\n" - " register unsigned int len;\n" : - option[C] ? - "(str, len)\n" - " register const char *str;\n" - " register unsigned int len;\n" : - option[ANSIC] | option[CPLUSPLUS] ? - "(register const char *str, register unsigned int len)\n" : - ""); - - /* Output the function's body. */ - printf ("{\n"); - - if (option[ENUM] && !option[GLOBAL]) - { - Output_Enum style (" "); - output_constants (style); - } - - if (!option[GLOBAL]) - output_lookup_tables (); - - if (option[LENTABLE]) - output_lookup_function_body (Output_Compare_Memcmp ()); - else - { - if (option[COMP]) - output_lookup_function_body (Output_Compare_Strncmp ()); - else - output_lookup_function_body (Output_Compare_Strcmp ()); - } - - printf ("}\n"); -} - -/* ------------------------------------------------------------------------- */ - -/* Generates the hash function and the key word recognizer function - based upon the user's Options. */ - -void -Key_List::output (void) -{ - T (Trace t ("Key_List::output");) - - compute_min_max (); - - if (option[C] | option[ANSIC] | option[CPLUSPLUS]) - { - const_always = "const "; - const_readonly_array = (option[CONST] ? "const " : ""); - const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : ""); - } - else - { - const_always = ""; - const_readonly_array = ""; - const_for_struct = ""; - } - - if (!option[TYPE]) - { - return_type = (const_always[0] ? "const char *" : "char *"); - struct_tag = (const_always[0] ? "const char *" : "char *"); - } - - char_to_index = (option[SEVENBIT] ? "" : "(unsigned char)"); - - printf ("/* "); - if (option[KRC]) - printf ("KR-C"); - else if (option[C]) - printf ("C"); - else if (option[ANSIC]) - printf ("ANSI-C"); - else if (option[CPLUSPLUS]) - printf ("C++"); - printf (" code produced by gperf version %s */\n", version_string); - Options::print_options (); - - printf ("%s\n", include_src); - - if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */ - printf ("%s;\n", array_type); - - if (option[INCLUDE]) - printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */ - - if (!option[ENUM]) - { - Output_Defines style; - output_constants (style); - } - else if (option[GLOBAL]) - { - Output_Enum style (""); - output_constants (style); - } - - printf ("/* maximum key range = %d, duplicates = %d */\n\n", - max_hash_value - min_hash_value + 1, total_duplicates); - - if (option[CPLUSPLUS]) - printf ("class %s\n" - "{\n" - "private:\n" - " static inline unsigned int %s (const char *str, unsigned int len);\n" - "public:\n" - " static %s%s%s (const char *str, unsigned int len);\n" - "};\n" - "\n", - option.get_class_name (), option.get_hash_name (), - const_for_struct, return_type, option.get_function_name ()); - - output_hash_function (); - - if (option[GLOBAL]) - output_lookup_tables (); - - output_lookup_function (); - - if (additional_code) - for (int c; (c = getchar ()) != EOF; putchar (c)) - ; - - fflush (stdout); -} - -/* ========================= End of Output routines ========================= */ - -/* Sorts the keys by hash value. */ - -void -Key_List::sort (void) -{ - T (Trace t ("Key_List::sort");) - hash_sort = 1; - occurrence_sort = 0; - - head = merge_sort (head); -} - -/* Dumps the key list to stderr stream. */ - -void -Key_List::dump () -{ - T (Trace t ("Key_List::dump");) - int field_width = option.get_max_keysig_size (); - - fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n", - field_width, "char_set"); - - for (List_Node *ptr = head; ptr; ptr = ptr->next) - fprintf (stderr, "%11d,%11d,%6d, %*.*s, %.*s\n", - ptr->hash_value, ptr->key_length, ptr->index, - field_width, ptr->char_set_length, ptr->char_set, - ptr->key_length, ptr->key); -} - -/* Simple-minded constructor action here... */ - -Key_List::Key_List (void) -{ - T (Trace t ("Key_List::Key_List");) - total_keys = 1; - max_key_len = INT_MIN; - min_key_len = INT_MAX; - array_type = 0; - return_type = 0; - struct_tag = 0; - head = 0; - total_duplicates = 0; - additional_code = 0; -} - -/* Returns the length of entire key list. */ - -int -Key_List::keyword_list_length (void) -{ - T (Trace t ("Key_List::keyword_list_length");) - return list_len; -} - -/* Returns length of longest key read. */ - -int -Key_List::max_key_length (void) -{ - T (Trace t ("Key_List::max_key_length");) - return max_key_len; -} - |