Merge pull request #2309 from mitza-oci/warnings
[ACE_TAO.git] / ACE / apps / gperf / ace_gperf.texi
blob501f1512407fef4df2dbe199f7db5697e28b7fc9
1 \input texinfo  @c -*-texinfo-*-
3 @include version.texi
5 @c %**start of header
6 @settitle User's Guide to @code{gperf}
7 @setfilename gperf.info
8 @c %**end of header
10 @ifinfo
11 @dircategory GNU programming tools
12 @direntry
13 * Gperf: (ace_gperf).                Perfect Hash Function Generator.
14 @end direntry
15 @end ifinfo
17 @ifinfo
18 This file documents the features of the GNU Perfect Hash Function Generator
20 Copyright (C) 1989 Free Software Foundation, Inc.
22 Permission is granted to make and distribute verbatim copies of
23 this manual provided the copyright notice and this permission notice
24 are preserved on all copies.
26 @ignore
27 Permission is granted to process this file through @TeX{} and print the
28 results, provided the printed document carries copying permission
29 notice identical to this one except for the removal of this paragraph
30 (this paragraph not being relevant to the printed manual).
32 @end ignore
34 Permission is granted to copy and distribute modified versions of this
35 manual under the conditions for verbatim copying, provided also that the
36 section entitled ``GNU General Public License'' is included exactly as
37 in the original, and provided that the entire resulting derived work is
38 distributed under the terms of a permission notice identical to this one.
40 Permission is granted to copy and distribute translations of this manual
41 into another language, under the above conditions for modified versions,
42 except that the section entitled ``GNU @code{gperf} General Public License'' an
44 this permission notice may be included in translations approved by the
45 Free Software Foundation instead of in the original English.
46 @end ifinfo
48 @setchapternewpage odd
50 @titlepage
51 @title GNU GPERF Utility
52 @subtitle User's Guide
53 @subtitle Last updated @value{UPDATED}
54 @subtitle For GPERF version @value{VERSION}
55 @author Douglas C. Schmidt
57 @c  The following two commands
58 @c  start the copyright page.
59 @page
60 @vskip 0pt plus 1filll
61 Copyright @copyright{} 1989 Free Software Foundation, Inc.
64 Permission is granted to make and distribute verbatim copies of
65 this manual provided the copyright notice and this permission notice
66 are preserved on all copies.
68 Permission is granted to copy and distribute modified versions of this
69 manual under the conditions for verbatim copying, provided also that the
70 section entitled ``GNU @code{gperf} General Public License'' is included exactl
71 y as
72 in the original, and provided that the entire resulting derived work is
73 distributed under the terms of a permission notice identical to this one.
75 Permission is granted to copy and distribute translations of this manual
76 into another language, under the above conditions for modified versions,
77 except that the section entitled ``GNU @code{gperf} General Public License'' ma
78 y be
79 included in a translation approved by the author instead of in the original
80 English.
81 @end titlepage
83 @ifinfo
84 @node Top, Copying, (dir), (dir)
85 @top GNU GPERF Utility
86 @chapter Introduction
88 This manual documents the GNU @code{gperf} perfect hash function generator
89 utility, focusing on its features and how to use them, and how to report
90 bugs.
92 @end ifinfo
93 @menu
94 * Copying::                     GNU @code{gperf} General Public License says
95                                 how you can copy and share @code{gperf}.
96 * Contributors::                People who have contributed to @code{gperf}.
97 * Motivation::                  Static search structures and GNU GPERF.
98 * Search Structures::           Static search structures and GNU @code{gperf}
99 * Description::                 High-level discussion of how GPERF functions.
100 * Options::                     A description of options to the program.
101 * Bugs::                        Known bugs and limitations with GPERF.
102 * Projects::                    Things still left to do.
103 * Implementation::              Implementation Details for GNU GPERF.
104 * Bibliography::                Material Referenced in this Report.
106  --- The Detailed Node Listing ---
108 High-Level Description of GNU @code{gperf}
110 * Input Format::                Input Format to @code{gperf}
111 * Output Format::               Output Format for Generated C Code with @code{gperf}
113 Input Format to @code{gperf}
115 * Declarations::                @code{struct} Declarations and C Code Inclusion.
116 * Keywords::                    Format for Keyword Entries.
117 * Functions::                   Including Additional C Functions.
118 @end menu
120 @node Copying, Contributors, Top, Top
121 @unnumbered GNU GENERAL PUBLIC LICENSE
122 @center Version 1, February 1989
124 @display
125 Copyright @copyright{} 1989 Free Software Foundation, Inc.
126 675 Mass Ave, Cambridge, MA 02139, USA
128 Everyone is permitted to copy and distribute verbatim copies
129 of this license document, but changing it is not allowed.
130 @end display
132 @unnumberedsec Preamble
134   The license agreements of most software companies try to keep users
135 at the mercy of those companies.  By contrast, our General Public
136 License is intended to guarantee your freedom to share and change free
137 software---to make sure the software is free for all its users.  The
138 General Public License applies to the Free Software Foundation's
139 software and to any other program whose authors commit to using it.
140 You can use it for your programs, too.
142   When we speak of free software, we are referring to freedom, not
143 price.  Specifically, the General Public License is designed to make
144 sure that you have the freedom to give away or sell copies of free
145 software, that you receive source code or can get it if you want it,
146 that you can change the software or use pieces of it in new free
147 programs; and that you know you can do these things.
149   To protect your rights, we need to make restrictions that forbid
150 anyone to deny you these rights or to ask you to surrender the rights.
151 These restrictions translate to certain responsibilities for you if you
152 distribute copies of the software, or if you modify it.
154   For example, if you distribute copies of a such a program, whether
155 gratis or for a fee, you must give the recipients all the rights that
156 you have.  You must make sure that they, too, receive or can get the
157 source code.  And you must tell them their rights.
159   We protect your rights with two steps: (1) copyright the software, and
160 (2) offer you this license which gives you legal permission to copy,
161 distribute and/or modify the software.
163   Also, for each author's protection and ours, we want to make certain
164 that everyone understands that there is no warranty for this free
165 software.  If the software is modified by someone else and passed on, we
166 want its recipients to know that what they have is not the original, so
167 that any problems introduced by others will not reflect on the original
168 authors' reputations.
170   The precise terms and conditions for copying, distribution and
171 modification follow.
173 @iftex
174 @unnumberedsec TERMS AND CONDITIONS
175 @end iftex
176 @ifinfo
177 @center TERMS AND CONDITIONS
178 @end ifinfo
180 @enumerate
181 @item
182 This License Agreement applies to any program or other work which
183 contains a notice placed by the copyright holder saying it may be
184 distributed under the terms of this General Public License.  The
185 ``Program'', below, refers to any such program or work, and a ``work based
186 on the Program'' means either the Program or any work containing the
187 Program or a portion of it, either verbatim or with modifications.  Each
188 licensee is addressed as ``you''.
190 @item
191 You may copy and distribute verbatim copies of the Program's source
192 code as you receive it, in any medium, provided that you conspicuously and
193 appropriately publish on each copy an appropriate copyright notice and
194 disclaimer of warranty; keep intact all the notices that refer to this
195 General Public License and to the absence of any warranty; and give any
196 other recipients of the Program a copy of this General Public License
197 along with the Program.  You may charge a fee for the physical act of
198 transferring a copy.
200 @item
201 You may modify your copy or copies of the Program or any portion of
202 it, and copy and distribute such modifications under the terms of Paragraph
203 1 above, provided that you also do the following:
205 @itemize @bullet
206 @item
207 cause the modified files to carry prominent notices stating that
208 you changed the files and the date of any change; and
210 @item
211 cause the whole of any work that you distribute or publish, that
212 in whole or in part contains the Program or any part thereof, either
213 with or without modifications, to be licensed at no charge to all
214 third parties under the terms of this General Public License (except
215 that you may choose to grant warranty protection to some or all
216 third parties, at your option).
218 @item
219 If the modified program normally reads commands interactively when
220 run, you must cause it, when started running for such interactive use
221 in the simplest and most usual way, to print or display an
222 announcement including an appropriate copyright notice and a notice
223 that there is no warranty (or else, saying that you provide a
224 warranty) and that users may redistribute the program under these
225 conditions, and telling the user how to view a copy of this General
226 Public License.
228 @item
229 You may charge a fee for the physical act of transferring a
230 copy, and you may at your option offer warranty protection in
231 exchange for a fee.
232 @end itemize
234 Mere aggregation of another independent work with the Program (or its
235 derivative) on a volume of a storage or distribution medium does not bring
236 the other work under the scope of these terms.
238 @item
239 You may copy and distribute the Program (or a portion or derivative of
240 it, under Paragraph 2) in object code or executable form under the terms of
241 Paragraphs 1 and 2 above provided that you also do one of the following:
243 @itemize @bullet
244 @item
245 accompany it with the complete corresponding machine-readable
246 source code, which must be distributed under the terms of
247 Paragraphs 1 and 2 above; or,
249 @item
250 accompany it with a written offer, valid for at least three
251 years, to give any third party free (except for a nominal charge
252 for the cost of distribution) a complete machine-readable copy of the
253 corresponding source code, to be distributed under the terms of
254 Paragraphs 1 and 2 above; or,
256 @item
257 accompany it with the information you received as to where the
258 corresponding source code may be obtained.  (This alternative is
259 allowed only for noncommercial distribution and only if you
260 received the program in object code or executable form alone.)
261 @end itemize
263 Source code for a work means the preferred form of the work for making
264 modifications to it.  For an executable file, complete source code means
265 all the source code for all modules it contains; but, as a special
266 exception, it need not include source code for modules which are standard
267 libraries that accompany the operating system on which the executable
268 file runs, or for standard header files or definitions files that
269 accompany that operating system.
271 @item
272 You may not copy, modify, sublicense, distribute or transfer the
273 Program except as expressly provided under this General Public License.
274 Any attempt otherwise to copy, modify, sublicense, distribute or transfer
275 the Program is void, and will automatically terminate your rights to use
276 the Program under this License.  However, parties who have received
277 copies, or rights to use copies, from you under this General Public
278 License will not have their licenses terminated so long as such parties
279 remain in full compliance.
281 @item
282 By copying, distributing or modifying the Program (or any work based
283 on the Program) you indicate your acceptance of this license to do so,
284 and all its terms and conditions.
286 @item
287 Each time you redistribute the Program (or any work based on the
288 Program), the recipient automatically receives a license from the original
289 licensor to copy, distribute or modify the Program subject to these
290 terms and conditions.  You may not impose any further restrictions on the
291 recipients' exercise of the rights granted herein.
293 @item
294 The Free Software Foundation may publish revised and/or new versions
295 of the General Public License from time to time.  Such new versions will
296 be similar in spirit to the present version, but may differ in detail to
297 address new problems or concerns.
299 Each version is given a distinguishing version number.  If the Program
300 specifies a version number of the license which applies to it and ``any
301 later version'', you have the option of following the terms and conditions
302 either of that version or of any later version published by the Free
303 Software Foundation.  If the Program does not specify a version number of
304 the license, you may choose any version ever published by the Free Software
305 Foundation.
307 @item
308 If you wish to incorporate parts of the Program into other free
309 programs whose distribution conditions are different, write to the author
310 to ask for permission.  For software which is copyrighted by the Free
311 Software Foundation, write to the Free Software Foundation; we sometimes
312 make exceptions for this.  Our decision will be guided by the two goals
313 of preserving the free status of all derivatives of our free software and
314 of promoting the sharing and reuse of software generally.
316 @iftex
317 @heading NO WARRANTY
318 @end iftex
319 @ifinfo
320 @center NO WARRANTY
321 @end ifinfo
323 @item
324 BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
325 FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
326 OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
327 PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
328 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
329 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
330 TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
331 PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
332 REPAIR OR CORRECTION.
334 @item
335 IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL
336 ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
337 REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
338 INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES
339 ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT
340 LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES
341 SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE
342 WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN
343 ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
344 @end enumerate
346 @iftex
347 @heading END OF TERMS AND CONDITIONS
348 @end iftex
349 @ifinfo
350 @center END OF TERMS AND CONDITIONS
351 @end ifinfo
353 @page
354 @unnumberedsec Appendix: How to Apply These Terms to Your New Programs
356   If you develop a new program, and you want it to be of the greatest
357 possible use to humanity, the best way to achieve this is to make it
358 free software which everyone can redistribute and change under these
359 terms.
361   To do so, attach the following notices to the program.  It is safest to
362 attach them to the start of each source file to most effectively convey
363 the exclusion of warranty; and each file should have at least the
364 ``copyright'' line and a pointer to where the full notice is found.
366 @smallexample
367 @var{one line to give the program's name and a brief idea of what it does.}
368 Copyright (C) 19@var{yy}  @var{name of author}
370 This program is free software; you can redistribute it and/or modify
371 it under the terms of the GNU General Public License as published by
372 the Free Software Foundation; either version 1, or (at your option)
373 any later version.
375 This program is distributed in the hope that it will be useful,
376 but WITHOUT ANY WARRANTY; without even the implied warranty of
377 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
378 GNU General Public License for more details.
380 You should have received a copy of the GNU General Public License
381 along with this program; if not, write to the Free Software
382 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
383 @end smallexample
385 Also add information on how to contact you by electronic and paper mail.
387 If the program is interactive, make it output a short notice like this
388 when it starts in an interactive mode:
390 @smallexample
391 Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author}
392 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
393 This is free software, and you are welcome to redistribute it
394 under certain conditions; type `show c' for details.
395 @end smallexample
397 The hypothetical commands `show w' and `show c' should show the
398 appropriate parts of the General Public License.  Of course, the
399 commands you use may be called something other than `show w' and `show
400 c'; they could even be mouse-clicks or menu items---whatever suits your
401 program.
403 You should also get your employer (if you work as a programmer) or your
404 school, if any, to sign a ``copyright disclaimer'' for the program, if
405 necessary.  Here a sample; alter the names:
407 @example
408 Yoyodyne, Inc., hereby disclaims all copyright interest in the
409 program `Gnomovision' (a program to direct compilers to make passes
410 at assemblers) written by James Hacker.
412 @var{signature of Ty Coon}, 1 April 1989
413 Ty Coon, President of Vice
414 @end example
416 That's all there is to it!
418 @node Contributors, Motivation, Copying, Top
419 @unnumbered Contributors to GNU @code{gperf} Utility
421 @itemize @bullet
422 @item
423 The GNU @code{gperf} perfect hash function generator utility was
424 originally written in GNU C++ by Douglas C. Schmidt.  It is now also
425 available in a highly-portable ``old-style'' C version.  The general
426 idea for the perfect hash function generator was inspired by Keith
427 Bostic's algorithm written in C, and distributed to net.sources around
428 1984.  The current program is a heavily modified, enhanced, and extended
429 implementation of Keith's basic idea, created at the University of
430 California, Irvine.  Bugs, patches, and suggestions should be reported
431 to schmidt at ics.uci.edu.
433 @item
434 Special thanks is extended to Michael Tiemann and Doug Lea, for
435 providing a useful compiler, and for giving me a forum to exhibit my
436 creation.
438 In addition, Adam de Boor and Nels Olson provided many tips and insights
439 that greatly helped improve the quality and functionality of @code{gperf}.
440 @end itemize
442 @node Motivation, Search Structures, Contributors, Top
443 @chapter Introduction
445 @code{gperf} is a perfect hash function generator written in C++.  It
446 transforms an @emph{n} element user-specified keyword set @emph{W} into
447 a perfect hash function @emph{F}.  @emph{F} uniquely maps keywords in
448 @emph{W} onto the range 0..@emph{k}, where @emph{k} >= @emph{n}.  If
449 @emph{k = n} then @emph{F} is a @emph{minimal} perfect hash function.
450 @code{gperf} generates a 0..@emph{k} element static lookup table and a
451 pair of C functions.  These functions determine whether a given
452 character string @emph{s} occurs in @emph{W}, using at most one probe
453 into the lookup table.
455 @code{gperf} currently generates the reserved keyword recognizer for
456 lexical analyzers in several production and research compilers and
457 language processing tools, including GNU C, GNU C++, GNU Pascal, GNU
458 Modula 3, and GNU indent.  Complete C++ source code for @code{gperf} is
459 available via anonymous ftp from ics.uci.edu.  @code{gperf} also is
460 distributed along with the GNU libg++ library.  A highly portable,
461 functionally equivalent K&R C version of @code{gperf} is archived in
462 comp.sources.unix, volume 20.  Finally, a paper describing
463 @code{gperf}'s design and implementation in greater detail is available
464 in the Second USENIX C++ Conference proceedings.
466 @node Search Structures, Description, Motivation, Top
467 @chapter Static search structures and GNU @code{gperf}
469 A @dfn{static search structure} is an Abstract Data Type with certain
470 fundamental operations, @emph{e.g.}, @emph{initialize}, @emph{insert},
471 and @emph{retrieve}.  Conceptually, all insertions occur before any
472 retrievals.  In practice, @code{gperf} generates a @code{static} array
473 containing search set keywords and any associated attributes specified
474 by the user.  Thus, there is essentially no execution-time cost for the
475 insertions.  It is a useful data structure for representing @emph{static
476 search sets}.  Static search sets occur frequently in software system
477 applications.  Typical static search sets include compiler reserved
478 words, assembler instruction opcodes, and built-in shell interpreter
479 commands.  Search set members, called @dfn{keywords}, are inserted into
480 the structure only once, usually during program initialization, and are
481 not generally modified at run-time.
483 Numerous static search structure implementations exist, @emph{e.g.},
484 arrays, linked lists, binary search trees, digital search tries, and
485 hash tables.  Different approaches offer trade-offs between space
486 utilization and search time efficiency.  For example, an @emph{n} element
487 sorted array is space efficient, though the average-case time
488 complexity for retrieval operations using binary search is
489 proportional to log @emph{n}.  Conversely, hash table implementations
490 often locate a table entry in constant time, but typically impose
491 additional memory overhead and exhibit poor worst case performance.
494 @emph{Minimal perfect hash functions} provide an optimal solution for a
495 particular class of static search sets.  A minimal perfect hash
496 function is defined by two properties:
498 @itemize @bullet
499 @item
500 It allows keyword recognition in a static search set using at most
501 @emph{one} probe into the hash table.  This represents the ``perfect''
502 property.
503 @item
504 The actual memory allocated to store the keywords is precisely large
505 enough for the keyword set, and @emph{no larger}.  This is the
506 ``minimal'' property.
507 @end itemize
509 For most applications it is far easier to generate @emph{perfect} hash
510 functions than @emph{minimal perfect} hash functions.  Moreover,
511 non-minimal perfect hash functions frequently execute faster than
512 minimal ones in practice.  This phenomena occurs since searching a
513 sparse keyword table increases the probability of locating a ``null''
514 entry, thereby reducing string comparisons.  @code{gperf}'s default
515 behavior generates @emph{near-minimal} perfect hash functions for
516 keyword sets.  However, @code{gperf} provides many options that permit
517 user control over the degree of minimality and perfection.
519 Static search sets often exhibit relative stability over time.  For
520 example, Ada's 63 reserved words have remained constant for nearly a
521 decade.  It is therefore frequently worthwhile to expend concerted
522 effort building an optimal search structure @emph{once}, if it
523 subsequently receives heavy use multiple times.  @code{gperf} removes
524 the drudgery associated with constructing time- and space-efficient
525 search structures by hand.  It has proven a useful and practical tool
526 for serious programming projects.  Output from @code{gperf} is currently
527 used in several production and research compilers, including GNU C, GNU
528 C++, GNU Pascal, and GNU Modula 3.  The latter two compilers are not yet
529 part of the official GNU distribution.  Each compiler utilizes
530 @code{gperf} to automatically generate static search structures that
531 efficiently identify their respective reserved keywords.
533 @node Description, Options, Search Structures, Top
534 @chapter High-Level Description of GNU @code{gperf}
536 @menu
537 * Input Format::                Input Format to @code{gperf}
538 * Output Format::               Output Format for Generated C Code with @code{gperf}
539 @end menu
541 The perfect hash function generator @code{gperf} reads a set of
542 ``keywords'' from a @dfn{keyfile} (or from the standard input by
543 default).  It attempts to derive a perfect hashing function that
544 recognizes a member of the @dfn{static keyword set} with at most a
545 single probe into the lookup table.  If @code{gperf} succeeds in
546 generating such a function it produces a pair of C source code routines
547 that perform hashing and table lookup recognition.  All generated C code
548 is directed to the standard output.  Command-line options described
549 below allow you to modify the input and output format to @code{gperf}.
551 By default, @code{gperf} attempts to produce time-efficient code, with
552 less emphasis on efficient space utilization.  However, several options
553 exist that permit trading-off execution time for storage space and vice
554 versa.  In particular, expanding the generated table size produces a
555 sparse search structure, generally yielding faster searches.
556 Conversely, you can direct @code{gperf} to utilize a C @code{switch}
557 statement scheme that minimizes data space storage size.  Furthermore,
558 using a C @code{switch} may actually speed up the keyword retrieval time
559 somewhat.  Actual results depend on your C compiler, of course.
561 In general, @code{gperf} assigns values to the characters it is using
562 for hashing until some set of values gives each keyword a unique value.
563 A helpful heuristic is that the larger the hash value range, the easier
564 it is for @code{gperf} to find and generate a perfect hash function.
565 Experimentation is the key to getting the most from @code{gperf}.
567 @node Input Format, Output Format, Description, Description
568 @section Input Format to @code{gperf}
570 You can control the input keyfile format by varying certain command-line
571 arguments, in particular the @samp{-t} option.  The input's appearance
572 is similar to GNU utilities @code{flex} and @code{bison} (or UNIX
573 utilities @code{lex} and @code{yacc}).  Here's an outline of the general
574 format:
576 @example
577 @group
578 declarations
580 keywords
582 functions
583 @end group
584 @end example
586 @emph{Unlike} @code{flex} or @code{bison}, all sections of @code{gperf}'s input
587 are optional.  The following sections describe the input format for each
588 section.
590 @menu
591 * Declarations::                @code{struct} Declarations and C Code Inclusion.
592 * Keywords::                    Format for Keyword Entries.
593 * Functions::                   Including Additional C Functions.
594 @end menu
596 @node Declarations, Keywords, Input Format, Input Format
597 @subsection @code{struct} Declarations and C Code Inclusion
599 The keyword input file optionally contains a section for including
600 arbitrary C declarations and definitions, as well as provisions for
601 providing a user-supplied @code{struct}.  If the @samp{-t} option
602 @emph{is} enabled, you @emph{must} provide a C @code{struct} as the last
603 component in the declaration section from the keyfile file.  The first
604 field in this struct must be a @code{char *} identifier called ``name,''
605 although it is possible to modify this field's name with the @samp{-K}
606 option described below.
608 Here is simple example, using months of the year and their attributes as
609 input:
611 @example
612 @group
613 struct months @{ char *name; int number; int days; int leap_days; @};
615 january,   1, 31, 31
616 february,  2, 28, 29
617 march,     3, 31, 31
618 april,     4, 30, 30
619 may,       5, 31, 31
620 june,      6, 30, 30
621 july,      7, 31, 31
622 august,    8, 31, 31
623 september, 9, 30, 30
624 october,  10, 31, 31
625 november, 11, 30, 30
626 december, 12, 31, 31
627 @end group
628 @end example
630 Separating the @code{struct} declaration from the list of key words and
631 other fields are a pair of consecutive percent signs, @code{%%},
632 appearing left justified in the first column, as in the UNIX utility
633 @code{lex}.
635 Using a syntax similar to GNU utilities @code{flex} and @code{bison}, it
636 is possible to directly include C source text and comments verbatim into
637 the generated output file.  This is accomplished by enclosing the region
638 inside left-justified surrounding @code{%@{}, @code{%@}} pairs.  Here is
639 an input fragment based on the previous example that illustrates this
640 feature:
642 @example
643 @group
645 #include <assert.h>
646 /* This section of code is inserted directly into the output. */
647 int return_month_days (struct months *months, int is_leap_year);
649 struct months @{ char *name; int number; int days; int leap_days; @};
651 january,   1, 31, 31
652 february,  2, 28, 29
653 march,     3, 31, 31
655 @end group
656 @end example
658 It is possible to omit the declaration section entirely.  In this case
659 the keyfile begins directly with the first keyword line, @emph{e.g.}:
661 @example
662 @group
663 january,   1, 31, 31
664 february,  2, 28, 29
665 march,     3, 31, 31
666 april,     4, 30, 30
668 @end group
669 @end example
671 @node Keywords, Functions, Declarations, Input Format
672 @subsection Format for Keyword Entries
674 The second keyfile format section contains lines of keywords and any
675 associated attributes you might supply.  A line beginning with @samp{#}
676 in the first column is considered a comment.  Everything following the
677 @samp{#} is ignored, up to and including the following newline.
679 The first field of each non-comment line is always the key itself.  It
680 should be given as a simple name, @emph{i.e.}, without surrounding
681 string quotation marks, and be left-justified flush against the first
682 column.  In this context, a ``field'' is considered to extend up to, but
683 not include, the first blank, comma, or newline.  Here is a simple
684 example taken from a partial list of C reserved words:
686 @example
687 @group
688 # These are a few C reserved words, see the c.@code{gperf} file
689 # for a complete list of ANSI C reserved words.
690 unsigned
691 sizeof
692 switch
693 signed
695 default
697 while
698 return
699 @end group
700 @end example
702 Note that unlike @code{flex} or @code{bison} the first @code{%%} marker
703 may be elided if the declaration section is empty.
705 Additional fields may optionally follow the leading keyword.  Fields
706 should be separated by commas, and terminate at the end of line.  What
707 these fields mean is entirely up to you; they are used to initialize the
708 elements of the user-defined @code{struct} provided by you in the
709 declaration section.  If the @samp{-t} option is @emph{not} enabled
710 these fields are simply ignored.  All previous examples except the last
711 one contain keyword attributes.
713 @node Functions,  , Keywords, Input Format
714 @subsection Including Additional C Functions
716 The optional third section also corresponds closely with conventions
717 found in @code{flex} and @code{bison}.  All text in this section,
718 starting at the final @code{%%} and extending to the end of the input
719 file, is included verbatim into the generated output file.  Naturally,
720 it is your responsibility to ensure that the code contained in this
721 section is valid C.
723 @node Output Format,  , Input Format, Description
724 @section Output Format for Generated C Code with @code{gperf}
726 Several options control how the generated C code appears on the standard
727 output.  Two C function are generated.  They are called @code{hash} and
728 @code{in_word_set}, although you may modify the name for
729 @code{in_word_set} with a command-line option.  Both functions require
730 two arguments, a string, @code{char *} @var{str}, and a length
731 parameter, @code{int} @var{len}.  Their default function prototypes are
732 as follows:
734 @example
735 @group
736 static int hash (char *str, int len);
737 int in_word_set (char *str, int len);
738 @end group
739 @end example
741 By default, the generated @code{hash} function returns an integer value
742 created by adding @var{len} to several user-specified @var{str} key
743 positions indexed into an @dfn{associated values} table stored in a
744 local static array.  The associated values table is constructed
745 internally by @code{gperf} and later output as a static local C array called
746 @var{hash_table}; its meaning and properties are described below.
747 @xref{Implementation}. The relevant key positions are specified via the
748 @samp{-k} option when running @code{gperf}, as detailed in the @emph{Options}
749 section below. @xref{Options}.
751 Two options, @samp{-g} (assume you are compiling with GNU C and its
752 @code{inline} feature) and @samp{-a} (assume ANSI C-style function
753 prototypes), alter the content of both the generated @code{hash} and
754 @code{in_word_set} routines.  However, function @code{in_word_set} may
755 be modified more extensively, in response to your option settings.  The
756 options that affect the @code{in_word_set} structure are:
758 @itemize @bullet
759 @table @samp
760 @item -p
761 Have function @code{in_word_set} return a pointer rather than a boolean.
763 @item -t
764 Make use of the user-defined @code{struct}.
766 @item -S @var{total switch statements}
767 Generate 1 or more C @code{switch} statement rather than use a large,
768 (and potentially sparse) static array.  Although the exact time and
769 space savings of this approach vary according to your C compiler's
770 degree of optimization, this method often results in smaller and faster
771 code.
772 @end table
773 @end itemize
775 If the @samp{-t}, @samp{-S}, and @samp{-p} options are omitted the
776 default action is to generate a @code{char *} array containing the keys,
777 together with additional null strings used for padding the array.  By
778 experimenting with the various input and output options, and timing the
779 resulting C code, you can determine the best option choices for
780 different keyword set characteristics.
782 @node Options, Bugs, Description, Top
783 @chapter Options to the @code{gperf} Utility
785 There are @emph{many} options to @code{gperf}.  They were added to make
786 the program more convenient for use with real applications.  ``On-line''
787 help is readily available via the @samp{-h} option.  Other options
788 include:
790 @itemize @bullet
791 @table @samp
792 @item -a
793 Generate ANSI Standard C code using function prototypes.  The default is
794 to use ``classic'' K&R C function declaration syntax.
796 @item -c
797 Generates C code that uses the @code{strncmp} function to perform
798 string comparisons.  The default action is to use @code{strcmp}.
800 @item -C
801 Makes the contents of all generated lookup tables constant, @emph{i.e.},
802 ``readonly.''  Many compilers can generate more efficient code for this
803 by putting the tables in readonly memory.
805 @item -d
806 Enables the debugging option.  This produces verbose diagnostics to
807 ``standard error'' when @code{gperf} is executing.  It is useful both for
808 maintaining the program and for determining whether a given set of
809 options is actually speeding up the search for a solution.  Some useful
810 information is dumped at the end of the program when the @samp{-d}
811 option is enabled.
813 @item -D
814 Handle keywords whose key position sets hash to duplicate values.
815 Duplicate hash values occur for two reasons:
817 @itemize @bullet
818 @item
819 Since @code{gperf} does not backtrack it is possible for it to process
820 all your input keywords without finding a unique mapping for each word.
821 However, frequently only a very small number of duplicates occur, and
822 the majority of keys still require one probe into the table.
823 @item
824 Sometimes a set of keys may have the same names, but possess different
825 attributes.  With the -D option @code{gperf} treats all these keys as part of
826 an equivalence class and generates a perfect hash function with multiple
827 comparisons for duplicate keys.  It is up to you to completely
828 disambiguate the keywords by modifying the generated C code.  However,
829 @code{gperf} helps you out by organizing the output.
830 @end itemize
832 Option @samp{-D} is extremely useful for certain large or highly
833 redundant keyword sets, @emph{i.e.}, assembler instruction opcodes.
834 Using this option usually means that the generated hash function is no
835 longer perfect.  On the other hand, it permits @code{gperf} to work on
836 keyword sets that it otherwise could not handle.
838 @item -e @var{keyword delimiter list}
839 Allows the user to provide a string containing delimiters used to
840 separate keywords from their attributes.  The default is ",\n".  This
841 option is essential if you want to use keywords that have embedded
842 commas or newlines.  One useful trick is to use -e'TAB', where TAB is
843 the literal tab character.
845 @item -E
846 Define constant values using an enum local to the lookup function rather
847 than with #defines.  This also means that different lookup functions can
848 reside in the same file.  Thanks to James Clark (jjc at ai.mit.edu).
850 @item -f @var{iteration amount}
851 Generate the perfect hash function ``fast.''  This decreases @code{gperf}'s
852 running time at the cost of minimizing generated table-size.  The
853 iteration amount represents the number of times to iterate when
854 resolving a collision.  `0' means `iterate by the number of keywords.
855 This option is probably most useful when used in conjunction with options
856 @samp{-D} and/or @samp{-S} for @emph{large} keyword sets.
858 @item -g
859 Assume a GNU compiler, @emph{e.g.}, @code{g++} or @code{gcc}.  This
860 makes all generated routines use the ``inline'' keyword to remove the
861 cost of function calls.  Note that @samp{-g} does @emph{not} imply
862 @samp{-a}, since other non-ANSI C compilers may have provisions for a
863 function @code{inline} feature.
865 @item -G
866 Generate the static table of keywords as a static global variable,
867 rather than hiding it inside of the lookup function (which is the
868 default behavior).
870 @item -h
871 Prints a short summary on the meaning of each program option.  Aborts
872 further program execution.
874 @item -H @var{hash function name}
875 Allows you to specify the name for the generated hash function.  Default
876 name is `hash.'  This option permits the use of two hash tables in the
877 same file.
879 @item -i @var{initial value}
880 Provides an initial @var{value} for the associate values array.  Default
881 is 0.  Increasing the initial value helps inflate the final table size,
882 possibly leading to more time efficient keyword lookups.  Note that this
883 option is not particularly useful when @samp{-S} is used.  Also,
884 @samp{-i} is overriden when the @samp{-r} option is used.
886 @item -j @var{jump value}
887 Affects the ``jump value,'' @emph{i.e.}, how far to advance the
888 associated character value upon collisions.  @var{Jump value} is rounded
889 up to an odd number, the default is 5.  If the @var{jump value} is 0 @code{gper
891 jumps by random amounts.
893 @item -k @var{keys}
894 Allows selection of the character key positions used in the keywords'
895 hash function. The allowable choices range between 1-126, inclusive.
896 The positions are separated by commas, @emph{e.g.}, @samp{-k 9,4,13,14};
897 ranges may be used, @emph{e.g.}, @samp{-k 2-7}; and positions may occur
898 in any order.  Furthermore, the meta-character '*' causes the generated
899 hash function to consider @strong{all} character positions in each key,
900 whereas '$' instructs the hash function to use the ``final character''
901 of a key (this is the only way to use a character position greater than
902 126, incidentally).
904 For instance, the option @samp{-k 1,2,4,6-10,'$'} generates a hash
905 function that considers positions 1,2,4,6,7,8,9,10, plus the last
906 character in each key (which may differ for each key, obviously).  Keys
907 with length less than the indicated key positions work properly, since
908 selected key positions exceeding the key length are simply not
909 referenced in the hash function.
911 @item -K @var{key name}
912 By default, the program assumes the structure component identifier for
913 the keyword is ``name.''  This option allows an arbitrary choice of
914 identifier for this component, although it still must occur as the first
915 field in your supplied @code{struct}.
917 @item -l
918 Compare key lengths before trying a string comparison.  This might cut
919 down on the number of string comparisons made during the lookup, since
920 keys with different lengths are never compared via @code{strcmp}.
921 However, using @samp{-l} might greatly increase the size of the
922 generated C code if the lookup table range is large (which implies that
923 the switch option @samp{-S} is not enabled), since the length table
924 contains as many elements as there are entries in the lookup table.
926 @item -L @var{generated language name}
927 Instructs @code{gperf} to generate code in the language specified by the
928 option's argument.  Languages handled are currently C++ and C.  The
929 default is C.
931 @item -n
932 Instructs the generator not to include the length of a keyword when
933 computing its hash value.  This may save a few assembly instructions in
934 the generated lookup table.
936 @item -N @var{lookup function name}
937 Allows you to specify the name for the generated lookup function.
938 Default name is `in_word_set.'  This option permits completely automatic
939 generation of perfect hash functions, especially when multiple generated
940 hash functions are used in the same application.
942 @item -o
943 Reorders the keywords by sorting the keywords so that frequently
944 occuring key position set components appear first.  A second reordering
945 pass follows so that keys with ``already determined values'' are placed
946 towards the front of the keylist.  This may decrease the time required
947 to generate a perfect hash function for many keyword sets, and also
948 produce more minimal perfect hash functions.  The reason for this is
949 that the reordering helps prune the search time by handling inevitable
950 collisions early in the search process.  On the other hand, if the
951 number of keywords is @emph{very} large using @samp{-o} may
952 @emph{increase} @code{gperf}'s execution time, since collisions will begin
953 earlier and continue throughout the remainder of keyword processing.
954 See Cichelli's paper from the January 1980 Communications of the ACM for
955 details.
957 @item -p
958 Changes the return value of the generated function @code{in_word_set}
959 from boolean (@emph{i.e.}, 0 or 1), to either type ``pointer to
960 user-defined struct,'' (if the @samp{-t} option is enabled), or simply
961 to @code{char *}, if @samp{-t} is not enabled.  This option is most
962 useful when the @samp{-t} option (allowing user-defined structs) is
963 used.  For example, it is possible to automatically generate the GNU C
964 reserved word lookup routine with the options @samp{-p} and @samp{-t}.
966 @item -r
967 Utilizes randomness to initialize the associated values table.  This
968 frequently generates solutions faster than using deterministic
969 initialization (which starts all associated values at 0).  Furthermore,
970 using the randomization option generally increases the size of the
971 table.  If @code{gperf} has difficultly with a certain keyword set try using
972 @samp{-r} or @samp{-D}.
974 @item -s @var{size-multiple}
975 Affects the size of the generated hash table.  The numeric argument for
976 this option indicates ``how many times larger or smaller'' the maximum
977 associated value range should be, in relationship to the number of keys.
978 If the @var{size-multiple} is negative the maximum associated value is
979 calculated by @emph{dividing} it into the total number of keys.  For
980 example, a value of 3 means ``allow the maximum associated value to be
981 about 3 times larger than the number of input keys.''
983 Conversely, a value of -3 means ``allow the maximum associated value to
984 be about 3 times smaller than the number of input keys.''  Negative
985 values are useful for limiting the overall size of the generated hash
986 table, though this usually increases the number of duplicate hash
987 values.
989 If `generate switch' option @samp{-S} is @emph{not} enabled, the maximum
990 associated value influences the static array table size, and a larger
991 table should decrease the time required for an unsuccessful search, at
992 the expense of extra table space.
994 The default value is 1, thus the default maximum associated value about
995 the same size as the number of keys (for efficiency, the maximum
996 associated value is always rounded up to a power of 2).  The actual
997 table size may vary somewhat, since this technique is essentially a
998 heuristic.  In particular, setting this value too high slows down
999 @code{gperf}'s runtime, since it must search through a much larger range
1000 of values.  Judicious use of the @samp{-f} option helps alleviate this
1001 overhead, however.
1003 @item -S @var{total switch statements}
1004 Causes the generated C code to use a @code{switch} statement scheme,
1005 rather than an array lookup table.  This can lead to a reduction in both
1006 time and space requirements for some keyfiles.  The argument to this
1007 option determines how many @code{switch} statements are generated. A
1008 value of 1 generates 1 @code{switch} containing all the elements, a
1009 value of 2 generates 2 tables with 1/2 the elements in each
1010 @code{switch}, etc.  This is useful since many C compilers cannot
1011 correctly generate code for large @code{switch} statements. This option
1012 was inspired in part by Keith Bostic's original C program.
1014 @item -t
1015 Allows you to include a @code{struct} type declaration for generated
1016 code.  Any text before a pair of consecutive %% is consider part of the
1017 type declaration.  Key words and additional fields may follow this, one
1018 group of fields per line.  A set of examples for generating perfect hash
1019 tables and functions for Ada, C, and G++, Pascal, and Modula 2 and 3
1020 reserved words are distributed with this release.
1022 @item -T
1023 Prevents the transfer of the type declaration to the output file.  Use
1024 this option if the type is already defined elsewhere.
1026 @item -v
1027 Prints out the current version number.
1029 @item -Z @var{class name}
1030 Allow user to specify name of generated C++ class.  Default name is
1031 @code{Perfect_Hash}.
1032 @end table
1033 @end itemize
1035 @node Bugs, Projects, Options, Top
1036 @chapter Known Bugs and Limitations with @code{gperf}
1038 The following are some limitations with the current release of
1039 @code{gperf}:
1041 @itemize @bullet
1042 @item
1043 The @code{gperf} utility is tuned to execute quickly, and works quickly
1044 for small to medium size data sets (around 1000 keywords).  It is
1045 extremely useful for maintaining perfect hash functions for compiler
1046 keyword sets.  Several recent enhancements now enable @code{gperf} to
1047 work efficiently on much larger keyword sets (over 15,000 keywords).
1048 When processing large keyword sets it helps greatly to have over 8 megs
1049 of RAM.
1051 However, since @code{gperf} does not backtrack no guaranteed solution
1052 occurs on every run.  On the other hand, it is usually easy to obtain a
1053 solution by varying the option parameters.  In particular, try the
1054 @samp{-r} option, and also try changing the default arguments to the
1055 @samp{-s} and @samp{-j} options.  To @emph{guarantee} a solution, use
1056 the @samp{-D} and @samp{-S} options, although the final results are not
1057 likely to be a @emph{perfect} hash function anymore!  Finally, use the
1058 @samp{-f} option if you want @code{gperf} to generate the perfect hash
1059 function @emph{fast}, with less emphasis on making it minimal.
1061 @item
1062 The size of the generate static keyword array can get @emph{extremely}
1063 large if the input keyword file is large or if the keywords are quite
1064 similar.  This tends to slow down the compilation of the generated C
1065 code, and @emph{greatly} inflates the object code size.  If this
1066 situation occurs, consider using the @samp{-S} option to reduce data
1067 size, potentially increasing keyword recognition time a negligible
1068 amount.  Since many C compilers cannot correctly generated code for
1069 large switch statements it is important to qualify the @var{-S} option
1070 with an appropriate numerical argument that controls the number of
1071 switch statements generated.
1073 @item
1074 The maximum number of key positions selected for a given key has an
1075 arbitrary limit of 126.  This restriction should be removed, and if
1076 anyone considers this a problem write me and let me know so I can remove
1077 the constraint.
1079 @item
1080 The C++ source code only compiles correctly with GNU G++, version 1.36
1081 (and hopefully later versions).  Porting to AT&T cfront would be
1082 tedious, but possible (and desirable).  There is also a K&R C version
1083 available now.  This should compile without change on most BSD systems,
1084 but may require a bit of work to run on SYSV, since @code{gperf} uses
1085 @var{alloca} in several places.  Send mail to schmidt at ics.uci.edu for
1086 information.
1087 @end itemize
1089 @node Projects, Implementation, Bugs, Top
1090 @chapter Things Still Left to Do
1092 It should be ``relatively'' easy to replace the current perfect hash
1093 function algorithm with a more exhaustive approach; the perfect hash
1094 module is essential independent from other program modules.  Additional
1095 worthwhile improvements include:
1097 @itemize @bullet
1098 @item
1099 Make the algorithm more robust.  At present, the program halts with an
1100 error diagnostic if it can't find a direct solution and the @samp{-D}
1101 option is not enabled.  A more comprehensive, albeit computationally
1102 expensive, approach would employ backtracking or enable alternative
1103 options and retry.  It's not clear how helpful this would be, in
1104 general, since most search sets are rather small in practice.
1106 @item
1107 Another useful extension involves modifying the program to generate
1108 ``minimal'' perfect hash functions (under certain circumstances, the
1109 current version can be rather extravagant in the generated table size).
1110 Again, this is mostly of theoretical interest, since a sparse table
1111 often produces faster lookups, and use of the @samp{-S} @code{switch}
1112 option can minimize the data size, at the expense of slightly longer
1113 lookups (note that the gcc compiler generally produces good code for
1114 @code{switch} statements, reducing the need for more complex schemes).
1116 @item
1117 In addition to improving the algorithm, it would also be useful to
1118 generate a C++ class or Ada package as the code output, in addition to
1119 the current C routines.
1120 @end itemize
1122 @node Implementation, Bibliography, Projects, Top
1123 @chapter Implementation Details of GNU @code{gperf}
1125 A paper describing the high-level description of the data structures and
1126 algorithms used to implement @code{gperf} will soon be available.  This
1127 paper is useful not only from a maintenance and enhancement perspective,
1128 but also because they demonstrate several clever and useful programming
1129 techniques, @emph{e.g.}, `Iteration Number' boolean arrays, double
1130 hashing, a ``safe'' and efficient method for reading arbitrarily long
1131 input from a file, and a provably optimal algorithm for simultaneously
1132 determining both the minimum and maximum elements in a list.
1134 @page
1136 @node Bibliography,  , Implementation, Top
1137 @chapter Bibliography
1139 [1] Chang, C.C.: @i{A Scheme for Constructing Ordered Minimal Perfect
1140 Hashing Functions} Information Sciences 39(1986), 187-195.
1142 [2] Cichelli, Richard J. @i{Author's Response to ``On Cichelli's Minimal Perfec
1143 t Hash
1144 Functions Method''} Communications of the ACM, 23, 12(December 1980), 729.
1146 [3] Cichelli, Richard J. @i{Minimal Perfect Hash Functions Made Simple}
1147 Communications of the ACM, 23, 1(January 1980), 17-19.
1149 [4] Cook, C. R. and Oldehoeft, R.R. @i{A Letter Oriented Minimal
1150 Perfect Hashing Function} SIGPLAN Notices, 17, 9(September 1982), 18-27.
1152 [5] Cormack, G. V. and Horspool, R. N. S. and Kaiserwerth, M.
1153 @i{Practical Perfect Hashing} Computer Journal, 28, 1(January 1985), 54-58.
1155 [6] Jaeschke, G. @i{Reciprocal Hashing: A Method for Generating Minimal
1156 Perfect Hashing Functions} Communications of the ACM, 24, 12(December
1157 1981), 829-833.
1159 [7] Jaeschke, G. and Osterburg, G. @i{On Cichelli's Minimal Perfect
1160 Hash Functions Method} Communications of the ACM, 23, 12(December 1980),
1161 728-729.
1163 [8] Sager, Thomas J. @i{A Polynomial Time Generator for Minimal Perfect
1164 Hash Functions} Communications of the ACM, 28, 5(December 1985), 523-532
1166 [9] Schmidt, Douglas C. @i{GPERF: A Perfect Hash Function Generator}
1167 Second USENIX C++ Conference Proceedings, April 1990.
1169 [10] Sebesta, R.W. and Taylor, M.A. @i{Minimal Perfect Hash Functions
1170 for Reserved Word Lists}  SIGPLAN Notices, 20, 12(September 1985), 47-53.
1172 [11] Sprugnoli, R. @i{Perfect Hashing Functions: A Single Probe
1173 Retrieving Method for Static Sets} Communications of the ACM, 20
1174 11(November 1977), 841-850.
1176 [12] Stallman, Richard M. @i{Using and Porting GNU CC} Free Software Foundation,
1177 1988.
1179 [13] Stroustrup, Bjarne @i{The C++ Programming Language.} Addison-Wesley, 1986.
1181 [14] Tiemann, Michael D. @i{User's Guide to GNU C++} Free Software
1182 Foundation, 1989.
1184 @contents
1185 @bye