diff options
Diffstat (limited to 'gcc-4.4.0/gcc/ada/g-pehage.ads')
| -rw-r--r-- | gcc-4.4.0/gcc/ada/g-pehage.ads | 232 |
1 files changed, 0 insertions, 232 deletions
diff --git a/gcc-4.4.0/gcc/ada/g-pehage.ads b/gcc-4.4.0/gcc/ada/g-pehage.ads deleted file mode 100644 index 8b75f2e88..000000000 --- a/gcc-4.4.0/gcc/ada/g-pehage.ads +++ /dev/null @@ -1,232 +0,0 @@ ------------------------------------------------------------------------------- --- -- --- GNAT COMPILER COMPONENTS -- --- -- --- 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 -- --- -- --- S p e c -- --- -- --- Copyright (C) 2002-2008, AdaCore -- --- -- --- GNAT is free software; you can redistribute it and/or modify it under -- --- terms of the GNU General Public License as published by the Free Soft- -- --- ware Foundation; either version 2, or (at your option) any later ver- -- --- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- --- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- --- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- --- for more details. You should have received a copy of the GNU General -- --- Public License distributed with GNAT; see file COPYING. If not, write -- --- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, -- --- Boston, MA 02110-1301, USA. -- --- -- --- As a special exception, if other files instantiate generics from this -- --- unit, or you link this unit with other files to produce an executable, -- --- this unit does not by itself cause the resulting executable to be -- --- covered by the GNU General Public License. This exception does not -- --- however invalidate any other reasons why the executable file might be -- --- covered by the GNU Public License. -- --- -- --- GNAT was originally developed by the GNAT team at New York University. -- --- Extensive contributions were provided by Ada Core Technologies Inc. -- --- -- ------------------------------------------------------------------------------- - --- This package provides a generator of static minimal perfect hash functions. --- To understand what a perfect hash function is, we define several notions. --- These definitions are inspired from the following paper: - --- Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal --- Algorithm for Generating Minimal Perfect Hash Functions'', Information --- Processing Letters, 43(1992) pp.257-264, Oct.1992 - --- Let W be a set of m words. A hash function h is a function that maps the --- set of words W into some given interval of integers [0, k-1], where k is an --- integer, usually k >= m. h (w) where is a word computes an address or an --- integer from I for the storage or the retrieval of that item. The storage --- area used to store items is known as a hash table. Words for which the same --- address is computed are called synonyms. Due to the existence of synonyms a --- situation called collision may arise in which two items w1 and w2 have the --- same address. Several schemes for resolving known. A perfect hash function --- is an injection from the word set W to the integer interval I with k >= m. --- If k = m, then h is a minimal perfect hash function. A hash function is --- order preserving if it puts entries into the hash table in prespecified --- order. - --- A minimal perfect hash function is defined by two properties: - --- Since no collisions occur each item can be retrieved from the table in --- *one* probe. This represents the "perfect" property. - --- The hash table size corresponds to the exact size of W and *no larger*. --- This represents the "minimal" property. - --- The functions generated by this package require the words to be known in --- advance (they are "static" hash functions). The hash functions are also --- order preserving. If w2 is inserted after w1 in the generator, then (w1) --- < f (w2). These hashing functions are convenient for use with realtime --- applications. - -package GNAT.Perfect_Hash_Generators is - - Default_K_To_V : constant Float := 2.05; - -- Default ratio for the algorithm. When K is the number of keys, V = - -- (K_To_V) * K is the size of the main table of the hash function. To - -- converge, the algorithm requires K_To_V to be strictly greater than 2.0. - - Default_Pkg_Name : constant String := "Perfect_Hash"; - -- Default package name in which the hash function is defined - - Default_Position : constant String := ""; - -- The generator allows selection of the character positions used in the - -- hash function. By default, all positions are selected. - - Default_Tries : constant Positive := 20; - -- This algorithm may not succeed to find a possible mapping on the first - -- try and may have to iterate a number of times. This constant bounds the - -- number of tries. - - type Optimization is (Memory_Space, CPU_Time); - Default_Optimization : constant Optimization := CPU_Time; - -- Optimize either the memory space or the execution time - - Verbose : Boolean := False; - -- Output the status of the algorithm. For instance, the tables, the random - -- graph (edges, vertices) and selected char positions are output between - -- two iterations. - - procedure Initialize - (Seed : Natural; - K_To_V : Float := Default_K_To_V; - Optim : Optimization := CPU_Time; - Tries : Positive := Default_Tries); - -- Initialize the generator and its internal structures. Set the ratio of - -- vertices over keys in the random graphs. This value has to be greater - -- than 2.0 in order for the algorithm to succeed. The word set is not - -- modified (in particular when it is already set). For instance, it is - -- possible to run several times the generator with different settings on - -- the same words. - -- - -- A classical way of doing is to Insert all the words and then to invoke - -- Initialize and Compute. If Compute fails to find a perfect hash - -- function, invoke Initialize another time with other configuration - -- parameters (probably with a greater K_To_V ratio). Once successful, - -- invoke Produce and Finalize. - - procedure Finalize; - -- Deallocate the internal structures and the words table - - procedure Insert (Value : String); - -- Insert a new word in the table - - Too_Many_Tries : exception; - -- Raised after Tries unsuccessful runs - - procedure Compute (Position : String := Default_Position); - -- Compute the hash function. Position allows to define selection of - -- character positions used in the word hash function. Positions can be - -- separated by commas and range like x-y may be used. Character '$' - -- represents the final character of a word. With an empty position, the - -- generator automatically produces positions to reduce the memory usage. - -- Raise Too_Many_Tries in case that the algorithm does not succeed in less - -- than Tries attempts (see Initialize). - - procedure Produce (Pkg_Name : String := Default_Pkg_Name); - -- Generate the hash function package Pkg_Name. This package includes the - -- minimal perfect Hash function. - - -- The routines and structures defined below allow producing the hash - -- function using a different way from the procedure above. The procedure - -- Define returns the lengths of an internal table and its item type size. - -- The function Value returns the value of each item in the table. - - -- The hash function has the following form: - - -- h (w) = (g (f1 (w)) + g (f2 (w))) mod m - - -- G is a function based on a graph table [0,n-1] -> [0,m-1]. m is the - -- number of keys. n is an internally computed value and it can be obtained - -- as the length of vector G. - - -- F1 and F2 are two functions based on two function tables T1 and T2. - -- Their definition depends on the chosen optimization mode. - - -- Only some character positions are used in the words because they are - -- significant. They are listed in a character position table (P in the - -- pseudo-code below). For instance, in {"jan", "feb", "mar", "apr", "jun", - -- "jul", "aug", "sep", "oct", "nov", "dec"}, only positions 2 and 3 are - -- significant (the first character can be ignored). In this example, P = - -- {2, 3} - - -- When Optimization is CPU_Time, the first dimension of T1 and T2 - -- corresponds to the character position in the word and the second to the - -- character set. As all the character set is not used, we define a used - -- character table which associates a distinct index to each used character - -- (unused characters are mapped to zero). In this case, the second - -- dimension of T1 and T2 is reduced to the used character set (C in the - -- pseudo-code below). Therefore, the hash function has the following: - - -- function Hash (S : String) return Natural is - -- F : constant Natural := S'First - 1; - -- L : constant Natural := S'Length; - -- F1, F2 : Natural := 0; - -- J : <t>; - - -- begin - -- for K in P'Range loop - -- exit when L < P (K); - -- J := C (S (P (K) + F)); - -- F1 := (F1 + Natural (T1 (K, J))) mod <n>; - -- F2 := (F2 + Natural (T2 (K, J))) mod <n>; - -- end loop; - - -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>; - -- end Hash; - - -- When Optimization is Memory_Space, the first dimension of T1 and T2 - -- corresponds to the character position in the word and the second - -- dimension is ignored. T1 and T2 are no longer matrices but vectors. - -- Therefore, the used character table is not available. The hash function - -- has the following form: - - -- function Hash (S : String) return Natural is - -- F : constant Natural := S'First - 1; - -- L : constant Natural := S'Length; - -- F1, F2 : Natural := 0; - -- J : <t>; - - -- begin - -- for K in P'Range loop - -- exit when L < P (K); - -- J := Character'Pos (S (P (K) + F)); - -- F1 := (F1 + Natural (T1 (K) * J)) mod <n>; - -- F2 := (F2 + Natural (T2 (K) * J)) mod <n>; - -- end loop; - - -- return (Natural (G (F1)) + Natural (G (F2))) mod <m>; - -- end Hash; - - type Table_Name is - (Character_Position, - Used_Character_Set, - Function_Table_1, - Function_Table_2, - Graph_Table); - - procedure Define - (Name : Table_Name; - Item_Size : out Natural; - Length_1 : out Natural; - Length_2 : out Natural); - -- Return the definition of the table Name. This includes the length of - -- dimensions 1 and 2 and the size of an unsigned integer item. When - -- Length_2 is zero, the table has only one dimension. All the ranges - -- start from zero. - - function Value - (Name : Table_Name; - J : Natural; - K : Natural := 0) return Natural; - -- Return the value of the component (I, J) of the table Name. When the - -- table has only one dimension, J is ignored. - -end GNAT.Perfect_Hash_Generators; |