------------------------------------------------------------------------------
-- --
-- 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 : ;
-- 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 ;
-- F2 := (F2 + Natural (T2 (K, J))) mod ;
-- end loop;
-- return (Natural (G (F1)) + Natural (G (F2))) mod ;
-- 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 : ;
-- 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 ;
-- F2 := (F2 + Natural (T2 (K) * J)) mod ;
-- end loop;
-- return (Natural (G (F1)) + Natural (G (F2))) mod ;
-- 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;