Xref: utzoo gnu.gcc:431 comp.sources.wanted:7150
Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!unmvax!pprg.unm.edu!hc!ames!elroy!usc!orion.cf.uci.edu!uci-ics!zola.ics.uci.edu!schmidt
From: schmidt@zola.ics.uci.edu (Doug Schmidt)
Newsgroups: gnu.gcc,comp.sources.wanted
Subject: Re: looking for perfect hash information
Keywords: perfect hash, searching
Message-ID: <12639@paris.ics.uci.edu>
Date: 25 Apr 89 05:10:47 GMT
References: <5077@ingr.com>
Sender: news@paris.ics.uci.edu
Reply-To: Doug Schmidt <schmidt@zola.ics.uci.edu>
Organization: University of California at Irvine: ICS Dept.
Lines: 39

In article <5077@ingr.com> henges@ingr.com (John Hengesbach) writes:
++ 
++ I am looking for information on the perfect hashing scheme used in the GNU
++ C compiler.  I understand how the whole things works, given the table of
++ keywords and the indexes of the characters.  The question is how would
++ the program work that created the order of the table and the offsets of
++ the character?
++ 
++ Does any one have the details?  

The program, gperf, is pretty straight-forward actually, though it
uses some tricky data structures to speed up searching.  Essentially,
the program attempts to generate a unique mapping of selected keyword
`key characters' within a user-controlled range.  Many options exist,
they generally permit the user to specify trade-offs between keyword
lookup time and storage table space.  The algorithm has a some
limitations, e.g., it doesn't always work well for large (> 1000) sets
of similar keys.  However, for computer language keywords and most
assembly language instruction sets it performs extremely well.

You can obtain a copy of the latest version via anonymous ftp from
ics.uci.edu (128.195.1.1).  It's in the pub/ subdirectory and is
called gperf-1.5.tar.Z.  It is written in GNU G++ (a C version is
being created).  Included in the distribution are input files
that generate perfect hash functions for Ada, C, C++, Modula 2 and 3,
and Pascal.  If you'd like to provide input files for other languages
please send them to me.

   Thanks,

      Doug        

p.s. If anyone does *not* have access to FTP, and would like a copy
     of gperf, please send me email and I'll post it to you.
--
On a clear day, under blue skies, there is no need to seek.
And asking about Buddha                +------------------------+
Is like proclaiming innocence,         | schmidt@ics.uci.edu    |
With loot in your pocket.              | office: (714) 856-4043 |