gcc/ada/g-perhas.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                  G N A T . P E R F E C T _ H A S H                       --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --              Copyright (C) 2002-2003 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 package GNAT.Perfect_Hash is
  35 pragma Pure (Perfect_Hash);
  36
  37    --  The packages in this hierarchy implement perfect hash
  38    --  functions. To understand what a perfect hash function is, we
  39    --  define several notions. These definitions are inspired from the
  40    --  following paper:
  41    --
  42    --    Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An
  43    --    Optimal Algorithm for Generating Minimal Perfect Hash Functions'',
  44    --    Information Processing Letters, 43(1992) pp.257-264, Oct.1992
  45    --
  46    --  Let W be a set of m words. A hash function h is a function that
  47    --  maps the set of words W into some given interval of integers
  48    --  [0, k-1], where k is an integer, usually k >= m. h (w) where w
  49    --  is a word computes an address or an integer from I for the
  50    --  storage or the retrieval of that item. The storage area used to
  51    --  store items is known as a hash table. Words for which the same
  52    --  address is computed are called synonyms. Due to the existence
  53    --  of synonyms a situation called collision may arise in which two
  54    --  items w1 and w2 have the same address. Several schemes for
  55    --  resolving known. A perfect hash function is an injection from
  56    --  the word set W to the integer interval I with k >= m. If k = m,
  57    --  then h is a minimal perfect hash function. A hash function is
  58    --  order preserving if it puts entries into the hash table in a
  59    --  prespecified order.
  60    --
  61    --  A minimal perfect hash function is defined by two properties:
  62    --  * Since no collisions occur each item can be retrieved from the
  63    --    table in *one* probe. This represents the "perfect" property.
  64    --  * The hash table size corresponds to the exact size of W and
  65    --    *no larger*. This represents the "minimal" property.
  66
  67 end GNAT.Perfect_Hash;