|
111
|
1 ------------------------------------------------------------------------------
|
|
|
2 -- --
|
|
|
3 -- GNAT COMPILER COMPONENTS --
|
|
|
4 -- --
|
|
|
5 -- G N A T . P E R F E C T _ H A S H _ G E N E R A T O R S --
|
|
|
6 -- --
|
|
|
7 -- S p e c --
|
|
|
8 -- --
|
|
|
9 -- Copyright (C) 2002-2017, AdaCore --
|
|
|
10 -- --
|
|
|
11 -- GNAT is free software; you can redistribute it and/or modify it under --
|
|
|
12 -- terms of the GNU General Public License as published by the Free Soft- --
|
|
|
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
|
|
|
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
|
|
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
|
|
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
|
|
|
17 -- --
|
|
|
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
|
|
|
19 -- additional permissions described in the GCC Runtime Library Exception, --
|
|
|
20 -- version 3.1, as published by the Free Software Foundation. --
|
|
|
21 -- --
|
|
|
22 -- You should have received a copy of the GNU General Public License and --
|
|
|
23 -- a copy of the GCC Runtime Library Exception along with this program; --
|
|
|
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
|
|
|
25 -- <http://www.gnu.org/licenses/>. --
|
|
|
26 -- --
|
|
|
27 -- GNAT was originally developed by the GNAT team at New York University. --
|
|
|
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
|
|
|
29 -- --
|
|
|
30 ------------------------------------------------------------------------------
|
|
|
31
|
|
|
32 -- This package provides a generator of static minimal perfect hash functions.
|
|
|
33 -- To understand what a perfect hash function is, we define several notions.
|
|
|
34 -- These definitions are inspired from the following paper:
|
|
|
35
|
|
|
36 -- Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal
|
|
|
37 -- Algorithm for Generating Minimal Perfect Hash Functions'', Information
|
|
|
38 -- Processing Letters, 43(1992) pp.257-264, Oct.1992
|
|
|
39
|
|
|
40 -- Let W be a set of m words. A hash function h is a function that maps the
|
|
|
41 -- set of words W into some given interval I of integers [0, k-1], where k is
|
|
|
42 -- an integer, usually k >= m. h (w) where w is a word in W computes an
|
|
|
43 -- address or an integer from I for the storage or the retrieval of that
|
|
|
44 -- item. The storage area used to store items is known as a hash table. Words
|
|
|
45 -- for which the same address is computed are called synonyms. Due to the
|
|
|
46 -- existence of synonyms a situation called collision may arise in which two
|
|
|
47 -- items w1 and w2 have the same address. Several schemes for resolving
|
|
|
48 -- collisions are known. A perfect hash function is an injection from the word
|
|
|
49 -- set W to the integer interval I with k >= m. If k = m, then h is a minimal
|
|
|
50 -- perfect hash function. A hash function is order preserving if it puts
|
|
|
51 -- entries into the hash table in a prespecified order.
|
|
|
52
|
|
|
53 -- A minimal perfect hash function is defined by two properties:
|
|
|
54
|
|
|
55 -- Since no collisions occur each item can be retrieved from the table in
|
|
|
56 -- *one* probe. This represents the "perfect" property.
|
|
|
57
|
|
|
58 -- The hash table size corresponds to the exact size of W and *no larger*.
|
|
|
59 -- This represents the "minimal" property.
|
|
|
60
|
|
|
61 -- The functions generated by this package require the words to be known in
|
|
|
62 -- advance (they are "static" hash functions). The hash functions are also
|
|
|
63 -- order preserving. If w2 is inserted after w1 in the generator, then h (w1)
|
|
|
64 -- < h (w2). These hashing functions are convenient for use with realtime
|
|
|
65 -- applications.
|
|
|
66
|
|
|
67 package GNAT.Perfect_Hash_Generators is
|
|
|
68
|
|
|
69 Default_K_To_V : constant Float := 2.05;
|
|
|
70 -- Default ratio for the algorithm. When K is the number of keys, V =
|
|
|
71 -- (K_To_V) * K is the size of the main table of the hash function. To
|
|
|
72 -- converge, the algorithm requires K_To_V to be strictly greater than 2.0.
|
|
|
73
|
|
|
74 Default_Pkg_Name : constant String := "Perfect_Hash";
|
|
|
75 -- Default package name in which the hash function is defined
|
|
|
76
|
|
|
77 Default_Position : constant String := "";
|
|
|
78 -- The generator allows selection of the character positions used in the
|
|
|
79 -- hash function. By default, all positions are selected.
|
|
|
80
|
|
|
81 Default_Tries : constant Positive := 20;
|
|
|
82 -- This algorithm may not succeed to find a possible mapping on the first
|
|
|
83 -- try and may have to iterate a number of times. This constant bounds the
|
|
|
84 -- number of tries.
|
|
|
85
|
|
|
86 type Optimization is (Memory_Space, CPU_Time);
|
|
|
87 -- Optimize either the memory space or the execution time. Note: in
|
|
|
88 -- practice, the optimization mode has little effect on speed. The tables
|
|
|
89 -- are somewhat smaller with Memory_Space.
|
|
|
90
|
|
|
91 Verbose : Boolean := False;
|
|
|
92 -- Output the status of the algorithm. For instance, the tables, the random
|
|
|
93 -- graph (edges, vertices) and selected char positions are output between
|
|
|
94 -- two iterations.
|
|
|
95
|
|
|
96 procedure Initialize
|
|
|
97 (Seed : Natural;
|
|
|
98 K_To_V : Float := Default_K_To_V;
|
|
|
99 Optim : Optimization := Memory_Space;
|
|
|
100 Tries : Positive := Default_Tries);
|
|
|
101 -- Initialize the generator and its internal structures. Set the ratio of
|
|
|
102 -- vertices over keys in the random graphs. This value has to be greater
|
|
|
103 -- than 2.0 in order for the algorithm to succeed. The word set is not
|
|
|
104 -- modified (in particular when it is already set). For instance, it is
|
|
|
105 -- possible to run several times the generator with different settings on
|
|
|
106 -- the same words.
|
|
|
107 --
|
|
|
108 -- A classical way of doing is to Insert all the words and then to invoke
|
|
|
109 -- Initialize and Compute. If Compute fails to find a perfect hash
|
|
|
110 -- function, invoke Initialize another time with other configuration
|
|
|
111 -- parameters (probably with a greater K_To_V ratio). Once successful,
|
|
|
112 -- invoke Produce and Finalize.
|
|
|
113
|
|
|
114 procedure Finalize;
|
|
|
115 -- Deallocate the internal structures and the words table
|
|
|
116
|
|
|
117 procedure Insert (Value : String);
|
|
|
118 -- Insert a new word into the table. ASCII.NUL characters are not allowed.
|
|
|
119
|
|
|
120 Too_Many_Tries : exception;
|
|
|
121 -- Raised after Tries unsuccessful runs
|
|
|
122
|
|
|
123 procedure Compute (Position : String := Default_Position);
|
|
|
124 -- Compute the hash function. Position allows the definition of selection
|
|
|
125 -- of character positions used in the word hash function. Positions can be
|
|
|
126 -- separated by commas and ranges like x-y may be used. Character '$'
|
|
|
127 -- represents the final character of a word. With an empty position, the
|
|
|
128 -- generator automatically produces positions to reduce the memory usage.
|
|
|
129 -- Raise Too_Many_Tries if the algorithm does not succeed within Tries
|
|
|
130 -- attempts (see Initialize).
|
|
|
131
|
|
|
132 procedure Produce
|
|
|
133 (Pkg_Name : String := Default_Pkg_Name;
|
|
|
134 Use_Stdout : Boolean := False);
|
|
|
135 -- Generate the hash function package Pkg_Name. This package includes the
|
|
|
136 -- minimal perfect Hash function. The output is normally placed in the
|
|
|
137 -- current directory, in files X.ads and X.adb, where X is the standard
|
|
|
138 -- GNAT file name for a package named Pkg_Name. If Use_Stdout is True, the
|
|
|
139 -- output goes to standard output, and no files are written.
|
|
|
140
|
|
|
141 ----------------------------------------------------------------
|
|
|
142
|
|
|
143 -- The routines and structures defined below allow producing the hash
|
|
|
144 -- function using a different way from the procedure above. The procedure
|
|
|
145 -- Define returns the lengths of an internal table and its item type size.
|
|
|
146 -- The function Value returns the value of each item in the table.
|
|
|
147
|
|
|
148 -- The hash function has the following form:
|
|
|
149
|
|
|
150 -- h (w) = (g (f1 (w)) + g (f2 (w))) mod m
|
|
|
151
|
|
|
152 -- G is a function based on a graph table [0,n-1] -> [0,m-1]. m is the
|
|
|
153 -- number of keys. n is an internally computed value and it can be obtained
|
|
|
154 -- as the length of vector G.
|
|
|
155
|
|
|
156 -- F1 and F2 are two functions based on two function tables T1 and T2.
|
|
|
157 -- Their definition depends on the chosen optimization mode.
|
|
|
158
|
|
|
159 -- Only some character positions are used in the words because they are
|
|
|
160 -- significant. They are listed in a character position table (P in the
|
|
|
161 -- pseudo-code below). For instance, in {"jan", "feb", "mar", "apr", "jun",
|
|
|
162 -- "jul", "aug", "sep", "oct", "nov", "dec"}, only positions 2 and 3 are
|
|
|
163 -- significant (the first character can be ignored). In this example, P =
|
|
|
164 -- {2, 3}
|
|
|
165
|
|
|
166 -- When Optimization is CPU_Time, the first dimension of T1 and T2
|
|
|
167 -- corresponds to the character position in the word and the second to the
|
|
|
168 -- character set. As all the character set is not used, we define a used
|
|
|
169 -- character table which associates a distinct index to each used character
|
|
|
170 -- (unused characters are mapped to zero). In this case, the second
|
|
|
171 -- dimension of T1 and T2 is reduced to the used character set (C in the
|
|
|
172 -- pseudo-code below). Therefore, the hash function has the following:
|
|
|
173
|
|
|
174 -- function Hash (S : String) return Natural is
|
|
|
175 -- F : constant Natural := S'First - 1;
|
|
|
176 -- L : constant Natural := S'Length;
|
|
|
177 -- F1, F2 : Natural := 0;
|
|
|
178 -- J : <t>;
|
|
|
179
|
|
|
180 -- begin
|
|
|
181 -- for K in P'Range loop
|
|
|
182 -- exit when L < P (K);
|
|
|
183 -- J := C (S (P (K) + F));
|
|
|
184 -- F1 := (F1 + Natural (T1 (K, J))) mod <n>;
|
|
|
185 -- F2 := (F2 + Natural (T2 (K, J))) mod <n>;
|
|
|
186 -- end loop;
|
|
|
187
|
|
|
188 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
|
|
|
189 -- end Hash;
|
|
|
190
|
|
|
191 -- When Optimization is Memory_Space, the first dimension of T1 and T2
|
|
|
192 -- corresponds to the character position in the word and the second
|
|
|
193 -- dimension is ignored. T1 and T2 are no longer matrices but vectors.
|
|
|
194 -- Therefore, the used character table is not available. The hash function
|
|
|
195 -- has the following form:
|
|
|
196
|
|
|
197 -- function Hash (S : String) return Natural is
|
|
|
198 -- F : constant Natural := S'First - 1;
|
|
|
199 -- L : constant Natural := S'Length;
|
|
|
200 -- F1, F2 : Natural := 0;
|
|
|
201 -- J : <t>;
|
|
|
202
|
|
|
203 -- begin
|
|
|
204 -- for K in P'Range loop
|
|
|
205 -- exit when L < P (K);
|
|
|
206 -- J := Character'Pos (S (P (K) + F));
|
|
|
207 -- F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
|
|
|
208 -- F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
|
|
|
209 -- end loop;
|
|
|
210
|
|
|
211 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
|
|
|
212 -- end Hash;
|
|
|
213
|
|
|
214 type Table_Name is
|
|
|
215 (Character_Position,
|
|
|
216 Used_Character_Set,
|
|
|
217 Function_Table_1,
|
|
|
218 Function_Table_2,
|
|
|
219 Graph_Table);
|
|
|
220
|
|
|
221 procedure Define
|
|
|
222 (Name : Table_Name;
|
|
|
223 Item_Size : out Natural;
|
|
|
224 Length_1 : out Natural;
|
|
|
225 Length_2 : out Natural);
|
|
|
226 -- Return the definition of the table Name. This includes the length of
|
|
|
227 -- dimensions 1 and 2 and the size of an unsigned integer item. When
|
|
|
228 -- Length_2 is zero, the table has only one dimension. All the ranges
|
|
|
229 -- start from zero.
|
|
|
230
|
|
|
231 function Value
|
|
|
232 (Name : Table_Name;
|
|
|
233 J : Natural;
|
|
|
234 K : Natural := 0) return Natural;
|
|
|
235 -- Return the value of the component (I, J) of the table Name. When the
|
|
|
236 -- table has only one dimension, J is ignored.
|
|
|
237
|
|
|
238 end GNAT.Perfect_Hash_Generators;
|
