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.

Pre requisite

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:

int
select
print

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;
private
...
end Hashing;

How to use the hash

Using the perfect hash generator is simple:

with Hashing;

  if Hashing.Is_Keyword (S) then
     -- 'S' is one of our keyword
  else
     -- No, it's not a keyword
  end if;