summaryrefslogtreecommitdiff
path: root/apps/gperf/src/Gen_Perf.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'apps/gperf/src/Gen_Perf.cpp')
-rw-r--r--apps/gperf/src/Gen_Perf.cpp454
1 files changed, 0 insertions, 454 deletions
diff --git a/apps/gperf/src/Gen_Perf.cpp b/apps/gperf/src/Gen_Perf.cpp
deleted file mode 100644
index a946421a80d..00000000000
--- a/apps/gperf/src/Gen_Perf.cpp
+++ /dev/null
@@ -1,454 +0,0 @@
-// -*- C++ -*-
-
-// $Id$
-
-// Copyright (C) 1989 Free Software Foundation, Inc.
-// written by Douglas C. Schmidt (schmidt@cs.wustl.edu)
-
-// This file is part of GNU GPERF.
-
-// This program 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 2
-// of the License, or (at your option) any later version.
-
-// This program 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 this program; if not, write to the Free Software
-// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-
-#include "Gen_Perf.h"
-
-ACE_RCSID(src, Gen_Perf, "$Id$")
-
-#if defined (ACE_HAS_GPERF)
-
-#include "Vectors.h"
-
-// Current release version.
-extern const char *version_string;
-
-// Reads input keys, possibly applies the reordering heuristic, sets
-// the maximum associated value size (rounded up to the nearest power
-// of 2), may initialize the associated values array, and determines
-// the maximum hash table size. Note: using the random numbers is
-// often helpful, though not as deterministic, of course!
-
-Gen_Perf::Gen_Perf (void)
- : fewest_collisions (0),
- num_done (1)
-{
-}
-
-// Merge two disjoint hash key multisets to form the ordered disjoint
-// union of the sets. (In a multiset, an element can occur multiple
-// times). Precondition: both set1 and set2 must be
-// ordered. Returns the length of the combined set.
-
-int
-Gen_Perf::compute_disjoint_union (char *set1, char *set2, char *set3)
-{
- char *base = set3;
-
- while (*set1 && *set2)
- if (*set1 == *set2)
- set1++, set2++;
- else
- {
- *set3 = *set1 < *set2 ? *set1++ : *set2++;
- if (set3 == base || *set3 != *(set3 - 1))
- set3++;
- }
-
- while (*set1)
- {
- *set3 = *set1++;
- if (set3 == base || *set3 != *(set3 - 1))
- set3++;
- }
-
- while (*set2)
- {
- *set3 = *set2++;
- if (set3 == base || *set3 != *(set3 - 1))
- set3++;
- }
- *set3 = '\0';
- return set3 - base;
-}
-
-// Sort the UNION_SET in increasing frequency of occurrence. This
-// speeds up later processing since we may assume the resulting set
-// (Set_3, in this case), is ordered. Uses insertion sort, since the
-// UNION_SET is typically short.
-
-void
-Gen_Perf::sort_set (char *union_set, int len)
-{
- for (int i = 0, j = len - 1; i < j; i++)
- {
- char curr, tmp;
-
- for (curr = i + 1, tmp = union_set[curr];
- curr > 0
- && Vectors::occurrences[tmp] < Vectors::occurrences[union_set[curr-1]];
- curr--)
- union_set[curr] = union_set[curr - 1];
-
- union_set[curr] = tmp;
- }
-}
-
-// Generate a keysig's hash value.
-
-int
-Gen_Perf::hash (List_Node *key_node)
-{
- int sum = option[NOLENGTH] ? 0 : key_node->length;
-
- for (char *ptr = key_node->keysig; *ptr; ptr++)
- sum += Vectors::asso_values[*ptr];
-
- key_node->hash_value = sum;
- return sum;
-}
-
-// Find out how character value change affects successfully hash
-// items. Returns FALSE if no other hash values are affected, else
-// returns TRUE. Note that because Option.Get_Asso_Max is a power of
-// two we can guarantee that all legal Vectors::Asso_Values are
-// visited without repetition since Option.Get_Jump was forced to be
-// an odd value!
-
-inline int
-Gen_Perf::affects_prev (char c, List_Node *curr)
-{
- int original_char = Vectors::asso_values[c];
- int total_iterations;
-
- if (!option[FAST])
- total_iterations = option.asso_max ();
- else
- {
- total_iterations = option.iterations ();
-
- if (total_iterations == 0)
- total_iterations = this->key_list.keyword_list_length ();
- }
-
- // Try all legal associated values.
-
- for (int i = total_iterations - 1; i >= 0; i--)
- {
- int collisions = 0;
-
- Vectors::asso_values[c] = Vectors::asso_values[c] +
- (option.jump () ? option.jump () : ACE_OS::rand ()) & option.asso_max () - 1;
-
- // Iteration Number array is a win, O(1) intialization time!
- this->char_search.reset ();
-
- // See how this asso_value change affects previous keywords. If
- // it does better than before we'll take it!
-
- for (List_Node *ptr = this->key_list.head;
- this->char_search.find (this->hash (ptr)) == 0
- || ++collisions < fewest_collisions;
- ptr = ptr->next)
- if (ptr == curr)
- {
- fewest_collisions = collisions;
- if (option[DEBUGGING])
- ACE_DEBUG ((LM_DEBUG,
- "- resolved after %d iterations",
- total_iterations - i));
- return 0;
- }
- }
-
- // Restore original values, no more tries.
- Vectors::asso_values[c] = original_char;
- // If we're this far it's time to try the next character....
- return 1;
-}
-
-// Change a character value, try least-used characters first.
-
-int
-Gen_Perf::change (List_Node *prior, List_Node *curr)
-{
- if (option[DEBUGGING])
- ACE_DEBUG ((LM_DEBUG,
- "collision on keyword #%d, prior = \"%s\", curr = \"%s\" hash = %d\n",
- num_done,
- prior->key,
- curr->key,
- curr->hash_value));
- Gen_Perf::sort_set (this->union_set,
- compute_disjoint_union (prior->keysig,
- curr->keysig,
- this->union_set));
-
- // Try changing some values, if change doesn't alter other values
- // continue normal action.
- fewest_collisions++;
-
- for (char *temp = union_set; *temp != '\0'; temp++)
- if (affects_prev (*temp, curr) == 0)
- {
- if (option[DEBUGGING])
- ACE_DEBUG ((LM_DEBUG,
- " by changing asso_value['%c'] (char #%d) to %d\n",
- *temp,
- temp - union_set + 1,
- Vectors::asso_values[*temp]));
- // Good, doesn't affect previous hash values, we'll take it.
- return 0;
- }
-
- for (List_Node *ptr = this->key_list.head;
- ptr != curr;
- ptr = ptr->next)
- this->hash (ptr);
-
- this->hash (curr);
-
- if (option[DEBUGGING])
- ACE_DEBUG ((LM_DEBUG,
- "** collision not resolved after %d iterations, %d duplicates remain, continuing...\n",
- !option[FAST] ? option.asso_max () : option.iterations () ? option.iterations () : this->key_list.keyword_list_length (),
- fewest_collisions + this->key_list.total_duplicates));
- return 0;
-}
-
-int
-Gen_Perf::open (void)
-{
- if (this->key_list.read_keys () == -1)
- return -1;
-
- if (option[ORDER])
- this->key_list.reorder ();
-
- int asso_value_max = option.asso_max ();
- int non_linked_length = this->key_list.keyword_list_length ();
-
- if (asso_value_max == 0)
- asso_value_max = non_linked_length;
- else if (asso_value_max > 0)
- asso_value_max *= non_linked_length;
- else // if (asso_value_max < 0)
- asso_value_max = non_linked_length / -asso_value_max;
-
- option.asso_max (ACE_POW (asso_value_max));
-
- if (option[RANDOM])
- {
- ACE_OS::srand (ACE_OS::time (0));
-
- for (int i = 0; i < ACE_STANDARD_CHARACTER_SET_SIZE; i++)
- Vectors::asso_values[i] = (ACE_OS::rand () & asso_value_max - 1);
- }
- else
- {
- int asso_value = option.initial_value ();
-
- // Initialize array if user requests non-zero default.
- if (asso_value)
- for (int i = ACE_STANDARD_CHARACTER_SET_SIZE - 1; i >= 0; i--)
- Vectors::asso_values[i] = asso_value & option.asso_max () - 1;
- }
-
- this->max_hash_value = this->key_list.max_key_length ()
- + option.asso_max ()
- * option.max_keysig_size ();
-
- ACE_NEW_RETURN (this->union_set,
- char[2 * option.max_keysig_size () + 1],
- -1);
- printf ("/* ");
-
- if (option[C])
- printf ("C");
-
- else if (option[CPLUSPLUS])
- printf ("C++");
-
- printf (" code produced by gperf version %s */\n",
- version_string);
- Options::print_options ();
-
- if (option[DEBUGGING])
- ACE_DEBUG ((LM_DEBUG,
- "total non-linked keys = %d\n"
- "total duplicates = %d\n"
- "maximum associated value is %d\n"
- "maximum size of generated hash table is %d\n",
- non_linked_length,
- this->key_list.total_duplicates,
- asso_value_max,
- max_hash_value));
- if (this->char_search.open (max_hash_value + 1) == -1)
- return -1;
- 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;
-}
-
-int
-Gen_Perf::compute_linear_search (void)
-{
- // Convert the list of keys to a linear list without
- // equivalence classes.
- 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;
-}
-
-int
-Gen_Perf::compute_perfect_hash (void)
-{
- List_Node *curr;
-
- for (curr = this->key_list.head;
- curr != 0;
- curr = curr->next)
- {
- this->hash (curr);
-
- for (List_Node *ptr = this->key_list.head;
- ptr != curr;
- ptr = ptr->next)
- if (ptr->hash_value == curr->hash_value)
- {
- if (this->change (ptr, curr) == -1)
- return -1;
- break;
- }
- num_done++;
- }
-
- // Make one final check, just to make sure nothing weird happened...
-
- this->char_search.reset ();
-
- for (curr = this->key_list.head;
- curr;
- curr = curr->next)
- if (this->char_search.find (this->hash (curr)) != 0)
- if (option[DUP])
- // Keep track of the number of "dynamic" links (i.e., keys
- // that hash to the same value) so that we can use it later
- // when generating the output.
- this->key_list.total_duplicates++;
- else
- {
- // Yow, big problems. we're outta here!
- ACE_ERROR ((LM_ERROR,
- "\nInternal error, duplicate value %d:\n"
- "try options -D or -r, or use new key positions.\n\n",
- this->hash (curr)));
- return -1;
- }
-
- return 0;
-}
-
-// Does the hard stuff.... Initializes the Bool Array, and attempts
-// to find a perfect function that will hash all the key words without
-// getting any duplications. This is made much easier since we aren't
-// attempting to generate *minimum* functions, only perfect ones. If
-// we can't generate a perfect function in one pass *and* the user
-// hasn't enabled the DUP option, we'll inform the user to try the
-// randomization option, use -D, or choose alternative key positions.
-// The alternatives (e.g., back-tracking) are too time-consuming, i.e,
-// exponential in the number of keys.
-
-int
-Gen_Perf::run (void)
-{
- if (this->open () == -1)
- return 1;
-
- if (option[BINARYSEARCH])
- {
- if (this->compute_binary_search () == -1)
- return 1;
- }
- else if (option[LINEARSEARCH])
- {
- if (this->compute_linear_search () == -1)
- return 1;
- }
- else
- {
- 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 ();
- }
-
- this->key_list.output ();
- return 0;
-}
-
-// Prints out some diagnostics upon completion.
-
-Gen_Perf::~Gen_Perf (void)
-{
- if (option[DEBUGGING])
- {
- ACE_DEBUG ((LM_DEBUG,
- "\ndumping occurrence and associated values tables\n"));
- for (int i = 0; i < ACE_STANDARD_CHARACTER_SET_SIZE; i++)
- if (Vectors::occurrences[i])
- ACE_DEBUG ((LM_DEBUG,
- "Vectors::asso_values[%c] = %6d, Vectors::occurrences[%c] = %6d\n",
- i,
- Vectors::asso_values[i],
- i,
- Vectors::occurrences[i]));
- ACE_DEBUG ((LM_DEBUG,
- "end table dumping\n"));
- }
-
- delete [] this->union_set;
-}
-
-#endif /* ACE_HAS_GPERF */
View Lorry Controller Status