contrib/gperf/src/search.h

   1 /* This may look like C code, but it is really -*- C++ -*- */
   2
   3 /* Search algorithm.
   4
   5    Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
   6    Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
   7    and Bruno Haible <bruno@clisp.org>.
   8
   9    This file is part of GNU GPERF.
  10
  11    GNU GPERF is free software; you can redistribute it and/or modify
  12    it under the terms of the GNU General Public License as published by
  13    the Free Software Foundation; either version 2, or (at your option)
  14    any later version.
  15
  16    GNU GPERF is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19    GNU General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; see the file COPYING.
  23    If not, write to the Free Software Foundation, Inc.,
  24    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  25
  26 #ifndef search_h
  27 #define search_h 1
  28
  29 #include "keyword-list.h"
  30 #include "positions.h"
  31 #include "bool-array.h"
  32
  33 struct EquivalenceClass;
  34
  35 class Search
  36 {
  37 public:
  38                         Search (KeywordExt_List *list);
  39                         ~Search ();
  40   void                  optimize ();
  41 private:
  42   void                  prepare ();
  43
  44   /* Computes the upper bound on the indices passed to asso_values[],
  45      assuming no alpha_increments.  */
  46   unsigned int          compute_alpha_size () const;
  47
  48   /* Computes the unification rules between different asso_values[c],
  49      assuming no alpha_increments.  */
  50   unsigned int *        compute_alpha_unify () const;
  51
  52   /* Initializes each keyword's _selchars array.  */
  53   void                  init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify) const;
  54   /* Deletes each keyword's _selchars array.  */
  55   void                  delete_selchars () const;
  56
  57   /* Count the duplicate keywords that occur with a given set of positions.  */
  58   unsigned int          count_duplicates_tuple (const Positions& positions, const unsigned int *alpha_unify) const;
  59
  60   /* Find good key positions.  */
  61   void                  find_positions ();
  62
  63   /* Count the duplicate keywords that occur with the found set of positions.  */
  64   unsigned int          count_duplicates_tuple () const;
  65
  66   /* Computes the upper bound on the indices passed to asso_values[].  */
  67   unsigned int          compute_alpha_size (const unsigned int *alpha_inc) const;
  68
  69   /* Computes the unification rules between different asso_values[c].  */
  70   unsigned int *        compute_alpha_unify (const Positions& positions, const unsigned int *alpha_inc) const;
  71
  72   /* Initializes each keyword's _selchars array.  */
  73   void                  init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc) const;
  74
  75   /* Count the duplicate keywords that occur with the given set of positions
  76      and a given alpha_inc[] array.  */
  77   unsigned int          count_duplicates_multiset (const unsigned int *alpha_inc) const;
  78
  79   /* Find good _alpha_inc[].  */
  80   void                  find_alpha_inc ();
  81
  82   /* Initializes the asso_values[] related parameters.  */
  83   void                  prepare_asso_values ();
  84
  85   EquivalenceClass *    compute_partition (bool *undetermined) const;
  86
  87   unsigned int          count_possible_collisions (EquivalenceClass *partition, unsigned int c) const;
  88
  89   bool                  unchanged_partition (EquivalenceClass *partition, unsigned int c) const;
  90
  91   /* Finds some _asso_values[] that fit.  */
  92   void                  find_asso_values ();
  93
  94   /* Computes a keyword's hash value, relative to the current _asso_values[],
  95      and stores it in keyword->_hash_value.  */
  96   int                   compute_hash (KeywordExt *keyword) const;
  97
  98   /* Finds good _asso_values[].  */
  99   void                  find_good_asso_values ();
 100
 101   /* Sorts the keyword list by hash value.  */
 102   void                  sort ();
 103
 104 public:
 105
 106   /* Linked list of keywords.  */
 107   KeywordExt_List *     _head;
 108
 109   /* Total number of keywords, counting duplicates.  */
 110   int                   _total_keys;
 111
 112   /* Maximum length of the longest keyword.  */
 113   int                   _max_key_len;
 114
 115   /* Minimum length of the shortest keyword.  */
 116   int                   _min_key_len;
 117
 118   /* User-specified or computed key positions.  */
 119   Positions             _key_positions;
 120
 121   /* Adjustments to add to bytes add specific key positions.  */
 122   unsigned int *        _alpha_inc;
 123
 124   /* Size of alphabet.  */
 125   unsigned int          _alpha_size;
 126
 127   /* Alphabet character unification, either the identity or a mapping from
 128      upper case characters to lower case characters (and maybe more).  */
 129   unsigned int *        _alpha_unify;
 130
 131   /* Maximum _selchars_length over all keywords.  */
 132   unsigned int          _max_selchars_length;
 133
 134   /* Total number of duplicates that have been moved to _duplicate_link lists
 135      (not counting their representatives which stay on the main list).  */
 136   int                   _total_duplicates;
 137
 138   /* Counts occurrences of each key set character.
 139      _occurrences[c] is the number of times that c occurs among the _selchars
 140      of a keyword.  */
 141   int *                 _occurrences;
 142   /* Value associated with each character. */
 143   int *                 _asso_values;
 144
 145 private:
 146
 147   /* Length of _head list.  Number of keywords, not counting duplicates.  */
 148   int                   _list_len;
 149
 150   /* Exclusive upper bound for every _asso_values[c].  A power of 2.  */
 151   unsigned int          _asso_value_max;
 152
 153   /* Initial value for asso_values table.  -1 means random.  */
 154   int                   _initial_asso_value;
 155   /* Jump length when trying alternative values.  0 means random.  */
 156   int                   _jump;
 157
 158   /* Maximal possible hash value.  */
 159   int                   _max_hash_value;
 160
 161   /* Sparse bit vector for collision detection.  */
 162   Bool_Array *          _collision_detector;
 163 };
 164
 165 #endif