1While teaching a data structures course at University of California, 2Irvine, I developed a program called GPERF that generates perfect hash 3functions for sets of key words. A perfect hash function is simply:
| 1While teaching a data structures course at University of California, 2Irvine, I developed a program called GPERF that generates perfect hash 3functions for sets of key words. A perfect hash function is simply:
|
4 5 A hash function and a data structure that allows 6 recognition of a key word in a set of words using
| 4 5 A hash function and a data structure that allows 6 recognition of a key word in a set of words using
|
7 exactly 1 probe into the data structure.
| 7 exactly 1 probe into the data structure.
|
8
| 8
|
9The gperf.texinfo file explains how the program works, the form of the 10input, what options are available, and hints on choosing the best 11options for particular key word sets. The texinfo file is readable 12both via the GNU emacs `info' command, and is also suitable for
| 9The gperf.texinfo file explains how the program works, the form of the 10input, what options are available, and hints on choosing the best 11options for particular key word sets. The texinfo file is readable 12both via the GNU emacs `info' command, and is also suitable for
|
13typesetting with TeX. The texinfo.tex macros needed to run 14gperf.texinfo through TeX are available in the GNU GCC release. If 15you don't have access to these please email me and I'll send them to 16you (about 75k). 17
| 13typesetting with TeX. 14
|
18The enclosed Makefile creates the executable program ``gperf'' and 19also runs some tests.
| 15The enclosed Makefile creates the executable program ``gperf'' and 16also runs some tests.
|
20
| 17
|
21Output from the GPERF program is used to recognize reserved words in 22the GNU C, GNU C++, and GNU Pascal compilers, as well as with the GNU 23indent program.
| 18Output from the GPERF program is used to recognize reserved words in 19the GNU C, GNU C++, and GNU Pascal compilers, as well as with the GNU 20indent program.
|
24
| 21
|
25Happy hacking!
| 22Happy hacking!
|
26
| 23
|
27Douglas C. Schmidt
| 24Douglas C. Schmidt
|
28schmidt@ics.uci.edu
| |
| |