Mercurial > hg > CbC > CbC_gcc
comparison gcc/ada/libgnat/g-pehage.ads @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
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; |