gperf.texinfo

早期freebsd实现

The positions are separated by commas, @emph{e.g.}, @samp{-k 9,4,13,14};
ranges may be used, @emph{e.g.}, @samp{-k 2-7}; and positions may occur
in any order.  Furthermore, the meta-character '*' causes the generated
hash function to consider @strong{all} character positions in each key,
whereas '$' instructs the hash function to use the ``final character''
of a key (this is the only way to use a character position greater than
126, incidentally).

For instance, the option @samp{-k 1,2,4,6-10,'$'} generates a hash
function that considers positions 1,2,4,6,7,8,9,10, plus the last
character in each key (which may differ for each key, obviously).  Keys
with length less than the indicated key positions work properly, since
selected key positions exceeding the key length are simply not
referenced in the hash function.

@item -K @var{key name}
By default, the program assumes the structure component identifier for
the keyword is ``name.''  This option allows an arbitrary choice of
identifier for this component, although it still must occur as the first
field in your supplied @code{struct}.

@item -l
Compare key lengths before trying a string comparison.  This might cut
down on the number of string comparisons made during the lookup, since
keys with different lengths are never compared via @code{strcmp}.
However, using @samp{-l} might greatly increase the size of the
generated C code if the lookup table range is large (which implies that
the switch option @samp{-S} is not enabled), since the length table
contains as many elements as there are entries in the lookup table.

@item -L @var{generated language name}
Instructs @code{gperf} to generate code in the language specified by the
option's argument.  Languages handled are currently C++ and C.  The
default is C.

@item -n
Instructs the generator not to include the length of a keyword when
computing its hash value.  This may save a few assembly instructions in
the generated lookup table.

@item -N @var{lookup function name}
Allows you to specify the name for the generated lookup function.
Default name is `in_word_set.'  This option permits completely automatic
generation of perfect hash functions, especially when multiple generated
hash functions are used in the same application.

Note that if -LC++ is enabled this option provides the name of the
generated C++ class (since the name of the generated lookup member
function is then @code{operator ()}).

@item -o
Reorders the keywords by sorting the keywords so that frequently
occuring key position set components appear first.  A second reordering
pass follows so that keys with ``already determined values'' are placed
towards the front of the keylist.  This may decrease the time required
to generate a perfect hash function for many keyword sets, and also
produce more minimal perfect hash functions.  The reason for this is
that the reordering helps prune the search time by handling inevitable
collisions early in the search process.  On the other hand, if the
number of keywords is @emph{very} large using @samp{-o} may
@emph{increase} @code{gperf}'s execution time, since collisions will begin
earlier and continue throughout the remainder of keyword processing.
See Cichelli's paper from the January 1980 Communications of the ACM for
details.

@item -p
Changes the return value of the generated function @code{in_word_set}
from boolean (@emph{i.e.}, 0 or 1), to either type ``pointer to
user-defined struct,'' (if the @samp{-t} option is enabled), or simply
to @code{char *}, if @samp{-t} is not enabled.  This option is most
useful when the @samp{-t} option (allowing user-defined structs) is
used.  For example, it is possible to automatically generate the GNU C
reserved word lookup routine with the options @samp{-p} and @samp{-t}.

@item -r
Utilizes randomness to initialize the associated values table.  This
frequently generates solutions faster than using deterministic
initialization (which starts all associated values at 0).  Furthermore,
using the randomization option generally increases the size of the
table.  If @code{gperf} has difficultly with a certain keyword set try using
@samp{-r} or @samp{-D}.

@item -s @var{size-multiple}
Affects the size of the generated hash table.  The numeric argument for
this option indicates ``how many times larger or smaller'' the maximum
associated value range should be, in relationship to the number of keys.
If the @var{size-multiple} is negative the maximum associated value is
calculated by @emph{dividing} it into the total number of keys.  For
example, a value of 3 means ``allow the maximum associated value to be
about 3 times larger than the number of input keys.''  

Conversely, a value of -3 means ``allow the maximum associated value to
be about 3 times smaller than the number of input keys.''  Negative
values are useful for limiting the overall size of the generated hash
table, though this usually increases the number of duplicate hash
values.

If `generate switch' option @samp{-S} is @emph{not} enabled, the maximum
associated value influences the static array table size, and a larger
table should decrease the time required for an unsuccessful search, at
the expense of extra table space.

The default value is 1, thus the default maximum associated value about
the same size as the number of keys (for efficiency, the maximum
associated value is always rounded up to a power of 2).  The actual
table size may vary somewhat, since this technique is essentially a
heuristic.  In particular, setting this value too high slows down
@code{gperf}'s runtime, since it must search through a much larger range
of values.  Judicious use of the @samp{-f} option helps alleviate this
overhead, however.

@item -S @var{total switch statements}
Causes the generated C code to use a @code{switch} statement scheme,
rather than an array lookup table.  This can lead to a reduction in both
time and space requirements for some keyfiles.  The argument to this
option determines how many @code{switch} statements are generated. A
value of 1 generates 1 @code{switch} containing all the elements, a
value of 2 generates 2 tables with 1/2 the elements in each
@code{switch}, etc.  This is useful since many C compilers cannot
correctly generate code for large @code{switch} statements. This option
was inspired in part by Keith Bostic's original C program.

@item -t
Allows you to include a @code{struct} type declaration for generated
code.  Any text before a pair of consecutive %% is consider part of the
type declaration.  Key words and additional fields may follow this, one
group of fields per line.  A set of examples for generating perfect hash
tables and functions for Ada, C, and G++, Pascal, and Modula 2 and 3
reserved words are distributed with this release.

@item -T
Prevents the transfer of the type declaration to the output file.  Use
this option if the type is already defined elsewhere.

@item -v
Prints out the current version number.

@item -Z @var{class name}
Allow user to specify name of generated C++ class.  Default name is
@code{Perfect_Hash}.
@end table
@end itemize

@node Bugs, Projects, Options, Top
@chapter Known Bugs and Limitations with @code{gperf}

The following are some limitations with the current release of
@code{gperf}:

@itemize @bullet
@item
The @code{gperf} utility is tuned to execute quickly, and works quickly
for small to medium size data sets (around 1000 keywords).  It is
extremely useful for maintaining perfect hash functions for compiler
keyword sets.  Several recent enhancements now enable @code{gperf} to
work efficiently on much larger keyword sets (over 15,000 keywords).
When processing large keyword sets it helps greatly to have over 8 megs
of RAM.

However, since @code{gperf} does not backtrack no guaranteed solution
occurs on every run.  On the other hand, it is usually easy to obtain a
solution by varying the option parameters.  In particular, try the
@samp{-r} option, and also try changing the default arguments to the
@samp{-s} and @samp{-j} options.  To @emph{guarantee} a solution, use
the @samp{-D} and @samp{-S} options, although the final results are not
likely to be a @emph{perfect} hash function anymore!  Finally, use the
@samp{-f} option if you want @code{gperf} to generate the perfect hash
function @emph{fast}, with less emphasis on making it minimal.

@item 
The size of the generate static keyword array can get @emph{extremely}
large if the input keyword file is large or if the keywords are quite
similar.  This tends to slow down the compilation of the generated C
code, and @emph{greatly} inflates the object code size.  If this
situation occurs, consider using the @samp{-S} option to reduce data
size, potentially increasing keyword recognition time a negligible
amount.  Since many C compilers cannot correctly generated code for
large switch statements it is important to qualify the @var{-S} option
with an appropriate numerical argument that controls the number of
switch statements generated.

@item 
The maximum number of key positions selected for a given key has an
arbitrary limit of 126.  This restriction should be removed, and if
anyone considers this a problem write me and let me know so I can remove
the constraint.

@item
The C++ source code only compiles correctly with GNU G++, version 1.36
(and hopefully later versions).  Porting to AT&T cfront would be
tedious, but possible (and desirable).  There is also a K&R C version
available now.  This should compile without change on most BSD systems,
but may require a bit of work to run on SYSV, since @code{gperf} uses
@var{alloca} in several places.  Send mail to schmidt at ics.uci.edu for
information.
@end itemize

@node Projects, Implementation, Bugs, Top
@chapter Things Still Left to Do

It should be ``relatively'' easy to replace the current perfect hash
function algorithm with a more exhaustive approach; the perfect hash
module is essential independent from other program modules.  Additional
worthwhile improvements include:

@itemize @bullet
@item 
Make the algorithm more robust.  At present, the program halts with an
error diagnostic if it can't find a direct solution and the @samp{-D}
option is not enabled.  A more comprehensive, albeit computationally
expensive, approach would employ backtracking or enable alternative
options and retry.  It's not clear how helpful this would be, in
general, since most search sets are rather small in practice.

@item 
Another useful extension involves modifying the program to generate
``minimal'' perfect hash functions (under certain circumstances, the
current version can be rather extravagant in the generated table size).
Again, this is mostly of theoretical interest, since a sparse table
often produces faster lookups, and use of the @samp{-S} @code{switch}
option can minimize the data size, at the expense of slightly longer
lookups (note that the gcc compiler generally produces good code for
@code{switch} statements, reducing the need for more complex schemes).

@item
In addition to improving the algorithm, it would also be useful to
generate a C++ class or Ada package as the code output, in addition to
the current C routines.
@end itemize

@node Implementation, Bibliography, Projects, Top
@chapter Implementation Details of GNU @code{gperf}

A paper describing the high-level description of the data structures and
algorithms used to implement @code{gperf} will soon be available.  This
paper is useful not only from a maintenance and enhancement perspective,
but also because they demonstrate several clever and useful programming
techniques, @emph{e.g.}, `Iteration Number' boolean arrays, double
hashing, a ``safe'' and efficient method for reading arbitrarily long
input from a file, and a provably optimal algorithm for simultaneously
determining both the minimum and maximum elements in a list.

@page

@node Bibliography,  , Implementation, Top
@chapter Bibliography

[1] Chang, C.C.: @i{A Scheme for Constructing Ordered Minimal Perfect
Hashing Functions} Information Sciences 39(1986), 187-195.
       
[2] Cichelli, Richard J. @i{Author's Response to ``On Cichelli's Minimal Perfec
t Hash
Functions Method''} Communications of the ACM, 23, 12(December 1980), 729.
    
[3] Cichelli, Richard J. @i{Minimal Perfect Hash Functions Made Simple}
Communications of the ACM, 23, 1(January 1980), 17-19.
           
[4] Cook, C. R. and Oldehoeft, R.R. @i{A Letter Oriented Minimal
Perfect Hashing Function} SIGPLAN Notices, 17, 9(September 1982), 18-27.

[5] Cormack, G. V. and Horspool, R. N. S. and Kaiserwerth, M.
@i{Practical Perfect Hashing} Computer Journal, 28, 1(January 1985), 54-58.
    
[6] Jaeschke, G. @i{Reciprocal Hashing: A Method for Generating Minimal
Perfect Hashing Functions} Communications of the ACM, 24, 12(December
1981), 829-833.

[7] Jaeschke, G. and Osterburg, G. @i{On Cichelli's Minimal Perfect
Hash Functions Method} Communications of the ACM, 23, 12(December 1980),
728-729.

[8] Sager, Thomas J. @i{A Polynomial Time Generator for Minimal Perfect
Hash Functions} Communications of the ACM, 28, 5(December 1985), 523-532

[9] Schmidt, Douglas C. @i{GPERF: A Perfect Hash Function Generator}
Second USENIX C++ Conference Proceedings, April 1990.

[10] Sebesta, R.W. and Taylor, M.A. @i{Minimal Perfect Hash Functions
for Reserved Word Lists}  SIGPLAN Notices, 20, 12(September 1985), 47-53.

[11] Sprugnoli, R. @i{Perfect Hashing Functions: A Single Probe
Retrieving Method for Static Sets} Communications of the ACM, 20
11(November 1977), 841-850.

[12] Stallman, Richard M. @i{Using and Porting GNU CC} Free Software Foundation,
1988.

[13] Stroustrup, Bjarne @i{The C++ Programming Language.} Addison-Wesley, 1986.

[14] Tiemann, Michael D. @i{User's Guide to GNU C++} Free Software
Foundation, 1989.

@contents
@bye