[comp.lang.c] Adaptive perfect hashing

laba-3ec@web-3g.berkeley.edu (Adrian J Ho) (02/19/90)

Does anyone have any references to adaptive perfect hashing algorithms?  I'm
writing a PostScript-like interpreter and I'd like to speed up dictionary
lookups radically (especially since I'm expecting HUGE dictionaries).  What
I'm basically looking for is the ability to generate a perfect hash function
(a la gperf) on the fly.  Obviously, I'm not going to call it every time the
user adds a new definition, so the speed of the algorithm is not too
important (wouldn't mind having my cake and eating it too, though).

Also, does anyone have any C code that implements the algorithms?  I'd
rather not re-invent the wheel if at all possible, and wading through the
gperf code isn't very smart right when homework's starting to pile up.

PS. I heard rumors that the paper alluded to in the gperf docs
("Implementation Details of GNU gperf", v2.0) that describes "the high-level
description of the data structures and algorithms used to implement gperf"
has been released.  Can anyone confirm this, and if so, how can I go about
getting a copy?

Please email all replies to me, as I don't read these newsgroups regularly.
I'll post a summary after an appropriate length of time.

Thanks in advance.

-----------------------------------------------------------------------------
Adrian J Ho					   adrianho@cory.berkeley.edu
University of California, Berkeley		   adrianho@soda.berkeley.edu

schmidt@crimee.ics.uci.edu (Doug Schmidt) (02/19/90)

In article <1990Feb18.233444.7345@agate.berkeley.edu>, laba-3ec@web-3g (Adrian J Ho) writes:
>PS. I heard rumors that the paper alluded to in the gperf docs
>("Implementation Details of GNU gperf", v2.0) that describes "the high-level
>description of the data structures and algorithms used to implement gperf"
>has been released.  Can anyone confirm this, and if so, how can I go about
>getting a copy?

Sure, you can get a quasi-legible copy via anonymous ftp from
ics.uci.edu (128.195.1.1), in a file called gperf.tex.  It is
quasi-legible since you'll need to run it through LaTeX and a I didn't
include the bibtex file nor one of the special figures (it seems to
break everyone's dvi driver anyway).  However, the main algorithm is
described in detail.

The final copy of this paper will be published in the upcoming USENIX
C++ Conference Workshop proceedings, available after the middle of
April, I'd guess.

If anyone has any comments or suggests about the paper please let me
know, there's still time to make revisions!

Doug
--
A monk asked Kegon, ``How does an enlightened      | schmidt@ics.uci.edu (ARPA)
one return to the ordinary world?'' Kegon replied, | office: (714) 856-4043
``A broken mirror never reflects again; fallen
flowers never go back to the old branches.''