1 /* This may look like C code, but it is really -*- C++ -*- */
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>.
9 This file is part of GNU GPERF.
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)
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.
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. */
29 #include "keyword-list.h"
30 #include "positions.h"
31 #include "bool-array.h"
33 struct EquivalenceClass;
38 Search (KeywordExt_List *list);
44 /* Computes the upper bound on the indices passed to asso_values[],
45 assuming no alpha_increments. */
46 unsigned int compute_alpha_size () const;
48 /* Computes the unification rules between different asso_values[c],
49 assuming no alpha_increments. */
50 unsigned int * compute_alpha_unify () const;
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;
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;
60 /* Find good key positions. */
61 void find_positions ();
63 /* Count the duplicate keywords that occur with the found set of positions. */
64 unsigned int count_duplicates_tuple () const;
66 /* Computes the upper bound on the indices passed to asso_values[]. */
67 unsigned int compute_alpha_size (const unsigned int *alpha_inc) const;
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;
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;
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;
79 /* Find good _alpha_inc[]. */
80 void find_alpha_inc ();
82 /* Initializes the asso_values[] related parameters. */
83 void prepare_asso_values ();
85 EquivalenceClass * compute_partition (bool *undetermined) const;
87 unsigned int count_possible_collisions (EquivalenceClass *partition, unsigned int c) const;
89 bool unchanged_partition (EquivalenceClass *partition, unsigned int c) const;
91 /* Finds some _asso_values[] that fit. */
92 void find_asso_values ();
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;
98 /* Finds good _asso_values[]. */
99 void find_good_asso_values ();
101 /* Sorts the keyword list by hash value. */
106 /* Linked list of keywords. */
107 KeywordExt_List * _head;
109 /* Total number of keywords, counting duplicates. */
112 /* Maximum length of the longest keyword. */
115 /* Minimum length of the shortest keyword. */
118 /* User-specified or computed key positions. */
119 Positions _key_positions;
121 /* Adjustments to add to bytes add specific key positions. */
122 unsigned int * _alpha_inc;
124 /* Size of alphabet. */
125 unsigned int _alpha_size;
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;
131 /* Maximum _selchars_length over all keywords. */
132 unsigned int _max_selchars_length;
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;
138 /* Counts occurrences of each key set character.
139 _occurrences[c] is the number of times that c occurs among the _selchars
142 /* Value associated with each character. */
147 /* Length of _head list. Number of keywords, not counting duplicates. */
150 /* Exclusive upper bound for every _asso_values[c]. A power of 2. */
151 unsigned int _asso_value_max;
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. */
158 /* Maximal possible hash value. */
161 /* Sparse bit vector for collision detection. */
162 Bool_Array * _collision_detector;