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 Ada Core Technologies, Inc.           --
  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,  59 Temple Place - Suite 330,  Boston, --
  20 -- MA 02111-1307, 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 single generator of static minimal perfect
  35 --  hash functions. No collisions occur and each item can be retrieved
  36 --  from the table in one probe (perfect property). The hash table
  37 --  size corresponds to the exact size of W and *no larger* (minimal
  38 --  property). The key set has to be know in advance (static
  39 --  property). The hash functions are also order preservering. If w2
  40 --  is inserted after w1 in the generator, then f (w1) < f (w2). These
  41 --  hashing functions are convenient for use with realtime applications.
  42
  43 package GNAT.Perfect_Hash.Generators is
  44
  45    Default_K_To_V : constant Float  := 2.05;
  46    --  Default ratio for the algorithm. When K is the number of keys,
  47    --  V = (K_To_V) * K is the size of the main table of the hash function.
  48
  49    Default_Pkg_Name : constant String := "Perfect_Hash";
  50    --  Default package name in which the hash function is defined.
  51
  52    Default_Position : constant String := "";
  53    --  The generator allows selection of the character positions used
  54    --  in the hash function. By default, all positions are selected.
  55
  56    type Optimization is (Memory_Space, CPU_Time);
  57    Default_Optimization : constant Optimization := CPU_Time;
  58    --  Optimize either the memory space or the execution time.
  59
  60    Verbose  : Boolean := False;
  61
  62    procedure Initialize
  63      (Seed   : Natural;
  64       K_To_V : Float        := Default_K_To_V;
  65       Optim  : Optimization := CPU_Time);
  66    --  Initialize the generator and its internal structures. Set the
  67    --  ratio of vertices over keys in the random graphs. This value
  68    --  has to be greater than 2.0 in order for the algorithm to succeed.
  69
  70    procedure Finalize;
  71    --  Deallocate the internal structures.
  72
  73    procedure Insert (Value : String);
  74    --  Insert a new key in the table.
  75
  76    procedure Compute (Position : String := Default_Position);
  77    --  Compute the hash function. Position allows to define a
  78    --  selection of character positions used in the keywords hash
  79    --  function. Positions can be separated by commas and range like
  80    --  x-y may be used. Character '$' represents the final character
  81    --  of a key. With an empty position, the generator automatically
  82    --  produces positions to reduce the memory usage.
  83
  84    procedure Produce (Pkg_Name  : String := Default_Pkg_Name);
  85    --  Generate the hash function package Pkg_Name. This package
  86    --  includes the minimal perfect Hash function.
  87
  88    --  The routines and structures defined below allow producing the
  89    --  hash function using a different way from the procedure above.
  90    --  The procedure Define returns the lengths of an internal table
  91    --  and its item type size. The function Value returns the value of
  92    --  each item in the table.
  93
  94    --  The hash function has the following form:
  95
  96    --             h (w) = (g (f1 (w)) + g (f2 (w))) mod m
  97
  98    --  G is a function based on a graph table [0,n-1] -> [0,m-1]. m is
  99    --  the number of keys. n is an internally computed value and it
 100    --  can be obtained as the length of vector G.
 101
 102    --  F1 and F2 are two functions based on two function tables T1 and
 103    --  T2. Their definition depends on the chosen optimization mode.
 104
 105    --  Only some character positions are used in the keys because they
 106    --  are significant. They are listed in a character position table
 107    --  (P in the pseudo-code below). For instance, in {"jan", "feb",
 108    --  "mar", "apr", "jun", "jul", "aug", "sep", "oct", "nov", "dec"},
 109    --  only positions 2 and 3 are significant (the first character can
 110    --  be ignored). In this example, P = {2, 3}
 111
 112    --  When Optimization is CPU_Time, the first dimension of T1 and T2
 113    --  corresponds to the character position in the key and the second
 114    --  to the character set. As all the character set is not used, we
 115    --  define a used character table which associates a distinct index
 116    --  to each used character (unused characters are mapped to
 117    --  zero). In this case, the second dimension of T1 and T2 is
 118    --  reduced to the used character set (C in the pseudo-code
 119    --  below). Therefore, the hash function has the following:
 120
 121    --    function Hash (S : String) return Natural is
 122    --       F      : constant Natural := S'First - 1;
 123    --       L      : constant Natural := S'Length;
 124    --       F1, F2 : Natural := 0;
 125    --       J      : <t>;
 126
 127    --    begin
 128    --       for K in P'Range loop
 129    --          exit when L < P (K);
 130    --          J  := C (S (P (K) + F));
 131    --          F1 := (F1 + Natural (T1 (K, J))) mod <n>;
 132    --          F2 := (F2 + Natural (T2 (K, J))) mod <n>;
 133    --       end loop;
 134
 135    --       return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 136    --    end Hash;
 137
 138    --  When Optimization is Memory_Space, the first dimension of T1
 139    --  and T2 corresponds to the character position in the key and the
 140    --  second dimension is ignored. T1 and T2 are no longer matrices
 141    --  but vectors. Therefore, the used character table is not
 142    --  available. The hash function has the following form:
 143
 144    --     function Hash (S : String) return Natural is
 145    --        F      : constant Natural := S'First - 1;
 146    --        L      : constant Natural := S'Length;
 147    --        F1, F2 : Natural := 0;
 148    --        J      : <t>;
 149
 150    --     begin
 151    --        for K in P'Range loop
 152    --           exit when L < P (K);
 153    --           J  := Character'Pos (S (P (K) + F));
 154    --           F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
 155    --           F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
 156    --        end loop;
 157
 158    --        return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 159    --     end Hash;
 160
 161    type Table_Name is
 162      (Character_Position,
 163       Used_Character_Set,
 164       Function_Table_1,
 165       Function_Table_2,
 166       Graph_Table);
 167
 168    procedure Define
 169      (Name      : Table_Name;
 170       Item_Size : out Natural;
 171       Length_1  : out Natural;
 172       Length_2  : out Natural);
 173    --  Return the definition of the table Name. This includes the
 174    --  length of dimensions 1 and 2 and the size of an unsigned
 175    --  integer item. When Length_2 is zero, the table has only one
 176    --  dimension. All the ranges start from zero.
 177
 178    function Value
 179      (Name : Table_Name;
 180       J    : Natural;
 181       K    : Natural := 0)
 182       return Natural;
 183    --  Return the value of the component (I, J) of the table
 184    --  Name. When the table has only one dimension, J is ignored.
 185
 186 end GNAT.Perfect_Hash.Generators;