Perfect Hash Tables

Submitted by raevnos on Sat, 2011-04-16 02:04

For cases where we have to check to see if a string is one of a fixed set of values that will never change while a MUSH is running, Penn uses a tool called gperf to generate lookup functions that use a perfect hash table to quickly and efficiently check for a match.

For details on the format of a gperf file, see its documentation.

To include a gperf-generated table in Penn:

  1. Create a new foo.gperf gperf file. See the existing ones for templates.
  2. Look for the existing gperf entries in src/ and add a new one following their template to generate foo.c.
  3. Run ./config.status to rebuild src/Makefile.
  4. In the source file that uses the lookup function, #include "foo.c"

Examples can be seen in src/funmath.c and src/markup.c, among others.