By stephane.carrez 2012-01-16 21:31:23
A perfect hash function is a function that returns a distinct hash number for each keyword of a well defined set.
gperf is famous and well known perfect hash generator used for C or C++ languages. Ada is not supported.
The gperfhash is a sample from
the Ada Utility Library which generates an Ada package that implements such perfect hash operation.
It is not as complete as gperf but allows to easily get a hash operation.
The gperfhash tool uses the GNAT package GNAT.Perfect_Hash_Generators.
Since the gperfhash tool is provided by the Ada Util samples, you must build these samples with the following command:
$ gnatmake -Psamples
Define a keyword file
First, create a file which contains one keyword on each line. For example, let's write a keywords.txt file which contains the following three keywords:
Generate the package
Run the gperfhash tool and give it the package name.
$ gperfhash -p Hashing keywords.txt
The package defines a Hash and an Is_Keyword function.
The Hash function returns a hash number for each string passed as argument. The hash number will be different for each string that matches one of our keyword.
You can give a string not in the keyword list, in that case the hash function will return a number that collides with a hash number of one or our keyword.
The Is_Keyword function allows to check whether a string is a keyword of the list. This is very useful when you just want to know whether a string is a reserved keyword in some application.
The package specification is the following:
-- Generated by gperfhash
package Hashing is
function Hash (S : String) return Natural;
-- Returns true if the string <b>S</b> is a keyword.
function Is_Keyword (S : in String) return Boolean;
type Name_Access is access constant String;
type Keyword_Array is array (Natural range <>) of Name_Access;
Keywords : constant Keyword_Array;
How to use the hash
Using the perfect hash generator is simple:
if Hashing.Is_Keyword (S) then
-- 'S' is one of our keyword
-- No, it's not a keyword