gcc/ada/libgnat/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-2024, 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 3,  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.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- GNAT was originally developed  by the GNAT team at  New York University. --
  28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  29 --                                                                          --
  30 ------------------------------------------------------------------------------
  31
  32 --  This package provides a generator of static minimal perfect hash functions.
  33 --  To understand what a perfect hash function is, we define several notions.
  34 --  These definitions are inspired from the following paper:
  35
  36 --    Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal
  37 --    Algorithm for Generating Minimal Perfect Hash Functions'', Information
  38 --    Processing Letters, 43(1992) pp.257-264, Oct.1992
  39
  40 --  Let W be a set of m words. A hash function h is a function that maps the
  41 --  set of words W into some given interval I of integers [0, k-1], where k is
  42 --  an integer, usually k >= m. h (w) where w is a word in W computes an
  43 --  address or an integer from I for the storage or the retrieval of that
  44 --  item. The storage area used to store items is known as a hash table. Words
  45 --  for which the same address is computed are called synonyms. Due to the
  46 --  existence of synonyms a situation called collision may arise in which two
  47 --  items w1 and w2 have the same address. Several schemes for resolving
  48 --  collisions are known. A perfect hash function is an injection from the word
  49 --  set W to the integer interval I with k >= m.  If k = m, then h is a minimal
  50 --  perfect hash function. A hash function is order preserving if it puts
  51 --  entries into the hash table in a prespecified order.
  52
  53 --  A minimal perfect hash function is defined by two properties:
  54
  55 --    Since no collisions occur each item can be retrieved from the table in
  56 --    *one* probe. This represents the "perfect" property.
  57
  58 --    The hash table size corresponds to the exact size of W and *no larger*.
  59 --    This represents the "minimal" property.
  60
  61 --  The functions generated by this package require the words to be known in
  62 --  advance (they are "static" hash functions). The hash functions are also
  63 --  order preserving. If w2 is inserted after w1 in the generator, then h (w1)
  64 --  < h (w2). These hashing functions are convenient for use with realtime
  65 --  applications.
  66
  67 with System.Perfect_Hash_Generators;
  68
  69 package GNAT.Perfect_Hash_Generators is
  70
  71    package SPHG renames System.Perfect_Hash_Generators;
  72
  73    Default_K_To_V : constant Float  := 2.05;
  74    --  Default ratio for the algorithm. When K is the number of keys, V =
  75    --  (K_To_V) * K is the size of the main table of the hash function. To
  76    --  converge, the algorithm requires K_To_V to be strictly greater than 2.0.
  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 in the
  83    --  hash function. By default, all positions are selected.
  84
  85    Default_Tries : constant Positive := 20;
  86    --  This algorithm may not succeed to find a possible mapping on the first
  87    --  try and may have to iterate a number of times. This constant bounds the
  88    --  number of tries.
  89
  90    type Optimization is new SPHG.Optimization;
  91    --  Optimize either the memory space or the execution time. Note: in
  92    --  practice, the optimization mode has little effect on speed. The tables
  93    --  are somewhat smaller with Memory_Space.
  94
  95    Verbose : Boolean renames SPHG.Verbose;
  96    --  Output the status of the algorithm. For instance, the tables, the random
  97    --  graph (edges, vertices) and selected char positions are output between
  98    --  two iterations.
  99
 100    procedure Initialize
 101      (Seed   : Natural;
 102       K_To_V : Float        := Default_K_To_V;
 103       Optim  : Optimization := Memory_Space;
 104       Tries  : Positive     := Default_Tries);
 105    --  Initialize the generator and its internal structures. Set the ratio of
 106    --  vertices over keys in the random graphs. This value has to be greater
 107    --  than 2.0 in order for the algorithm to succeed. The word set is not
 108    --  modified (in particular when it is already set). For instance, it is
 109    --  possible to run several times the generator with different settings on
 110    --  the same words.
 111    --
 112    --  A classical way of doing is to Insert all the words and then to invoke
 113    --  Initialize and Compute. If this fails to find a perfect hash function,
 114    --  invoke Initialize again with other configuration parameters (probably
 115    --  with a greater K_To_V ratio). Once successful, invoke Produce and then
 116    --  Finalize.
 117
 118    procedure Finalize;
 119    --  Deallocate the internal structures and the words table
 120
 121    procedure Insert (Value : String);
 122    --  Insert a new word into the table. ASCII.NUL characters are not allowed.
 123
 124    Too_Many_Tries : exception renames SPHG.Too_Many_Tries;
 125    --  Raised after Tries unsuccessful runs
 126
 127    procedure Compute (Position : String := Default_Position);
 128    --  Compute the hash function. Position allows the definition of selection
 129    --  of character positions used in the word hash function. Positions can be
 130    --  separated by commas and ranges like x-y may be used. Character '$'
 131    --  represents the final character of a word. With an empty position, the
 132    --  generator automatically produces positions to reduce the memory usage.
 133    --  Raise Too_Many_Tries if the algorithm does not succeed within Tries
 134    --  attempts (see Initialize).
 135
 136    procedure Produce
 137      (Pkg_Name   : String  := Default_Pkg_Name;
 138       Use_Stdout : Boolean := False);
 139    --  Generate the hash function package Pkg_Name. This package includes the
 140    --  minimal perfect Hash function. The output is normally placed in the
 141    --  current directory, in files X.ads and X.adb, where X is the standard
 142    --  GNAT file name for a package named Pkg_Name. If Use_Stdout is True, the
 143    --  output goes to standard output, and no files are written.
 144
 145 end GNAT.Perfect_Hash_Generators;