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 Ada Core Technologies, Inc. --
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, 59 Temple Place - Suite 330, Boston, --
20 -- MA 02111-1307, 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 single generator of static minimal perfect
35 -- hash functions. No collisions occur and each item can be retrieved
36 -- from the table in one probe (perfect property). The hash table
37 -- size corresponds to the exact size of W and *no larger* (minimal
38 -- property). The key set has to be know in advance (static
39 -- property). The hash functions are also order preservering. If w2
40 -- is inserted after w1 in the generator, then f (w1) < f (w2). These
41 -- hashing functions are convenient for use with realtime applications.
43 package GNAT
.Perfect_Hash
.Generators
is
45 Default_K_To_V
: constant Float := 2.05;
46 -- Default ratio for the algorithm. When K is the number of keys,
47 -- V = (K_To_V) * K is the size of the main table of the hash function.
49 Default_Pkg_Name
: constant String := "Perfect_Hash";
50 -- Default package name in which the hash function is defined.
52 Default_Position
: constant String := "";
53 -- The generator allows selection of the character positions used
54 -- in the hash function. By default, all positions are selected.
56 type Optimization
is (Memory_Space
, CPU_Time
);
57 Default_Optimization
: constant Optimization
:= CPU_Time
;
58 -- Optimize either the memory space or the execution time.
60 Verbose
: Boolean := False;
64 K_To_V
: Float := Default_K_To_V
;
65 Optim
: Optimization
:= CPU_Time
);
66 -- Initialize the generator and its internal structures. Set the
67 -- ratio of vertices over keys in the random graphs. This value
68 -- has to be greater than 2.0 in order for the algorithm to succeed.
71 -- Deallocate the internal structures.
73 procedure Insert
(Value
: String);
74 -- Insert a new key in the table.
76 procedure Compute
(Position
: String := Default_Position
);
77 -- Compute the hash function. Position allows to define a
78 -- selection of character positions used in the keywords hash
79 -- function. Positions can be separated by commas and range like
80 -- x-y may be used. Character '$' represents the final character
81 -- of a key. With an empty position, the generator automatically
82 -- produces positions to reduce the memory usage.
84 procedure Produce
(Pkg_Name
: String := Default_Pkg_Name
);
85 -- Generate the hash function package Pkg_Name. This package
86 -- includes the minimal perfect Hash function.
88 -- The routines and structures defined below allow producing the
89 -- hash function using a different way from the procedure above.
90 -- The procedure Define returns the lengths of an internal table
91 -- and its item type size. The function Value returns the value of
92 -- each item in the table.
94 -- The hash function has the following form:
96 -- h (w) = (g (f1 (w)) + g (f2 (w))) mod m
98 -- G is a function based on a graph table [0,n-1] -> [0,m-1]. m is
99 -- the number of keys. n is an internally computed value and it
100 -- can be obtained as the length of vector G.
102 -- F1 and F2 are two functions based on two function tables T1 and
103 -- T2. Their definition depends on the chosen optimization mode.
105 -- Only some character positions are used in the keys because they
106 -- are significant. They are listed in a character position table
107 -- (P in the pseudo-code below). For instance, in {"jan", "feb",
108 -- "mar", "apr", "jun", "jul", "aug", "sep", "oct", "nov", "dec"},
109 -- only positions 2 and 3 are significant (the first character can
110 -- be ignored). In this example, P = {2, 3}
112 -- When Optimization is CPU_Time, the first dimension of T1 and T2
113 -- corresponds to the character position in the key and the second
114 -- to the character set. As all the character set is not used, we
115 -- define a used character table which associates a distinct index
116 -- to each used character (unused characters are mapped to
117 -- zero). In this case, the second dimension of T1 and T2 is
118 -- reduced to the used character set (C in the pseudo-code
119 -- below). Therefore, the hash function has the following:
121 -- function Hash (S : String) return Natural is
122 -- F : constant Natural := S'First - 1;
123 -- L : constant Natural := S'Length;
124 -- F1, F2 : Natural := 0;
128 -- for K in P'Range loop
129 -- exit when L < P (K);
130 -- J := C (S (P (K) + F));
131 -- F1 := (F1 + Natural (T1 (K, J))) mod <n>;
132 -- F2 := (F2 + Natural (T2 (K, J))) mod <n>;
135 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
138 -- When Optimization is Memory_Space, the first dimension of T1
139 -- and T2 corresponds to the character position in the key and the
140 -- second dimension is ignored. T1 and T2 are no longer matrices
141 -- but vectors. Therefore, the used character table is not
142 -- available. The hash function has the following form:
144 -- function Hash (S : String) return Natural is
145 -- F : constant Natural := S'First - 1;
146 -- L : constant Natural := S'Length;
147 -- F1, F2 : Natural := 0;
151 -- for K in P'Range loop
152 -- exit when L < P (K);
153 -- J := Character'Pos (S (P (K) + F));
154 -- F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
155 -- F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
158 -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
170 Item_Size
: out Natural;
171 Length_1
: out Natural;
172 Length_2
: out Natural);
173 -- Return the definition of the table Name. This includes the
174 -- length of dimensions 1 and 2 and the size of an unsigned
175 -- integer item. When Length_2 is zero, the table has only one
176 -- dimension. All the ranges start from zero.
183 -- Return the value of the component (I, J) of the table
184 -- Name. When the table has only one dimension, J is ignored.
186 end GNAT
.Perfect_Hash
.Generators
;