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