aboutsummaryrefslogtreecommitdiffstats
path: root/src/search.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/search.cc')
-rw-r--r--src/search.cc1684
1 files changed, 1684 insertions, 0 deletions
diff --git a/src/search.cc b/src/search.cc
new file mode 100644
index 000000000000..c2459701036d
--- /dev/null
+++ b/src/search.cc
@@ -0,0 +1,1684 @@
+/* Search algorithm.
+ Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
+ Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
+ and Bruno Haible <bruno@clisp.org>.
+
+ 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 2, 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 this program; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+
+/* Specification. */
+#include "search.h"
+
+#include <stdio.h>
+#include <stdlib.h> /* declares exit(), rand(), srand() */
+#include <string.h> /* declares memset(), memcmp() */
+#include <time.h> /* declares time() */
+#include <math.h> /* declares exp() */
+#include <limits.h> /* defines INT_MIN, INT_MAX, UINT_MAX */
+#include "options.h"
+#include "hash-table.h"
+#include "config.h"
+
+/* ============================== Portability ============================== */
+
+/* Assume ISO C++ 'for' scoping rule. */
+#define for if (0) ; else for
+
+/* Dynamically allocated array with dynamic extent:
+
+ Example:
+ DYNAMIC_ARRAY (my_array, int, n);
+ ...
+ FREE_DYNAMIC_ARRAY (my_array);
+
+ Attention: depending on your implementation my_array is either the array
+ itself or a pointer to the array! Always use my_array only as expression!
+ */
+#if HAVE_DYNAMIC_ARRAY
+ #define DYNAMIC_ARRAY(var,eltype,size) eltype var[size]
+ #define FREE_DYNAMIC_ARRAY(var)
+#else
+ #define DYNAMIC_ARRAY(var,eltype,size) eltype *var = new eltype[size]
+ #define FREE_DYNAMIC_ARRAY(var) delete[] var
+#endif
+
+/* ================================ Theory ================================= */
+
+/* The general form of the hash function is
+
+ hash (keyword) = sum (asso_values[keyword[i] + alpha_inc[i]] : i in Pos)
+ + len (keyword)
+
+ where Pos is a set of byte positions,
+ each alpha_inc[i] is a nonnegative integer,
+ each asso_values[c] is a nonnegative integer,
+ len (keyword) is the keyword's length if !option[NOLENGTH], or 0 otherwise.
+
+ Theorem 1: If all keywords are different, there is a set Pos such that
+ all tuples (keyword[i] : i in Pos) are different.
+
+ Theorem 2: If all tuples (keyword[i] : i in Pos) are different, there
+ are nonnegative integers alpha_inc[i] such that all multisets
+ {keyword[i] + alpha_inc[i] : i in Pos} are different.
+
+ Define selchars[keyword] := {keyword[i] + alpha_inc[i] : i in Pos}.
+
+ Theorem 3: If all multisets selchars[keyword] are different, there are
+ nonnegative integers asso_values[c] such that all hash values
+ sum (asso_values[c] : c in selchars[keyword]) are different.
+
+ Based on these three facts, we find the hash function in three steps:
+
+ Step 1 (Finding good byte positions):
+ Find a set Pos, as small as possible, such that all tuples
+ (keyword[i] : i in Pos) are different.
+
+ Step 2 (Finding good alpha increments):
+ Find nonnegative integers alpha_inc[i], as many of them as possible being
+ zero, and the others being as small as possible, such that all multisets
+ {keyword[i] + alpha_inc[i] : i in Pos} are different.
+
+ Step 3 (Finding good asso_values):
+ Find asso_values[c] such that all hash (keyword) are different.
+
+ In other words, each step finds a projection that is injective on the
+ given finite set:
+ proj1 : String --> Map (Pos --> N)
+ proj2 : Map (Pos --> N) --> Map (Pos --> N) / S(Pos)
+ proj3 : Map (Pos --> N) / S(Pos) --> N
+ where
+ N denotes the set of nonnegative integers,
+ Map (A --> B) := Hom_Set (A, B) is the set of maps from A to B, and
+ S(Pos) is the symmetric group over Pos.
+
+ This was the theory for option[NOLENGTH]; if !option[NOLENGTH], slight
+ modifications apply:
+ proj1 : String --> Map (Pos --> N) x N
+ proj2 : Map (Pos --> N) x N --> Map (Pos --> N) / S(Pos) x N
+ proj3 : Map (Pos --> N) / S(Pos) x N --> N
+
+ For a case-insensitive hash function, the general form is
+
+ hash (keyword) =
+ sum (asso_values[alpha_unify[keyword[i] + alpha_inc[i]]] : i in Pos)
+ + len (keyword)
+
+ where alpha_unify[c] is chosen so that an upper/lower case change in
+ keyword[i] doesn't change alpha_unify[keyword[i] + alpha_inc[i]].
+ */
+
+/* ==================== Initialization and Preparation ===================== */
+
+Search::Search (KeywordExt_List *list)
+ : _head (list)
+{
+}
+
+void
+Search::prepare ()
+{
+ /* Compute the total number of keywords. */
+ _total_keys = 0;
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ _total_keys++;
+
+ /* Compute the minimum and maximum keyword length. */
+ _max_key_len = INT_MIN;
+ _min_key_len = INT_MAX;
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ if (_max_key_len < keyword->_allchars_length)
+ _max_key_len = keyword->_allchars_length;
+ if (_min_key_len > keyword->_allchars_length)
+ _min_key_len = keyword->_allchars_length;
+ }
+
+ /* Exit program if an empty string is used as keyword, since the comparison
+ expressions don't work correctly for looking up an empty string. */
+ if (_min_key_len == 0)
+ {
+ fprintf (stderr, "Empty input keyword is not allowed.\n"
+ "To recognize an empty input keyword, your code should check for\n"
+ "len == 0 before calling the gperf generated lookup function.\n");
+ exit (1);
+ }
+
+ /* Exit program if the characters in the keywords are not in the required
+ range. */
+ if (option[SEVENBIT])
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ const char *k = keyword->_allchars;
+ for (int i = keyword->_allchars_length; i > 0; k++, i--)
+ if (!(static_cast<unsigned char>(*k) < 128))
+ {
+ fprintf (stderr, "Option --seven-bit has been specified,\n"
+ "but keyword \"%.*s\" contains non-ASCII characters.\n"
+ "Try removing option --seven-bit.\n",
+ keyword->_allchars_length, keyword->_allchars);
+ exit (1);
+ }
+ }
+}
+
+/* ====================== Finding good byte positions ====================== */
+
+/* Computes the upper bound on the indices passed to asso_values[],
+ assuming no alpha_increments. */
+unsigned int
+Search::compute_alpha_size () const
+{
+ return (option[SEVENBIT] ? 128 : 256);
+}
+
+/* Computes the unification rules between different asso_values[c],
+ assuming no alpha_increments. */
+unsigned int *
+Search::compute_alpha_unify () const
+{
+ if (option[UPPERLOWER])
+ {
+ /* Uppercase to lowercase mapping. */
+ unsigned int alpha_size = compute_alpha_size();
+ unsigned int *alpha_unify = new unsigned int[alpha_size];
+ for (unsigned int c = 0; c < alpha_size; c++)
+ alpha_unify[c] = c;
+ for (unsigned int c = 'A'; c <= 'Z'; c++)
+ alpha_unify[c] = c + ('a'-'A');
+ return alpha_unify;
+ }
+ else
+ /* Identity mapping. */
+ return NULL;
+}
+
+/* Initializes each keyword's _selchars array. */
+void
+Search::init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify) const
+{
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ temp->first()->init_selchars_tuple(positions, alpha_unify);
+}
+
+/* Deletes each keyword's _selchars array. */
+void
+Search::delete_selchars () const
+{
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ temp->first()->delete_selchars();
+}
+
+/* Count the duplicate keywords that occur with a given set of positions.
+ In other words, it returns the difference
+ # K - # proj1 (K)
+ where K is the multiset of given keywords. */
+unsigned int
+Search::count_duplicates_tuple (const Positions& positions, const unsigned int *alpha_unify) const
+{
+ /* Run through the keyword list and count the duplicates incrementally.
+ The result does not depend on the order of the keyword list, thanks to
+ the formula above. */
+ init_selchars_tuple (positions, alpha_unify);
+
+ unsigned int count = 0;
+ {
+ Hash_Table representatives (_total_keys, option[NOLENGTH]);
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ if (representatives.insert (keyword))
+ count++;
+ }
+ }
+
+ delete_selchars ();
+
+ return count;
+}
+
+/* Find good key positions. */
+
+void
+Search::find_positions ()
+{
+ /* If the user gave the key positions, we use them. */
+ if (option[POSITIONS])
+ {
+ _key_positions = option.get_key_positions();
+ return;
+ }
+
+ /* Compute preliminary alpha_unify table. */
+ unsigned int *alpha_unify = compute_alpha_unify ();
+
+ /* 1. Find positions that must occur in order to distinguish duplicates. */
+ Positions mandatory;
+
+ if (!option[DUP])
+ {
+ for (KeywordExt_List *l1 = _head; l1 && l1->rest(); l1 = l1->rest())
+ {
+ KeywordExt *keyword1 = l1->first();
+ for (KeywordExt_List *l2 = l1->rest(); l2; l2 = l2->rest())
+ {
+ KeywordExt *keyword2 = l2->first();
+
+ /* If keyword1 and keyword2 have the same length and differ
+ in just one position, and it is not the last character,
+ this position is mandatory. */
+ if (keyword1->_allchars_length == keyword2->_allchars_length)
+ {
+ int n = keyword1->_allchars_length;
+ int i;
+ for (i = 0; i < n - 1; i++)
+ {
+ unsigned char c1 = keyword1->_allchars[i];
+ unsigned char c2 = keyword2->_allchars[i];
+ if (option[UPPERLOWER])
+ {
+ if (c1 >= 'A' && c1 <= 'Z')
+ c1 += 'a' - 'A';
+ if (c2 >= 'A' && c2 <= 'Z')
+ c2 += 'a' - 'A';
+ }
+ if (c1 != c2)
+ break;
+ }
+ if (i < n - 1)
+ {
+ int j;
+ for (j = i + 1; j < n; j++)
+ {
+ unsigned char c1 = keyword1->_allchars[j];
+ unsigned char c2 = keyword2->_allchars[j];
+ if (option[UPPERLOWER])
+ {
+ if (c1 >= 'A' && c1 <= 'Z')
+ c1 += 'a' - 'A';
+ if (c2 >= 'A' && c2 <= 'Z')
+ c2 += 'a' - 'A';
+ }
+ if (c1 != c2)
+ break;
+ }
+ if (j >= n)
+ {
+ /* Position i is mandatory. */
+ if (!mandatory.contains (i))
+ mandatory.add (i);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* 2. Add positions, as long as this decreases the duplicates count. */
+ int imax = (_max_key_len - 1 < Positions::MAX_KEY_POS - 1
+ ? _max_key_len - 1 : Positions::MAX_KEY_POS - 1);
+ Positions current = mandatory;
+ unsigned int current_duplicates_count =
+ count_duplicates_tuple (current, alpha_unify);
+ for (;;)
+ {
+ Positions best;
+ unsigned int best_duplicates_count = UINT_MAX;
+
+ for (int i = imax; i >= -1; i--)
+ if (!current.contains (i))
+ {
+ Positions tryal = current;
+ tryal.add (i);
+ unsigned int try_duplicates_count =
+ count_duplicates_tuple (tryal, alpha_unify);
+
+ /* We prefer 'try' to 'best' if it produces less duplicates,
+ or if it produces the same number of duplicates but with
+ a more efficient hash function. */
+ if (try_duplicates_count < best_duplicates_count
+ || (try_duplicates_count == best_duplicates_count && i >= 0))
+ {
+ best = tryal;
+ best_duplicates_count = try_duplicates_count;
+ }
+ }
+
+ /* Stop adding positions when it gives no improvement. */
+ if (best_duplicates_count >= current_duplicates_count)
+ break;
+
+ current = best;
+ current_duplicates_count = best_duplicates_count;
+ }
+
+ /* 3. Remove positions, as long as this doesn't increase the duplicates
+ count. */
+ for (;;)
+ {
+ Positions best;
+ unsigned int best_duplicates_count = UINT_MAX;
+
+ for (int i = imax; i >= -1; i--)
+ if (current.contains (i) && !mandatory.contains (i))
+ {
+ Positions tryal = current;
+ tryal.remove (i);
+ unsigned int try_duplicates_count =
+ count_duplicates_tuple (tryal, alpha_unify);
+
+ /* We prefer 'try' to 'best' if it produces less duplicates,
+ or if it produces the same number of duplicates but with
+ a more efficient hash function. */
+ if (try_duplicates_count < best_duplicates_count
+ || (try_duplicates_count == best_duplicates_count && i == -1))
+ {
+ best = tryal;
+ best_duplicates_count = try_duplicates_count;
+ }
+ }
+
+ /* Stop removing positions when it gives no improvement. */
+ if (best_duplicates_count > current_duplicates_count)
+ break;
+
+ current = best;
+ current_duplicates_count = best_duplicates_count;
+ }
+
+ /* 4. Replace two positions by one, as long as this doesn't increase the
+ duplicates count. */
+ for (;;)
+ {
+ Positions best;
+ unsigned int best_duplicates_count = UINT_MAX;
+
+ for (int i1 = imax; i1 >= -1; i1--)
+ if (current.contains (i1) && !mandatory.contains (i1))
+ for (int i2 = imax; i2 >= -1; i2--)
+ if (current.contains (i2) && !mandatory.contains (i2) && i2 != i1)
+ for (int i3 = imax; i3 >= 0; i3--)
+ if (!current.contains (i3))
+ {
+ Positions tryal = current;
+ tryal.remove (i1);
+ tryal.remove (i2);
+ tryal.add (i3);
+ unsigned int try_duplicates_count =
+ count_duplicates_tuple (tryal, alpha_unify);
+
+ /* We prefer 'try' to 'best' if it produces less duplicates,
+ or if it produces the same number of duplicates but with
+ a more efficient hash function. */
+ if (try_duplicates_count < best_duplicates_count
+ || (try_duplicates_count == best_duplicates_count
+ && (i1 == -1 || i2 == -1 || i3 >= 0)))
+ {
+ best = tryal;
+ best_duplicates_count = try_duplicates_count;
+ }
+ }
+
+ /* Stop removing positions when it gives no improvement. */
+ if (best_duplicates_count > current_duplicates_count)
+ break;
+
+ current = best;
+ current_duplicates_count = best_duplicates_count;
+ }
+
+ /* That's it. Hope it's good enough. */
+ _key_positions = current;
+
+ if (option[DEBUG])
+ {
+ /* Print the result. */
+ fprintf (stderr, "\nComputed positions: ");
+ PositionReverseIterator iter = _key_positions.reviterator();
+ bool seen_lastchar = false;
+ bool first = true;
+ for (int i; (i = iter.next ()) != PositionReverseIterator::EOS; )
+ {
+ if (!first)
+ fprintf (stderr, ", ");
+ if (i == Positions::LASTCHAR)
+ seen_lastchar = true;
+ else
+ {
+ fprintf (stderr, "%d", i + 1);
+ first = false;
+ }
+ }
+ if (seen_lastchar)
+ {
+ if (!first)
+ fprintf (stderr, ", ");
+ fprintf (stderr, "$");
+ }
+ fprintf (stderr, "\n");
+ }
+
+ /* Free preliminary alpha_unify table. */
+ delete[] alpha_unify;
+}
+
+/* Count the duplicate keywords that occur with the found set of positions.
+ In other words, it returns the difference
+ # K - # proj1 (K)
+ where K is the multiset of given keywords. */
+unsigned int
+Search::count_duplicates_tuple () const
+{
+ unsigned int *alpha_unify = compute_alpha_unify ();
+ unsigned int count = count_duplicates_tuple (_key_positions, alpha_unify);
+ delete[] alpha_unify;
+ return count;
+}
+
+/* ===================== Finding good alpha increments ===================== */
+
+/* Computes the upper bound on the indices passed to asso_values[]. */
+unsigned int
+Search::compute_alpha_size (const unsigned int *alpha_inc) const
+{
+ unsigned int max_alpha_inc = 0;
+ for (int i = 0; i < _max_key_len; i++)
+ if (max_alpha_inc < alpha_inc[i])
+ max_alpha_inc = alpha_inc[i];
+ return (option[SEVENBIT] ? 128 : 256) + max_alpha_inc;
+}
+
+/* Computes the unification rules between different asso_values[c]. */
+unsigned int *
+Search::compute_alpha_unify (const Positions& positions, const unsigned int *alpha_inc) const
+{
+ if (option[UPPERLOWER])
+ {
+ /* Without alpha increments, we would simply unify
+ 'A' -> 'a', ..., 'Z' -> 'z'.
+ But when a keyword contains at position i a character c,
+ we have the constraint
+ asso_values[tolower(c) + alpha_inc[i]] ==
+ asso_values[toupper(c) + alpha_inc[i]].
+ This introduces a unification
+ toupper(c) + alpha_inc[i] -> tolower(c) + alpha_inc[i].
+ Note that this unification can extend outside the range of
+ ASCII letters! But still every unified character pair is at
+ a distance of 'a'-'A' = 32, or (after chained unification)
+ at a multiple of 32. So in the end the alpha_unify vector has
+ the form c -> c + 32 * f(c) where f(c) is a nonnegative
+ integer. */
+ unsigned int alpha_size = compute_alpha_size (alpha_inc);
+
+ unsigned int *alpha_unify = new unsigned int[alpha_size];
+ for (unsigned int c = 0; c < alpha_size; c++)
+ alpha_unify[c] = c;
+
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ /* Iterate through the selected character positions. */
+ PositionIterator iter = positions.iterator(keyword->_allchars_length);
+
+ for (int i; (i = iter.next ()) != PositionIterator::EOS; )
+ {
+ unsigned int c;
+ if (i == Positions::LASTCHAR)
+ c = static_cast<unsigned char>(keyword->_allchars[keyword->_allchars_length - 1]);
+ else if (i < keyword->_allchars_length)
+ c = static_cast<unsigned char>(keyword->_allchars[i]);
+ else
+ abort ();
+ if (c >= 'A' && c <= 'Z')
+ c += 'a' - 'A';
+ if (c >= 'a' && c <= 'z')
+ {
+ if (i != Positions::LASTCHAR)
+ c += alpha_inc[i];
+ /* Unify c with c - ('a'-'A'). */
+ unsigned int d = alpha_unify[c];
+ unsigned int b = c - ('a'-'A');
+ for (int a = b; a >= 0 && alpha_unify[a] == b; a -= ('a'-'A'))
+ alpha_unify[a] = d;
+ }
+ }
+ }
+ return alpha_unify;
+ }
+ else
+ /* Identity mapping. */
+ return NULL;
+}
+
+/* Initializes each keyword's _selchars array. */
+void
+Search::init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc) const
+{
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ temp->first()->init_selchars_multiset(positions, alpha_unify, alpha_inc);
+}
+
+/* Count the duplicate keywords that occur with the given set of positions
+ and a given alpha_inc[] array.
+ In other words, it returns the difference
+ # K - # proj2 (proj1 (K))
+ where K is the multiset of given keywords. */
+unsigned int
+Search::count_duplicates_multiset (const unsigned int *alpha_inc) const
+{
+ /* Run through the keyword list and count the duplicates incrementally.
+ The result does not depend on the order of the keyword list, thanks to
+ the formula above. */
+ unsigned int *alpha_unify = compute_alpha_unify (_key_positions, alpha_inc);
+ init_selchars_multiset (_key_positions, alpha_unify, alpha_inc);
+
+ unsigned int count = 0;
+ {
+ Hash_Table representatives (_total_keys, option[NOLENGTH]);
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ if (representatives.insert (keyword))
+ count++;
+ }
+ }
+
+ delete_selchars ();
+ delete[] alpha_unify;
+
+ return count;
+}
+
+/* Find good _alpha_inc[]. */
+
+void
+Search::find_alpha_inc ()
+{
+ /* The goal is to choose _alpha_inc[] such that it doesn't introduce
+ artificial duplicates.
+ In other words, the goal is # proj2 (proj1 (K)) = # proj1 (K). */
+ unsigned int duplicates_goal = count_duplicates_tuple ();
+
+ /* Start with zero increments. This is sufficient in most cases. */
+ unsigned int *current = new unsigned int [_max_key_len];
+ for (int i = 0; i < _max_key_len; i++)
+ current[i] = 0;
+ unsigned int current_duplicates_count = count_duplicates_multiset (current);
+
+ if (current_duplicates_count > duplicates_goal)
+ {
+ /* Look which _alpha_inc[i] we are free to increment. */
+ unsigned int nindices;
+ {
+ nindices = 0;
+ PositionIterator iter = _key_positions.iterator(_max_key_len);
+ for (;;)
+ {
+ int key_pos = iter.next ();
+ if (key_pos == PositionIterator::EOS)
+ break;
+ if (key_pos != Positions::LASTCHAR)
+ nindices++;
+ }
+ }
+
+ DYNAMIC_ARRAY (indices, unsigned int, nindices);
+ {
+ unsigned int j = 0;
+ PositionIterator iter = _key_positions.iterator(_max_key_len);
+ for (;;)
+ {
+ int key_pos = iter.next ();
+ if (key_pos == PositionIterator::EOS)
+ break;
+ if (key_pos != Positions::LASTCHAR)
+ indices[j++] = key_pos;
+ }
+ if (!(j == nindices))
+ abort ();
+ }
+
+ /* Perform several rounds of searching for a good alpha increment.
+ Each round reduces the number of artificial collisions by adding
+ an increment in a single key position. */
+ DYNAMIC_ARRAY (best, unsigned int, _max_key_len);
+ DYNAMIC_ARRAY (tryal, unsigned int, _max_key_len);
+ do
+ {
+ /* An increment of 1 is not always enough. Try higher increments
+ also. */
+ for (unsigned int inc = 1; ; inc++)
+ {
+ unsigned int best_duplicates_count = UINT_MAX;
+
+ for (unsigned int j = 0; j < nindices; j++)
+ {
+ memcpy (tryal, current, _max_key_len * sizeof (unsigned int));
+ tryal[indices[j]] += inc;
+ unsigned int try_duplicates_count =
+ count_duplicates_multiset (tryal);
+
+ /* We prefer 'try' to 'best' if it produces less
+ duplicates. */
+ if (try_duplicates_count < best_duplicates_count)
+ {
+ memcpy (best, tryal, _max_key_len * sizeof (unsigned int));
+ best_duplicates_count = try_duplicates_count;
+ }
+ }
+
+ /* Stop this round when we got an improvement. */
+ if (best_duplicates_count < current_duplicates_count)
+ {
+ memcpy (current, best, _max_key_len * sizeof (unsigned int));
+ current_duplicates_count = best_duplicates_count;
+ break;
+ }
+ }
+ }
+ while (current_duplicates_count > duplicates_goal);
+ FREE_DYNAMIC_ARRAY (tryal);
+ FREE_DYNAMIC_ARRAY (best);
+
+ if (option[DEBUG])
+ {
+ /* Print the result. */
+ fprintf (stderr, "\nComputed alpha increments: ");
+ bool first = true;
+ for (unsigned int j = nindices; j-- > 0; )
+ if (current[indices[j]] != 0)
+ {
+ if (!first)
+ fprintf (stderr, ", ");
+ fprintf (stderr, "%u:+%u",
+ indices[j] + 1, current[indices[j]]);
+ first = false;
+ }
+ fprintf (stderr, "\n");
+ }
+ FREE_DYNAMIC_ARRAY (indices);
+ }
+
+ _alpha_inc = current;
+ _alpha_size = compute_alpha_size (_alpha_inc);
+ _alpha_unify = compute_alpha_unify (_key_positions, _alpha_inc);
+}
+
+/* ======================= Finding good asso_values ======================== */
+
+/* Initializes the asso_values[] related parameters. */
+
+void
+Search::prepare_asso_values ()
+{
+ KeywordExt_List *temp;
+
+ /* Initialize each keyword's _selchars array. */
+ init_selchars_multiset(_key_positions, _alpha_unify, _alpha_inc);
+
+ /* Compute the maximum _selchars_length over all keywords. */
+ _max_selchars_length = _key_positions.iterator(_max_key_len).remaining();
+
+ /* Check for duplicates, i.e. keywords with the same _selchars array
+ (and - if !option[NOLENGTH] - also the same length).
+ We deal with these by building an equivalence class, so that only
+ 1 keyword is representative of the entire collection. Only this
+ representative remains in the keyword list; the others are accessible
+ through the _duplicate_link chain, starting at the representative.
+ This *greatly* simplifies processing during later stages of the program.
+ Set _total_duplicates and _list_len = _total_keys - _total_duplicates. */
+ {
+ _list_len = _total_keys;
+ _total_duplicates = 0;
+ /* Make hash table for efficiency. */
+ Hash_Table representatives (_list_len, option[NOLENGTH]);
+
+ KeywordExt_List *prev = NULL; /* list node before temp */
+ for (temp = _head; temp; )
+ {
+ KeywordExt *keyword = temp->first();
+ KeywordExt *other_keyword = representatives.insert (keyword);
+ KeywordExt_List *garbage = NULL;
+
+ if (other_keyword)
+ {
+ _total_duplicates++;
+ _list_len--;
+ /* Remove keyword from the main list. */
+ prev->rest() = temp->rest();
+ garbage = temp;
+ /* And insert it on other_keyword's duplicate list. */
+ keyword->_duplicate_link = other_keyword->_duplicate_link;
+ other_keyword->_duplicate_link = keyword;
+
+ /* Complain if user hasn't enabled the duplicate option. */
+ if (!option[DUP] || option[DEBUG])
+ {
+ fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"",
+ keyword->_allchars_length, keyword->_allchars,
+ other_keyword->_allchars_length, other_keyword->_allchars);
+ for (int j = 0; j < keyword->_selchars_length; j++)
+ putc (keyword->_selchars[j], stderr);
+ fprintf (stderr, "\".\n");
+ }
+ }
+ else
+ {
+ keyword->_duplicate_link = NULL;
+ prev = temp;
+ }
+ temp = temp->rest();
+ if (garbage)
+ delete garbage;
+ }
+ if (option[DEBUG])
+ representatives.dump();
+ }
+
+ /* Exit program if duplicates exists and option[DUP] not set, since we
+ don't want to continue in this case. (We don't want to turn on
+ option[DUP] implicitly, because the generated code is usually much
+ slower. */
+ if (_total_duplicates)
+ {
+ if (option[DUP])
+ fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n",
+ _total_duplicates);
+ else
+ {
+ fprintf (stderr, "%d input keys have identical hash values,\n",
+ _total_duplicates);
+ if (option[POSITIONS])
+ fprintf (stderr, "try different key positions or use option -D.\n");
+ else
+ fprintf (stderr, "use option -D.\n");
+ exit (1);
+ }
+ }
+
+ /* Compute the occurrences of each character in the alphabet. */
+ _occurrences = new int[_alpha_size];
+ memset (_occurrences, 0, _alpha_size * sizeof (_occurrences[0]));
+ for (temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ const unsigned int *ptr = keyword->_selchars;
+ for (int count = keyword->_selchars_length; count > 0; ptr++, count--)
+ _occurrences[*ptr]++;
+ }
+
+ /* Memory allocation. */
+ _asso_values = new int[_alpha_size];
+
+ int non_linked_length = _list_len;
+ unsigned int asso_value_max;
+
+ asso_value_max =
+ static_cast<unsigned int>(non_linked_length * option.get_size_multiple());
+ /* Round up to the next power of two. This makes it easy to ensure
+ an _asso_value[c] is >= 0 and < asso_value_max. Also, the jump value
+ being odd, it guarantees that Search::try_asso_value() will iterate
+ through different values for _asso_value[c]. */
+ if (asso_value_max == 0)
+ asso_value_max = 1;
+ asso_value_max |= asso_value_max >> 1;
+ asso_value_max |= asso_value_max >> 2;
+ asso_value_max |= asso_value_max >> 4;
+ asso_value_max |= asso_value_max >> 8;
+ asso_value_max |= asso_value_max >> 16;
+ asso_value_max++;
+ _asso_value_max = asso_value_max;
+
+ /* Given the bound for _asso_values[c], we have a bound for the possible
+ hash values, as computed in compute_hash(). */
+ _max_hash_value = (option[NOLENGTH] ? 0 : _max_key_len)
+ + (_asso_value_max - 1) * _max_selchars_length;
+ /* Allocate a sparse bit vector for detection of collisions of hash
+ values. */
+ _collision_detector = new Bool_Array (_max_hash_value + 1);
+
+ if (option[DEBUG])
+ {
+ fprintf (stderr, "total non-linked keys = %d\nmaximum associated value is %d"
+ "\nmaximum size of generated hash table is %d\n",
+ non_linked_length, asso_value_max, _max_hash_value);
+
+ int field_width;
+
+ field_width = 0;
+ {
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ if (field_width < keyword->_selchars_length)
+ field_width = keyword->_selchars_length;
+ }
+ }
+
+ fprintf (stderr, "\ndumping the keyword list without duplicates\n");
+ fprintf (stderr, "keyword #, %*s, keyword\n", field_width, "keysig");
+ int i = 0;
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ fprintf (stderr, "%9d, ", ++i);
+ if (field_width > keyword->_selchars_length)
+ fprintf (stderr, "%*s", field_width - keyword->_selchars_length, "");
+ for (int j = 0; j < keyword->_selchars_length; j++)
+ putc (keyword->_selchars[j], stderr);
+ fprintf (stderr, ", %.*s\n",
+ keyword->_allchars_length, keyword->_allchars);
+ }
+ fprintf (stderr, "\nend of keyword list\n\n");
+ }
+
+ if (option[RANDOM] || option.get_jump () == 0)
+ /* We will use rand(), so initialize the random number generator. */
+ srand (static_cast<long>(time (0)));
+
+ _initial_asso_value = (option[RANDOM] ? -1 : option.get_initial_asso_value ());
+ _jump = option.get_jump ();
+}
+
+/* Finds some _asso_values[] that fit. */
+
+/* The idea is to choose the _asso_values[] one by one, in a way that
+ a choice that has been made never needs to be undone later. This
+ means that we split the work into several steps. Each step chooses
+ one or more _asso_values[c]. The result of choosing one or more
+ _asso_values[c] is that the partitioning of the keyword set gets
+ broader.
+ Look at this partitioning: After every step, the _asso_values[] of a
+ certain set C of characters are undetermined. (At the beginning, C
+ is the set of characters c with _occurrences[c] > 0. At the end, C
+ is empty.) To each keyword K, we associate the multiset of _selchars
+ for which the _asso_values[] are undetermined:
+ K --> K->_selchars intersect C.
+ Consider two keywords equivalent if their value under this mapping is
+ the same. This introduces an equivalence relation on the set of
+ keywords. The equivalence classes partition the keyword set. (At the
+ beginning, the partition is the finest possible: each K is an equivalence
+ class by itself, because all K have a different _selchars. At the end,
+ all K have been merged into a single equivalence class.)
+ The partition before a step is always a refinement of the partition
+ after the step.
+ We choose the steps in such a way that the partition really becomes
+ broader at each step. (A step that only chooses an _asso_values[c]
+ without changing the partition is better merged with the previous step,
+ to avoid useless backtracking.) */
+
+struct EquivalenceClass
+{
+ /* The keywords in this equivalence class. */
+ KeywordExt_List * _keywords;
+ KeywordExt_List * _keywords_last;
+ /* The number of keywords in this equivalence class. */
+ unsigned int _cardinality;
+ /* The undetermined selected characters for the keywords in this
+ equivalence class, as a canonically reordered multiset. */
+ unsigned int * _undetermined_chars;
+ unsigned int _undetermined_chars_length;
+
+ EquivalenceClass * _next;
+};
+
+struct Step
+{
+ /* The characters whose values are being determined in this step. */
+ unsigned int _changing_count;
+ unsigned int * _changing;
+ /* Exclusive upper bound for the _asso_values[c] of this step.
+ A power of 2. */
+ unsigned int _asso_value_max;
+ /* The characters whose values will be determined after this step. */
+ bool * _undetermined;
+ /* The keyword set partition after this step. */
+ EquivalenceClass * _partition;
+ /* The expected number of iterations in this step. */
+ double _expected_lower;
+ double _expected_upper;
+
+ Step * _next;
+};
+
+static inline bool
+equals (const unsigned int *ptr1, const unsigned int *ptr2, unsigned int len)
+{
+ while (len > 0)
+ {
+ if (*ptr1 != *ptr2)
+ return false;
+ ptr1++;
+ ptr2++;
+ len--;
+ }
+ return true;
+}
+
+EquivalenceClass *
+Search::compute_partition (bool *undetermined) const
+{
+ EquivalenceClass *partition = NULL;
+ EquivalenceClass *partition_last = NULL;
+ for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ /* Compute the undetermined characters for this keyword. */
+ unsigned int *undetermined_chars =
+ new unsigned int[keyword->_selchars_length];
+ unsigned int undetermined_chars_length = 0;
+
+ for (int i = 0; i < keyword->_selchars_length; i++)
+ if (undetermined[keyword->_selchars[i]])
+ undetermined_chars[undetermined_chars_length++] = keyword->_selchars[i];
+
+ /* Look up the equivalence class to which this keyword belongs. */
+ EquivalenceClass *equclass;
+ for (equclass = partition; equclass; equclass = equclass->_next)
+ if (equclass->_undetermined_chars_length == undetermined_chars_length
+ && equals (equclass->_undetermined_chars, undetermined_chars,
+ undetermined_chars_length))
+ break;
+ if (equclass == NULL)
+ {
+ equclass = new EquivalenceClass();
+ equclass->_keywords = NULL;
+ equclass->_keywords_last = NULL;
+ equclass->_cardinality = 0;
+ equclass->_undetermined_chars = undetermined_chars;
+ equclass->_undetermined_chars_length = undetermined_chars_length;
+ equclass->_next = NULL;
+ if (partition)
+ partition_last->_next = equclass;
+ else
+ partition = equclass;
+ partition_last = equclass;
+ }
+ else
+ delete[] undetermined_chars;
+
+ /* Add the keyword to the equivalence class. */
+ KeywordExt_List *cons = new KeywordExt_List(keyword);
+ if (equclass->_keywords)
+ equclass->_keywords_last->rest() = cons;
+ else
+ equclass->_keywords = cons;
+ equclass->_keywords_last = cons;
+ equclass->_cardinality++;
+ }
+
+ /* Free some of the allocated memory. The caller doesn't need it. */
+ for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
+ delete[] cls->_undetermined_chars;
+
+ return partition;
+}
+
+static void
+delete_partition (EquivalenceClass *partition)
+{
+ while (partition != NULL)
+ {
+ EquivalenceClass *equclass = partition;
+ partition = equclass->_next;
+ delete_list (equclass->_keywords);
+ //delete[] equclass->_undetermined_chars; // already freed above
+ delete equclass;
+ }
+}
+
+/* Compute the possible number of collisions when _asso_values[c] is
+ chosen, leading to the given partition. */
+unsigned int
+Search::count_possible_collisions (EquivalenceClass *partition, unsigned int c) const
+{
+ /* Every equivalence class p is split according to the frequency of
+ occurrence of c, leading to equivalence classes p1, p2, ...
+ This leads to (|p|^2 - |p1|^2 - |p2|^2 - ...)/2 possible collisions.
+ Return the sum of this expression over all equivalence classes. */
+ unsigned int sum = 0;
+ unsigned int m = _max_selchars_length;
+ DYNAMIC_ARRAY (split_cardinalities, unsigned int, m + 1);
+ for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
+ {
+ for (unsigned int i = 0; i <= m; i++)
+ split_cardinalities[i] = 0;
+
+ for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ unsigned int count = 0;
+ for (int i = 0; i < keyword->_selchars_length; i++)
+ if (keyword->_selchars[i] == c)
+ count++;
+
+ split_cardinalities[count]++;
+ }
+
+ sum += cls->_cardinality * cls->_cardinality;
+ for (unsigned int i = 0; i <= m; i++)
+ sum -= split_cardinalities[i] * split_cardinalities[i];
+ }
+ FREE_DYNAMIC_ARRAY (split_cardinalities);
+ return sum;
+}
+
+/* Test whether adding c to the undetermined characters changes the given
+ partition. */
+bool
+Search::unchanged_partition (EquivalenceClass *partition, unsigned int c) const
+{
+ for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
+ {
+ unsigned int first_count = UINT_MAX;
+
+ for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+
+ unsigned int count = 0;
+ for (int i = 0; i < keyword->_selchars_length; i++)
+ if (keyword->_selchars[i] == c)
+ count++;
+
+ if (temp == cls->_keywords)
+ first_count = count;
+ else if (count != first_count)
+ /* c would split this equivalence class. */
+ return false;
+ }
+ }
+ return true;
+}
+
+void
+Search::find_asso_values ()
+{
+ Step *steps;
+
+ /* Determine the steps, starting with the last one. */
+ {
+ bool *undetermined;
+ bool *determined;
+
+ steps = NULL;
+
+ undetermined = new bool[_alpha_size];
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ undetermined[c] = false;
+
+ determined = new bool[_alpha_size];
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ determined[c] = true;
+
+ for (;;)
+ {
+ /* Compute the partition that needs to be refined. */
+ EquivalenceClass *partition = compute_partition (undetermined);
+
+ /* Determine the main character to be chosen in this step.
+ Choosing such a character c has the effect of splitting every
+ equivalence class (according the the frequency of occurrence of c).
+ We choose the c with the minimum number of possible collisions,
+ so that characters which lead to a large number of collisions get
+ handled early during the search. */
+ unsigned int chosen_c;
+ unsigned int chosen_possible_collisions;
+ {
+ unsigned int best_c = 0;
+ unsigned int best_possible_collisions = UINT_MAX;
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (_occurrences[c] > 0 && determined[c])
+ {
+ unsigned int possible_collisions =
+ count_possible_collisions (partition, c);
+ if (possible_collisions < best_possible_collisions)
+ {
+ best_c = c;
+ best_possible_collisions = possible_collisions;
+ }
+ }
+ if (best_possible_collisions == UINT_MAX)
+ {
+ /* All c with _occurrences[c] > 0 are undetermined. We are
+ are the starting situation and don't need any more step. */
+ delete_partition (partition);
+ break;
+ }
+ chosen_c = best_c;
+ chosen_possible_collisions = best_possible_collisions;
+ }
+
+ /* We need one more step. */
+ Step *step = new Step();
+
+ step->_undetermined = new bool[_alpha_size];
+ memcpy (step->_undetermined, undetermined, _alpha_size*sizeof(bool));
+
+ step->_partition = partition;
+
+ /* Now determine how the equivalence classes will be before this
+ step. */
+ undetermined[chosen_c] = true;
+ partition = compute_partition (undetermined);
+
+ /* Now determine which other characters should be determined in this
+ step, because they will not change the equivalence classes at
+ this point. It is the set of all c which, for all equivalence
+ classes, have the same frequency of occurrence in every keyword
+ of the equivalence class. */
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (_occurrences[c] > 0 && determined[c]
+ && unchanged_partition (partition, c))
+ {
+ undetermined[c] = true;
+ determined[c] = false;
+ }
+
+ /* main_c must be one of these. */
+ if (determined[chosen_c])
+ abort ();
+
+ /* Now the set of changing characters of this step. */
+ unsigned int changing_count;
+
+ changing_count = 0;
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (undetermined[c] && !step->_undetermined[c])
+ changing_count++;
+
+ unsigned int *changing = new unsigned int[changing_count];
+ changing_count = 0;
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (undetermined[c] && !step->_undetermined[c])
+ changing[changing_count++] = c;
+
+ step->_changing = changing;
+ step->_changing_count = changing_count;
+
+ step->_asso_value_max = _asso_value_max;
+
+ step->_expected_lower =
+ exp (static_cast<double>(chosen_possible_collisions)
+ / static_cast<double>(_max_hash_value));
+ step->_expected_upper =
+ exp (static_cast<double>(chosen_possible_collisions)
+ / static_cast<double>(_asso_value_max));
+
+ delete_partition (partition);
+
+ step->_next = steps;
+ steps = step;
+ }
+
+ delete[] determined;
+ delete[] undetermined;
+ }
+
+ if (option[DEBUG])
+ {
+ unsigned int stepno = 0;
+ for (Step *step = steps; step; step = step->_next)
+ {
+ stepno++;
+ fprintf (stderr, "Step %u chooses _asso_values[", stepno);
+ for (unsigned int i = 0; i < step->_changing_count; i++)
+ {
+ if (i > 0)
+ fprintf (stderr, ",");
+ fprintf (stderr, "'%c'", step->_changing[i]);
+ }
+ fprintf (stderr, "], expected number of iterations between %g and %g.\n",
+ step->_expected_lower, step->_expected_upper);
+ fprintf (stderr, "Keyword equivalence classes:\n");
+ for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
+ {
+ fprintf (stderr, "\n");
+ for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
+ {
+ KeywordExt *keyword = temp->first();
+ fprintf (stderr, " %.*s\n",
+ keyword->_allchars_length, keyword->_allchars);
+ }
+ }
+ fprintf (stderr, "\n");
+ }
+ }
+
+ /* Initialize _asso_values[]. (The value given here matters only
+ for those c which occur in all keywords with equal multiplicity.) */
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ _asso_values[c] = 0;
+
+ unsigned int stepno = 0;
+ for (Step *step = steps; step; step = step->_next)
+ {
+ stepno++;
+
+ /* Initialize the asso_values[]. */
+ unsigned int k = step->_changing_count;
+ for (unsigned int i = 0; i < k; i++)
+ {
+ unsigned int c = step->_changing[i];
+ _asso_values[c] =
+ (_initial_asso_value < 0 ? rand () : _initial_asso_value)
+ & (step->_asso_value_max - 1);
+ }
+
+ unsigned int iterations = 0;
+ DYNAMIC_ARRAY (iter, unsigned int, k);
+ for (unsigned int i = 0; i < k; i++)
+ iter[i] = 0;
+ unsigned int ii = (_jump != 0 ? k - 1 : 0);
+
+ for (;;)
+ {
+ /* Test whether these asso_values[] lead to collisions among
+ the equivalence classes that should be collision-free. */
+ bool has_collision = false;
+ for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
+ {
+ /* Iteration Number array is a win, O(1) initialization time! */
+ _collision_detector->clear ();
+
+ for (KeywordExt_List *ptr = cls->_keywords; ptr; ptr = ptr->rest())
+ {
+ KeywordExt *keyword = ptr->first();
+
+ /* Compute the new hash code for the keyword, leaving apart
+ the yet undetermined asso_values[]. */
+ int hashcode;
+ {
+ int sum = option[NOLENGTH] ? 0 : keyword->_allchars_length;
+ const unsigned int *p = keyword->_selchars;
+ int i = keyword->_selchars_length;
+ for (; i > 0; p++, i--)
+ if (!step->_undetermined[*p])
+ sum += _asso_values[*p];
+ hashcode = sum;
+ }
+
+ /* See whether it collides with another keyword's hash code,
+ from the same equivalence class. */
+ if (_collision_detector->set_bit (hashcode))
+ {
+ has_collision = true;
+ break;
+ }
+ }
+
+ /* Don't need to continue looking at the other equivalence
+ classes if we already have found a collision. */
+ if (has_collision)
+ break;
+ }
+
+ iterations++;
+ if (!has_collision)
+ break;
+
+ /* Try other asso_values[]. */
+ if (_jump != 0)
+ {
+ /* The way we try various values for
+ asso_values[step->_changing[0],...step->_changing[k-1]]
+ is like this:
+ for (bound = 0,1,...)
+ for (ii = 0,...,k-1)
+ iter[ii] := bound
+ iter[0..ii-1] := values <= bound
+ iter[ii+1..k-1] := values < bound
+ and
+ asso_values[step->_changing[i]] =
+ _initial_asso_value + iter[i] * _jump.
+ This makes it more likely to find small asso_values[].
+ */
+ unsigned int bound = iter[ii];
+ unsigned int i = 0;
+ while (i < ii)
+ {
+ unsigned int c = step->_changing[i];
+ iter[i]++;
+ _asso_values[c] =
+ (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
+ if (iter[i] <= bound)
+ goto found_next;
+ _asso_values[c] =
+ (_asso_values[c] - iter[i] * _jump)
+ & (step->_asso_value_max - 1);
+ iter[i] = 0;
+ i++;
+ }
+ i = ii + 1;
+ while (i < k)
+ {
+ unsigned int c = step->_changing[i];
+ iter[i]++;
+ _asso_values[c] =
+ (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
+ if (iter[i] < bound)
+ goto found_next;
+ _asso_values[c] =
+ (_asso_values[c] - iter[i] * _jump)
+ & (step->_asso_value_max - 1);
+ iter[i] = 0;
+ i++;
+ }
+ /* Switch from one ii to the next. */
+ {
+ unsigned int c = step->_changing[ii];
+ _asso_values[c] =
+ (_asso_values[c] - bound * _jump)
+ & (step->_asso_value_max - 1);
+ iter[ii] = 0;
+ }
+ /* Here all iter[i] == 0. */
+ ii++;
+ if (ii == k)
+ {
+ ii = 0;
+ bound++;
+ if (bound == step->_asso_value_max)
+ {
+ /* Out of search space! We can either backtrack, or
+ increase the available search space of this step.
+ It seems simpler to choose the latter solution. */
+ step->_asso_value_max = 2 * step->_asso_value_max;
+ if (step->_asso_value_max > _asso_value_max)
+ {
+ _asso_value_max = step->_asso_value_max;
+ /* Reinitialize _max_hash_value. */
+ _max_hash_value =
+ (option[NOLENGTH] ? 0 : _max_key_len)
+ + (_asso_value_max - 1) * _max_selchars_length;
+ /* Reinitialize _collision_detector. */
+ delete _collision_detector;
+ _collision_detector =
+ new Bool_Array (_max_hash_value + 1);
+ }
+ }
+ }
+ {
+ unsigned int c = step->_changing[ii];
+ iter[ii] = bound;
+ _asso_values[c] =
+ (_asso_values[c] + bound * _jump)
+ & (step->_asso_value_max - 1);
+ }
+ found_next: ;
+ }
+ else
+ {
+ /* Random. */
+ unsigned int c = step->_changing[ii];
+ _asso_values[c] =
+ (_asso_values[c] + rand ()) & (step->_asso_value_max - 1);
+ /* Next time, change the next c. */
+ ii++;
+ if (ii == k)
+ ii = 0;
+ }
+ }
+ FREE_DYNAMIC_ARRAY (iter);
+
+ if (option[DEBUG])
+ {
+ fprintf (stderr, "Step %u chose _asso_values[", stepno);
+ for (unsigned int i = 0; i < step->_changing_count; i++)
+ {
+ if (i > 0)
+ fprintf (stderr, ",");
+ fprintf (stderr, "'%c'", step->_changing[i]);
+ }
+ fprintf (stderr, "] in %u iterations.\n", iterations);
+ }
+ }
+
+ /* Free allocated memory. */
+ while (steps != NULL)
+ {
+ Step *step = steps;
+ steps = step->_next;
+ delete[] step->_changing;
+ delete[] step->_undetermined;
+ delete_partition (step->_partition);
+ delete step;
+ }
+}
+
+/* Computes a keyword's hash value, relative to the current _asso_values[],
+ and stores it in keyword->_hash_value. */
+
+inline int
+Search::compute_hash (KeywordExt *keyword) const
+{
+ int sum = option[NOLENGTH] ? 0 : keyword->_allchars_length;
+
+ const unsigned int *p = keyword->_selchars;
+ int i = keyword->_selchars_length;
+ for (; i > 0; p++, i--)
+ sum += _asso_values[*p];
+
+ return keyword->_hash_value = sum;
+}
+
+/* Finds good _asso_values[]. */
+
+void
+Search::find_good_asso_values ()
+{
+ prepare_asso_values ();
+
+ /* Search for good _asso_values[]. */
+ int asso_iteration;
+ if ((asso_iteration = option.get_asso_iterations ()) == 0)
+ /* Try only the given _initial_asso_value and _jump. */
+ find_asso_values ();
+ else
+ {
+ /* Try different pairs of _initial_asso_value and _jump, in the
+ following order:
+ (0, 1)
+ (1, 1)
+ (2, 1) (0, 3)
+ (3, 1) (1, 3)
+ (4, 1) (2, 3) (0, 5)
+ (5, 1) (3, 3) (1, 5)
+ ..... */
+ KeywordExt_List *saved_head = _head;
+ int best_initial_asso_value = 0;
+ int best_jump = 1;
+ int *best_asso_values = new int[_alpha_size];
+ int best_collisions = INT_MAX;
+ int best_max_hash_value = INT_MAX;
+
+ _initial_asso_value = 0; _jump = 1;
+ for (;;)
+ {
+ /* Restore the keyword list in its original order. */
+ _head = copy_list (saved_head);
+ /* Find good _asso_values[]. */
+ find_asso_values ();
+ /* Test whether it is the best solution so far. */
+ int collisions = 0;
+ int max_hash_value = INT_MIN;
+ _collision_detector->clear ();
+ for (KeywordExt_List *ptr = _head; ptr; ptr = ptr->rest())
+ {
+ KeywordExt *keyword = ptr->first();
+ int hashcode = compute_hash (keyword);
+ if (max_hash_value < hashcode)
+ max_hash_value = hashcode;
+ if (_collision_detector->set_bit (hashcode))
+ collisions++;
+ }
+ if (collisions < best_collisions
+ || (collisions == best_collisions
+ && max_hash_value < best_max_hash_value))
+ {
+ memcpy (best_asso_values, _asso_values,
+ _alpha_size * sizeof (_asso_values[0]));
+ best_collisions = collisions;
+ best_max_hash_value = max_hash_value;
+ }
+ /* Delete the copied keyword list. */
+ delete_list (_head);
+
+ if (--asso_iteration == 0)
+ break;
+ /* Prepare for next iteration. */
+ if (_initial_asso_value >= 2)
+ _initial_asso_value -= 2, _jump += 2;
+ else
+ _initial_asso_value += _jump, _jump = 1;
+ }
+ _head = saved_head;
+ /* Install the best found asso_values. */
+ _initial_asso_value = best_initial_asso_value;
+ _jump = best_jump;
+ memcpy (_asso_values, best_asso_values,
+ _alpha_size * sizeof (_asso_values[0]));
+ delete[] best_asso_values;
+ /* The keywords' _hash_value fields are recomputed below. */
+ }
+}
+
+/* ========================================================================= */
+
+/* Comparison function for sorting by increasing _hash_value. */
+static bool
+less_by_hash_value (KeywordExt *keyword1, KeywordExt *keyword2)
+{
+ return keyword1->_hash_value < keyword2->_hash_value;
+}
+
+/* Sorts the keyword list by hash value. */
+
+void
+Search::sort ()
+{
+ _head = mergesort_list (_head, less_by_hash_value);
+}
+
+void
+Search::optimize ()
+{
+ /* Preparations. */
+ prepare ();
+
+ /* Step 1: Finding good byte positions. */
+ find_positions ();
+
+ /* Step 2: Finding good alpha increments. */
+ find_alpha_inc ();
+
+ /* Step 3: Finding good asso_values. */
+ find_good_asso_values ();
+
+ /* Make one final check, just to make sure nothing weird happened.... */
+ _collision_detector->clear ();
+ for (KeywordExt_List *curr_ptr = _head; curr_ptr; curr_ptr = curr_ptr->rest())
+ {
+ KeywordExt *curr = curr_ptr->first();
+ unsigned int hashcode = compute_hash (curr);
+ if (_collision_detector->set_bit (hashcode))
+ {
+ /* This shouldn't happen. proj1, proj2, proj3 must have been
+ computed to be injective on the given keyword set. */
+ fprintf (stderr,
+ "\nInternal error, unexpected duplicate hash code\n");
+ if (option[POSITIONS])
+ fprintf (stderr, "try options -m or -r, or use new key positions.\n\n");
+ else
+ fprintf (stderr, "try options -m or -r.\n\n");
+ exit (1);
+ }
+ }
+
+ /* Sorts the keyword list by hash value. */
+ sort ();
+
+ /* Set unused asso_values[c] to max_hash_value + 1. This is not absolutely
+ necessary, but speeds up the lookup function in many cases of lookup
+ failure: no string comparison is needed once the hash value of a string
+ is larger than the hash value of any keyword. */
+ int max_hash_value;
+ {
+ KeywordExt_List *temp;
+ for (temp = _head; temp->rest(); temp = temp->rest())
+ ;
+ max_hash_value = temp->first()->_hash_value;
+ }
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (_occurrences[c] == 0)
+ _asso_values[c] = max_hash_value + 1;
+
+ /* Propagate unified asso_values. */
+ if (_alpha_unify)
+ for (unsigned int c = 0; c < _alpha_size; c++)
+ if (_alpha_unify[c] != c)
+ _asso_values[c] = _asso_values[_alpha_unify[c]];
+}
+
+/* Prints out some diagnostics upon completion. */
+
+Search::~Search ()
+{
+ delete _collision_detector;
+ if (option[DEBUG])
+ {
+ fprintf (stderr, "\ndumping occurrence and associated values tables\n");
+
+ for (unsigned int i = 0; i < _alpha_size; i++)
+ if (_occurrences[i])
+ fprintf (stderr, "asso_values[%c] = %6d, occurrences[%c] = %6d\n",
+ i, _asso_values[i], i, _occurrences[i]);
+
+ fprintf (stderr, "end table dumping\n");
+
+ 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, _max_key_len);
+
+ int field_width = _max_selchars_length;
+ fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
+ field_width, "selchars");
+ for (KeywordExt_List *ptr = _head; ptr; ptr = ptr->rest())
+ {
+ fprintf (stderr, "%11d,%11d,%6d, ",
+ ptr->first()->_hash_value, ptr->first()->_allchars_length, ptr->first()->_final_index);
+ if (field_width > ptr->first()->_selchars_length)
+ fprintf (stderr, "%*s", field_width - ptr->first()->_selchars_length, "");
+ for (int j = 0; j < ptr->first()->_selchars_length; j++)
+ putc (ptr->first()->_selchars[j], stderr);
+ fprintf (stderr, ", %.*s\n",
+ ptr->first()->_allchars_length, ptr->first()->_allchars);
+ }
+
+ fprintf (stderr, "End dumping list.\n\n");
+ }
+ delete[] _asso_values;
+ delete[] _occurrences;
+ delete[] _alpha_unify;
+ delete[] _alpha_inc;
+}