Xref: utzoo comp.lang.misc:4121 comp.lang.c:26051
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!bionet!agate!web-3g!laba-3ec
From: laba-3ec@web-3g.berkeley.edu (Adrian J Ho)
Newsgroups: comp.lang.misc,comp.lang.c
Subject: Adaptive perfect hashing
Summary: Algorithms and/or code needed
Keywords: perfect hashing adaptive gperf
Message-ID: <1990Feb18.233444.7345@agate.berkeley.edu>
Date: 18 Feb 90 23:34:44 GMT
References: <1990Feb10.160605.25254@ux1.cso.uiuc.edu> <4896@brazos.Rice.edu>
Sender: laba-3ec@web.berkeley.edu (Adrian J Ho)
Reply-To: adrianho@cory.berkeley.edu (Adrian J Ho)
Organization: University of California, Berkeley
Lines: 26

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