From 533744c77137b94ed05e2ca445ba97d71c79ee5f Mon Sep 17 00:00:00 2001 From: kris Date: Sat, 25 Mar 2000 07:45:29 +0000 Subject: Virgin import of gperf v2.7 --- contrib/gperf/doc/Makefile.in | 129 +++++ contrib/gperf/doc/configure | 863 +++++++++++++++++++++++++++ contrib/gperf/doc/configure.in | 33 ++ contrib/gperf/doc/gperf.1 | 23 + contrib/gperf/doc/gperf.texi | 1251 ++++++++++++++++++++++++++++++++++++++++ 5 files changed, 2299 insertions(+) create mode 100644 contrib/gperf/doc/Makefile.in create mode 100755 contrib/gperf/doc/configure create mode 100644 contrib/gperf/doc/configure.in create mode 100644 contrib/gperf/doc/gperf.1 create mode 100644 contrib/gperf/doc/gperf.texi (limited to 'contrib/gperf/doc') diff --git a/contrib/gperf/doc/Makefile.in b/contrib/gperf/doc/Makefile.in new file mode 100644 index 0000000..bfacd16 --- /dev/null +++ b/contrib/gperf/doc/Makefile.in @@ -0,0 +1,129 @@ +# Makefile for gperf/doc + +# Copyright (C) 1998 Free Software Foundation, Inc. +# +# This file is part of GNU GPERF. +# +# GNU GPERF is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 1, or (at your option) +# any later version. +# +# GNU GPERF is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GNU GPERF; see the file COPYING. If not, write to the Free +# Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA. + +#### Start of system configuration section. #### + +# Directories used by "make": +srcdir = @srcdir@ + +# Directories used by "make install": +prefix = @prefix@ +local_prefix = /usr/local +exec_prefix = @exec_prefix@ +infodir = @infodir@ +mandir = @mandir@ +man1dir = $(mandir)/man1 +dvidir = $(mandir)/dvi +htmldir = $(mandir)/html + +# Programs used by "make": +RM = rm -f +@SET_MAKE@ + +# Programs used by "make" if you have changed the documentation files: +TEX = tex +TEXI2DVI = texi2dvi +DVIPS = dvips -Pljfour +MAKEINFO = LANGUAGE= makeinfo +TEXI2HTML = texi2html + +# Programs used by "make install": +INSTALL = @INSTALL@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_DATA = @INSTALL_DATA@ + +#### End of system configuration section. #### + +SHELL = /bin/sh + +VPATH = $(srcdir) + +all : info dvi ps html + + +info : $(srcdir)/gperf.info + +$(srcdir)/gperf.info : $(srcdir)/gperf.texi + cd $(srcdir) && $(MAKEINFO) --no-split gperf.texi + + +dvi : $(srcdir)/gperf.dvi + +$(srcdir)/gperf.dvi : $(srcdir)/gperf.texi + cd $(srcdir) && $(RM) gperf.aux gperf.toc gperf.cp gperf.fn gperf.ky gperf.pg gperf.tp gperf.vr gperf.log + cd $(srcdir) && $(TEXI2DVI) gperf.texi + cd $(srcdir) && $(RM) gperf.aux gperf.toc gperf.cp gperf.fn gperf.ky gperf.pg gperf.tp gperf.vr gperf.log + + +ps : $(srcdir)/gperf.ps + +$(srcdir)/gperf.ps : $(srcdir)/gperf.dvi + $(DVIPS) -o $@ $< + + +html : gperf.html gperf_toc.html + +gperf.html : $(srcdir)/gperf.texi + cd $(srcdir) && $(TEXI2HTML) -expandinfo -number -monolithic gperf.texi + +gperf_toc.html : $(srcdir)/gperf.texi + cd $(srcdir) && $(RM) gperf_*.html + cd $(srcdir) && $(TEXI2HTML) -expandinfo -number -split_chapter gperf.texi + + +install : all force + if [ ! -d $(infodir) ] ; then mkdir $(infodir) ; fi + $(INSTALL_DATA) $(srcdir)/gperf.info $(infodir)/gperf.info + if [ ! -d $(mandir) ] ; then mkdir $(mandir) ; fi + if [ ! -d $(man1dir) ] ; then mkdir $(man1dir) ; fi + $(INSTALL_DATA) $(srcdir)/gperf.1 $(man1dir)/gperf.1 + if [ ! -d $(dvidir) ] ; then mkdir $(dvidir) ; fi + $(INSTALL_DATA) $(srcdir)/gperf.dvi $(dvidir)/gperf.dvi + if [ ! -d $(htmldir) ] ; then mkdir $(htmldir) ; fi + $(INSTALL_DATA) $(srcdir)/gperf.html $(htmldir)/gperf.html + +installdirs : force + if [ ! -d $(infodir) ] ; then mkdir $(infodir) ; fi + if [ ! -d $(mandir) ] ; then mkdir $(mandir) ; fi + if [ ! -d $(man1dir) ] ; then mkdir $(man1dir) ; fi + if [ ! -d $(dvidir) ] ; then mkdir $(dvidir) ; fi + if [ ! -d $(htmldir) ] ; then mkdir $(htmldir) ; fi + +uninstall : force + $(RM) $(infodir)/gperf.info + $(RM) $(man1dir)/gperf.1 + $(RM) $(dvidir)/gperf.dvi + $(RM) $(htmldir)/gperf.html + +check : all + +mostlyclean : clean + +clean : force + $(RM) *~ *.aux *.toc *.cp *.fn *.ky *.pg *.tp *.vr *.my *.log core + +distclean : clean + $(RM) config.status config.log config.cache Makefile + +maintainer-clean : distclean + $(RM) *.info *.dvi *.ps *.html + +force : + diff --git a/contrib/gperf/doc/configure b/contrib/gperf/doc/configure new file mode 100755 index 0000000..7b6e3c3 --- /dev/null +++ b/contrib/gperf/doc/configure @@ -0,0 +1,863 @@ +#! /bin/sh + +# Guess values for system-dependent variables and create Makefiles. +# Generated automatically using autoconf version 2.12 +# Copyright (C) 1992, 93, 94, 95, 96 Free Software Foundation, Inc. +# +# This configure script is free software; the Free Software Foundation +# gives unlimited permission to copy, distribute and modify it. + +# Defaults: +ac_help= +ac_default_prefix=/usr/local +# Any additions from configure.in: + +# Initialize some variables set by options. +# The variables have the same names as the options, with +# dashes changed to underlines. +build=NONE +cache_file=./config.cache +exec_prefix=NONE +host=NONE +no_create= +nonopt=NONE +no_recursion= +prefix=NONE +program_prefix=NONE +program_suffix=NONE +program_transform_name=s,x,x, +silent= +site= +srcdir= +target=NONE +verbose= +x_includes=NONE +x_libraries=NONE +bindir='${exec_prefix}/bin' +sbindir='${exec_prefix}/sbin' +libexecdir='${exec_prefix}/libexec' +datadir='${prefix}/share' +sysconfdir='${prefix}/etc' +sharedstatedir='${prefix}/com' +localstatedir='${prefix}/var' +libdir='${exec_prefix}/lib' +includedir='${prefix}/include' +oldincludedir='/usr/include' +infodir='${prefix}/info' +mandir='${prefix}/man' + +# Initialize some other variables. +subdirs= +MFLAGS= MAKEFLAGS= +# Maximum number of lines to put in a shell here document. +ac_max_here_lines=12 + +ac_prev= +for ac_option +do + + # If the previous option needs an argument, assign it. + if test -n "$ac_prev"; then + eval "$ac_prev=\$ac_option" + ac_prev= + continue + fi + + case "$ac_option" in + -*=*) ac_optarg=`echo "$ac_option" | sed 's/[-_a-zA-Z0-9]*=//'` ;; + *) ac_optarg= ;; + esac + + # Accept the important Cygnus configure options, so we can diagnose typos. + + case "$ac_option" in + + -bindir | --bindir | --bindi | --bind | --bin | --bi) + ac_prev=bindir ;; + -bindir=* | --bindir=* | --bindi=* | --bind=* | --bin=* | --bi=*) + bindir="$ac_optarg" ;; + + -build | --build | --buil | --bui | --bu) + ac_prev=build ;; + -build=* | --build=* | --buil=* | --bui=* | --bu=*) + build="$ac_optarg" ;; + + -cache-file | --cache-file | --cache-fil | --cache-fi \ + | --cache-f | --cache- | --cache | --cach | --cac | --ca | --c) + ac_prev=cache_file ;; + -cache-file=* | --cache-file=* | --cache-fil=* | --cache-fi=* \ + | --cache-f=* | --cache-=* | --cache=* | --cach=* | --cac=* | --ca=* | --c=*) + cache_file="$ac_optarg" ;; + + -datadir | --datadir | --datadi | --datad | --data | --dat | --da) + ac_prev=datadir ;; + -datadir=* | --datadir=* | --datadi=* | --datad=* | --data=* | --dat=* \ + | --da=*) + datadir="$ac_optarg" ;; + + -disable-* | --disable-*) + ac_feature=`echo $ac_option|sed -e 's/-*disable-//'` + # Reject names that are not valid shell variable names. + if test -n "`echo $ac_feature| sed 's/[-a-zA-Z0-9_]//g'`"; then + { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; } + fi + ac_feature=`echo $ac_feature| sed 's/-/_/g'` + eval "enable_${ac_feature}=no" ;; + + -enable-* | --enable-*) + ac_feature=`echo $ac_option|sed -e 's/-*enable-//' -e 's/=.*//'` + # Reject names that are not valid shell variable names. + if test -n "`echo $ac_feature| sed 's/[-_a-zA-Z0-9]//g'`"; then + { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; } + fi + ac_feature=`echo $ac_feature| sed 's/-/_/g'` + case "$ac_option" in + *=*) ;; + *) ac_optarg=yes ;; + esac + eval "enable_${ac_feature}='$ac_optarg'" ;; + + -exec-prefix | --exec_prefix | --exec-prefix | --exec-prefi \ + | --exec-pref | --exec-pre | --exec-pr | --exec-p | --exec- \ + | --exec | --exe | --ex) + ac_prev=exec_prefix ;; + -exec-prefix=* | --exec_prefix=* | --exec-prefix=* | --exec-prefi=* \ + | --exec-pref=* | --exec-pre=* | --exec-pr=* | --exec-p=* | --exec-=* \ + | --exec=* | --exe=* | --ex=*) + exec_prefix="$ac_optarg" ;; + + -gas | --gas | --ga | --g) + # Obsolete; use --with-gas. + with_gas=yes ;; + + -help | --help | --hel | --he) + # Omit some internal or obsolete options to make the list less imposing. + # This message is too long to be a string in the A/UX 3.1 sh. + cat << EOF +Usage: configure [options] [host] +Options: [defaults in brackets after descriptions] +Configuration: + --cache-file=FILE cache test results in FILE + --help print this message + --no-create do not create output files + --quiet, --silent do not print \`checking...' messages + --version print the version of autoconf that created configure +Directory and file names: + --prefix=PREFIX install architecture-independent files in PREFIX + [$ac_default_prefix] + --exec-prefix=EPREFIX install architecture-dependent files in EPREFIX + [same as prefix] + --bindir=DIR user executables in DIR [EPREFIX/bin] + --sbindir=DIR system admin executables in DIR [EPREFIX/sbin] + --libexecdir=DIR program executables in DIR [EPREFIX/libexec] + --datadir=DIR read-only architecture-independent data in DIR + [PREFIX/share] + --sysconfdir=DIR read-only single-machine data in DIR [PREFIX/etc] + --sharedstatedir=DIR modifiable architecture-independent data in DIR + [PREFIX/com] + --localstatedir=DIR modifiable single-machine data in DIR [PREFIX/var] + --libdir=DIR object code libraries in DIR [EPREFIX/lib] + --includedir=DIR C header files in DIR [PREFIX/include] + --oldincludedir=DIR C header files for non-gcc in DIR [/usr/include] + --infodir=DIR info documentation in DIR [PREFIX/info] + --mandir=DIR man documentation in DIR [PREFIX/man] + --srcdir=DIR find the sources in DIR [configure dir or ..] + --program-prefix=PREFIX prepend PREFIX to installed program names + --program-suffix=SUFFIX append SUFFIX to installed program names + --program-transform-name=PROGRAM + run sed PROGRAM on installed program names +EOF + cat << EOF +Host type: + --build=BUILD configure for building on BUILD [BUILD=HOST] + --host=HOST configure for HOST [guessed] + --target=TARGET configure for TARGET [TARGET=HOST] +Features and packages: + --disable-FEATURE do not include FEATURE (same as --enable-FEATURE=no) + --enable-FEATURE[=ARG] include FEATURE [ARG=yes] + --with-PACKAGE[=ARG] use PACKAGE [ARG=yes] + --without-PACKAGE do not use PACKAGE (same as --with-PACKAGE=no) + --x-includes=DIR X include files are in DIR + --x-libraries=DIR X library files are in DIR +EOF + if test -n "$ac_help"; then + echo "--enable and --with options recognized:$ac_help" + fi + exit 0 ;; + + -host | --host | --hos | --ho) + ac_prev=host ;; + -host=* | --host=* | --hos=* | --ho=*) + host="$ac_optarg" ;; + + -includedir | --includedir | --includedi | --included | --include \ + | --includ | --inclu | --incl | --inc) + ac_prev=includedir ;; + -includedir=* | --includedir=* | --includedi=* | --included=* | --include=* \ + | --includ=* | --inclu=* | --incl=* | --inc=*) + includedir="$ac_optarg" ;; + + -infodir | --infodir | --infodi | --infod | --info | --inf) + ac_prev=infodir ;; + -infodir=* | --infodir=* | --infodi=* | --infod=* | --info=* | --inf=*) + infodir="$ac_optarg" ;; + + -libdir | --libdir | --libdi | --libd) + ac_prev=libdir ;; + -libdir=* | --libdir=* | --libdi=* | --libd=*) + libdir="$ac_optarg" ;; + + -libexecdir | --libexecdir | --libexecdi | --libexecd | --libexec \ + | --libexe | --libex | --libe) + ac_prev=libexecdir ;; + -libexecdir=* | --libexecdir=* | --libexecdi=* | --libexecd=* | --libexec=* \ + | --libexe=* | --libex=* | --libe=*) + libexecdir="$ac_optarg" ;; + + -localstatedir | --localstatedir | --localstatedi | --localstated \ + | --localstate | --localstat | --localsta | --localst \ + | --locals | --local | --loca | --loc | --lo) + ac_prev=localstatedir ;; + -localstatedir=* | --localstatedir=* | --localstatedi=* | --localstated=* \ + | --localstate=* | --localstat=* | --localsta=* | --localst=* \ + | --locals=* | --local=* | --loca=* | --loc=* | --lo=*) + localstatedir="$ac_optarg" ;; + + -mandir | --mandir | --mandi | --mand | --man | --ma | --m) + ac_prev=mandir ;; + -mandir=* | --mandir=* | --mandi=* | --mand=* | --man=* | --ma=* | --m=*) + mandir="$ac_optarg" ;; + + -nfp | --nfp | --nf) + # Obsolete; use --without-fp. + with_fp=no ;; + + -no-create | --no-create | --no-creat | --no-crea | --no-cre \ + | --no-cr | --no-c) + no_create=yes ;; + + -no-recursion | --no-recursion | --no-recursio | --no-recursi \ + | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r) + no_recursion=yes ;; + + -oldincludedir | --oldincludedir | --oldincludedi | --oldincluded \ + | --oldinclude | --oldinclud | --oldinclu | --oldincl | --oldinc \ + | --oldin | --oldi | --old | --ol | --o) + ac_prev=oldincludedir ;; + -oldincludedir=* | --oldincludedir=* | --oldincludedi=* | --oldincluded=* \ + | --oldinclude=* | --oldinclud=* | --oldinclu=* | --oldincl=* | --oldinc=* \ + | --oldin=* | --oldi=* | --old=* | --ol=* | --o=*) + oldincludedir="$ac_optarg" ;; + + -prefix | --prefix | --prefi | --pref | --pre | --pr | --p) + ac_prev=prefix ;; + -prefix=* | --prefix=* | --prefi=* | --pref=* | --pre=* | --pr=* | --p=*) + prefix="$ac_optarg" ;; + + -program-prefix | --program-prefix | --program-prefi | --program-pref \ + | --program-pre | --program-pr | --program-p) + ac_prev=program_prefix ;; + -program-prefix=* | --program-prefix=* | --program-prefi=* \ + | --program-pref=* | --program-pre=* | --program-pr=* | --program-p=*) + program_prefix="$ac_optarg" ;; + + -program-suffix | --program-suffix | --program-suffi | --program-suff \ + | --program-suf | --program-su | --program-s) + ac_prev=program_suffix ;; + -program-suffix=* | --program-suffix=* | --program-suffi=* \ + | --program-suff=* | --program-suf=* | --program-su=* | --program-s=*) + program_suffix="$ac_optarg" ;; + + -program-transform-name | --program-transform-name \ + | --program-transform-nam | --program-transform-na \ + | --program-transform-n | --program-transform- \ + | --program-transform | --program-transfor \ + | --program-transfo | --program-transf \ + | --program-trans | --program-tran \ + | --progr-tra | --program-tr | --program-t) + ac_prev=program_transform_name ;; + -program-transform-name=* | --program-transform-name=* \ + | --program-transform-nam=* | --program-transform-na=* \ + | --program-transform-n=* | --program-transform-=* \ + | --program-transform=* | --program-transfor=* \ + | --program-transfo=* | --program-transf=* \ + | --program-trans=* | --program-tran=* \ + | --progr-tra=* | --program-tr=* | --program-t=*) + program_transform_name="$ac_optarg" ;; + + -q | -quiet | --quiet | --quie | --qui | --qu | --q \ + | -silent | --silent | --silen | --sile | --sil) + silent=yes ;; + + -sbindir | --sbindir | --sbindi | --sbind | --sbin | --sbi | --sb) + ac_prev=sbindir ;; + -sbindir=* | --sbindir=* | --sbindi=* | --sbind=* | --sbin=* \ + | --sbi=* | --sb=*) + sbindir="$ac_optarg" ;; + + -sharedstatedir | --sharedstatedir | --sharedstatedi \ + | --sharedstated | --sharedstate | --sharedstat | --sharedsta \ + | --sharedst | --shareds | --shared | --share | --shar \ + | --sha | --sh) + ac_prev=sharedstatedir ;; + -sharedstatedir=* | --sharedstatedir=* | --sharedstatedi=* \ + | --sharedstated=* | --sharedstate=* | --sharedstat=* | --sharedsta=* \ + | --sharedst=* | --shareds=* | --shared=* | --share=* | --shar=* \ + | --sha=* | --sh=*) + sharedstatedir="$ac_optarg" ;; + + -site | --site | --sit) + ac_prev=site ;; + -site=* | --site=* | --sit=*) + site="$ac_optarg" ;; + + -srcdir | --srcdir | --srcdi | --srcd | --src | --sr) + ac_prev=srcdir ;; + -srcdir=* | --srcdir=* | --srcdi=* | --srcd=* | --src=* | --sr=*) + srcdir="$ac_optarg" ;; + + -sysconfdir | --sysconfdir | --sysconfdi | --sysconfd | --sysconf \ + | --syscon | --sysco | --sysc | --sys | --sy) + ac_prev=sysconfdir ;; + -sysconfdir=* | --sysconfdir=* | --sysconfdi=* | --sysconfd=* | --sysconf=* \ + | --syscon=* | --sysco=* | --sysc=* | --sys=* | --sy=*) + sysconfdir="$ac_optarg" ;; + + -target | --target | --targe | --targ | --tar | --ta | --t) + ac_prev=target ;; + -target=* | --target=* | --targe=* | --targ=* | --tar=* | --ta=* | --t=*) + target="$ac_optarg" ;; + + -v | -verbose | --verbose | --verbos | --verbo | --verb) + verbose=yes ;; + + -version | --version | --versio | --versi | --vers) + echo "configure generated by autoconf version 2.12" + exit 0 ;; + + -with-* | --with-*) + ac_package=`echo $ac_option|sed -e 's/-*with-//' -e 's/=.*//'` + # Reject names that are not valid shell variable names. + if test -n "`echo $ac_package| sed 's/[-_a-zA-Z0-9]//g'`"; then + { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; } + fi + ac_package=`echo $ac_package| sed 's/-/_/g'` + case "$ac_option" in + *=*) ;; + *) ac_optarg=yes ;; + esac + eval "with_${ac_package}='$ac_optarg'" ;; + + -without-* | --without-*) + ac_package=`echo $ac_option|sed -e 's/-*without-//'` + # Reject names that are not valid shell variable names. + if test -n "`echo $ac_package| sed 's/[-a-zA-Z0-9_]//g'`"; then + { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; } + fi + ac_package=`echo $ac_package| sed 's/-/_/g'` + eval "with_${ac_package}=no" ;; + + --x) + # Obsolete; use --with-x. + with_x=yes ;; + + -x-includes | --x-includes | --x-include | --x-includ | --x-inclu \ + | --x-incl | --x-inc | --x-in | --x-i) + ac_prev=x_includes ;; + -x-includes=* | --x-includes=* | --x-include=* | --x-includ=* | --x-inclu=* \ + | --x-incl=* | --x-inc=* | --x-in=* | --x-i=*) + x_includes="$ac_optarg" ;; + + -x-libraries | --x-libraries | --x-librarie | --x-librari \ + | --x-librar | --x-libra | --x-libr | --x-lib | --x-li | --x-l) + ac_prev=x_libraries ;; + -x-libraries=* | --x-libraries=* | --x-librarie=* | --x-librari=* \ + | --x-librar=* | --x-libra=* | --x-libr=* | --x-lib=* | --x-li=* | --x-l=*) + x_libraries="$ac_optarg" ;; + + -*) { echo "configure: error: $ac_option: invalid option; use --help to show usage" 1>&2; exit 1; } + ;; + + *) + if test -n "`echo $ac_option| sed 's/[-a-z0-9.]//g'`"; then + echo "configure: warning: $ac_option: invalid host type" 1>&2 + fi + if test "x$nonopt" != xNONE; then + { echo "configure: error: can only configure for one host and one target at a time" 1>&2; exit 1; } + fi + nonopt="$ac_option" + ;; + + esac +done + +if test -n "$ac_prev"; then + { echo "configure: error: missing argument to --`echo $ac_prev | sed 's/_/-/g'`" 1>&2; exit 1; } +fi + +trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15 + +# File descriptor usage: +# 0 standard input +# 1 file creation +# 2 errors and warnings +# 3 some systems may open it to /dev/tty +# 4 used on the Kubota Titan +# 6 checking for... messages and results +# 5 compiler messages saved in config.log +if test "$silent" = yes; then + exec 6>/dev/null +else + exec 6>&1 +fi +exec 5>./config.log + +echo "\ +This file contains any messages produced by compilers while +running configure, to aid debugging if configure makes a mistake. +" 1>&5 + +# Strip out --no-create and --no-recursion so they do not pile up. +# Also quote any args containing shell metacharacters. +ac_configure_args= +for ac_arg +do + case "$ac_arg" in + -no-create | --no-create | --no-creat | --no-crea | --no-cre \ + | --no-cr | --no-c) ;; + -no-recursion | --no-recursion | --no-recursio | --no-recursi \ + | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r) ;; + *" "*|*" "*|*[\[\]\~\#\$\^\&\*\(\)\{\}\\\|\;\<\>\?]*) + ac_configure_args="$ac_configure_args '$ac_arg'" ;; + *) ac_configure_args="$ac_configure_args $ac_arg" ;; + esac +done + +# NLS nuisances. +# Only set these to C if already set. These must not be set unconditionally +# because not all systems understand e.g. LANG=C (notably SCO). +# Fixing LC_MESSAGES prevents Solaris sh from translating var values in `set'! +# Non-C LC_CTYPE values break the ctype check. +if test "${LANG+set}" = set; then LANG=C; export LANG; fi +if test "${LC_ALL+set}" = set; then LC_ALL=C; export LC_ALL; fi +if test "${LC_MESSAGES+set}" = set; then LC_MESSAGES=C; export LC_MESSAGES; fi +if test "${LC_CTYPE+set}" = set; then LC_CTYPE=C; export LC_CTYPE; fi + +# confdefs.h avoids OS command line length limits that DEFS can exceed. +rm -rf conftest* confdefs.h +# AIX cpp loses on an empty file, so make sure it contains at least a newline. +echo > confdefs.h + +# A filename unique to this package, relative to the directory that +# configure is in, which we can look for to find out if srcdir is correct. +ac_unique_file=gperf.1 + +# Find the source files, if location was not specified. +if test -z "$srcdir"; then + ac_srcdir_defaulted=yes + # Try the directory containing this script, then its parent. + ac_prog=$0 + ac_confdir=`echo $ac_prog|sed 's%/[^/][^/]*$%%'` + test "x$ac_confdir" = "x$ac_prog" && ac_confdir=. + srcdir=$ac_confdir + if test ! -r $srcdir/$ac_unique_file; then + srcdir=.. + fi +else + ac_srcdir_defaulted=no +fi +if test ! -r $srcdir/$ac_unique_file; then + if test "$ac_srcdir_defaulted" = yes; then + { echo "configure: error: can not find sources in $ac_confdir or .." 1>&2; exit 1; } + else + { echo "configure: error: can not find sources in $srcdir" 1>&2; exit 1; } + fi +fi +srcdir=`echo "${srcdir}" | sed 's%\([^/]\)/*$%\1%'` + +# Prefer explicitly selected file to automatically selected ones. +if test -z "$CONFIG_SITE"; then + if test "x$prefix" != xNONE; then + CONFIG_SITE="$prefix/share/config.site $prefix/etc/config.site" + else + CONFIG_SITE="$ac_default_prefix/share/config.site $ac_default_prefix/etc/config.site" + fi +fi +for ac_site_file in $CONFIG_SITE; do + if test -r "$ac_site_file"; then + echo "loading site script $ac_site_file" + . "$ac_site_file" + fi +done + +if test -r "$cache_file"; then + echo "loading cache $cache_file" + . $cache_file +else + echo "creating cache $cache_file" + > $cache_file +fi + +ac_ext=c +# CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options. +ac_cpp='$CPP $CPPFLAGS' +ac_compile='${CC-cc} -c $CFLAGS $CPPFLAGS conftest.$ac_ext 1>&5' +ac_link='${CC-cc} -o conftest $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS 1>&5' +cross_compiling=$ac_cv_prog_cc_cross + +if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null; then + # Stardent Vistra SVR4 grep lacks -e, says ghazi@caip.rutgers.edu. + if (echo -n testing; echo 1,2,3) | sed s/-n/xn/ | grep xn >/dev/null; then + ac_n= ac_c=' +' ac_t=' ' + else + ac_n=-n ac_c= ac_t= + fi +else + ac_n= ac_c='\c' ac_t= +fi + + +echo $ac_n "checking whether ${MAKE-make} sets \${MAKE}""... $ac_c" 1>&6 +echo "configure:523: checking whether ${MAKE-make} sets \${MAKE}" >&5 +set dummy ${MAKE-make}; ac_make=`echo "$2" | sed 'y%./+-%__p_%'` +if eval "test \"`echo '$''{'ac_cv_prog_make_${ac_make}_set'+set}'`\" = set"; then + echo $ac_n "(cached) $ac_c" 1>&6 +else + cat > conftestmake <<\EOF +all: + @echo 'ac_maketemp="${MAKE}"' +EOF +# GNU make sometimes prints "make[1]: Entering...", which would confuse us. +eval `${MAKE-make} -f conftestmake 2>/dev/null | grep temp=` +if test -n "$ac_maketemp"; then + eval ac_cv_prog_make_${ac_make}_set=yes +else + eval ac_cv_prog_make_${ac_make}_set=no +fi +rm -f conftestmake +fi +if eval "test \"`echo '$ac_cv_prog_make_'${ac_make}_set`\" = yes"; then + echo "$ac_t""yes" 1>&6 + SET_MAKE= +else + echo "$ac_t""no" 1>&6 + SET_MAKE="MAKE=${MAKE-make}" +fi + +# Find a good install program. We prefer a C program (faster), +# so one script is as good as another. But avoid the broken or +# incompatible versions: +# SysV /etc/install, /usr/sbin/install +# SunOS /usr/etc/install +# IRIX /sbin/install +# AIX /bin/install +# AFS /usr/afsws/bin/install, which mishandles nonexistent args +# SVR4 /usr/ucb/install, which tries to use the nonexistent group "staff" +# ./install, which can be erroneously created by make from ./install.sh. +echo $ac_n "checking for a BSD compatible install""... $ac_c" 1>&6 +echo "configure:560: checking for a BSD compatible install" >&5 +if test -z "$INSTALL"; then +if eval "test \"`echo '$''{'cl_cv_path_install'+set}'`\" = set"; then + echo $ac_n "(cached) $ac_c" 1>&6 +else + IFS="${IFS= }"; ac_save_ifs="$IFS"; IFS="${IFS}:" + for ac_dir in $PATH; do + # Account for people who put trailing slashes in PATH elements. + case "$ac_dir/" in + /|./|.//|/etc/*|/usr/sbin/*|/usr/etc/*|/sbin/*|/usr/afsws/bin/*|/usr/ucb/*) ;; + *) + # OSF1 and SCO ODT 3.0 have their own names for install. + for ac_prog in ginstall installbsd scoinst install; do + if test -f $ac_dir/$ac_prog; then + if test $ac_prog = install && + grep dspmsg $ac_dir/$ac_prog >/dev/null 2>&1; then + # AIX install. It has an incompatible calling convention. + # OSF/1 installbsd also uses dspmsg, but is usable. + : + else + if test $ac_prog = installbsd && + grep src/bos $ac_dir/$ac_prog >/dev/null 2>&1; then + # AIX installbsd doesn't work without option "-g". + : + else + ac_cv_path_install="$ac_dir/$ac_prog -c" + break 2 + fi + fi + fi + done + ;; + esac + done + IFS="$ac_save_ifs" + # As a last resort, use cp. + test -z "$cl_cv_path_install" && cl_cv_path_install="cp" + +fi + INSTALL="$cl_cv_path_install" +fi +echo "$ac_t""$INSTALL" 1>&6 +# Use test -z because SunOS4 sh mishandles braces in ${var-val}. +# It thinks the first close brace ends the variable substitution. +test -z "$INSTALL_PROGRAM" && INSTALL_PROGRAM='$(INSTALL)' +if test -z "$INSTALL_DATA"; then + case "$INSTALL" in + cp | */cp ) INSTALL_DATA='$(INSTALL)' ;; + * ) INSTALL_DATA='$(INSTALL) -m 644' ;; + esac +fi + + trap '' 1 2 15 +cat > confcache <<\EOF +# This file is a shell script that caches the results of configure +# tests run on this system so they can be shared between configure +# scripts and configure runs. It is not useful on other systems. +# If it contains results you don't want to keep, you may remove or edit it. +# +# By default, configure uses ./config.cache as the cache file, +# creating it if it does not exist already. You can give configure +# the --cache-file=FILE option to use a different cache file; that is +# what configure does when it calls configure scripts in +# subdirectories, so they share the cache. +# Giving --cache-file=/dev/null disables caching, for debugging configure. +# config.status only pays attention to the cache file if you give it the +# --recheck option to rerun configure. +# +EOF +# The following way of writing the cache mishandles newlines in values, +# but we know of no workaround that is simple, portable, and efficient. +# So, don't put newlines in cache variables' values. +# Ultrix sh set writes to stderr and can't be redirected directly, +# and sets the high bit in the cache file unless we assign to the vars. +(set) 2>&1 | + case `(ac_space=' '; set) 2>&1` in + *ac_space=\ *) + # `set' does not quote correctly, so add quotes (double-quote substitution + # turns \\\\ into \\, and sed turns \\ into \). + sed -n \ + -e "s/'/'\\\\''/g" \ + -e "s/^\\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\\)=\\(.*\\)/\\1=\${\\1='\\2'}/p" + ;; + *) + # `set' quotes correctly as required by POSIX, so do not add quotes. + sed -n -e 's/^\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\)=\(.*\)/\1=${\1=\2}/p' + ;; + esac >> confcache +if cmp -s $cache_file confcache; then + : +else + if test -w $cache_file; then + echo "updating cache $cache_file" + cat confcache > $cache_file + else + echo "not updating unwritable cache $cache_file" + fi +fi +rm -f confcache + +trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15 + +test "x$prefix" = xNONE && prefix=$ac_default_prefix +# Let make expand exec_prefix. +test "x$exec_prefix" = xNONE && exec_prefix='${prefix}' + +# Any assignment to VPATH causes Sun make to only execute +# the first set of double-colon rules, so remove it if not needed. +# If there is a colon in the path, we need to keep it. +if test "x$srcdir" = x.; then + ac_vpsub='/^[ ]*VPATH[ ]*=[^:]*$/d' +fi + +trap 'rm -f $CONFIG_STATUS conftest*; exit 1' 1 2 15 + +# Transform confdefs.h into DEFS. +# Protect against shell expansion while executing Makefile rules. +# Protect against Makefile macro expansion. +cat > conftest.defs <<\EOF +s%#define \([A-Za-z_][A-Za-z0-9_]*\) *\(.*\)%-D\1=\2%g +s%[ `~#$^&*(){}\\|;'"<>?]%\\&%g +s%\[%\\&%g +s%\]%\\&%g +s%\$%$$%g +EOF +DEFS=`sed -f conftest.defs confdefs.h | tr '\012' ' '` +rm -f conftest.defs + + +# Without the "./", some shells look in PATH for config.status. +: ${CONFIG_STATUS=./config.status} + +echo creating $CONFIG_STATUS +rm -f $CONFIG_STATUS +cat > $CONFIG_STATUS </dev/null | sed 1q`: +# +# $0 $ac_configure_args +# +# Compiler output produced by configure, useful for debugging +# configure, is in ./config.log if it exists. + +ac_cs_usage="Usage: $CONFIG_STATUS [--recheck] [--version] [--help]" +for ac_option +do + case "\$ac_option" in + -recheck | --recheck | --rechec | --reche | --rech | --rec | --re | --r) + echo "running \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion" + exec \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion ;; + -version | --version | --versio | --versi | --vers | --ver | --ve | --v) + echo "$CONFIG_STATUS generated by autoconf version 2.12" + exit 0 ;; + -help | --help | --hel | --he | --h) + echo "\$ac_cs_usage"; exit 0 ;; + *) echo "\$ac_cs_usage"; exit 1 ;; + esac +done + +ac_given_srcdir=$srcdir + +trap 'rm -fr `echo "Makefile" | sed "s/:[^ ]*//g"` conftest*; exit 1' 1 2 15 +EOF +cat >> $CONFIG_STATUS < conftest.subs <<\\CEOF +$ac_vpsub +$extrasub +s%@CFLAGS@%$CFLAGS%g +s%@CPPFLAGS@%$CPPFLAGS%g +s%@CXXFLAGS@%$CXXFLAGS%g +s%@DEFS@%$DEFS%g +s%@LDFLAGS@%$LDFLAGS%g +s%@LIBS@%$LIBS%g +s%@exec_prefix@%$exec_prefix%g +s%@prefix@%$prefix%g +s%@program_transform_name@%$program_transform_name%g +s%@bindir@%$bindir%g +s%@sbindir@%$sbindir%g +s%@libexecdir@%$libexecdir%g +s%@datadir@%$datadir%g +s%@sysconfdir@%$sysconfdir%g +s%@sharedstatedir@%$sharedstatedir%g +s%@localstatedir@%$localstatedir%g +s%@libdir@%$libdir%g +s%@includedir@%$includedir%g +s%@oldincludedir@%$oldincludedir%g +s%@infodir@%$infodir%g +s%@mandir@%$mandir%g +s%@SET_MAKE@%$SET_MAKE%g +s%@INSTALL@%$INSTALL%g +s%@INSTALL_PROGRAM@%$INSTALL_PROGRAM%g +s%@INSTALL_DATA@%$INSTALL_DATA%g + +CEOF +EOF + +cat >> $CONFIG_STATUS <<\EOF + +# Split the substitutions into bite-sized pieces for seds with +# small command number limits, like on Digital OSF/1 and HP-UX. +ac_max_sed_cmds=90 # Maximum number of lines to put in a sed script. +ac_file=1 # Number of current file. +ac_beg=1 # First line for current file. +ac_end=$ac_max_sed_cmds # Line after last line for current file. +ac_more_lines=: +ac_sed_cmds="" +while $ac_more_lines; do + if test $ac_beg -gt 1; then + sed "1,${ac_beg}d; ${ac_end}q" conftest.subs > conftest.s$ac_file + else + sed "${ac_end}q" conftest.subs > conftest.s$ac_file + fi + if test ! -s conftest.s$ac_file; then + ac_more_lines=false + rm -f conftest.s$ac_file + else + if test -z "$ac_sed_cmds"; then + ac_sed_cmds="sed -f conftest.s$ac_file" + else + ac_sed_cmds="$ac_sed_cmds | sed -f conftest.s$ac_file" + fi + ac_file=`expr $ac_file + 1` + ac_beg=$ac_end + ac_end=`expr $ac_end + $ac_max_sed_cmds` + fi +done +if test -z "$ac_sed_cmds"; then + ac_sed_cmds=cat +fi +EOF + +cat >> $CONFIG_STATUS <> $CONFIG_STATUS <<\EOF +for ac_file in .. $CONFIG_FILES; do if test "x$ac_file" != x..; then + # Support "outfile[:infile[:infile...]]", defaulting infile="outfile.in". + case "$ac_file" in + *:*) ac_file_in=`echo "$ac_file"|sed 's%[^:]*:%%'` + ac_file=`echo "$ac_file"|sed 's%:.*%%'` ;; + *) ac_file_in="${ac_file}.in" ;; + esac + + # Adjust a relative srcdir, top_srcdir, and INSTALL for subdirectories. + + # Remove last slash and all that follows it. Not all systems have dirname. + ac_dir=`echo $ac_file|sed 's%/[^/][^/]*$%%'` + if test "$ac_dir" != "$ac_file" && test "$ac_dir" != .; then + # The file is in a subdirectory. + test ! -d "$ac_dir" && mkdir "$ac_dir" + ac_dir_suffix="/`echo $ac_dir|sed 's%^\./%%'`" + # A "../" for each directory in $ac_dir_suffix. + ac_dots=`echo $ac_dir_suffix|sed 's%/[^/]*%../%g'` + else + ac_dir_suffix= ac_dots= + fi + + case "$ac_given_srcdir" in + .) srcdir=. + if test -z "$ac_dots"; then top_srcdir=. + else top_srcdir=`echo $ac_dots|sed 's%/$%%'`; fi ;; + /*) srcdir="$ac_given_srcdir$ac_dir_suffix"; top_srcdir="$ac_given_srcdir" ;; + *) # Relative path. + srcdir="$ac_dots$ac_given_srcdir$ac_dir_suffix" + top_srcdir="$ac_dots$ac_given_srcdir" ;; + esac + + + echo creating "$ac_file" + rm -f "$ac_file" + configure_input="Generated automatically from `echo $ac_file_in|sed 's%.*/%%'` by configure." + case "$ac_file" in + *Makefile*) ac_comsub="1i\\ +# $configure_input" ;; + *) ac_comsub= ;; + esac + + ac_file_inputs=`echo $ac_file_in|sed -e "s%^%$ac_given_srcdir/%" -e "s%:% $ac_given_srcdir/%g"` + sed -e "$ac_comsub +s%@configure_input@%$configure_input%g +s%@srcdir@%$srcdir%g +s%@top_srcdir@%$top_srcdir%g +" $ac_file_inputs | (eval "$ac_sed_cmds") > $ac_file +fi; done +rm -f conftest.s* + +EOF +cat >> $CONFIG_STATUS <> $CONFIG_STATUS <<\EOF + +exit 0 +EOF +chmod +x $CONFIG_STATUS +rm -fr confdefs* $ac_clean_files +test "$no_create" = yes || ${CONFIG_SHELL-/bin/sh} $CONFIG_STATUS || exit 1 + diff --git a/contrib/gperf/doc/configure.in b/contrib/gperf/doc/configure.in new file mode 100644 index 0000000..f72482c --- /dev/null +++ b/contrib/gperf/doc/configure.in @@ -0,0 +1,33 @@ +dnl autoconf configuration for gperf/doc + +dnl Copyright (C) 1998 Free Software Foundation, Inc. +dnl written by Douglas C. Schmidt (schmidt@ics.uci.edu) +dnl +dnl This file is part of GNU GPERF. +dnl +dnl GNU GPERF is free software; you can redistribute it and/or modify +dnl it under the terms of the GNU General Public License as published by +dnl the Free Software Foundation; either version 1, or (at your option) +dnl any later version. +dnl +dnl GNU GPERF is distributed in the hope that it will be useful, +dnl but WITHOUT ANY WARRANTY; without even the implied warranty of +dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +dnl GNU General Public License for more details. +dnl +dnl You should have received a copy of the GNU General Public License +dnl along with GNU GPERF; see the file COPYING. If not, write to the +dnl Free Software Foundation, 59 Temple Place - Suite 330, Boston, +dnl MA 02111-1307, USA. + +AC_INIT(gperf.1) +AC_PROG_MAKE_SET +dnl +dnl checks for programs +dnl +CL_PROG_INSTALL + dnl sets variables INSTALL, INSTALL_DATA, INSTALL_PROGRAM +dnl +dnl That's it. +dnl +AC_OUTPUT(Makefile) diff --git a/contrib/gperf/doc/gperf.1 b/contrib/gperf/doc/gperf.1 new file mode 100644 index 0000000..1e4a2aa --- /dev/null +++ b/contrib/gperf/doc/gperf.1 @@ -0,0 +1,23 @@ +.TH GPERF 1 "March 7, 1998 +.UC 4 +.SH NAME +gperf \- generate a perfect hash function from a key set +.SH SYNOPSIS +.B gperf +[ +.B \-adghijklnoprsStv +] [ +.I keyfile +] +.SH DESCRIPTION + +\fIgperf\fP reads a set of ``keys'' from \fIkeyfile\fP (or, by +default, from the standard input) and attempts to find a non-minimal +perfect hashing function that recognizes a member of the key set in +constant, i.e., O(1), time. If such a function is found the program +generates a pair of \fIC\fP source code routines that perform the +hashing and table lookup. All generated code is directed to the +standard output. + +Please refer to the \fIgperf.texi\fP file for more information. +This file is distributed with \fIgperf\fP release. diff --git a/contrib/gperf/doc/gperf.texi b/contrib/gperf/doc/gperf.texi new file mode 100644 index 0000000..c4a3575 --- /dev/null +++ b/contrib/gperf/doc/gperf.texi @@ -0,0 +1,1251 @@ +\input texinfo @c -*-texinfo-*- + +@settitle User's Guide to @code{gperf} +@setfilename gperf.info + +@ifinfo +@format +START-INFO-DIR-ENTRY +* Gperf: (gperf). Perfect Hash Function Generator. +END-INFO-DIR-ENTRY +@end format +@end ifinfo + +@ifinfo +This file documents the features of the GNU Perfect Hash Function Generator + +Copyright (C) 1989-1998 Free Software Foundation, Inc. + +Permission is granted to make and distribute verbatim copies of +this manual provided the copyright notice and this permission notice +are preserved on all copies. + +@ignore +Permission is granted to process this file through @TeX{} and print the +results, provided the printed document carries copying permission +notice identical to this one except for the removal of this paragraph +(this paragraph not being relevant to the printed manual). + +@end ignore + +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided also that the +section entitled ``GNU General Public License'' is included exactly as +in the original, and provided that the entire resulting derived work is +distributed under the terms of a permission notice identical to this one. + +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that the section entitled ``GNU @code{gperf} General Public License'' and +this permission notice may be included in translations approved by the +Free Software Foundation instead of in the original English. +@end ifinfo + +@setchapternewpage odd + +@titlepage +@center @titlefont{User's Guide} +@sp 2 +@center @titlefont{for the} +@sp 2 +@center @titlefont{GNU GPERF Utility} +@sp 4 +@center Douglas C. Schmidt +@sp 3 +@center last updated 14 April 1998 +@sp 1 +@center for version 2.7 +@page +@vskip 0pt plus 1filll +Copyright @copyright{} 1989-1998 Free Software Foundation, Inc. + + +Permission is granted to make and distribute verbatim copies of +this manual provided the copyright notice and this permission notice +are preserved on all copies. + +Permission is granted to copy and distribute modified versions of this +manual under the conditions for verbatim copying, provided also that the +section entitled ``GNU @code{gperf} General Public License'' is included exactly as +in the original, and provided that the entire resulting derived work is +distributed under the terms of a permission notice identical to this one. + +Permission is granted to copy and distribute translations of this manual +into another language, under the above conditions for modified versions, +except that the section entitled ``GNU @code{gperf} General Public License'' may be +included in a translation approved by the author instead of in the original +English. +@end titlepage + +@ifinfo +@node Top, Copying, (dir), (dir) +@unnumbered Introduction + +This manual documents the GNU @code{gperf} perfect hash function generator +utility, focusing on its features and how to use them, and how to report +bugs. + +@end ifinfo +@menu +* Copying:: GNU @code{gperf} General Public License says + how you can copy and share @code{gperf}. +* Contributors:: People who have contributed to @code{gperf}. +* Motivation:: Static search structures and GNU GPERF. +* Search Structures:: Static search structures and GNU @code{gperf} +* Description:: High-level discussion of how GPERF functions. +* Options:: A description of options to the program. +* Bugs:: Known bugs and limitations with GPERF. +* Projects:: Things still left to do. +* Implementation:: Implementation Details for GNU GPERF. +* Bibliography:: Material Referenced in this Report. + + --- The Detailed Node Listing --- + +High-Level Description of GNU @code{gperf} + +* Input Format:: Input Format to @code{gperf} +* Output Format:: Output Format for Generated C Code with @code{gperf} + +Input Format to @code{gperf} + +* Declarations:: @code{struct} Declarations and C Code Inclusion. +* Keywords:: Format for Keyword Entries. +* Functions:: Including Additional C Functions. + +Options to the @code{gperf} Utility + +* Input Details:: Options that affect Interpretation of the Input File +* Output Language:: Specifying the Language for the Output Code +* Output Details:: Fine tuning Details in the Output Code +* Algorithmic Details:: Changing the Algorithms employed by @code{gperf} +* Verbosity:: Informative Output +@end menu + +@node Copying, Contributors, Top, Top +@unnumbered GNU GENERAL PUBLIC LICENSE +@center Version 1, February 1989 + +@display +Copyright @copyright{} 1989 Free Software Foundation, Inc. +675 Mass Ave, Cambridge, MA 02139, USA + +Everyone is permitted to copy and distribute verbatim copies +of this license document, but changing it is not allowed. +@end display + +@unnumberedsec Preamble + + The license agreements of most software companies try to keep users +at the mercy of those companies. By contrast, our General Public +License is intended to guarantee your freedom to share and change free +software---to make sure the software is free for all its users. The +General Public License applies to the Free Software Foundation's +software and to any other program whose authors commit to using it. +You can use it for your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Specifically, the General Public License is designed to make +sure that you have the freedom to give away or sell copies of free +software, that you receive source code or can get it if you want it, +that you can change the software or use pieces of it in new free +programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of a such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must tell them their rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + The precise terms and conditions for copying, distribution and +modification follow. + +@iftex +@unnumberedsec TERMS AND CONDITIONS +@end iftex +@ifinfo +@center TERMS AND CONDITIONS +@end ifinfo + +@enumerate +@item +This License Agreement applies to any program or other work which +contains a notice placed by the copyright holder saying it may be +distributed under the terms of this General Public License. The +``Program'', below, refers to any such program or work, and a ``work based +on the Program'' means either the Program or any work containing the +Program or a portion of it, either verbatim or with modifications. Each +licensee is addressed as ``you''. + +@item +You may copy and distribute verbatim copies of the Program's source +code as you receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice and +disclaimer of warranty; keep intact all the notices that refer to this +General Public License and to the absence of any warranty; and give any +other recipients of the Program a copy of this General Public License +along with the Program. You may charge a fee for the physical act of +transferring a copy. + +@item +You may modify your copy or copies of the Program or any portion of +it, and copy and distribute such modifications under the terms of Paragraph +1 above, provided that you also do the following: + +@itemize @bullet +@item +cause the modified files to carry prominent notices stating that +you changed the files and the date of any change; and + +@item +cause the whole of any work that you distribute or publish, that +in whole or in part contains the Program or any part thereof, either +with or without modifications, to be licensed at no charge to all +third parties under the terms of this General Public License (except +that you may choose to grant warranty protection to some or all +third parties, at your option). + +@item +If the modified program normally reads commands interactively when +run, you must cause it, when started running for such interactive use +in the simplest and most usual way, to print or display an +announcement including an appropriate copyright notice and a notice +that there is no warranty (or else, saying that you provide a +warranty) and that users may redistribute the program under these +conditions, and telling the user how to view a copy of this General +Public License. + +@item +You may charge a fee for the physical act of transferring a +copy, and you may at your option offer warranty protection in +exchange for a fee. +@end itemize + +Mere aggregation of another independent work with the Program (or its +derivative) on a volume of a storage or distribution medium does not bring +the other work under the scope of these terms. + +@item +You may copy and distribute the Program (or a portion or derivative of +it, under Paragraph 2) in object code or executable form under the terms of +Paragraphs 1 and 2 above provided that you also do one of the following: + +@itemize @bullet +@item +accompany it with the complete corresponding machine-readable +source code, which must be distributed under the terms of +Paragraphs 1 and 2 above; or, + +@item +accompany it with a written offer, valid for at least three +years, to give any third party free (except for a nominal charge +for the cost of distribution) a complete machine-readable copy of the +corresponding source code, to be distributed under the terms of +Paragraphs 1 and 2 above; or, + +@item +accompany it with the information you received as to where the +corresponding source code may be obtained. (This alternative is +allowed only for noncommercial distribution and only if you +received the program in object code or executable form alone.) +@end itemize + +Source code for a work means the preferred form of the work for making +modifications to it. For an executable file, complete source code means +all the source code for all modules it contains; but, as a special +exception, it need not include source code for modules which are standard +libraries that accompany the operating system on which the executable +file runs, or for standard header files or definitions files that +accompany that operating system. + +@item +You may not copy, modify, sublicense, distribute or transfer the +Program except as expressly provided under this General Public License. +Any attempt otherwise to copy, modify, sublicense, distribute or transfer +the Program is void, and will automatically terminate your rights to use +the Program under this License. However, parties who have received +copies, or rights to use copies, from you under this General Public +License will not have their licenses terminated so long as such parties +remain in full compliance. + +@item +By copying, distributing or modifying the Program (or any work based +on the Program) you indicate your acceptance of this license to do so, +and all its terms and conditions. + +@item +Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the original +licensor to copy, distribute or modify the Program subject to these +terms and conditions. You may not impose any further restrictions on the +recipients' exercise of the rights granted herein. + +@item +The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of the license which applies to it and ``any +later version'', you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +the license, you may choose any version ever published by the Free Software +Foundation. + +@item +If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + +@iftex +@heading NO WARRANTY +@end iftex +@ifinfo +@center NO WARRANTY +@end ifinfo + +@item +BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + +@item +IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL +ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES +ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT +LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES +SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE +WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN +ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. +@end enumerate + +@iftex +@heading END OF TERMS AND CONDITIONS +@end iftex +@ifinfo +@center END OF TERMS AND CONDITIONS +@end ifinfo + +@page +@unnumberedsec Appendix: How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to humanity, the best way to achieve this is to make it +free software which everyone can redistribute and change under these +terms. + + To do so, attach the following notices to the program. It is safest to +attach them to the start of each source file to most effectively convey +the exclusion of warranty; and each file should have at least the +``copyright'' line and a pointer to where the full notice is found. + +@smallexample +@var{one line to give the program's name and a brief idea of what it does.} +Copyright (C) 19@var{yy} @var{name of author} + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 1, or (at your option) +any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +@end smallexample + +Also add information on how to contact you by electronic and paper mail. + +If the program is interactive, make it output a short notice like this +when it starts in an interactive mode: + +@smallexample +Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author} +Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. +This is free software, and you are welcome to redistribute it +under certain conditions; type `show c' for details. +@end smallexample + +The hypothetical commands `show w' and `show c' should show the +appropriate parts of the General Public License. Of course, the +commands you use may be called something other than `show w' and `show +c'; they could even be mouse-clicks or menu items---whatever suits your +program. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a ``copyright disclaimer'' for the program, if +necessary. Here a sample; alter the names: + +@example +Yoyodyne, Inc., hereby disclaims all copyright interest in the +program `Gnomovision' (a program to direct compilers to make passes +at assemblers) written by James Hacker. + +@var{signature of Ty Coon}, 1 April 1989 +Ty Coon, President of Vice +@end example + +That's all there is to it! + +@node Contributors, Motivation, Copying, Top +@unnumbered Contributors to GNU @code{gperf} Utility + +@itemize @bullet +@item +The GNU @code{gperf} perfect hash function generator utility was +originally written in GNU C++ by Douglas C. Schmidt. It is now also +available in a highly-portable ``old-style'' C version. The general +idea for the perfect hash function generator was inspired by Keith +Bostic's algorithm written in C, and distributed to net.sources around +1984. The current program is a heavily modified, enhanced, and extended +implementation of Keith's basic idea, created at the University of +California, Irvine. Bugs, patches, and suggestions should be reported +to @code{} and @code{}. + +@item +Special thanks is extended to Michael Tiemann and Doug Lea, for +providing a useful compiler, and for giving me a forum to exhibit my +creation. + +In addition, Adam de Boor and Nels Olson provided many tips and insights +that greatly helped improve the quality and functionality of @code{gperf}. +@end itemize + +@node Motivation, Search Structures, Contributors, Top +@chapter Introduction + +@code{gperf} is a perfect hash function generator written in C++. It +transforms an @var{n} element user-specified keyword set @var{W} into +a perfect hash function @var{F}. @var{F} uniquely maps keywords in +@var{W} onto the range 0..@var{k}, where @var{k >= n}. If +@var{k = n} then @var{F} is a @emph{minimal} perfect hash function. +@code{gperf} generates a 0..@var{k} element static lookup table and a +pair of C functions. These functions determine whether a given +character string @var{s} occurs in @var{W}, using at most one probe +into the lookup table. + +@code{gperf} currently generates the reserved keyword recognizer for +lexical analyzers in several production and research compilers and +language processing tools, including GNU C, GNU C++, GNU Pascal, GNU +Modula 3, and GNU indent. Complete C++ source code for @code{gperf} is +available via anonymous ftp from @code{ics.uci.edu} and +@code{ftp.santafe.edu}. @code{gperf} was also distributed along with +the GNU libg++ library for several years. A highly portable, +functionally equivalent K&R C version of @code{gperf} is archived in +comp.sources.unix, volume 20. Finally, a paper describing +@code{gperf}'s design and implementation in greater detail is available +in the Second USENIX C++ Conference proceedings. + +@node Search Structures, Description, Motivation, Top +@chapter Static search structures and GNU @code{gperf} + +A @dfn{static search structure} is an Abstract Data Type with certain +fundamental operations, e.g., @emph{initialize}, @emph{insert}, +and @emph{retrieve}. Conceptually, all insertions occur before any +retrievals. In practice, @code{gperf} generates a @code{static} array +containing search set keywords and any associated attributes specified +by the user. Thus, there is essentially no execution-time cost for the +insertions. It is a useful data structure for representing @emph{static +search sets}. Static search sets occur frequently in software system +applications. Typical static search sets include compiler reserved +words, assembler instruction opcodes, and built-in shell interpreter +commands. Search set members, called @dfn{keywords}, are inserted into +the structure only once, usually during program initialization, and are +not generally modified at run-time. + +Numerous static search structure implementations exist, e.g., +arrays, linked lists, binary search trees, digital search tries, and +hash tables. Different approaches offer trade-offs between space +utilization and search time efficiency. For example, an @var{n} element +sorted array is space efficient, though the average-case time +complexity for retrieval operations using binary search is +proportional to log @var{n}. Conversely, hash table implementations +often locate a table entry in constant time, but typically impose +additional memory overhead and exhibit poor worst case performance. + + +@emph{Minimal perfect hash functions} provide an optimal solution for a +particular class of static search sets. A minimal perfect hash +function is defined by two properties: + +@itemize @bullet +@item +It allows keyword recognition in a static search set using at most +@emph{one} probe into the hash table. This represents the ``perfect'' +property. +@item +The actual memory allocated to store the keywords is precisely large +enough for the keyword set, and @emph{no larger}. This is the +``minimal'' property. +@end itemize + +For most applications it is far easier to generate @emph{perfect} hash +functions than @emph{minimal perfect} hash functions. Moreover, +non-minimal perfect hash functions frequently execute faster than +minimal ones in practice. This phenomena occurs since searching a +sparse keyword table increases the probability of locating a ``null'' +entry, thereby reducing string comparisons. @code{gperf}'s default +behavior generates @emph{near-minimal} perfect hash functions for +keyword sets. However, @code{gperf} provides many options that permit +user control over the degree of minimality and perfection. + +Static search sets often exhibit relative stability over time. For +example, Ada's 63 reserved words have remained constant for nearly a +decade. It is therefore frequently worthwhile to expend concerted +effort building an optimal search structure @emph{once}, if it +subsequently receives heavy use multiple times. @code{gperf} removes +the drudgery associated with constructing time- and space-efficient +search structures by hand. It has proven a useful and practical tool +for serious programming projects. Output from @code{gperf} is currently +used in several production and research compilers, including GNU C, GNU +C++, GNU Pascal, and GNU Modula 3. The latter two compilers are not yet +part of the official GNU distribution. Each compiler utilizes +@code{gperf} to automatically generate static search structures that +efficiently identify their respective reserved keywords. + +@node Description, Options, Search Structures, Top +@chapter High-Level Description of GNU @code{gperf} + +@menu +* Input Format:: Input Format to @code{gperf} +* Output Format:: Output Format for Generated C Code with @code{gperf} +@end menu + +The perfect hash function generator @code{gperf} reads a set of +``keywords'' from a @dfn{keyfile} (or from the standard input by +default). It attempts to derive a perfect hashing function that +recognizes a member of the @dfn{static keyword set} with at most a +single probe into the lookup table. If @code{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 @code{gperf}. + +By default, @code{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 @code{gperf} to utilize a C @code{switch} +statement scheme that minimizes data space storage size. Furthermore, +using a C @code{switch} may actually speed up the keyword retrieval time +somewhat. Actual results depend on your C compiler, of course. + +In general, @code{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 @code{gperf} to find and generate a perfect hash function. +Experimentation is the key to getting the most from @code{gperf}. + +@node Input Format, Output Format, Description, Description +@section Input Format to @code{gperf} + +You can control the input keyfile format by varying certain command-line +arguments, in particular the @samp{-t} option. The input's appearance +is similar to GNU utilities @code{flex} and @code{bison} (or UNIX +utilities @code{lex} and @code{yacc}). Here's an outline of the general +format: + +@example +@group +declarations +%% +keywords +%% +functions +@end group +@end example + +@emph{Unlike} @code{flex} or @code{bison}, all sections of @code{gperf}'s input +are optional. The following sections describe the input format for each +section. + +@menu +* Declarations:: @code{struct} Declarations and C Code Inclusion. +* Keywords:: Format for Keyword Entries. +* Functions:: Including Additional C Functions. +@end menu + +@node Declarations, Keywords, Input Format, Input Format +@subsection @code{struct} Declarations and C Code Inclusion + +The keyword input file optionally contains a section for including +arbitrary C declarations and definitions, as well as provisions for +providing a user-supplied @code{struct}. If the @samp{-t} option +@emph{is} enabled, you @emph{must} provide a C @code{struct} as the last +component in the declaration section from the keyfile file. The first +field in this struct must be a @code{char *} identifier called @samp{name}, +although it is possible to modify this field's name with the @samp{-K} +option described below. + +Here is simple example, using months of the year and their attributes as +input: + +@example +@group +struct months @{ 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 +@end group +@end example + +Separating the @code{struct} declaration from the list of key words and +other fields are a pair of consecutive percent signs, @code{%%}, +appearing left justified in the first column, as in the UNIX utility +@code{lex}. + +Using a syntax similar to GNU utilities @code{flex} and @code{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 @code{%@{}, @code{%@}} pairs. Here is +an input fragment based on the previous example that illustrates this +feature: + +@example +@group +%@{ +#include +/* This section of code is inserted directly into the output. */ +int return_month_days (struct months *months, int is_leap_year); +%@} +struct months @{ char *name; int number; int days; int leap_days; @}; +%% +january, 1, 31, 31 +february, 2, 28, 29 +march, 3, 31, 31 +... +@end group +@end example + +It is possible to omit the declaration section entirely. In this case +the keyfile begins directly with the first keyword line, e.g.: + +@example +@group +january, 1, 31, 31 +february, 2, 28, 29 +march, 3, 31, 31 +april, 4, 30, 30 +... +@end group +@end example + +@node Keywords, Functions, Declarations, Input Format +@subsection Format for Keyword Entries + +The second keyfile format section contains lines of keywords and any +associated attributes you might supply. A line beginning with @samp{#} +in the first column is considered a comment. Everything following the +@samp{#} is ignored, up to and including the following newline. + +The first field of each non-comment line is always the key itself. It +should be given as a simple name, i.e., without surrounding +string quotation marks, and be left-justified flush against the first +column. 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: + +@example +@group +# These are a few C reserved words, see the c.@code{gperf} file +# for a complete list of ANSI C reserved words. +unsigned +sizeof +switch +signed +if +default +for +while +return +@end group +@end example + +Note that unlike @code{flex} or @code{bison} the first @code{%%} 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 @code{struct} provided by you in the +declaration section. If the @samp{-t} option is @emph{not} enabled +these fields are simply ignored. All previous examples except the last +one contain keyword attributes. + +@node Functions, , Keywords, Input Format +@subsection Including Additional C Functions + +The optional third section also corresponds closely with conventions +found in @code{flex} and @code{bison}. All text in this section, +starting at the final @code{%%} 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. + +@node Output Format, , Input Format, Description +@section Output Format for Generated C Code with @code{gperf} + +Several options control how the generated C code appears on the standard +output. Two C function are generated. They are called @code{hash} and +@code{in_word_set}, although you may modify the name for +@code{in_word_set} with a command-line option. Both functions require +two arguments, a string, @code{char *} @var{str}, and a length +parameter, @code{int} @var{len}. Their default function prototypes are +as follows: + +@example +@group +static int hash (char *str, int len); +int in_word_set (char *str, int len); +@end group +@end example + +By default, the generated @code{hash} function returns an integer value +created by adding @var{len} to several user-specified @var{str} key +positions indexed into an @dfn{associated values} table stored in a +local static array. The associated values table is constructed +internally by @code{gperf} and later output as a static local C array called +@var{hash_table}; its meaning and properties are described below. +@xref{Implementation}. The relevant key positions are specified via the +@samp{-k} option when running @code{gperf}, as detailed in the @emph{Options} +section below. @xref{Options}. + +Two options, @samp{-g} (assume you are compiling with GNU C and its +@code{inline} feature) and @samp{-a} (assume ANSI C-style function +prototypes), alter the content of both the generated @code{hash} and +@code{in_word_set} routines. However, function @code{in_word_set} may +be modified more extensively, in response to your option settings. The +options that affect the @code{in_word_set} structure are: + +@itemize @bullet +@table @samp +@item -t +Make use of the user-defined @code{struct}. + +@item -S @var{total switch statements} +Generate 1 or more C @code{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. +@end table +@end itemize + +If the @samp{-t} and @samp{-S} options are omitted, the +default action is to generate a @code{char *} array containing the keys, +together with additional null 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. + +@node Options, Input Details, Description, Top +@chapter Options to the @code{gperf} Utility + +There are @emph{many} options to @code{gperf}. They were added to make +the program more convenient for use with real applications. ``On-line'' +help is readily available via the @samp{-h} option. Here is the complete +list of options. + +@menu +* Input Details:: Options that affect Interpretation of the Input File +* Output Language:: Specifying the Language for the Output Code +* Output Details:: Fine tuning Details in the Output Code +* Algorithmic Details:: Changing the Algorithms employed by @code{gperf} +* Verbosity:: Informative Output +@end menu + +@node Input Details, Output Language, Options, Options +@section Options that affect Interpretation of the Input File + +@itemize @bullet +@table @samp +@item -e @var{keyword delimiter list} +Allows the user to provide a string containing delimiters used to +separate keywords from their attributes. The default is ",\n". This +option is essential if you want to use keywords that have embedded +commas or newlines. One useful trick is to use -e'TAB', where TAB is +the literal tab character. + +@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. +@end table +@end itemize + +@node Output Language, Output Details, Input Details, Options +@section Options to specify the Language for the Output Code + +@itemize @bullet +@table @samp +@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: + +@itemize @bullet +@table @samp +@item KR-C +Old-style K&R C. This language is understood by old-style C compilers and +ANSI C compilers, but ANSI C compilers may flag warnings (or even errors) +because of lacking @samp{const}. + +@item C +Common C. This language is understood by ANSI C compilers, and also by +old-style C compilers, provided that you @code{#define const} to empty +for compilers which don't know about this keyword. + +@item ANSI-C +ANSI C. This language is understood by ANSI C compilers and C++ compilers. + +@item C++ +C++. This language is understood by C++ compilers. +@end table +@end itemize + +The default is C. + +@item -a +This option is supported for compatibility with previous releases of +@code{gperf}. It does not do anything. + +@item -g +This option is supported for compatibility with previous releases of +@code{gperf}. It does not do anything. +@end table +@end itemize + +@node Output Details, Algorithmic Details, Output Language, Options +@section Options for fine tuning Details in the Output Code + +@itemize @bullet +@table @samp +@item -K @var{key name} +This option is only useful when option @samp{-t} has been given. +By default, the program assumes the structure component identifier for +the keyword is @samp{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 -H @var{hash function name} +Allows you to specify the name for the generated hash function. Default +name is @samp{hash}. This option permits the use of two hash tables in the +same file. + +@item -N @var{lookup function name} +Allows you to specify the name for the generated lookup function. +Default name is @samp{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. + +@item -Z @var{class name} +This option is only useful when option @samp{-L C++} has been given. +It allows you to specify the name of generated C++ class. Default name is +@code{Perfect_Hash}. + +@item -7 +This option specifies that all strings that will be passed as arguments +to the generated hash function and the generated lookup function will +solely consist of 7-bit ASCII characters (characters in the range 0..127). +(Note that the ANSI C functions @code{isalnum} and @code{isgraph} do +@emph{not} guarantee that a character is in this range. Only an explicit +test like @samp{c >= 'A' && c <= 'Z'} guarantees this.) This was the +default in earlier versions of @code{gperf}; now the default is to assume +8-bit characters. + +@item -c +Generates C code that uses the @code{strncmp} function to perform +string comparisons. The default action is to use @code{strcmp}. + +@item -C +Makes the contents of all generated lookup tables constant, i.e., +``readonly''. Many compilers can generate more efficient code for this +by putting the tables in readonly memory. + +@item -E +Define constant values using an enum local to the lookup function rather +than with #defines. This also means that different lookup functions can +reside in the same file. Thanks to James Clark @code{}. + +@item -I +Include the necessary system include file, @code{}, 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. + +@item -G +Generate the static table of keywords as a static global variable, +rather than hiding it inside of the lookup function (which is the +default behavior). + +@item -W @var{hash table array name} +Allows you to specify the name for the generated array containing the +hash table. Default name is @samp{wordlist}. This option permits the +use of two hash tables in the same file, even when the option @samp{-G} +is given. + +@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 +Prevents the transfer of the type declaration to the output file. Use +this option if the type is already defined elsewhere. + +@item -p +This option is supported for compatibility with previous releases of +@code{gperf}. It does not do anything. +@end table +@end itemize + +@node Algorithmic Details, Verbosity, Output Details, Options +@section Options for changing the Algorithms employed by @code{gperf} + +@itemize @bullet +@table @samp +@item -k @var{keys} +Allows selection of the character key positions used in the keywords' +hash function. The allowable choices range between 1-126, inclusive. +The positions are separated by commas, e.g., @samp{-k 9,4,13,14}; +ranges may be used, 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 -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 -D +Handle keywords whose key position sets hash to duplicate values. +Duplicate hash values occur for two reasons: + +@itemize @bullet +@item +Since @code{gperf} does not backtrack it is possible for it to process +all your input keywords without finding a unique mapping for each word. +However, frequently only a very small number of duplicates occur, and +the majority of keys still require one probe into the table. +@item +Sometimes a set of keys may have the same names, but possess different +attributes. With the -D option @code{gperf} treats all these keys as part of +an equivalence class and generates a perfect hash function with multiple +comparisons for duplicate keys. It is up to you to completely +disambiguate the keywords by modifying the generated C code. However, +@code{gperf} helps you out by organizing the output. +@end itemize + +Option @samp{-D} is extremely useful for certain large or highly +redundant keyword sets, e.g., assembler instruction opcodes. +Using this option usually means that the generated hash function is no +longer perfect. On the other hand, it permits @code{gperf} to work on +keyword sets that it otherwise could not handle. + +@item -f @var{iteration amount} +Generate the perfect hash function ``fast''. This decreases @code{gperf}'s +running time at the cost of minimizing generated table-size. The +iteration amount represents the number of times to iterate when +resolving a collision. `0' means iterate by the number of keywords. +This option is probably most useful when used in conjunction with options +@samp{-D} and/or @samp{-S} for @emph{large} keyword sets. + +@item -i @var{initial value} +Provides an initial @var{value} for the associate values array. Default +is 0. Increasing the initial value helps inflate the final table size, +possibly leading to more time efficient keyword lookups. Note that this +option is not particularly useful when @samp{-S} is used. Also, +@samp{-i} is overriden when the @samp{-r} option is used. + +@item -j @var{jump value} +Affects the ``jump value'', i.e., how far to advance the +associated character value upon collisions. @var{Jump value} is rounded +up to an odd number, the default is 5. If the @var{jump value} is 0 +@code{gperf} jumps by random amounts. + +@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 -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 -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. +@end table +@end itemize + +@node Verbosity, Bugs, Algorithmic Details, Options +@section Informative Output + +@itemize @bullet +@table @samp +@item -h +Prints a short summary on the meaning of each program option. Aborts +further program execution. + +@item -v +Prints out the current version number. + +@item -d +Enables the debugging option. This produces verbose diagnostics to +``standard error'' when @code{gperf} is executing. It is useful both for +maintaining the program and for determining whether a given set of +options is actually speeding up the search for a solution. Some useful +information is dumped at the end of the program when the @samp{-d} +option is enabled. +@end table +@end itemize + +@node Bugs, Projects, Verbosity, 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. +@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, 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 Perfect 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 -- cgit v1.1