diff options
Diffstat (limited to 'src/search.h')
| -rw-r--r-- | src/search.h | 165 |
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 |