www.delorie.com/gnu/docs/gperf/gperf_7.html   search  
 
Buy GNU books!


Perfect Hash Function Generator

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3. High-Level Description of GNU gperf

3.1 Input Format to gperf  
3.2 Output Format for Generated C Code with gperf  
3.3 Use of NUL characters  

The perfect hash function generator gperf reads a set of "keywords" from a keyfile (or from the standard input by default). It attempts to derive a perfect hashing function that recognizes a member of the static keyword set with at most a single probe into the lookup table. If gperf succeeds in generating such a function it produces a pair of C source code routines that perform hashing and table lookup recognition. All generated C code is directed to the standard output. Command-line options described below allow you to modify the input and output format to gperf.

By default, gperf attempts to produce time-efficient code, with less emphasis on efficient space utilization. However, several options exist that permit trading-off execution time for storage space and vice versa. In particular, expanding the generated table size produces a sparse search structure, generally yielding faster searches. Conversely, you can direct gperf to utilize a C switch statement scheme that minimizes data space storage size. Furthermore, using a C switch may actually speed up the keyword retrieval time somewhat. Actual results depend on your C compiler, of course.

In general, gperf assigns values to the characters it is using for hashing until some set of values gives each keyword a unique value. A helpful heuristic is that the larger the hash value range, the easier it is for gperf to find and generate a perfect hash function. Experimentation is the key to getting the most from gperf.


  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003