| ------------------------------------------------------------------------------ |
| -- -- |
| -- GNAT COMPILER COMPONENTS -- |
| -- -- |
| -- S Y S T E M . P E R F E C T _ H A S H _ G E N E R A T O R S -- |
| -- -- |
| -- S p e c -- |
| -- -- |
| -- Copyright (C) 2002-2021, AdaCore -- |
| -- -- |
| -- GNAT is free software; you can redistribute it and/or modify it under -- |
| -- terms of the GNU General Public License as published by the Free Soft- -- |
| -- ware Foundation; either version 3, or (at your option) any later ver- -- |
| -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- |
| -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- |
| -- or FITNESS FOR A PARTICULAR PURPOSE. -- |
| -- -- |
| -- As a special exception under Section 7 of GPL version 3, you are granted -- |
| -- additional permissions described in the GCC Runtime Library Exception, -- |
| -- version 3.1, as published by the Free Software Foundation. -- |
| -- -- |
| -- You should have received a copy of the GNU General Public License and -- |
| -- a copy of the GCC Runtime Library Exception along with this program; -- |
| -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- |
| -- <http://www.gnu.org/licenses/>. -- |
| -- -- |
| -- GNAT was originally developed by the GNAT team at New York University. -- |
| -- Extensive contributions were provided by Ada Core Technologies Inc. -- |
| -- -- |
| ------------------------------------------------------------------------------ |
| |
| -- This package provides a generator of static minimal perfect hash functions. |
| -- To understand what a perfect hash function is, we define several notions. |
| -- These definitions are inspired from the following paper: |
| |
| -- Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal |
| -- Algorithm for Generating Minimal Perfect Hash Functions'', Information |
| -- Processing Letters, 43(1992) pp.257-264, Oct.1992 |
| |
| -- Let W be a set of m words. A hash function h is a function that maps the |
| -- set of words W into some given interval I of integers [0, k-1], where k is |
| -- an integer, usually k >= m. h (w) where w is a word in W computes an |
| -- address or an integer from I for the storage or the retrieval of that |
| -- item. The storage area used to store items is known as a hash table. Words |
| -- for which the same address is computed are called synonyms. Due to the |
| -- existence of synonyms a situation called collision may arise in which two |
| -- items w1 and w2 have the same address. Several schemes for resolving |
| -- collisions are known. A perfect hash function is an injection from the word |
| -- set W to the integer interval I with k >= m. If k = m, then h is a minimal |
| -- perfect hash function. A hash function is order preserving if it puts |
| -- entries into the hash table in a prespecified order. |
| |
| -- A minimal perfect hash function is defined by two properties: |
| |
| -- Since no collisions occur each item can be retrieved from the table in |
| -- *one* probe. This represents the "perfect" property. |
| |
| -- The hash table size corresponds to the exact size of W and *no larger*. |
| -- This represents the "minimal" property. |
| |
| -- The functions generated by this package require the words to be known in |
| -- advance (they are "static" hash functions). The hash functions are also |
| -- order preserving. If w2 is inserted after w1 in the generator, then h (w1) |
| -- < h (w2). These hashing functions are convenient for use with realtime |
| -- applications. |
| |
| pragma Compiler_Unit_Warning; |
| |
| package System.Perfect_Hash_Generators is |
| |
| type Optimization is (Memory_Space, CPU_Time); |
| -- Optimize either the memory space or the execution time. Note: in |
| -- practice, the optimization mode has little effect on speed. The tables |
| -- are somewhat smaller with Memory_Space. |
| |
| Verbose : Boolean := False; |
| -- Output the status of the algorithm. For instance, the tables, the random |
| -- graph (edges, vertices) and selected char positions are output between |
| -- two iterations. |
| |
| procedure Initialize |
| (Seed : Natural; |
| V : Positive; |
| Optim : Optimization; |
| Tries : Positive); |
| -- Initialize the generator and its internal structures. Set the number of |
| -- vertices in the random graphs. This value has to be greater than twice |
| -- the number of keys in order for the algorithm to succeed. The word set |
| -- is not modified (in particular when it is already set). For instance, it |
| -- is possible to run several times the generator with different settings |
| -- on the same words. |
| -- |
| -- A classical way of doing is to Insert all the words and then to invoke |
| -- Initialize and Compute. If this fails to find a perfect hash function, |
| -- invoke Initialize again with other configuration parameters (probably |
| -- with a greater number of vertices). Once successful, invoke Define and |
| -- Value, and then Finalize. |
| |
| procedure Finalize; |
| -- Deallocate the internal structures and the words table |
| |
| procedure Insert (Value : String); |
| -- Insert a new word into the table. ASCII.NUL characters are not allowed. |
| |
| Too_Many_Tries : exception; |
| -- Raised after Tries unsuccessful runs |
| |
| procedure Compute (Position : String); |
| -- Compute the hash function. Position allows the definition of selection |
| -- of character positions used in the word hash function. Positions can be |
| -- separated by commas and ranges like x-y may be used. Character '$' |
| -- represents the final character of a word. With an empty position, the |
| -- generator automatically produces positions to reduce the memory usage. |
| -- Raise Too_Many_Tries if the algorithm does not succeed within Tries |
| -- attempts (see Initialize). |
| |
| -- The procedure Define returns the lengths of an internal table and its |
| -- item type size. The function Value returns the value of each item in |
| -- the table. Together they can be used to retrieve the parameters of the |
| -- hash function which has been computed by a call to Compute. |
| |
| -- The hash function has the following form: |
| |
| -- h (w) = (g (f1 (w)) + g (f2 (w))) mod m |
| |
| -- G is a function based on a graph table [0,n-1] -> [0,m-1]. m is the |
| -- number of keys. n is an internally computed value and it can be obtained |
| -- as the length of vector G. |
| |
| -- F1 and F2 are two functions based on two function tables T1 and T2. |
| -- Their definition depends on the chosen optimization mode. |
| |
| -- Only some character positions are used in the words because they are |
| -- significant. They are listed in a character position table (P in the |
| -- pseudo-code below). For instance, in {"jan", "feb", "mar", "apr", "jun", |
| -- "jul", "aug", "sep", "oct", "nov", "dec"}, only positions 2 and 3 are |
| -- significant (the first character can be ignored). In this example, P = |
| -- {2, 3} |
| |
| -- When Optimization is CPU_Time, the first dimension of T1 and T2 |
| -- corresponds to the character position in the word and the second to the |
| -- character set. As all the character set is not used, we define a used |
| -- character table which associates a distinct index to each used character |
| -- (unused characters are mapped to zero). In this case, the second |
| -- dimension of T1 and T2 is reduced to the used character set (C in the |
| -- pseudo-code below). Therefore, the hash function has the following: |
| |
| -- function Hash (S : String) return Natural is |
| -- F : constant Natural := S'First - 1; |
| -- L : constant Natural := S'Length; |
| -- F1, F2 : Natural := 0; |
| -- J : <t>; |
| |
| -- begin |
| -- for K in P'Range loop |
| -- exit when L < P (K); |
| -- J := C (S (P (K) + F)); |
| -- F1 := (F1 + Natural (T1 (K, J))) mod <n>; |
| -- F2 := (F2 + Natural (T2 (K, J))) mod <n>; |
| -- end loop; |
| |
| -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>; |
| -- end Hash; |
| |
| -- When Optimization is Memory_Space, the first dimension of T1 and T2 |
| -- corresponds to the character position in the word and the second |
| -- dimension is ignored. T1 and T2 are no longer matrices but vectors. |
| -- Therefore, the used character table is not available. The hash function |
| -- has the following form: |
| |
| -- function Hash (S : String) return Natural is |
| -- F : constant Natural := S'First - 1; |
| -- L : constant Natural := S'Length; |
| -- F1, F2 : Natural := 0; |
| -- J : <t>; |
| |
| -- begin |
| -- for K in P'Range loop |
| -- exit when L < P (K); |
| -- J := Character'Pos (S (P (K) + F)); |
| -- F1 := (F1 + Natural (T1 (K) * J)) mod <n>; |
| -- F2 := (F2 + Natural (T2 (K) * J)) mod <n>; |
| -- end loop; |
| |
| -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>; |
| -- end Hash; |
| |
| type Table_Name is |
| (Character_Position, |
| Used_Character_Set, |
| Function_Table_1, |
| Function_Table_2, |
| Graph_Table); |
| |
| procedure Define |
| (Name : Table_Name; |
| Item_Size : out Natural; |
| Length_1 : out Natural; |
| Length_2 : out Natural); |
| -- Return the definition of the table Name. This includes the length of |
| -- dimensions 1 and 2 and the size of an unsigned integer item. When |
| -- Length_2 is zero, the table has only one dimension. All the ranges |
| -- start from zero. |
| |
| function Value |
| (Name : Table_Name; |
| J : Natural; |
| K : Natural := 0) return Natural; |
| -- Return the value of the component (J, K) of the table Name. When the |
| -- table has only one dimension, K is ignored. |
| |
| end System.Perfect_Hash_Generators; |
