aboutsummaryrefslogtreecommitdiffstats
path: root/src/search.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/search.h')
-rw-r--r--src/search.h165
1 files changed, 165 insertions, 0 deletions
diff --git a/src/search.h b/src/search.h
new file mode 100644
index 000000000000..6b562c9a8b68
--- /dev/null
+++ b/src/search.h
@@ -0,0 +1,165 @@
+/* This may look like C code, but it is really -*- C++ -*- */
+
+/* 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. */
+
+#ifndef search_h
+#define search_h 1
+
+#include "keyword-list.h"
+#include "positions.h"
+#include "bool-array.h"
+
+struct EquivalenceClass;
+
+class Search
+{
+public:
+ Search (KeywordExt_List *list);
+ ~Search ();
+ void optimize ();
+private:
+ void prepare ();
+
+ /* Computes the upper bound on the indices passed to asso_values[],
+ assuming no alpha_increments. */
+ unsigned int compute_alpha_size () const;
+
+ /* Computes the unification rules between different asso_values[c],
+ assuming no alpha_increments. */
+ unsigned int * compute_alpha_unify () const;
+
+ /* Initializes each keyword's _selchars array. */
+ void init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify) const;
+ /* Deletes each keyword's _selchars array. */
+ void delete_selchars () const;
+
+ /* Count the duplicate keywords that occur with a given set of positions. */
+ unsigned int count_duplicates_tuple (const Positions& positions, const unsigned int *alpha_unify) const;
+
+ /* Find good key positions. */
+ void find_positions ();
+
+ /* Count the duplicate keywords that occur with the found set of positions. */
+ unsigned int count_duplicates_tuple () const;
+
+ /* Computes the upper bound on the indices passed to asso_values[]. */
+ unsigned int compute_alpha_size (const unsigned int *alpha_inc) const;
+
+ /* Computes the unification rules between different asso_values[c]. */
+ unsigned int * compute_alpha_unify (const Positions& positions, const unsigned int *alpha_inc) const;
+
+ /* Initializes each keyword's _selchars array. */
+ void init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc) const;
+
+ /* Count the duplicate keywords that occur with the given set of positions
+ and a given alpha_inc[] array. */
+ unsigned int count_duplicates_multiset (const unsigned int *alpha_inc) const;
+
+ /* Find good _alpha_inc[]. */
+ void find_alpha_inc ();
+
+ /* Initializes the asso_values[] related parameters. */
+ void prepare_asso_values ();
+
+ EquivalenceClass * compute_partition (bool *undetermined) const;
+
+ unsigned int count_possible_collisions (EquivalenceClass *partition, unsigned int c) const;
+
+ bool unchanged_partition (EquivalenceClass *partition, unsigned int c) const;
+
+ /* Finds some _asso_values[] that fit. */
+ void find_asso_values ();
+
+ /* Computes a keyword's hash value, relative to the current _asso_values[],
+ and stores it in keyword->_hash_value. */
+ int compute_hash (KeywordExt *keyword) const;
+
+ /* Finds good _asso_values[]. */
+ void find_good_asso_values ();
+
+ /* Sorts the keyword list by hash value. */
+ void sort ();
+
+public:
+
+ /* Linked list of keywords. */
+ KeywordExt_List * _head;
+
+ /* Total number of keywords, counting duplicates. */
+ int _total_keys;
+
+ /* Maximum length of the longest keyword. */
+ int _max_key_len;
+
+ /* Minimum length of the shortest keyword. */
+ int _min_key_len;
+
+ /* User-specified or computed key positions. */
+ Positions _key_positions;
+
+ /* Adjustments to add to bytes add specific key positions. */
+ unsigned int * _alpha_inc;
+
+ /* Size of alphabet. */
+ unsigned int _alpha_size;
+
+ /* Alphabet character unification, either the identity or a mapping from
+ upper case characters to lower case characters (and maybe more). */
+ unsigned int * _alpha_unify;
+
+ /* Maximum _selchars_length over all keywords. */
+ unsigned int _max_selchars_length;
+
+ /* Total number of duplicates that have been moved to _duplicate_link lists
+ (not counting their representatives which stay on the main list). */
+ int _total_duplicates;
+
+ /* Counts occurrences of each key set character.
+ _occurrences[c] is the number of times that c occurs among the _selchars
+ of a keyword. */
+ int * _occurrences;
+ /* Value associated with each character. */
+ int * _asso_values;
+
+private:
+
+ /* Length of _head list. Number of keywords, not counting duplicates. */
+ int _list_len;
+
+ /* Exclusive upper bound for every _asso_values[c]. A power of 2. */
+ unsigned int _asso_value_max;
+
+ /* Initial value for asso_values table. -1 means random. */
+ int _initial_asso_value;
+ /* Jump length when trying alternative values. 0 means random. */
+ int _jump;
+
+ /* Maximal possible hash value. */
+ int _max_hash_value;
+
+ /* Sparse bit vector for collision detection. */
+ Bool_Array * _collision_detector;
+};
+
+#endif