henges@ingr.com (John Hengesbach) (04/25/89)
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? advTHANKSance, John Hengesbach Intergraph Corp. henges@ingr.com uunet!ingr!henges (205)772-2000 -- John Hengesbach uunet!ingr!henges Intergraph henges@ingr.com 1 Madison Industrial Park (205)772-2000 Huntsville, Alabama 35807
schmidt@zola.ics.uci.edu (Doug Schmidt) (04/25/89)
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 |