*** empty log message ***

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