| ------------------------------------------------------------------------------ |
| -- -- |
| -- GNAT COMPILER COMPONENTS -- |
| -- -- |
| -- 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 -- |
| -- -- |
| -- S p e c -- |
| -- -- |
| -- Copyright (C) 2002-2004 Ada Core Technologies, Inc. -- |
| -- -- |
| -- 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 2, 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. See the GNU General Public License -- |
| -- for more details. You should have received a copy of the GNU General -- |
| -- Public License distributed with GNAT; see file COPYING. If not, write -- |
| -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, -- |
| -- MA 02111-1307, USA. -- |
| -- -- |
| -- As a special exception, if other files instantiate generics from this -- |
| -- unit, or you link this unit with other files to produce an executable, -- |
| -- this unit does not by itself cause the resulting executable to be -- |
| -- covered by the GNU General Public License. This exception does not -- |
| -- however invalidate any other reasons why the executable file might be -- |
| -- covered by the GNU Public License. -- |
| -- -- |
| -- 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 of integers |
| -- [0, k-1], where k is an integer, usually k >= m. h (w) where w |
| -- is a word 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 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 key set to |
| -- be known in advance (they are "static" hash functions). |
| -- The hash functions are also order preservering. If w2 is inserted |
| -- after w1 in the generator, then f (w1) < f (w2). These hashing |
| -- functions are convenient for use with realtime applications. |
| |
| package GNAT.Perfect_Hash_Generators is |
| |
| Default_K_To_V : constant Float := 2.05; |
| -- Default ratio for the algorithm. When K is the number of keys, |
| -- V = (K_To_V) * K is the size of the main table of the hash function. |
| |
| Default_Pkg_Name : constant String := "Perfect_Hash"; |
| -- Default package name in which the hash function is defined. |
| |
| Default_Position : constant String := ""; |
| -- The generator allows selection of the character positions used |
| -- in the hash function. By default, all positions are selected. |
| |
| type Optimization is (Memory_Space, CPU_Time); |
| Default_Optimization : constant Optimization := CPU_Time; |
| -- Optimize either the memory space or the execution time. |
| |
| Verbose : Boolean := False; |
| -- Comment required ??? |
| |
| procedure Initialize |
| (Seed : Natural; |
| K_To_V : Float := Default_K_To_V; |
| Optim : Optimization := CPU_Time); |
| -- Initialize the generator and its internal structures. Set the |
| -- ratio of vertices over keys in the random graphs. This value |
| -- has to be greater than 2.0 in order for the algorithm to succeed. |
| |
| procedure Finalize; |
| -- Deallocate the internal structures. |
| |
| procedure Insert (Value : String); |
| -- Insert a new key in the table. |
| |
| procedure Compute (Position : String := Default_Position); |
| -- Compute the hash function. Position allows to define a |
| -- selection of character positions used in the keywords hash |
| -- function. Positions can be separated by commas and range like |
| -- x-y may be used. Character '$' represents the final character |
| -- of a key. With an empty position, the generator automatically |
| -- produces positions to reduce the memory usage. |
| |
| procedure Produce (Pkg_Name : String := Default_Pkg_Name); |
| -- Generate the hash function package Pkg_Name. This package |
| -- includes the minimal perfect Hash function. |
| |
| -- The routines and structures defined below allow producing the |
| -- hash function using a different way from the procedure above. |
| -- 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. |
| |
| -- 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 keys 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 key 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 key 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 (I, J) of the table |
| -- Name. When the table has only one dimension, J is ignored. |
| |
| end GNAT.Perfect_Hash_Generators; |
