diff options
Diffstat (limited to 'apps/gperf/src/Key_List.cpp')
| -rw-r--r-- | apps/gperf/src/Key_List.cpp | 1345 |
1 files changed, 0 insertions, 1345 deletions
diff --git a/apps/gperf/src/Key_List.cpp b/apps/gperf/src/Key_List.cpp deleted file mode 100644 index c1009b3441c..00000000000 --- a/apps/gperf/src/Key_List.cpp +++ /dev/null @@ -1,1345 +0,0 @@ -/* Routines for building, ordering, and printing the keyword list. -// $Id$ - - 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, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ - -#include "ace/Read_Buffer.h" -#include "Hash_Table.h" -#include "Vectors.h" -#include "Key_List.h" - -/* Make the hash table 10 times larger than the number of keyword entries. */ -static const int TABLE_MULTIPLE = 10; - -/* Default type for generated code. */ -static char *const default_array_type = "char *"; - -/* in_word_set return type, by default. */ -static char *const default_return_type = "char *"; - -/* How wide the printed field width must be to contain the maximum hash value. */ -static int field_width = 0; - -static int determined[ALPHA_SIZE]; - -/* Destructor dumps diagnostics during debugging. */ - -Key_List::~Key_List (void) -{ - 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 ? total_duplicates + 1 : 0, max_key_len); - dump (); - ACE_ERROR ((LM_ERROR, "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. */ - -char * -Key_List::get_special_input (char delimiter) -{ - 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. */ - -char * -Key_List::save_include_src (void) -{ - int c; - - if ((c = getchar ()) != '%') - ungetc (c, stdin); - else if ((c = getchar ()) != '{') - ACE_ERROR ((LM_ERROR, "internal error, %c != '{' on line %d in file %s%a", c, __LINE__, __FILE__, 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. */ - -char * -Key_List::get_array_type (void) -{ - return get_special_input ('%'); -} - -/* strcspn - find length of initial segment of S consisting entirely - ANSI string package, when GNU libc comes out I'll replace this...). */ - -inline int -Key_List::strcspn (const char *s, const char *reject) -{ - 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; -} - -/* 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) -{ - if (option[TYPE] && !(array_type = get_array_type ())) - return; /* Something's wrong, bug we'll catch it later on.... */ - else if (option[TYPE]) /* Yow, we've got a user-defined type... */ - { - int struct_tag_length = strcspn (array_type, "{\n\0"); - - if (option[POINTER]) /* And it must return a pointer... */ - { - return_type = new char[struct_tag_length + 2]; - strncpy (return_type, array_type, struct_tag_length); - return_type[struct_tag_length] = '*'; - return_type[struct_tag_length + 1] = '\0'; - } - - struct_tag = new char[struct_tag_length + 1]; - strncpy (struct_tag, array_type, struct_tag_length); - struct_tag[struct_tag_length] = '\0'; - } - else if (option[POINTER]) /* Return a char *. */ - 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 -Key_List::read_keys (void) -{ - include_src = save_include_src (); - set_output_types (); - - ACE_Read_Buffer input (stdin); - - char *ptr = input.read ('\n'); - - if (ptr == 0) - // Oops, problem with the input file. - ACE_ERROR ((LM_ERROR, "No words in input file, did you forget to prepend %s" - " or use -t accidentally?\n%a", "%%", 1)); - - /* Read in all the keywords from the input file. */ - else - { - const char *delimiter = option.get_delimiter (); - List_Node *temp, *trail = 0; - - head = new List_Node (ptr, strcspn (ptr, delimiter)); - - for (temp = head; - (ptr = input.read ('\n')) && strcmp (ptr, "%%"); - temp = temp->next) - { - temp->next = new List_Node (ptr, strcspn (ptr, delimiter)); - total_keys++; - } - - /* See if any additional source 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[ACE_POW (table_size)]; -#else - // Note: we don't use new, because that invokes a custom operator new. - int malloc_size = ACE_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); - - /* 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 (temp, 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) - { - 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]) - ACE_ERROR ((LM_ERROR, "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 (max_key_len < temp->length) - max_key_len = temp->length; - if (min_key_len > temp->length) - min_key_len = temp->length; - } - -#if !LARGE_STACK_ARRAYS - free (table); -#endif - - /* Exit program if links exists and option[DUP] not set, since we can't continue */ - if (total_duplicates) - ACE_ERROR ((LM_ERROR, option[DUP] - ? "%d input keys have identical hash values, examine output carefully...\n" - : "%d input keys have identical hash values,\ntry different key positions or use option -D.\n%a", total_duplicates, 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) -{ - if (!list1) - return list2; - else if (!list2) - return list1; - else if (occurrence_sort && list1->occurrence < list2->occurrence - || 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. */ - -List_Node * -Key_List::merge_sort (List_Node *a_head) -{ - if (!a_head || !a_head->next) - return a_head; - else - { - List_Node *middle = a_head; - List_Node *temp = a_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 (a_head), merge_sort (temp)); - } -} - -/* Returns the frequency of occurrence of elements in the key set. */ - -inline int -Key_List::get_occurrence (List_Node *ptr) -{ - int value = 0; - - for (char *temp = ptr->char_set; *temp; temp++) - value += Vectors::occurrences[*temp]; - - return value; -} - -/* Enables the index location of all key set elements that are now - determined. */ - -inline void -Key_List::set_determined (List_Node *ptr) -{ - for (char *temp = ptr->char_set; *temp; temp++) - determined[*temp] = 1; -} - -/* Returns TRUE if PTR's key set is already completely determined. */ - -inline int -Key_List::already_determined (List_Node *ptr) -{ - int is_determined = 1; - - for (char *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 -Key_List::reorder (void) -{ - List_Node *ptr; - - for (ptr = head; ptr; ptr = ptr->next) - ptr->occurrence = get_occurrence (ptr); - - occurrence_sort = !(hash_sort = 0); /* Pretty gross, eh?! */ - - 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; - } - } - } -} - -/* Outputs 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::output_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; - - if (!option[ENUM]) - printf ("\n#define TOTAL_KEYWORDS %d\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#define HASH_VALUE_RANGE %d" - "\n#define DUPLICATES %d\n\n", - total_keys, min_key_len, max_key_len, min_hash_value, - max_hash_value, max_hash_value - min_hash_value + 1, - total_duplicates ? total_duplicates + 1 : 0); - else if (option[GLOBAL]) - printf ("enum\n{\n" - " TOTAL_KEYWORDS = %d,\n" - " MIN_WORD_LENGTH = %d,\n" - " MAX_WORD_LENGTH = %d,\n" - " MIN_HASH_VALUE = %d,\n" - " MAX_HASH_VALUE = %d,\n" - " HASH_VALUE_RANGE = %d,\n" - " DUPLICATES = %d\n};\n\n", - total_keys, min_key_len, max_key_len, min_hash_value, - max_hash_value, max_hash_value - min_hash_value + 1, - total_duplicates ? total_duplicates + 1 : 0); -} - -/* 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 - Output_Lookup_Function. Then we use for switch statements to - perform either 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. */ - -void -Key_List::output_switch (void) -{ - char *comp_buffer; - List_Node *curr = head; - int pointer_and_type_enabled = option[POINTER] && option[TYPE]; - int total_switches = option.get_total_switches (); - int switch_size = keyword_list_length () / total_switches; - - if (pointer_and_type_enabled) - { -#if defined (__GNUG__) - comp_buffer = (char *) alloca (strlen ("charmap[*str] == *resword->%s && !strncasecmp (str + 1, resword->%s + 1, len - 1)") - + 2 * strlen (option.get_key_name ()) + 1); -#else - comp_buffer = new char [strlen ("charmap[*str] == *resword->%s && !strncasecmp (str + 1, resword->%s + 1, len - 1)") - + 2 * strlen (option.get_key_name ()) + 1]; -#endif - if (option[COMP]) - sprintf (comp_buffer, "%s == *resword->%s && !%s (str + 1, resword->%s + 1, len - 1)", - option[STRCASECMP] ? "charmap[*str]" : "*str", option.get_key_name (), - option[STRCASECMP] ? "strncasecmp" : "strncmp", option.get_key_name ()); - else - sprintf (comp_buffer, "%s == *resword->%s && !%s (str + 1, resword->%s + 1)", - option[STRCASECMP] ? "charmap[*str]" : "*str", option.get_key_name (), - option[STRCASECMP] ? "strcasecmp" : "strcmp", option.get_key_name ()); - } - else - { - if (option[COMP]) - comp_buffer = option[STRCASECMP] - ? "charmap[*str] == *resword && !strncasecmp (str + 1, resword + 1, len - 1)" - : "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)"; - else - comp_buffer = option[STRCASECMP] - ? "charmap[*str] == *resword && !strcasecmp (str + 1, resword + 1, len - 1)" - : "*str == *resword && !strcmp (str + 1, resword + 1, len - 1)"; - } - if (!option[OPTIMIZE]) - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n"); - printf (" register int key = %s (str, len);\n\n", option.get_hash_name ()); - if (!option[OPTIMIZE]) - printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"); - - printf (" {\n"); - - /* 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 && total_switches != 1) - 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[POINTER] || option[DUP]) - { - int i = 0; - - printf (" %s%s *resword; %s\n\n", - option[CONST] ? "const " : "", - pointer_and_type_enabled ? struct_tag : "char", - option[LENTABLE] && !option[DUP] ? "int key_len;" : ""); - if (total_switches == 1) - { - printf (" switch (key)\n {\n"); - lowest_case_value = 0; - } - else - 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[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[LENTABLE] && !option[DUP]) - printf (" key_len = %d;", temp->length); - printf (" break;\n"); - } - } - printf (" default: return 0;\n }\n"); - if (option[OPTIMIZE]) - printf (" return resword;\n"); - else - { - printf (option[LENTABLE] && !option[DUP] - ? " if (len == key_len && %s)\n return resword;\n" - : " if (%s)\n return resword;\n", comp_buffer); - printf (" return 0;\n"); - } - printf (" }\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[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 "); - if (option[COMP]) - printf ("return %s == *s && !%s;\n }\n", - option[STRCASECMP] ? "charmap[*str]" : "*str", - option[STRCASECMP] ? "strncasecmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)"); - else - printf ("return %s == *s && !%s;\n }\n", - option[STRCASECMP] ? "charmap[*str]" : "*str", - option[STRCASECMP] ? "strcasecmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)"); - curr = temp; - } - } - printf (" }\n %s\n}\n", option[OPTIMIZE] ? "" : "}\n return 0;"); -} - -/* 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) -{ - const int max_column = 15; - int index = 0; - int column = 0; - char *indent = option[GLOBAL] ? "" : " "; - List_Node *temp; - - if (!option[DUP] && !option[SWITCH]) - { - printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n ", - indent, option[CONST] ? "const " : "", - max_key_len <= UCHAR_MAX ? "char" : (max_key_len <= USHRT_MAX ? "short" : "long"), - indent, indent); - - for (temp = 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", indent, indent); - } -} -/* Prints out the array containing the key words for the Gen_Perf - hash function. */ - -void -Key_List::output_keyword_table (void) -{ - char *l_brace = *head->rest ? "{" : ""; - char *r_brace = *head->rest ? "}," : ""; - char *indent = option[GLOBAL] ? "" : " "; - int index = 0; - List_Node *temp; - - printf ("%sstatic %s%swordlist[] =\n%s%s{\n", - indent, option[CONST] ? "const " : "", struct_tag, indent, indent); - - /* Skip over leading blank entries if there are no duplicates. */ - - if (0 < head->hash_value) - printf (" "); - for (int column = 1; index < head->hash_value; index++, column++) - printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n "); - if (0 < head->hash_value && column % 10) - printf ("\n"); - - /* Generate an array of reserved words at appropriate locations. */ - - for (temp = head ; temp; temp = temp->next, index++) - { - temp->index = index; - - if (!option[SWITCH] && (total_duplicates == 0 || !option[DUP]) && 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", l_brace, temp->key, temp->rest, r_brace); - if (option[DEBUG]) - printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index); - putchar ('\n'); - continue; - } - } - - printf (" %s\"%s\", %s%s", l_brace, temp->key, temp->rest, r_brace); - if (option[DEBUG]) - printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index); - putchar ('\n'); - - /* Deal with links specially. */ - if (temp->link) - for (List_Node *links = temp->link; links; links = links->link) - { - links->index = ++index; - printf (" %s\"%s\", %s%s", l_brace, links->key, links->rest, r_brace); - if (option[DEBUG]) - printf (" /* hash value = %d, index = %d */", links->hash_value, links->index); - putchar ('\n'); - } - } - printf ("%s%s};\n\n", indent, indent); -} - -/* Generates C code for the hash function that returns the - proper encoding for each key word. */ - -void -Key_List::output_hash_function (void) -{ - const int max_column = 10; - int count = max_hash_value; - - /* Calculate maximum number of digits required for MAX_HASH_VALUE. */ - - for (field_width = 2; (count /= 10) > 0; field_width++) - ; - - if (option[GNU]) - printf ("#ifdef __GNUC__\ninline\n#endif\n"); - - if (option[C]) - printf ("static "); - printf ("unsigned int\n"); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - - printf (option[ANSI] - ? "%s (register const char *str, register int len)\n{\n static %sunsigned %s asso_values[] =\n {" - : "%s (str, len)\n register char *str;\n register int unsigned len;\n{\n static %sunsigned %s asso_values[] =\n {", - option.get_hash_name (), option[CONST] ? "const " : "", - max_hash_value <= UCHAR_MAX ? "char" : (max_hash_value <= USHRT_MAX ? "short" : "int")); - - for (count = 0; count < ALPHA_SIZE; ++count) - { - if (!(count % max_column)) - printf ("\n "); - - printf ("%*d,", - field_width, - Vectors::occurrences[count] ? Vectors::asso_values[count] : max_hash_value + 1); - } - - /* Optimize special case of ``-k 1,$'' */ - if (option[DEFAULTCHARS]) - { - if (option[STRCASECMP]) - printf ("\n };\n return %sasso_values[charmap[str[len - 1]]] + asso_values[charmap[str[0]]];\n}\n\n", - option[NOLENGTH] ? "" : "len + "); - else - printf ("\n };\n return %sasso_values[str[len - 1]] + asso_values[str[0]];\n}\n\n", - option[NOLENGTH] ? "" : "len + "); - } - else - { - int key_pos; - - option.reset (); - - /* Get first (also highest) key position. */ - key_pos = option.get (); - - /* We can perform additional optimizations here. */ - if (!option[ALLCHARS] && key_pos <= min_key_len) - { - printf ("\n };\n return %s", option[NOLENGTH] ? "" : "len + "); - - for (; key_pos != WORD_END; ) - { - printf (option[STRCASECMP] ? "asso_values[charmap[str[%d]]]" : "asso_values[str[%d]]", key_pos - 1); - if ((key_pos = option.get ()) != EOS) - printf (" + "); - else - break; - } - - printf ("%s;\n}\n\n", key_pos == WORD_END - ? (option[STRCASECMP] ? "asso_values[charmap[str[len - 1]]]" : "asso_values[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[NOLENGTH] ? "0" : "len", option[NOLENGTH] ? "len" : "hval"); - - /* User wants *all* characters considered in hash. */ - if (option[ALLCHARS]) - { - int i; - - /* Break these options up for speed (gee, is this misplaced efficiency or what?! */ - if (option[STRCASECMP]) - - for (i = max_key_len; i > 0; i--) - printf (" case %d:\n hval += asso_values[charmap[str[%d]]];\n", i, i - 1); - - else - - for (i = max_key_len; i > 0; i--) - printf (" case %d:\n hval += asso_values[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 (option[STRCASECMP] - ? " case %d:\n hval += asso_values[charmap[str[%d]]];\n" - : " case %d:\n hval += asso_values[str[%d]];\n", - key_pos, key_pos - 1); - } - while ((key_pos = option.get ()) != EOS && key_pos != WORD_END); - - printf (" }\n return hval%s;\n}\n\n", - key_pos == WORD_END - ? (option[STRCASECMP] ? " + asso_values[charmap[str[len - 1]]]" : " + asso_values[str[len - 1]]") - : ""); - } - } - } -} - -/* 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) -{ - if (total_duplicates > 0) - { - const int DEFAULT_VALUE = -1; - - 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]; -#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)); - int *lookup_array = (int*)malloc(sizeof(int) * (max_hash_value + 1)); - if (duplicates == NULL || lookup_array == NULL) - abort(); -#endif - duplicate_entry *dup_ptr = duplicates; - int *lookup_ptr = lookup_array + max_hash_value + 1; - - while (lookup_ptr > lookup_array) - *--lookup_ptr = DEFAULT_VALUE; - - 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, temp->index); - if (!temp->link && - (!temp->next || hash_value != temp->next->hash_value)) - continue; -#if LARGE_STACK_ARRAYS - *dup_ptr = (duplicate_entry) { hash_value, temp->index, 1 }; -#else - duplicate_entry _dups; - _dups.hash_value = hash_value; - _dups.index = temp->index; - _dups.count = 1; - *dup_ptr = _dups; -#endif - - 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, ptr->index); - } - - while (temp->next && hash_value == temp->next->hash_value) - { - temp = temp->next; - dup_ptr->count++; - if (option[DEBUG]) - fprintf (stderr, "dynamic linked keyword = %s, index = %d\n", temp->key, temp->index); - - 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, ptr->index); - } - } - dup_ptr++; - } - - while (--dup_ptr >= duplicates) - { - 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); - - /* Start searching for available space towards the right part of the lookup array. */ - int i; - for (i = dup_ptr->hash_value; i < max_hash_value; i++) - if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i + 1] == DEFAULT_VALUE) - { - lookup_array[i] = -dup_ptr->index; - lookup_array[i + 1] = -dup_ptr->count; - lookup_array[dup_ptr->hash_value] = max_hash_value + (i - dup_ptr->hash_value); - break; - } - - /* If we didn't find it to the right look to the left instead... */ - if (i == max_hash_value) - { - - for (i = dup_ptr->hash_value; i > 0; i--) - if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i - 1] == DEFAULT_VALUE) - { - lookup_array[i - 1] = -dup_ptr->index; - lookup_array[i] = -dup_ptr->count; - lookup_array[dup_ptr->hash_value] = -(max_hash_value + (dup_ptr->hash_value - i + 1)); - break; - } - - /* We are in *big* trouble if this happens! */ - assert (i != 0); - } - } - - int max = INT_MIN; - lookup_ptr = lookup_array + max_hash_value + 1; - while (lookup_ptr > lookup_array) - { - int val = abs (*--lookup_ptr); - if (max < val) - max = val; - } - - char *indent = option[GLOBAL] ? "" : " "; - printf ("%sstatic %s%s lookup[] =\n%s%s{\n ", indent, option[CONST] ? "const " : "", - max <= SCHAR_MAX ? "char" : (max <= USHRT_MAX ? "short" : "int"), - indent, indent); - - int count = max; - - /* Calculate maximum number of digits required for MAX_HASH_VALUE. */ - - for (field_width = 2; (count /= 10) > 0; field_width++) - ; - - const int max_column = 15; - int column = 0; - - for (lookup_ptr = lookup_array; - lookup_ptr < lookup_array + max_hash_value + 1; - lookup_ptr++) - printf ("%*d,%s", field_width, *lookup_ptr, ++column % (max_column - 1) ? "" : "\n "); - - printf ("\n%s%s};\n\n", indent, indent); -#if !LARGE_STACK_ARRAYS - free (duplicates); - free (lookup_array); -#endif - } -} -/* Generates C code to perform the keyword lookup. */ - -void -Key_List::output_lookup_function (void) -{ - if (!option[OPTIMIZE]) - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n"); - printf (" register int key = %s (str, len);\n\n", option.get_hash_name ()); - if (!option[OPTIMIZE]) - printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"); - printf (" {\n"); - - if (option[DUP] && total_duplicates > 0) - { - printf (" register int index = lookup[key];\n\n" - " if (index >= 0 && index < MAX_HASH_VALUE)\n"); - if (option[OPTIMIZE]) - printf (" return %swordlist[index];\n", option[TYPE] && option[POINTER] ? "&" : ""); - else - { - printf (" {\n" - " register %schar *s = wordlist[index]", option[CONST] ? "const " : ""); - if (array_type != default_array_type) - printf (".%s", option.get_key_name ()); - - printf (";\n\n if (%s%s == *s && !%s)\n return %s;\n }\n", - option[LENTABLE] ? "len == lengthtable[key]\n && " : "", - option[STRCASECMP] ? "charmap[*str]" : "*str", - option[COMP] ? (option[STRCASECMP] ? "strncasecmp (str + 1, s + 1, len - 1)" : "strncmp (str + 1, s + 1, len - 1)") - : (option[STRCASECMP] ? "strcasecmp (str + 1, s + 1)" : "strcmp (str + 1, s + 1)"), - option[TYPE] && option[POINTER] ? "&wordlist[index]" : "s"); - printf (" else if (index < 0 && index >= -MAX_HASH_VALUE)\n" - " return 0;\n"); - } - printf (" else\n {\n" - " register int offset = key + index + (index > 0 ? -MAX_HASH_VALUE : MAX_HASH_VALUE);\n" - " register %s%s*base = &wordlist[-lookup[offset]];\n" - " register %s%s*ptr = base + -lookup[offset + 1];\n\n" - " while (--ptr >= base)\n ", - option[CONST] ? "const " : "", struct_tag, - option[CONST] ? "const " : "", struct_tag); - if (array_type != default_array_type) - { - if (option[COMP]) - printf ("if (%s == *ptr->%s && !%s (str + 1, ptr->%s + 1, len - 1", - option[STRCASECMP] ? "charmap[*str]" : "*str", option.get_key_name (), - option[STRCASECMP] ? "strncasecmp" : "strncmp", option.get_key_name ()); - else - printf ("if (%s == *ptr->%s && !%s (str + 1, ptr->%s + 1", - option[STRCASECMP] ? "charmap[*str]" : "*str", option.get_key_name (), - option[STRCASECMP] ? "strcasecmp" : "strcmp", option.get_key_name ()); - } - else - printf (option[STRCASECMP] ? "if (charmap[*str] == **ptr && !%s" : "if (*str == **ptr && !%s", - option[COMP] - ? (option[STRCASECMP] ? "strncasecmp (str + 1, *ptr + 1, len - 1" : "strncmp (str + 1, *ptr + 1, len - 1") - : (option[STRCASECMP] ? "strcasecmp (str + 1, *ptr + 1" : "strcmp (str + 1, *ptr + 1")); - printf ("))\n return %sptr;" - "\n }\n }\n %s\n}\n", array_type == - default_array_type ? "*" : "", option[OPTIMIZE] ? "" : "}\n return 0;"); - } - else - { - if (option[OPTIMIZE]) - printf (" return %swordlist[key]", option[TYPE] && option[POINTER] ? "&" : ""); - else - { - printf (" register %schar *s = wordlist[key]", option[CONST] ? "const " : ""); - - if (array_type != default_array_type) - printf (".%s", option.get_key_name ()); - - printf (";\n\n if (%s%s == *s && !%s)\n return %s", - option[LENTABLE] ? "len == lengthtable[key]\n && " : "", - option[STRCASECMP] ? "charmap[*str]" : "*str", - option[COMP] - ? (option[STRCASECMP] ? "strncasecmp (str + 1, s + 1, len - 1)" : "strncmp (str + 1, s + 1, len - 1)") - : (option[STRCASECMP] ? "strcasecmp (str + 1, s + 1)" : "strcmp (str + 1, s + 1)"), - option[TYPE] && option[POINTER] ? "&wordlist[key]" : "s"); - } - printf (";\n }\n %s\n}\n", option[OPTIMIZE] ? "" : "}\n return 0;"); - } -} - -/* Output the table and the functions that map upper case into lower case! */ - -void -Key_List::output_strcasecmp (void) -{ - printf ("%s", - "/* This array is designed for mapping upper and lower case letter\n" - " * together for a case independent comparison. The mappings are\n" - " * based upon ascii character sequences.\n */" - "static char charmap[] = {\n" - " '\\000', '\\001', '\\002', '\\003', '\\004', '\\005', '\\006', '\\007',\n" - " '\\010', '\\011', '\\012', '\\013', '\\014', '\\015', '\\016', '\\017',\n" - " '\\020', '\\021', '\\022', '\\023', '\\024', '\\025', '\\026', '\\027',\n" - " '\\030', '\\031', '\\032', '\\033', '\\034', '\\035', '\\036', '\\037',\n" - " '\\040', '\\041', '\\042', '\\043', '\\044', '\\045', '\\046', '\\047',\n" - " '\\050', '\\051', '\\052', '\\053', '\\054', '\\055', '\\056', '\\057',\n" - " '\\060', '\\061', '\\062', '\\063', '\\064', '\\065', '\\066', '\\067',\n" - " '\\070', '\\071', '\\072', '\\073', '\\074', '\\075', '\\076', '\\077',\n" - " '\\100', '\\141', '\\142', '\\143', '\\144', '\\145', '\\146', '\\147',\n" - " '\\150', '\\151', '\\152', '\\153', '\\154', '\\155', '\\156', '\\157',\n" - " '\\160', '\\161', '\\162', '\\163', '\\164', '\\165', '\\166', '\\167',\n" - " '\\170', '\\171', '\\172', '\\133', '\\134', '\\135', '\\136', '\\137',\n" - " '\\140', '\\141', '\\142', '\\143', '\\144', '\\145', '\\146', '\\147',\n" - " '\\150', '\\151', '\\152', '\\153', '\\154', '\\155', '\\156', '\\157',\n" - " '\\160', '\\161', '\\162', '\\163', '\\164', '\\165', '\\166', '\\167',\n" - " '\\170', '\\171', '\\172', '\\173', '\\174', '\\175', '\\176', '\\177',\n" - " '\\200', '\\201', '\\202', '\\203', '\\204', '\\205', '\\206', '\\207',\n" - " '\\210', '\\211', '\\212', '\\213', '\\214', '\\215', '\\216', '\\217',\n" - " '\\220', '\\221', '\\222', '\\223', '\\224', '\\225', '\\226', '\\227',\n" - " '\\230', '\\231', '\\232', '\\233', '\\234', '\\235', '\\236', '\\237',\n" - " '\\240', '\\241', '\\242', '\\243', '\\244', '\\245', '\\246', '\\247',\n" - " '\\250', '\\251', '\\252', '\\253', '\\254', '\\255', '\\256', '\\257',\n" - " '\\260', '\\261', '\\262', '\\263', '\\264', '\\265', '\\266', '\\267',\n" - " '\\270', '\\271', '\\272', '\\273', '\\274', '\\275', '\\276', '\\277',\n" - " '\\300', '\\341', '\\342', '\\343', '\\344', '\\345', '\\346', '\\347',\n" - " '\\350', '\\351', '\\352', '\\353', '\\354', '\\355', '\\356', '\\357',\n" - " '\\360', '\\361', '\\362', '\\363', '\\364', '\\365', '\\366', '\\367',\n" - " '\\370', '\\371', '\\372', '\\333', '\\334', '\\335', '\\336', '\\337',\n" - " '\\340', '\\341', '\\342', '\\343', '\\344', '\\345', '\\346', '\\347',\n" - " '\\350', '\\351', '\\352', '\\353', '\\354', '\\355', '\\356', '\\357',\n" - " '\\360', '\\361', '\\362', '\\363', '\\364', '\\365', '\\366', '\\367',\n" - " '\\370', '\\371', '\\372', '\\373', '\\374', '\\375', '\\376', '\\377',\n};\n\nstatic int\n"); - if (option[COMP]) - { - printf ("%s", option[ANSI] - ? "strncasecmp (register char *s1, register char *s2, register int n)" - : "strncasecmp (s1, s2, n)\n register char *s1, *s2;\n register int n;"); - printf ("\n{\n register char *cm = charmap;\n\n while (--n >= 0 && cm[*s1] == cm[*s2++])\n" - " if (*s1++ == '\\0')\n return 0;\n" - "\n return n < 0 ? 0 : cm[*s1] - cm[*--s2];\n}\n\n"); - } - else - { - printf ("%s", option[ANSI] - ? "strcasecmp (register char *s1, register char *s2)" - : "strcasecmp (s1, s2)\n register char *s1, *s2;"); - printf ("\n{\n register char *cm = charmap;\n\n while (cm[*s1] == cm[*s2++])\n" - " if (*s1++ == '\\0')\n return 0;\n" - "\n return cm[*s1] - cm[*--s2];\n}\n\n"); - } -} - -/* Generates the hash function and the key word recognizer function - based upon the user's Options. */ - -void -Key_List::output (void) -{ - printf ("%s\n", include_src); - - if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */ - printf ("%s;\n", array_type); - - output_min_max (); - - if (option[STRCASECMP]) - output_strcasecmp (); - if (option[CPLUSPLUS]) - printf ("class %s\n{\nprivate:\n" - " static unsigned int hash (const char *str, int len);\npublic:\n" - " static %s%s%s (const char *str, int len);\n};\n\n", - option.get_class_name (), option[CONST] ? "const " : "", - return_type, option.get_function_name ()); - - output_hash_function (); - - if (option[GLOBAL]) - if (option[SWITCH]) - { - if (option[LENTABLE] && option[DUP]) - output_keylength_table (); - if (option[POINTER] && option[TYPE]) - output_keyword_table (); - } - else - { - if (option[LENTABLE]) - output_keylength_table (); - output_keyword_table (); - output_lookup_array (); - } - - if (option[GNU]) /* Use the inline keyword to remove function overhead. */ - printf ("#ifdef __GNUC__\ninline\n#endif\n"); - - printf ("%s%s\n", option[CONST] ? "const " : "", return_type); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - - printf (option[ANSI] - ? "%s (register const char *str, register int len)\n{\n" - : "%s (str, len)\n register char *str;\n register unsigned int len;\n{\n", - option.get_function_name ()); - - if (option[ENUM] && !option[GLOBAL]) - printf (" enum\n {\n" - " TOTAL_KEYWORDS = %d,\n" - " MIN_WORD_LENGTH = %d,\n" - " MAX_WORD_LENGTH = %d,\n" - " MIN_HASH_VALUE = %d,\n" - " MAX_HASH_VALUE = %d,\n" - " HASH_VALUE_RANGE = %d,\n" - " DUPLICATES = %d\n };\n\n", - total_keys, min_key_len, max_key_len, min_hash_value, - max_hash_value, max_hash_value - min_hash_value + 1, - total_duplicates ? total_duplicates + 1 : 0); - /* Use the switch in place of lookup table. */ - if (option[SWITCH]) - { - if (!option[GLOBAL]) - { - if (option[LENTABLE] && option[DUP]) - output_keylength_table (); - if (option[POINTER] && option[TYPE]) - output_keyword_table (); - } - output_switch (); - } - /* Use the lookup table, in place of switch. */ - else - { - if (!option[GLOBAL]) - { - if (option[LENTABLE]) - output_keylength_table (); - output_keyword_table (); - } - if (!option[GLOBAL]) - output_lookup_array (); - output_lookup_function (); - } - - if (additional_code) - { - for (;;) - { - int c = getchar (); - - if (c == EOF) - break; - else - putchar (c); - } - } - - fflush (stdout); -} - -/* Sorts the keys by hash value. */ - -void -Key_List::sort (void) -{ - hash_sort = 1; - occurrence_sort = 0; - - head = merge_sort (head); -} - -/* Dumps the key list to stderr stream. */ - -void -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->length, ptr->index, - field_width, ptr->char_set, ptr->key); -} - -/* Simple-minded constructor action here... */ - -Key_List::Key_List (void) -{ - total_keys = 1; - max_key_len = INT_MIN; - min_key_len = INT_MAX; - return_type = default_return_type; - array_type = struct_tag = default_array_type; - head = 0; - total_duplicates = 0; - additional_code = 0; -} - -/* Returns the length of entire key list. */ - -int -Key_List::keyword_list_length (void) -{ - return list_len; -} - -/* Returns length of longest key read. */ - -int -Key_List::max_key_length (void) -{ - return max_key_len; -} - |