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-2004 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 generator of static minimal perfect hash
  35 --  functions. To understand what a perfect hash function is, we
  36 --  define several notions. These definitions are inspired from the
  37 --  following paper:
  38
  39 --    Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An
  40 --    Optimal Algorithm for Generating Minimal Perfect Hash Functions'',
  41 --    Information Processing Letters, 43(1992) pp.257-264, Oct.1992
  42
  43 --  Let W be a set of m words. A hash function h is a function that
  44 --  maps the set of words W into some given interval of integers
  45 --  [0, k-1], where k is an integer, usually k >= m. h (w) where w
  46 --  is a word computes an address or an integer from I for the
  47 --  storage or the retrieval of that item. The storage area used to
  48 --  store items is known as a hash table. Words for which the same
  49 --  address is computed are called synonyms. Due to the existence
  50 --  of synonyms a situation called collision may arise in which two
  51 --  items w1 and w2 have the same address. Several schemes for
  52 --  resolving known. A perfect hash function is an injection from
  53 --  the word set W to the integer interval I with k >= m. If k = m,
  54 --  then h is a minimal perfect hash function. A hash function is
  55 --  order preserving if it puts entries into the hash table in a
  56 --  prespecified order.
  57
  58 --  A minimal perfect hash function is defined by two properties:
  59
  60 --    Since no collisions occur each item can be retrieved from the
  61 --    table in *one* probe. This represents the "perfect" property.
  62
  63 --    The hash table size corresponds to the exact size of W and
  64 --    *no larger*. This represents the "minimal" property.
  65
  66 --  The functions generated by this package require the key set to
  67 --  be known in advance (they are "static" hash functions).
  68 --  The hash functions are also order preservering. If w2 is inserted
  69 --  after w1 in the generator, then f (w1) < f (w2). These hashing
  70 --  functions are convenient for use with realtime applications.
  71
  72 package GNAT.Perfect_Hash_Generators is
  73
  74    Default_K_To_V : constant Float  := 2.05;
  75    --  Default ratio for the algorithm. When K is the number of keys,
  76    --  V = (K_To_V) * K is the size of the main table of the hash function.
  77
  78    Default_Pkg_Name : constant String := "Perfect_Hash";
  79    --  Default package name in which the hash function is defined.
  80
  81    Default_Position : constant String := "";
  82    --  The generator allows selection of the character positions used
  83    --  in the hash function. By default, all positions are selected.
  84
  85    type Optimization is (Memory_Space, CPU_Time);
  86    Default_Optimization : constant Optimization := CPU_Time;
  87    --  Optimize either the memory space or the execution time.
  88
  89    Verbose : Boolean := False;
  90    --  Comment required ???
  91
  92    procedure Initialize
  93      (Seed   : Natural;
  94       K_To_V : Float        := Default_K_To_V;
  95       Optim  : Optimization := CPU_Time);
  96    --  Initialize the generator and its internal structures. Set the
  97    --  ratio of vertices over keys in the random graphs. This value
  98    --  has to be greater than 2.0 in order for the algorithm to succeed.
  99
 100    procedure Finalize;
 101    --  Deallocate the internal structures.
 102
 103    procedure Insert (Value : String);
 104    --  Insert a new key in the table.
 105
 106    procedure Compute (Position : String := Default_Position);
 107    --  Compute the hash function. Position allows to define a
 108    --  selection of character positions used in the keywords hash
 109    --  function. Positions can be separated by commas and range like
 110    --  x-y may be used. Character '$' represents the final character
 111    --  of a key. With an empty position, the generator automatically
 112    --  produces positions to reduce the memory usage.
 113
 114    procedure Produce (Pkg_Name  : String := Default_Pkg_Name);
 115    --  Generate the hash function package Pkg_Name. This package
 116    --  includes the minimal perfect Hash function.
 117
 118    --  The routines and structures defined below allow producing the
 119    --  hash function using a different way from the procedure above.
 120    --  The procedure Define returns the lengths of an internal table
 121    --  and its item type size. The function Value returns the value of
 122    --  each item in the table.
 123
 124    --  The hash function has the following form:
 125
 126    --             h (w) = (g (f1 (w)) + g (f2 (w))) mod m
 127
 128    --  G is a function based on a graph table [0,n-1] -> [0,m-1]. m is
 129    --  the number of keys. n is an internally computed value and it
 130    --  can be obtained as the length of vector G.
 131
 132    --  F1 and F2 are two functions based on two function tables T1 and
 133    --  T2. Their definition depends on the chosen optimization mode.
 134
 135    --  Only some character positions are used in the keys because they
 136    --  are significant. They are listed in a character position table
 137    --  (P in the pseudo-code below). For instance, in {"jan", "feb",
 138    --  "mar", "apr", "jun", "jul", "aug", "sep", "oct", "nov", "dec"},
 139    --  only positions 2 and 3 are significant (the first character can
 140    --  be ignored). In this example, P = {2, 3}
 141
 142    --  When Optimization is CPU_Time, the first dimension of T1 and T2
 143    --  corresponds to the character position in the key and the second
 144    --  to the character set. As all the character set is not used, we
 145    --  define a used character table which associates a distinct index
 146    --  to each used character (unused characters are mapped to
 147    --  zero). In this case, the second dimension of T1 and T2 is
 148    --  reduced to the used character set (C in the pseudo-code
 149    --  below). Therefore, the hash function has the following:
 150
 151    --    function Hash (S : String) return Natural is
 152    --       F      : constant Natural := S'First - 1;
 153    --       L      : constant Natural := S'Length;
 154    --       F1, F2 : Natural := 0;
 155    --       J      : <t>;
 156
 157    --    begin
 158    --       for K in P'Range loop
 159    --          exit when L < P (K);
 160    --          J  := C (S (P (K) + F));
 161    --          F1 := (F1 + Natural (T1 (K, J))) mod <n>;
 162    --          F2 := (F2 + Natural (T2 (K, J))) mod <n>;
 163    --       end loop;
 164
 165    --       return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 166    --    end Hash;
 167
 168    --  When Optimization is Memory_Space, the first dimension of T1
 169    --  and T2 corresponds to the character position in the key and the
 170    --  second dimension is ignored. T1 and T2 are no longer matrices
 171    --  but vectors. Therefore, the used character table is not
 172    --  available. The hash function has the following form:
 173
 174    --     function Hash (S : String) return Natural is
 175    --        F      : constant Natural := S'First - 1;
 176    --        L      : constant Natural := S'Length;
 177    --        F1, F2 : Natural := 0;
 178    --        J      : <t>;
 179
 180    --     begin
 181    --        for K in P'Range loop
 182    --           exit when L < P (K);
 183    --           J  := Character'Pos (S (P (K) + F));
 184    --           F1 := (F1 + Natural (T1 (K) * J)) mod <n>;
 185    --           F2 := (F2 + Natural (T2 (K) * J)) mod <n>;
 186    --        end loop;
 187
 188    --        return (Natural (G (F1)) + Natural (G (F2))) mod <m>;
 189    --     end Hash;
 190
 191    type Table_Name is
 192      (Character_Position,
 193       Used_Character_Set,
 194       Function_Table_1,
 195       Function_Table_2,
 196       Graph_Table);
 197
 198    procedure Define
 199      (Name      : Table_Name;
 200       Item_Size : out Natural;
 201       Length_1  : out Natural;
 202       Length_2  : out Natural);
 203    --  Return the definition of the table Name. This includes the
 204    --  length of dimensions 1 and 2 and the size of an unsigned
 205    --  integer item. When Length_2 is zero, the table has only one
 206    --  dimension. All the ranges start from zero.
 207
 208    function Value
 209      (Name : Table_Name;
 210       J    : Natural;
 211       K    : Natural := 0)
 212       return Natural;
 213    --  Return the value of the component (I, J) of the table
 214    --  Name. When the table has only one dimension, J is ignored.
 215
 216 end GNAT.Perfect_Hash_Generators;