1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/* 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.,
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#ifndef search_h
#define search_h 1
#include "keyword-list.h"
#include "positions.h"
#include "bool-array.h"
class Search
{
public:
Search (KeywordExt_List *list);
~Search ();
void optimize ();
private:
void preprepare ();
/* Initializes each keyword's _selchars array. */
void init_selchars (bool use_all_chars, const Positions& positions) 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 (const Positions& positions) const;
void find_positions ();
void prepare ();
/* Computes the sum of occurrences of the _selchars of a keyword. */
int compute_occurrence (KeywordExt *ptr) const;
/* Auxiliary functions used by Search::reorder(). */
void clear_determined ();
void set_determined (KeywordExt *keyword);
bool already_determined (KeywordExt *keyword) const;
/* Reorders the keyword list so as to minimize search times. */
void reorder ();
/* Returns the length of keyword list. */
int keyword_list_length () const;
/* Returns the maximum length of keywords. */
int max_key_length () const;
/* Returns the number of key positions. */
int get_max_keysig_size () const;
/* Initializes the asso_values[] related parameters. */
void prepare_asso_values ();
/* Puts a first guess into asso_values[]. */
void init_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;
/* Sorts the given set in increasing frequency of _occurrences[]. */
void sort_by_occurrence (unsigned int *set, int len) const;
/* Tries various other values for _asso_values[c]. */
bool try_asso_value (unsigned int c, KeywordExt *curr, int iterations);
/* Attempts to change an _asso_value[], in order to resolve a hash value
collision between the two given keywords. */
void change_some_asso_value (KeywordExt *prior, KeywordExt *curr);
/* Finds good _asso_values[]. */
void find_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;
/* 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;
/* Size of alphabet. */
int const _alpha_size;
/* Counts occurrences of each key set character.
_occurrences[c] is the number of times that c occurs among the _selchars
of a keyword. */
int * const _occurrences;
/* Value associated with each character. */
int * const _asso_values;
private:
/* Length of _head list. Number of keywords, not counting duplicates. */
int _list_len;
/* Vector used during Search::reorder(). */
bool * const _determined;
/* Exclusive upper bound for every _asso_values[c]. A power of 2. */
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;
/* Minimal number of collisions found so far. */
int _fewest_collisions;
/* Scratch set, used during Search::change_some_asso_value. */
unsigned int * _union_set;
/* Number of keyword being handled during Search::find_asso_values. */
int _num_done;
};
#endif
|