-- --
-- S p e c --
-- --
--- Copyright (C) 2002-2005, AdaCore --
+-- Copyright (C) 2002-2008, 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- --
-- 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
+-- 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 preservering. If w2 is inserted after w1 in the generator, then (w1)
+-- order preserving. If w2 is inserted after w1 in the generator, then (w1)
-- < f (w2). These hashing functions are convenient for use with realtime
-- applications.
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. To
- -- converge, the algorithm requires K_To_V to be stricly greater than 2.0.
+ -- converge, the algorithm requires K_To_V to be strictly greater than 2.0.
Default_Pkg_Name : constant String := "Perfect_Hash";
-- Default package name in which the hash function is defined
Tries : Positive := Default_Tries);
-- 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. The key set is not
+ -- than 2.0 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 key set.
+ -- the same words.
+ --
+ -- A classical way of doing is to Insert all the words and then to invoke
+ -- Initialize and Compute. If Compute fails to find a perfect hash
+ -- function, invoke Initialize another time with other configuration
+ -- parameters (probably with a greater K_To_V ratio). Once successful,
+ -- invoke Produce and Finalize.
procedure Finalize;
- -- Deallocate the internal structures and the key table
+ -- Deallocate the internal structures and the words table
procedure Insert (Value : String);
- -- Insert a new key in the table
+ -- Insert a new word in the table
Too_Many_Tries : exception;
- -- Raised after Tries unsuccessfull runs
+ -- Raised after Tries unsuccessful runs
procedure Compute (Position : String := Default_Position);
-- Compute the hash function. Position allows to define selection of
- -- character positions used in the keywords hash function. Positions can be
+ -- character positions used in the word 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
+ -- 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 in case that the algorithm does not succeed in less
-- than Tries attempts (see Initialize).
-- 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
+ -- 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
-- {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
+ -- 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
-- 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
+ -- 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:
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.
+ -- Length_2 is zero, the table has only one dimension. All the ranges
+ -- start from zero.
function Value
(Name : Table_Name;
projects / gcc.git / blobdiff