gperf
The perfect hash function generator gperf reads a set of
“keywords” from an input file (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 bytes 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.
gperf
You can control the input file format by varying certain command-line
arguments, in particular the ‘-t’ option. The input's appearance
is similar to GNU utilities flex and bison (or UNIX
utilities lex and yacc). Here's an outline of the general
format:
declarations %% keywords %% functions
Unlike flex or bison, the declarations section and
the functions section are optional. The following sections describe the
input format for each section.
It is possible to omit the declaration section entirely, if the ‘-t’ option is not given. In this case the input file begins directly with the first keyword line, e.g.:
january february march april ...
The keyword input file optionally contains a section for including
arbitrary C declarations and definitions, gperf declarations that
act like command-line options, as well as for providing a user-supplied
struct.
struct
If the ‘-t’ option (or, equivalently, the ‘%struct-type’ declaration)
is enabled, you must provide a C struct as the last
component in the declaration section from the input file. The first
field in this struct must be of type char * or const char *
if the ‘-P’ option is not given, or of type int if the option
‘-P’ (or, equivalently, the ‘%pic’ declaration) is enabled.
This first field must be called ‘name’, although it is possible to modify
its name with the ‘-K’ option (or, equivalently, the
‘%define slot-name’ declaration) described below.
Here is a simple example, using months of the year and their attributes as input:
struct month { char *name; int number; int days; int leap_days; };
%%
january, 1, 31, 31
february, 2, 28, 29
march, 3, 31, 31
april, 4, 30, 30
may, 5, 31, 31
june, 6, 30, 30
july, 7, 31, 31
august, 8, 31, 31
september, 9, 30, 30
october, 10, 31, 31
november, 11, 30, 30
december, 12, 31, 31
Separating the struct declaration from the list of keywords and
other fields are a pair of consecutive percent signs, ‘%%’,
appearing left justified in the first column, as in the UNIX utility
lex.
If the struct has already been declared in an include file, it can
be mentioned in an abbreviated form, like this:
struct month; %% january, 1, 31, 31 ...
The declaration section can contain gperf declarations. They
influence the way gperf works, like command line options do.
In fact, every such declaration is equivalent to a command line option.
There are three forms of declarations:
When a declaration is given both in the input file and as a command line option, the command-line option's value prevails.
The following gperf declarations are available.
struct type declaration for generated
code; see above for an example.
gperf to generate code in the language specified by the
option's argument. Languages handled are currently:
#define const to empty
for compilers which don't know about this keyword.
struct.
Perfect_Hash.
isalnum and isgraph do
not guarantee that a byte is in this range. Only an explicit
test like ‘c >= 'A' && c <= 'Z'’ guarantees this.)
strcmp.
However, using ‘%compare-lengths’ might greatly increase the size of the
generated C code if the lookup table range is large (which implies that
the switch option ‘-S’ or ‘%switch’ is not enabled), since the length
table contains as many elements as there are entries in the lookup table.
strncmp function to perform
string comparisons. The default action is to use strcmp.
<jjc@ai.mit.edu>.
<string.h>, at the
beginning of the code. By default, this is not done; the user must
include this header file himself to allow compilation of the code.
TOTAL_KEYWORDS,
MIN_WORD_LENGTH, MAX_WORD_LENGTH, and so on. This option
permits the use of two hash tables in the same file, even when the option
‘-E’ (or, equivalently, the ‘%enum’ declaration) is not given or
the option ‘-G’ (or, equivalently, the ‘%global-table’ declaration)
is given.
switch statement scheme,
rather than an array lookup table. This can lead to a reduction in both
time and space requirements for some input files. The argument to this
option determines how many switch statements are generated. A
value of 1 generates 1 switch containing all the elements, a
value of 2 generates 2 tables with 1/2 the elements in each
switch, etc. This is useful since many C compilers cannot
correctly generate code for large switch statements. This option
was inspired in part by Keith Bostic's original C program.
Using a syntax similar to GNU utilities flex and bison, it
is possible to directly include C source text and comments verbatim into
the generated output file. This is accomplished by enclosing the region
inside left-justified surrounding ‘%{’, ‘%}’ pairs. Here is
an input fragment based on the previous example that illustrates this
feature:
%{
#include <assert.h>
/* This section of code is inserted directly into the output. */
int return_month_days (struct month *months, int is_leap_year);
%}
struct month { char *name; int number; int days; int leap_days; };
%%
january, 1, 31, 31
february, 2, 28, 29
march, 3, 31, 31
...
The second input file format section contains lines of keywords and any associated attributes you might supply. A line beginning with ‘#’ in the first column is considered a comment. Everything following the ‘#’ is ignored, up to and including the following newline. A line beginning with ‘%’ in the first column is an option declaration and must not occur within the keywords section.
The first field of each non-comment line is always the keyword itself. It
can be given in two ways: as a simple name, i.e., without surrounding
string quotation marks, or as a string enclosed in double-quotes, in
C syntax, possibly with backslash escapes like \" or \234
or \xa8. In either case, it must start right at the beginning
of the line, without leading whitespace.
In this context, a “field” is considered to extend up to, but
not include, the first blank, comma, or newline. Here is a simple
example taken from a partial list of C reserved words:
# These are a few C reserved words, see the c.gperf file # for a complete list of ANSI C reserved words. unsigned sizeof switch signed if default for while return
Note that unlike flex or bison the first ‘%%’ marker
may be elided if the declaration section is empty.
Additional fields may optionally follow the leading keyword. Fields
should be separated by commas, and terminate at the end of line. What
these fields mean is entirely up to you; they are used to initialize the
elements of the user-defined struct provided by you in the
declaration section. If the ‘-t’ option (or, equivalently, the
‘%struct-type’ declaration) is not enabled
these fields are simply ignored. All previous examples except the last
one contain keyword attributes.
The optional third section also corresponds closely with conventions
found in flex and bison. All text in this section,
starting at the final ‘%%’ and extending to the end of the input
file, is included verbatim into the generated output file. Naturally,
it is your responsibility to ensure that the code contained in this
section is valid C.
indent.
If you want to invoke GNU indent on a gperf input file,
you will see that GNU indent doesn't understand the ‘%%’,
‘%{’ and ‘%}’ directives that control gperf's
interpretation of the input file. Therefore you have to insert some
directives for GNU indent. More precisely, assuming the most
general input file structure
declarations part 1
%{
verbatim code
%}
declarations part 2
%%
keywords
%%
functions
you would insert ‘*INDENT-OFF*’ and ‘*INDENT-ON*’ comments as follows:
/* *INDENT-OFF* */
declarations part 1
%{
/* *INDENT-ON* */
verbatim code
/* *INDENT-OFF* */
%}
declarations part 2
%%
keywords
%%
/* *INDENT-ON* */
functions
gperf
Several options control how the generated C code appears on the standard
output. Two C functions are generated. They are called hash and
in_word_set, although you may modify their names with a command-line
option. Both functions require two arguments, a string, char *
str, and a length parameter, int len. Their default
function prototypes are as follows:
hash function returns an integer value
created by adding len to several user-specified str byte
positions indexed into an associated values table stored in a
local static array. The associated values table is constructed
internally by gperf and later output as a static local C array
called ‘hash_table’. The relevant selected positions (i.e. indices
into str) are specified via the ‘-k’ option when running
gperf, as detailed in the Options section below (see section 5 Invoking gperf).
NULL.
If the option ‘-c’ (or, equivalently, the ‘%compare-strncmp’ declaration) is not used, str must be a NUL terminated string of exactly length len. If ‘-c’ (or, equivalently, the ‘%compare-strncmp’ declaration) is used, str must simply be an array of len bytes and does not need to be NUL terminated.
The code generated for these two functions is affected by the following options:
struct.
switch statement rather than use a large,
(and potentially sparse) static array. Although the exact time and
space savings of this approach vary according to your C compiler's
degree of optimization, this method often results in smaller and faster
code.
If the ‘-t’ and ‘-S’ options (or, equivalently, the
‘%struct-type’ and ‘%switch’ declarations) are omitted, the default
action
is to generate a char * array containing the keywords, together with
additional empty strings used for padding the array. By experimenting
with the various input and output options, and timing the resulting C
code, you can determine the best option choices for different keyword
set characteristics.
By default, the code generated by gperf operates on zero
terminated strings, the usual representation of strings in C. This means
that the keywords in the input file must not contain NUL bytes,
and the str argument passed to hash or in_word_set
must be NUL terminated and have exactly length len.
If option ‘-c’ (or, equivalently, the ‘%compare-strncmp’
declaration) is used, then the str argument does not need
to be NUL terminated. The code generated by gperf will only
access the first len, not len+1, bytes starting at str.
However, the keywords in the input file still must not contain NUL
bytes.
If option ‘-l’ (or, equivalently, the ‘%compare-lengths’
declaration) is used, then the hash table performs binary
comparison. The keywords in the input file may contain NUL bytes,
written in string syntax as \000 or \x00, and the code
generated by gperf will treat NUL like any other byte.
Also, in this case the ‘-c’ option (or, equivalently, the
‘%compare-strncmp’ declaration) is ignored.
The identifiers of the functions, tables, and constants defined by the code
generated by gperf can be controlled through gperf declarations
or the equivalent command-line options. This is useful for three purposes:
gperf in a library, and to
avoid collisions with other libraries, you want to ensure that all exported
identifiers of this library start with a certain prefix.
By default, the only exported identifier is the lookup function. You can
therefore use the option ‘-N’ (or, equivalently, the
‘%define lookup-function-name’ declaration).
When you use the option ‘-L C++’ (or, equivalently, the
‘%language=C++’ declaration), the only exported entity is a class.
You control its name through the option ‘-Z’ (or, equivalently, the
‘%define class-name’ declaration).
gperf generated codes in a single compilation unit.
Assume you invoke gperf multiple times, with different input files,
and want the generated code to included from the same source file. In this
case, you have to customize not only the exported identifiers, but also the
names of functions with ‘static’ scope, types, and constants.
By default, you will have to deal with the lookup function, the hash
function, and the constants. You should therefore use the option ‘-N’
(or, equivalently, the ‘%define lookup-function-name’ declaration),
the option ‘-H’ (or, equivalently, the
‘%define hash-function-name’ declaration), and the option
‘--constants-prefix’ (or, equivalently, the
‘%define constants-prefix’ declaration).
If you use the option ‘-G’ (or, equivalently, the ‘%global-table’
declaration), you will also have to deal with the word array, the length
table if present, and the string pool if present. This means: You should
use the option ‘-W’ (or, equivalently, the
‘%define word-array-name’ declaration). If you use the option
‘-l’ (or, equivalently, the ‘%compare-lengths’ declaration), you
should use the option ‘--length-table-name’ (or, equivalently, the
‘%define length-table-name’ declaration). If you use the option
‘-P’ (or, equivalently, the ‘%pic’ declaration), you should use
the option ‘-Q’ (or, equivalently, the ‘%define string-pool-name’
declaration).
gperf is under GPL, but that does not cause the output produced
by gperf to be under GPL. The reason is that the output contains
only small pieces of text that come directly from gperf's source
code -- only about 7 lines long, too small for being significant --, and
therefore the output is not a “work based on gperf” (in the
sense of the GPL version 3).
On the other hand, the output produced by gperf contains
essentially all of the input file. Therefore the output is a
“derivative work” of the input (in the sense of U.S. copyright law);
and its copyright status depends on the copyright of the input. For most
software licenses, the result is that the the output is under the same
license, with the same copyright holder, as the input that was passed to
gperf.
Go to the first, previous, next, last section, table of contents.