path: root/src/search.cc

/* 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.,
   59 Temple Place - Suite 330, Boston, MA 02111-1307, 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"
/* Assume ISO C++ 'for' scoping rule.  */
#define for if (0) ; else for

/* The most 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.

   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, 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
 */

/* ==================== Initialization and Preparation ===================== */

Search::Search (KeywordExt_List *list)
  : _head (list)
{
}

void
Search::preprepare ()
{
  KeywordExt_List *temp;

  /* Compute the total number of keywords.  */
  _total_keys = 0;
  for (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 (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 key is not allowed.\n"
                       "To recognize an empty input key, 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 (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 ====================== */

/* Initializes each keyword's _selchars array.  */
void
Search::init_selchars_tuple (bool use_all_chars, const Positions& positions) const
{
  for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
    temp->first()->init_selchars_tuple(use_all_chars, positions);
}

/* 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
{
  /* 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 (option[ALLCHARS], positions);

  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;
    }

  /* 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 = 1; i < n; i++)
                    if (keyword1->_allchars[i-1] != keyword2->_allchars[i-1])
                      break;
                  if (i < n
                      && memcmp (&keyword1->_allchars[i],
                                 &keyword2->_allchars[i],
                                 n - i)
                         == 0)
                    {
                      /* 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 < Positions::MAX_KEY_POS
              ? _max_key_len : Positions::MAX_KEY_POS);
  Positions current = mandatory;
  unsigned int current_duplicates_count = count_duplicates_tuple (current);
  for (;;)
    {
      Positions best;
      unsigned int best_duplicates_count = UINT_MAX;

      for (int i = imax; i >= 0; i--)
        if (!current.contains (i))
          {
            Positions tryal = current;
            tryal.add (i);
            unsigned int try_duplicates_count = count_duplicates_tuple (tryal);

            /* 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 >= 0; i--)
        if (current.contains (i) && !mandatory.contains (i))
          {
            Positions tryal = current;
            tryal.remove (i);
            unsigned int try_duplicates_count = count_duplicates_tuple (tryal);

            /* 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 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 >= 0; i1--)
        if (current.contains (i1) && !mandatory.contains (i1))
          for (int i2 = imax; i2 >= 0; 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);

                    /* 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 == 0 || i2 == 0 || 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);
      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);
              first = false;
            }
        }
      if (seen_lastchar)
        {
          if (!first)
            fprintf (stderr, ", ");
          fprintf (stderr, "$");
        }
      fprintf (stderr, "\n");
    }
}

/* ===================== Finding good alpha increments ===================== */

/* Initializes each keyword's _selchars array.  */
void
Search::init_selchars_multiset (bool use_all_chars, const Positions& positions, const unsigned int *alpha_inc) const
{
  for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
    temp->first()->init_selchars_multiset(use_all_chars, positions, 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.  */
  init_selchars_multiset (option[ALLCHARS], _key_positions, 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 ();

  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 (_key_positions);

  /* 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;
      if (option[ALLCHARS])
        nindices = _max_key_len;
      else
        {
          /* Ignore Positions::LASTCHAR.  Remember that since Positions are
             sorted in decreasing order, Positions::LASTCHAR comes last.  */
          nindices = (_key_positions.get_size() == 0
                      || _key_positions[_key_positions.get_size() - 1]
                         != Positions::LASTCHAR
                      ? _key_positions.get_size()
                      : _key_positions.get_size() - 1);
        }

      unsigned int indices[nindices];
      if (option[ALLCHARS])
        for (unsigned int j = 0; j < nindices; j++)
          indices[j] = j;
      else
        {
          PositionIterator iter (_key_positions);
          for (unsigned int j = 0; j < nindices; j++)
            {
              int key_pos = iter.next ();
              if (key_pos == PositionIterator::EOS
                  || key_pos == Positions::LASTCHAR)
                abort ();
              indices[j] = key_pos - 1;
            }
        }

      /* 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.  */
      unsigned int best[_max_key_len];
      unsigned int tryal[_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);

      if (option[DEBUG])
        {
          /* Print the result.  */
          fprintf (stderr, "\nComputed alpha increments: ");
          if (option[ALLCHARS])
            {
              bool first = true;
              for (unsigned int j = 0; j < nindices; j++)
                if (current[indices[j]] != 0)
                  {
                    if (!first)
                      fprintf (stderr, ", ");
                    fprintf (stderr, "%u:+%u",
                             indices[j] + 1, current[indices[j]]);
                    first = false;
                  }
            }
          else
            {
              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");
        }
    }

  _alpha_inc = current;
}

/* ======================= Finding good asso_values ======================== */

void
Search::prepare ()
{
  KeywordExt_List *temp;

  /* Initialize each keyword's _selchars array.  */
  init_selchars_multiset(option[ALLCHARS], _key_positions, _alpha_inc);

  /* 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 _alpha_size, the upper bound on the indices passed to
     asso_values[].  */
  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];
  _alpha_size = (option[SEVENBIT] ? 128 : 256) + max_alpha_inc;

  /* 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];
}

/* ------------------------------------------------------------------------- */

/* Returns the length of keyword list.  */

int
Search::keyword_list_length () const
{
  return _list_len;
}

/* Returns the maximum length of keywords.  */

int
Search::max_key_length () const
{
  return _max_key_len;
}

/* Returns the number of key positions.  */

int
Search::get_max_keysig_size () const
{
  return option[ALLCHARS] ? _max_key_len : _key_positions.get_size();
}

/* ---------------------- Finding good asso_values[] ----------------------- */

/* Initializes the asso_values[] related parameters.  */

void
Search::prepare_asso_values ()
{
  int non_linked_length = keyword_list_length ();
  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_length ())
                    + (_asso_value_max - 1) * get_max_keysig_size ();
  /* 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 = get_max_keysig_size();
  unsigned int split_cardinalities[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];
    }
  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;
      unsigned int iter[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_length ())
                            + (_asso_value_max - 1) * get_max_keysig_size ();
                          /* 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;
            }
        }
      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 ();
  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.  */
  preprepare ();

  /* 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;
}

/* 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 = get_max_keysig_size ();
      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_inc;
}