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-2010, 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 67package 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 to define selection of 125 -- 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 238end GNAT.Perfect_Hash_Generators; 239