gcc/ada/g-pehage.ads

   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 2,  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.  See the GNU General Public License --
  17 -- for  more details.  You should have  received  a copy of the GNU General --
  18 -- Public License  distributed with GNAT;  see file COPYING.  If not, write --
  19 -- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth  Floor, --
  20 -- Boston, MA 02110-1301, USA.                                              --
  21 --                                                                          --
  22 -- As a special exception,  if other files  instantiate  generics from this --
  23 -- unit, or you link  this unit with other files  to produce an executable, --
  24 -- this  unit  does not  by itself cause  the resulting  executable  to  be --
  25 -- covered  by the  GNU  General  Public  License.  This exception does not --
  26 -- however invalidate  any other reasons why  the executable file  might be --
  27 -- covered by the  GNU Public License.                                      --
  28 --                                                                          --
  29 -- GNAT was originally developed  by the GNAT team at  New York University. --
  30 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  31 --                                                                          --
  32 ------------------------------------------------------------------------------
  33
  34 --  This package provides a generator of static minimal perfect hash functions.
  35 --  To understand what a perfect hash function is, we define several notions.
  36 --  These definitions are inspired from the following paper:
  37
  38 --    Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal
  39 --    Algorithm for Generating Minimal Perfect Hash Functions'', Information
  40 --    Processing Letters, 43(1992) pp.257-264, Oct.1992
  41
  42 --  Let W be a set of m words. A hash function h is a function that maps the
  43 --  set of words W into some given interval I of integers [0, k-1], where k is
  44 --  an integer, usually k >= m. h (w) where w is a word in W computes an
  45 --  address or an integer from I for the storage or the retrieval of that
  46 --  item. The storage area used to store items is known as a hash table. Words
  47 --  for which the same address is computed are called synonyms. Due to the
  48 --  existence of synonyms a situation called collision may arise in which two
  49 --  items w1 and w2 have the same address. Several schemes for resolving
  50 --  collisions are known. A perfect hash function is an injection from the word
  51 --  set W to the integer interval I with k >= m.  If k = m, then h is a minimal
  52 --  perfect hash function. A hash function is order preserving if it puts
  53 --  entries into the hash table in a prespecified order.
  54
  55 --  A minimal perfect hash function is defined by two properties:
  56
  57 --    Since no collisions occur each item can be retrieved from the table in
  58 --    *one* probe. This represents the "perfect" property.
  59
  60 --    The hash table size corresponds to the exact size of W and *no larger*.
  61 --    This represents the "minimal" property.
  62
  63 --  The functions generated by this package require the words to be known in
  64 --  advance (they are "static" hash functions). The hash functions are also
  65 --  order preserving. If w2 is inserted after w1 in the generator, then h (w1)
  66 --  < h (w2). These hashing functions are convenient for use with realtime
  67 --  applications.
  68
  69 package GNAT.Perfect_Hash_Generators is
  70
  71    Default_K_To_V : constant Float  := 2.05;
  72    --  Default ratio for the algorithm. When K is the number of keys, V =
  73    --  (K_To_V) * K is the size of the main table of the hash function. To
  74    --  converge, the algorithm requires K_To_V to be strictly greater than 2.0.
  75
  76    Default_Pkg_Name : constant String := "Perfect_Hash";
  77    --  Default package name in which the hash function is defined
  78
  79    Default_Position : constant String := "";
  80    --  The generator allows selection of the character positions used in the
  81    --  hash function. By default, all positions are selected.
  82
  83    Default_Tries : constant Positive := 20;
  84    --  This algorithm may not succeed to find a possible mapping on the first
  85    --  try and may have to iterate a number of times. This constant bounds the
  86    --  number of tries.
  87
  88    type Optimization is (Memory_Space, CPU_Time);
  89    --  Optimize either the memory space or the execution time. Note: in
  90    --  practice, the optimization mode has little effect on speed. The tables
  91    --  are somewhat smaller with Memory_Space.
  92
  93    Verbose : Boolean := False;
  94    --  Output the status of the algorithm. For instance, the tables, the random
  95    --  graph (edges, vertices) and selected char positions are output between
  96    --  two iterations.
  97
  98    procedure Initialize
  99      (Seed   : Natural;
 100       K_To_V : Float        := Default_K_To_V;
 101       Optim  : Optimization := Memory_Space;
 102       Tries  : Positive     := Default_Tries);
 103    --  Initialize the generator and its internal structures. Set the ratio of
 104    --  vertices over keys in the random graphs. This value has to be greater
 105    --  than 2.0 in order for the algorithm to succeed. The word set is not
 106    --  modified (in particular when it is already set). For instance, it is
 107    --  possible to run several times the generator with different settings on
 108    --  the same words.
 109    --
 110    --  A classical way of doing is to Insert all the words and then to invoke
 111    --  Initialize and Compute. If Compute fails to find a perfect hash
 112    --  function, invoke Initialize another time with other configuration
 113    --  parameters (probably with a greater K_To_V ratio). Once successful,
 114    --  invoke Produce and Finalize.
 115
 116    procedure Finalize;
 117    --  Deallocate the internal structures and the words table
 118
 119    procedure Insert (Value : String);
 120    --  Insert a new word into the table. ASCII.NUL characters are not allowed.
 121
 122    Too_Many_Tries : exception;
 123    --  Raised after Tries unsuccessful runs
 124
 125    procedure Compute (Position : String := Default_Position);
 126    --  Compute the hash function. Position allows to define selection of
 127    --  character positions used in the word hash function. Positions can be
 128    --  separated by commas and ranges like x-y may be used. Character '$'
 129    --  represents the final character of a word. With an empty position, the
 130    --  generator automatically produces positions to reduce the memory usage.
 131    --  Raise Too_Many_Tries if the algorithm does not succeed within Tries
 132    --  attempts (see Initialize).
 133
 134    procedure Produce (Pkg_Name : String := Default_Pkg_Name);
 135    --  Generate the hash function package Pkg_Name. This package includes the
 136    --  minimal perfect Hash function. The output is placed in the current
 137    --  directory, in files X.ads and X.adb, where X is the standard GNAT file
 138    --  name for a package named Pkg_Name.
 139
 140    ----------------------------------------------------------------
 141
 142    --  The routines and structures defined below allow producing the hash
 143    --  function using a different way from the procedure above. The procedure
 144    --  Define returns the lengths of an internal table and its item type size.
 145    --  The function Value returns the value of each item in the table.
 146
 147    --  The hash function has the following form:
 148
 149    --             h (w) = (g (f1 (w)) + g (f2 (w))) mod m
 150
 151    --  G is a function based on a graph table [0,n-1] -> [0,m-1]. m is the
 152    --  number of keys. n is an internally computed value and it can be obtained
 153    --  as the length of vector G.
 154
 155    --  F1 and F2 are two functions based on two function tables T1 and T2.
 156    --  Their definition depends on the chosen optimization mode.
 157
 158    --  Only some character positions are used in the words because they are
 159    --  significant. They are listed in a character position table (P in the
 160    --  pseudo-code below). For instance, in {"jan", "feb", "mar", "apr", "jun",
 161    --  "jul", "aug", "sep", "oct", "nov", "dec"}, only positions 2 and 3 are
 162    --  significant (the first character can be ignored). In this example, P =
 163    --  {2, 3}
 164
 165    --  When Optimization is CPU_Time, the first dimension of T1 and T2
 166    --  corresponds to the character position in the word and the second to the
 167    --  character set. As all the character set is not used, we define a used
 168    --  character table which associates a distinct index to each used character
 169    --  (unused characters are mapped to zero). In this case, the second
 170    --  dimension of T1 and T2 is reduced to the used character set (C in the
 171    --  pseudo-code below). Therefore, the hash function has the following:
 172
 173    --    function Hash (S : String) return Natural is
 174    --       F      : constant Natural := S'First - 1;
 175    --       L      : constant Natural := S'Length;
 176    --       F1, F2 : Natural := 0;
 177    --       J      : <t>;
 178
 179    --    begin
 180    --       for K in P'Range loop
 181    --          exit when L < P (K);
 182    --          J  := C (S (P (K) + F));
 183    --          F1 := (F1 + Natural (T1 (K, J))) mod <n>;
 184    --          F2 := (F2 + Natural (T2 (K, J))) mod <n>;
 185    --       end loop;
 186
 187    --       return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 188    --    end Hash;
 189
 190    --  When Optimization is Memory_Space, the first dimension of T1 and T2
 191    --  corresponds to the character position in the word and the second
 192    --  dimension is ignored. T1 and T2 are no longer matrices but vectors.
 193    --  Therefore, the used character table is not available. The hash function
 194    --  has the following form:
 195
 196    --     function Hash (S : String) return Natural is
 197    --        F      : constant Natural := S'First - 1;
 198    --        L      : constant Natural := S'Length;
 199    --        F1, F2 : Natural := 0;
 200    --        J      : <t>;
 201
 202    --     begin
 203    --        for K in P'Range loop
 204    --           exit when L < P (K);
 205    --           J  := Character'Pos (S (P (K) + F));
 206    --           F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
 207    --           F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
 208    --        end loop;
 209
 210    --        return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 211    --     end Hash;
 212
 213    type Table_Name is
 214      (Character_Position,
 215       Used_Character_Set,
 216       Function_Table_1,
 217       Function_Table_2,
 218       Graph_Table);
 219
 220    procedure Define
 221      (Name      : Table_Name;
 222       Item_Size : out Natural;
 223       Length_1  : out Natural;
 224       Length_2  : out Natural);
 225    --  Return the definition of the table Name. This includes the length of
 226    --  dimensions 1 and 2 and the size of an unsigned integer item. When
 227    --  Length_2 is zero, the table has only one dimension. All the ranges
 228    --  start from zero.
 229
 230    function Value
 231      (Name : Table_Name;
 232       J    : Natural;
 233       K    : Natural := 0) return Natural;
 234    --  Return the value of the component (I, J) of the table Name. When the
 235    --  table has only one dimension, J is ignored.
 236
 237 end GNAT.Perfect_Hash_Generators;