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
33struct EquivalenceClass;
34
35class Search
36{
37public:
38                        Search (KeywordExt_List *list);
39                        ~Search ();
40  void                  optimize ();
41private:
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
104public:
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
145private:
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
166