diff options
author | alex <alex@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1998-10-06 07:50:21 +0000 |
---|---|---|
committer | alex <alex@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1998-10-06 07:50:21 +0000 |
commit | d6da0aa6f98626370131dd77c031349b24f80dda (patch) | |
tree | 9b41f7710e76b8a4b17f5d950272e2bbc40e7d04 /apps | |
parent | d95eaa86e437e331702d2f8d214331e324c5c547 (diff) | |
download | ATCD-d6da0aa6f98626370131dd77c031349b24f80dda.tar.gz |
*** empty log message ***
Diffstat (limited to 'apps')
-rw-r--r-- | apps/gperf/ChangeLog | 20 | ||||
-rw-r--r-- | apps/gperf/src/Gen_Perf.cpp | 27 | ||||
-rw-r--r-- | apps/gperf/src/Key_List.cpp | 364 | ||||
-rw-r--r-- | apps/gperf/src/Options.cpp | 14 | ||||
-rw-r--r-- | apps/gperf/src/Options.h | 3 |
5 files changed, 313 insertions, 115 deletions
diff --git a/apps/gperf/ChangeLog b/apps/gperf/ChangeLog index 0245e8384ec..7c32787e95e 100644 --- a/apps/gperf/ChangeLog +++ b/apps/gperf/ChangeLog @@ -1,3 +1,23 @@ +Tue Oct 6 02:48:37 1998 Alexander Babu Arulanthu <alex@cs.wustl.edu> + + Thanks to Vishal the following things have been done to get Binary + Search code generated from GPERF. + + * src/Options.cpp (parse_args): Added the -B option for the binary + search. + + * src/Options.h (enum Option_Type): Added the BINARYSEARCH in the + enumeration. + + * src/Key_List.cpp : Added the function output_binary_search_function + (void). Changed the output function to include the Binary Search option. + Used option[BINARYSEARCH] to distinguish the binary search case from the + hashing case. + + * src/Key_List.h : Added the prototype for output_binary_search_function. + Also added the key_sort variable to enable sorting based on key values. + + Mon Oct 5 18:24:15 1998 Douglas C. Schmidt <schmidt@tango.cs.wustl.edu> * src/Gen_Perf: Created a new function that allows us to split the diff --git a/apps/gperf/src/Gen_Perf.cpp b/apps/gperf/src/Gen_Perf.cpp index 36e66889f81..7d284150422 100644 --- a/apps/gperf/src/Gen_Perf.cpp +++ b/apps/gperf/src/Gen_Perf.cpp @@ -296,9 +296,25 @@ Gen_Perf::open (void) return 0; } +// For binary search, do normal string sort on the keys, and then +// assign hash values from 0 to N-1. Then go ahead with the normal +// logic that is there for perfect hashing. int Gen_Perf::compute_binary_search (void) { + // Do a string sort. + this->key_list.string_sort (); + + // Assign hash values. + List_Node *curr; + int hash_value; + for (hash_value = 0, curr = this->key_list.head; + curr != 0; + curr = curr->next, hash_value++) + { + curr->hash_value = hash_value; + } + return 0; } @@ -378,12 +394,13 @@ Gen_Perf::run (void) { if (this->compute_perfect_hash () == -1) return 1; - } - // Sorts the key word list by hash value, and then outputs the list. - // The generated hash table code is only output if the early stage - // of processing turned out O.K. - this->key_list.sort (); + // Sorts the key word list by hash value, and then outputs the list. + // The generated hash table code is only output if the early stage + // of processing turned out O.K. + this->key_list.sort (); + } + this->key_list.output (); return 0; } diff --git a/apps/gperf/src/Key_List.cpp b/apps/gperf/src/Key_List.cpp index 1e11109755e..aab43358211 100644 --- a/apps/gperf/src/Key_List.cpp +++ b/apps/gperf/src/Key_List.cpp @@ -354,7 +354,8 @@ Key_List::merge (List_Node *list1, List_Node *list2) else if (!list2) return list1; else if (occurrence_sort && list1->occurrence < list2->occurrence - || hash_sort && list1->hash_value > list2->hash_value) + || hash_sort && list1->hash_value > list2->hash_value + || key_sort && strcmp (list1->key, list2->key) >= 0) { list2->next = merge (list2->next, list1); return list2; @@ -792,6 +793,7 @@ Key_List::output_keyword_table (void) if (0 < head->hash_value) printf (" "); + int column; for (column = 1; index < head->hash_value; column++) @@ -799,10 +801,10 @@ Key_List::output_keyword_table (void) 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++) @@ -851,10 +853,105 @@ Key_List::output_keyword_table (void) links->index); putchar ('\n'); } + } printf ("%s%s};\n\n", indent, indent); } +// Generates C code for the binary search algorithm that returns +// the proper encoding for each key word + +int +Key_List::output_binary_search_function (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 {\npublic:\n" + " static %s%s%s (const char *str, unsigned int len);\n};\n\n", + option.class_name (), + option[CONSTANT] ? "const " : "", + return_type, + option.function_name ()); + + // Use the inline keyword to remove function overhead. + if (option[INLINE]) + printf ("inline\n"); + + printf ("%s%s\n", option[CONSTANT] ? "const " : "", return_type); + if (option[CPLUSPLUS]) + printf ("%s::", option.class_name ()); + + printf (option[ANSI] + ? "%s (const char *str, unsigned int len)\n{\n" + : "%s (str, len)\n char *str;\n unsigned int len;\n{\n", + option.function_name ()); + +// Use the switch in place of lookup table. + + if (option[SWITCH]) + output_switch (); + + // Use the lookup table, in place of switch. + else + { + if (!option[GLOBAL]) + { + if (option[LENTABLE]) + output_keylength_table (); + output_keyword_table (); + } + } + + // Logic to handle the Binary Search. + + printf ("int first=0, last=0, middle=0;\n"); + printf ("%s*base;\n",struct_tag); + printf ("\nlast = %d;\n",total_keys-1); + printf ("while (last>=first)\n"); + printf ("\t{\n"); + printf ("\t middle = (last + first)/2;\n"); + printf ("\t if (strcmp(wordlist[middle].opname_,str)==0) break;\n"); + printf ("\t if (strcmp(wordlist[middle].opname_,str)<0) first = middle+1;\n"); + printf ("\t else last = middle-1;\n"); + printf ("\t}\n"); + printf ("if (last<first) return 0;\n"); + printf ("else return (&wordlist[middle]);\n}\n"); + + if (additional_code) + { + for (;;) + { + int c = getchar (); + + if (c == EOF) + break; + else + putchar (c); + } + } + + fflush(stdout); + + return 0; + +} + // Generates C code for the hash function that returns the proper // encoding for each key word. @@ -1345,127 +1442,138 @@ Key_List::output_strcasecmp (void) int Key_List::output (void) { - printf ("%s\n", include_src); + if (option[BINARYSEARCH]) + { + // Generate all the things necessary for doing binary search. + + // Output the lookup method for binary search. + output_binary_search_function (); + } + else + { + // Not binary search. Generate the usual GPERF things. + + printf ("%s\n", include_src); - // Get prototype for strncmp() and strcmp(). - if (!option[SKIPSTRINGH]) - printf ("#include <string.h>\n"); + // 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_); + if (option[TYPE] && !option[NOTYPE]) + printf ("%s;\n", + array_type_); - output_min_max (); + output_min_max (); - if (option[STRCASECMP]) - output_strcasecmp (); + 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, unsigned int len);\npublic:\n" - " static %s%s%s (const char *str, unsigned int len);\n};\n\n", - option.class_name (), - option.hash_name (), - option[CONSTANT] ? "const " : "", - return_type, - option.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 (); - if (output_lookup_array () == -1) - ACE_ERROR_RETURN ((LM_DEBUG, - "%p\n", - "output_lookup_array"), - -1); - } - - // Use the inline keyword to remove function overhead. - if (option[INLINE]) - printf ("inline\n"); - - printf ("%s%s\n", option[CONSTANT] ? "const " : "", return_type); - if (option[CPLUSPLUS]) - printf ("%s::", option.class_name ()); - - printf (option[ANSI] - ? "%s (const char *str, unsigned int len)\n{\n" - : "%s (str, len)\n char *str;\n unsigned int len;\n{\n", - option.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]) - 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]) - { - switch (output_lookup_array ()) - { - case -1: + if ((option[CPLUSPLUS]) && (!option[SKIPCLASS])) + printf ("class %s\n{\nprivate:\n" + " static unsigned int %s (const char *str, unsigned int len);\npublic:\n" + " static %s%s%s (const char *str, unsigned int len);\n};\n\n", + option.class_name (), + option.hash_name (), + option[CONSTANT] ? "const " : "", + return_type, + option.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 (); + if (output_lookup_array () == -1) ACE_ERROR_RETURN ((LM_DEBUG, "%p\n", "output_lookup_array"), -1); - /* NOTREACHED */ - case 0: - output_lookup_function (); - break; - /* NOTREACHED */ - default: - break; - /* NOTREACHED */ + } + + // Use the inline keyword to remove function overhead. + if (option[INLINE]) + printf ("inline\n"); + + printf ("%s%s\n", option[CONSTANT] ? "const " : "", return_type); + if (option[CPLUSPLUS]) + printf ("%s::", option.class_name ()); + + printf (option[ANSI] + ? "%s (const char *str, unsigned int len)\n{\n" + : "%s (str, len)\n char *str;\n unsigned int len;\n{\n", + option.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]) + 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]) + { + switch (output_lookup_array ()) + { + case -1: + ACE_ERROR_RETURN ((LM_DEBUG, + "%p\n", + "output_lookup_array"), + -1); + /* NOTREACHED */ + case 0: + output_lookup_function (); + break; + /* NOTREACHED */ + default: + break; + /* NOTREACHED */ + } } } - } - if (additional_code) - { - for (;;) + if (additional_code) { - int c = getchar (); + for (;;) + { + int c = getchar (); - if (c == EOF) - break; - else - putchar (c); + if (c == EOF) + break; + else + putchar (c); + } } + fflush (stdout); } - - fflush (stdout); return 0; } @@ -1481,6 +1589,49 @@ Key_List::sort (void) this->head = merge_sort (this->head); } +// Sorts the keys by normal strcmp. +void +Key_List::string_sort (void) +{ + + // Flatten the equivalence class list to a linear list. + + List_Node *ptr; + for(ptr=head;ptr;ptr=ptr->next) + { + List_Node *curr; + if(ptr->link) + { + for(curr=ptr->link;curr->link;curr=curr->link) + { + curr->next = curr->link; + } + curr->next = ptr->next; + ptr->next = ptr->link; + + } + } + + // Set all links to Null. + + for(ptr=head;ptr;ptr=ptr->next) + { + ptr->link = 0; + } + + // Set the sorting options. + + key_sort = 1; + hash_sort = 0; + occurrence_sort = 0; + + // Sort. + + this->head = merge_sort (head); + key_sort = 0; +} + + // Dumps the key list to stderr stream. void @@ -1550,6 +1701,7 @@ Key_List::Key_List (void) max_key_len (INT_MIN), min_key_len (INT_MAX), additional_code (0), + key_sort (0), total_keys (1) { } diff --git a/apps/gperf/src/Options.cpp b/apps/gperf/src/Options.cpp index b2d679f45ca..3853000d69d 100644 --- a/apps/gperf/src/Options.cpp +++ b/apps/gperf/src/Options.cpp @@ -78,7 +78,7 @@ void Options::usage (void) { ACE_ERROR ((LM_ERROR, - "Usage: %n [-acCdDef[num]gGhH<hashname>i<init>IjJ" + "Usage: %n [-aBcCdDef[num]gGhH<hashname>i<init>IjJ" "k<keys>K<keyname>lL<language>mMnN<function name>o" "Oprs<size>S<switches>tTvVZ<class name>].\n" "(type %n -h for help)\n")); @@ -223,7 +223,7 @@ Options::parse_args (int argc, char *argv[]) if (ACE_LOG_MSG->open (argv[0]) == -1) return -1; - ACE_Get_Opt getopt (argc, argv, "adcCDe:Ef:gGhH:i:IJj:k:K:lL:mMnN:oOprs:S:tTvVZ:"); + ACE_Get_Opt getopt (argc, argv, "aBcCdDe:Ef:gGhH:i:IJj:k:K:lL:mMnN:oOprs:S:tTvVZ:"); int option_char; argc_ = argc; @@ -239,7 +239,13 @@ Options::parse_args (int argc, char *argv[]) ACE_SET_BITS (option_word_, ANSI); break; } - // Generate strncmp rather than strcmp. + // Generate code for Binary Search. + case 'B': + { + ACE_SET_BITS (option_word_, BINARYSEARCH); + break; + } + // Generate strncmp rather than strcmp. case 'c': { ACE_SET_BITS (option_word_, COMP); @@ -306,6 +312,8 @@ Options::parse_args (int argc, char *argv[]) { ACE_OS::fprintf (stderr, "-a\tGenerate ANSI standard C output code, i.e., function prototypes.\n" + "-B\tGenerate code for Binary Search.\n" + "-c\tGenerate comparison code using strncmp rather than strcmp.\n" "-C\tMake the contents of generated lookup tables constant, i.e., readonly.\n" "-d\tEnables the debugging option (produces verbose output to the standard error).\n" diff --git a/apps/gperf/src/Options.h b/apps/gperf/src/Options.h index 84700be4dfb..f06e4cd044f 100644 --- a/apps/gperf/src/Options.h +++ b/apps/gperf/src/Options.h @@ -58,7 +58,8 @@ enum Option_Type ADA = 040000000, // Generate Ada code. MUTE = 0100000000, // Dont print the warnings. SKIPCLASS = 0200000000, // Skip the class definition part in the output while in C++ mode. - SKIPSTRINGH = 0400000000 // Skip including the header file string.h. + SKIPSTRINGH = 0400000000, // Skip including the header file string.h. + BINARYSEARCH = 01000000000 // Generates Binary Search code. }; // Define some useful constants (these don't really belong here, but |