1 ------------------------------------------------------------------------------
3 -- GNAT COMPILER COMPONENTS --
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 --
9 -- Copyright (C) 2002-2008, AdaCore --
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 2, 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. See the GNU General Public License --
17 -- for more details. You should have received a copy of the GNU General --
18 -- Public License distributed with GNAT; see file COPYING. If not, write --
19 -- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
20 -- Boston, MA 02110-1301, USA. --
22 -- As a special exception, if other files instantiate generics from this --
23 -- unit, or you link this unit with other files to produce an executable, --
24 -- this unit does not by itself cause the resulting executable to be --
25 -- covered by the GNU General Public License. This exception does not --
26 -- however invalidate any other reasons why the executable file might be --
27 -- covered by the GNU Public License. --
29 -- GNAT was originally developed by the GNAT team at New York University. --
30 -- Extensive contributions were provided by Ada Core Technologies Inc. --
32 ------------------------------------------------------------------------------
34 -- This package provides a generator of static minimal perfect hash functions.
35 -- To understand what a perfect hash function is, we define several notions.
36 -- These definitions are inspired from the following paper:
38 -- Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal
39 -- Algorithm for Generating Minimal Perfect Hash Functions'', Information
40 -- Processing Letters, 43(1992) pp.257-264, Oct.1992
42 -- Let W be a set of m words. A hash function h is a function that maps the
43 -- set of words W into some given interval of integers [0, k-1], where k is an
44 -- integer, usually k >= m. h (w) where is a word computes an address or an
45 -- integer from I for the storage or the retrieval of that item. The storage
46 -- area used to store items is known as a hash table. Words for which the same
47 -- address is computed are called synonyms. Due to the existence of synonyms a
48 -- situation called collision may arise in which two items w1 and w2 have the
49 -- same address. Several schemes for resolving known. A perfect hash function
50 -- is an injection from the word set W to the integer interval I with k >= m.
51 -- If k = m, then h is a minimal perfect hash function. A hash function is
52 -- order preserving if it puts entries into the hash table in prespecified
55 -- A minimal perfect hash function is defined by two properties:
57 -- Since no collisions occur each item can be retrieved from the table in
58 -- *one* probe. This represents the "perfect" property.
60 -- The hash table size corresponds to the exact size of W and *no larger*.
61 -- This represents the "minimal" property.
63 -- The functions generated by this package require the words to be known in
64 -- advance (they are "static" hash functions). The hash functions are also
65 -- order preserving. If w2 is inserted after w1 in the generator, then (w1)
66 -- < f (w2). These hashing functions are convenient for use with realtime
69 package GNAT.Perfect_Hash_Generators is
71 Default_K_To_V : constant Float := 2.05;
72 -- Default ratio for the algorithm. When K is the number of keys, V =
73 -- (K_To_V) * K is the size of the main table of the hash function. To
74 -- converge, the algorithm requires K_To_V to be strictly greater than 2.0.
76 Default_Pkg_Name : constant String := "Perfect_Hash";
77 -- Default package name in which the hash function is defined
79 Default_Position : constant String := "";
80 -- The generator allows selection of the character positions used in the
81 -- hash function. By default, all positions are selected.
83 Default_Tries : constant Positive := 20;
84 -- This algorithm may not succeed to find a possible mapping on the first
85 -- try and may have to iterate a number of times. This constant bounds the
88 type Optimization is (Memory_Space, CPU_Time);
89 Default_Optimization : constant Optimization := CPU_Time;
90 -- Optimize either the memory space or the execution time
92 Verbose : Boolean := False;
93 -- Output the status of the algorithm. For instance, the tables, the random
94 -- graph (edges, vertices) and selected char positions are output between
99 K_To_V : Float := Default_K_To_V;
100 Optim : Optimization := CPU_Time;
101 Tries : Positive := Default_Tries);
102 -- Initialize the generator and its internal structures. Set the
103 -- ratio of vertices over keys in the random graphs. This value
104 -- has to be greater than 2.0 in order for the algorithm to
105 -- succeed. The word set is not modified (in particular when it is
106 -- already set). For instance, it is possible to run several times
107 -- the generator with different settings on the same words.
109 -- A classical way of doing is to Insert all the words and then to
110 -- invoke Initialize and Compute. If Compute fails to find a
111 -- perfect hash function, invoke Initialize another time with
112 -- other configuration parameters (probably with a greater K_To_V
113 -- ratio). Once successful, invoke Produce and Finalize.
116 -- Deallocate the internal structures and the words table
118 procedure Insert (Value : String);
119 -- Insert a new word in the table
121 Too_Many_Tries : exception;
122 -- Raised after Tries unsuccessful runs
124 procedure Compute (Position : String := Default_Position);
125 -- Compute the hash function. Position allows to define selection of
126 -- character positions used in the word hash function. Positions can be
127 -- separated by commas and range like x-y may be used. Character '$'
128 -- represents the final character of a word. With an empty position, the
129 -- generator automatically produces positions to reduce the memory usage.
130 -- Raise Too_Many_Tries in case that the algorithm does not succeed in less
131 -- than Tries attempts (see Initialize).
133 procedure Produce (Pkg_Name : String := Default_Pkg_Name);
134 -- Generate the hash function package Pkg_Name. This package includes the
135 -- minimal perfect Hash function.
137 -- The routines and structures defined below allow producing the hash
138 -- function using a different way from the procedure above. The procedure
139 -- Define returns the lengths of an internal table and its item type size.
140 -- The function Value returns the value of each item in the table.
142 -- The hash function has the following form:
144 -- h (w) = (g (f1 (w)) + g (f2 (w))) mod m
146 -- G is a function based on a graph table [0,n-1] -> [0,m-1]. m is the
147 -- number of keys. n is an internally computed value and it can be obtained
148 -- as the length of vector G.
150 -- F1 and F2 are two functions based on two function tables T1 and T2.
151 -- Their definition depends on the chosen optimization mode.
153 -- Only some character positions are used in the words because they are
154 -- significant. They are listed in a character position table (P in the
155 -- pseudo-code below). For instance, in {"jan", "feb", "mar", "apr", "jun",
156 -- "jul", "aug", "sep", "oct", "nov", "dec"}, only positions 2 and 3 are
157 -- significant (the first character can be ignored). In this example, P =
160 -- When Optimization is CPU_Time, the first dimension of T1 and T2
161 -- corresponds to the character position in the word and the second to the
162 -- character set. As all the character set is not used, we define a used
163 -- character table which associates a distinct index to each used character
164 -- (unused characters are mapped to zero). In this case, the second
165 -- dimension of T1 and T2 is reduced to the used character set (C in the
166 -- pseudo-code below). Therefore, the hash function has the following:
168 -- function Hash (S : String) return Natural is
169 -- F : constant Natural := S'First - 1;
170 -- L : constant Natural := S'Length;
171 -- F1, F2 : Natural := 0;
175 -- for K in P'Range loop
176 -- exit when L < P (K);
177 -- J := C (S (P (K) + F));
178 -- F1 := (F1 + Natural (T1 (K, J))) mod <n>;
179 -- F2 := (F2 + Natural (T2 (K, J))) mod <n>;
182 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
185 -- When Optimization is Memory_Space, the first dimension of T1 and T2
186 -- corresponds to the character position in the word and the second
187 -- dimension is ignored. T1 and T2 are no longer matrices but vectors.
188 -- Therefore, the used character table is not available. The hash function
189 -- has the following form:
191 -- function Hash (S : String) return Natural is
192 -- F : constant Natural := S'First - 1;
193 -- L : constant Natural := S'Length;
194 -- F1, F2 : Natural := 0;
198 -- for K in P'Range loop
199 -- exit when L < P (K);
200 -- J := Character'Pos (S (P (K) + F));
201 -- F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
202 -- F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
205 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
217 Item_Size : out Natural;
218 Length_1 : out Natural;
219 Length_2 : out Natural);
220 -- Return the definition of the table Name. This includes the length of
221 -- dimensions 1 and 2 and the size of an unsigned integer item. When
222 -- Length_2 is zero, the table has only one dimension. All the ranges start
228 K : Natural := 0) return Natural;
229 -- Return the value of the component (I, J) of the table Name. When the
230 -- table has only one dimension, J is ignored.
232 end GNAT.Perfect_Hash_Generators;