diff options
Diffstat (limited to 'apps/gperf/src/Key_List.cpp')
| -rw-r--r-- | apps/gperf/src/Key_List.cpp | 1419 |
1 files changed, 0 insertions, 1419 deletions
diff --git a/apps/gperf/src/Key_List.cpp b/apps/gperf/src/Key_List.cpp deleted file mode 100644 index b8d29e32932..00000000000 --- a/apps/gperf/src/Key_List.cpp +++ /dev/null @@ -1,1419 +0,0 @@ -// $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 "Key_List.h" - -ACE_RCSID(src, Key_List, "$Id$") - -#if defined (ACE_HAS_GPERF) - -#include "ace/Read_Buffer.h" -#include "Hash_Table.h" -#include "Vectors.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]) - { - ACE_DEBUG ((LM_DEBUG, - "\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 ('%'); -} - -// 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 = ACE_OS::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 + 2]; - strncpy (struct_tag, array_type, struct_tag_length); - if (struct_tag[struct_tag_length] != ' ') - { - struct_tag[struct_tag_length] = ' '; - 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, ACE_OS::strcspn (ptr, delimiter)); - - for (temp = head; - (ptr = input.read ('\n')) && strcmp (ptr, "%%"); - temp = temp->next) - { - temp->next = new List_Node (ptr, ACE_OS::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; - - // 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 (); - - // 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 - // 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 !defined (LARGE_STACK_ARRAYS) - free (table); -#endif /* LARGE_STACK_ARRAYS */ - - // Exit program if links exists and option[DUP] not set, since - // we can't continue. - if (total_duplicates) - { - if (option[DUP]) - { - if (!option[MUTE]) - ACE_ERROR ((LM_ERROR, - "%d input keys have identical hash values, examine output carefully...\n", - total_duplicates, - 1)); - } - else - ACE_ERROR ((LM_ERROR, - "%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); - - // Switch to sorting by occurrence. - 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; - } - } - } -} - -// 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 (void) -{ - 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) - { - // Keep track of the longest string we'll need! - const char *s = "charmap[*str] == *resword->%s && !strncasecmp (str + 1, resword->%s + 1, len - 1)"; -#if defined (__GNUG__) - comp_buffer = - (char *) alloca (strlen (s) + 2 * strlen (option.get_key_name ()) + 1); -#else - comp_buffer = - new char [strlen (s) + 2 * strlen (option.get_key_name ()) + 1]; -#endif /* __GNUG__ */ - 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 && !strncasecmp (str + 1, resword + 1, len - 1)" - : "*str == *resword && !strcmp (str + 1, resword + 1)"; - } - if (!option[OPTIMIZE]) - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n"); - printf (" 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[CONSTANT] ? "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]) - ACE_DEBUG ((LM_DEBUG, - " /* 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[CONSTANT] ? "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[CONSTANT] ? "const " : "", - struct_tag, - indent, - indent); - - // Skip over leading blank entries if there are no duplicates. - - if (0 < head->hash_value) - printf (" "); - - int column; - - for (column = 1; index < head->hash_value; column++) - { - printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n "); - index++; - } - - 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]) - ACE_DEBUG ((LM_DEBUG, - " /* 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]) - ACE_DEBUG ((LM_DEBUG, - " /* 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]) - ACE_DEBUG ((LM_DEBUG, - " /* 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[INLINE]) - printf ("inline\n"); - - if (option[C]) - printf ("static "); - printf ("unsigned int\n"); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - - printf (option[ANSI] - ? "%s (const char *str, int len)\n{\n static %sunsigned %s asso_values[] =\n {" - : "%s (str, len)\n char *str;\n unsigned int len;\n{\n static %sunsigned %s asso_values[] =\n {", - option.get_hash_name (), option[CONSTANT] ? "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 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 in 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 defined (LARGE_STACK_ARRAYS) - duplicate_entry duplicates[total_duplicates]; - int lookup_array[max_hash_value + 1]; -#else - 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 /* LARGE_STACK_ARRAYS */ - - 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]) - ACE_DEBUG ((LM_DEBUG, - "keyword = %s, index = %d\n", - temp->key, - temp->index)); - if (!temp->link && - (!temp->next || hash_value != temp->next->hash_value)) - continue; - -#if defined (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 /* LARGE_STACK_ARRAYS */ - - for (List_Node *ptr = temp->link; ptr; ptr = ptr->link) - { - dup_ptr->count++; - if (option[DEBUG]) - ACE_DEBUG ((LM_DEBUG, - "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]) - ACE_DEBUG ((LM_DEBUG, - "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]) - ACE_DEBUG ((LM_DEBUG, - "static linked keyword = %s, index = %d\n", - ptr->key, - ptr->index)); - } - } - dup_ptr++; - } - - while (--dup_ptr >= duplicates) - { - if (option[DEBUG]) - ACE_DEBUG ((LM_DEBUG, - "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 %ssigned %s lookup[] =\n%s%s{\n ", indent, option[CONSTANT] ? "const " : "", - max <= SCHAR_MAX ? "char" : (max <= SHRT_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++) - continue; - - 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 !defined (LARGE_STACK_ARRAYS) - free (duplicates); - free (lookup_array); -#endif /* LARGE_STACK_ARRAYS */ - } -} - -// 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 (" 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 (" 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" - " %schar *s = wordlist[index]", option[CONSTANT] ? "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" - " int offset = key + index + (index > 0 ? -MAX_HASH_VALUE : MAX_HASH_VALUE);\n" - " %s%s*base = &wordlist[-lookup[offset]];\n" - " %s%s*ptr = base + -lookup[offset + 1];\n\n" - " while (--ptr >= base)\n ", - option[CONSTANT] ? "const " : "", struct_tag, - option[CONSTANT] ? "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 (" %schar *s = wordlist[key]", option[CONSTANT] ? "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 (char *s1, char *s2, int n)" - : "strncasecmp (s1, s2, n)\n char *s1, *s2;\n int n;"); - printf ("\n{\n 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 (char *s1, char *s2)" - : "strcasecmp (s1, s2)\n char *s1, *s2;"); - printf ("\n{\n 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); - - // Get prototype for strncmp() and strcmp(). - if (!option[SKIPSTRINGH]) - printf ("#include <string.h>\n"); - - // Output type declaration now, reference it later on.... - if (option[TYPE] && !option[NOTYPE]) - printf ("%s;\n", array_type); - - output_min_max (); - - if (option[STRCASECMP]) - output_strcasecmp (); - - // Class definition if -M is *not* enabled. - if ((option[CPLUSPLUS]) && (!option[SKIPCLASS])) - printf ("class %s\n{\nprivate:\n" - " static unsigned int %s (const char *str, int len);\npublic:\n" - " static %s%s%s (const char *str, int len);\n};\n\n", - option.get_class_name (), - option.get_hash_name (), - option[CONSTANT] ? "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[INLINE]) // Use the inline keyword to remove function overhead. - printf ("inline\n"); - - printf ("%s%s\n", option[CONSTANT] ? "const " : "", return_type); - if (option[CPLUSPLUS]) - printf ("%s::", option.get_class_name ()); - - printf (option[ANSI] - ? "%s (const char *str, int len)\n{\n" - : "%s (str, len)\n char *str;\n 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) -{ - // By default, we sort via hashing. - 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; -} - -#endif /* ACE_HAS_GPERF */ |