diff options
Diffstat (limited to 'contrib/gperf/src')
-rw-r--r-- | contrib/gperf/src/Makefile | 77 | ||||
-rw-r--r-- | contrib/gperf/src/boolarray.c | 90 | ||||
-rw-r--r-- | contrib/gperf/src/boolarray.h | 48 | ||||
-rw-r--r-- | contrib/gperf/src/getopt.c | 413 | ||||
-rw-r--r-- | contrib/gperf/src/gperf-to-do | 22 | ||||
-rw-r--r-- | contrib/gperf/src/hashtable.c | 132 | ||||
-rw-r--r-- | contrib/gperf/src/hashtable.h | 37 | ||||
-rw-r--r-- | contrib/gperf/src/iterator.c | 106 | ||||
-rw-r--r-- | contrib/gperf/src/keylist.c | 1033 | ||||
-rw-r--r-- | contrib/gperf/src/keylist.h | 54 | ||||
-rw-r--r-- | contrib/gperf/src/listnode.c | 111 | ||||
-rw-r--r-- | contrib/gperf/src/listnode.h | 43 | ||||
-rw-r--r-- | contrib/gperf/src/main.c | 96 | ||||
-rw-r--r-- | contrib/gperf/src/options.c | 444 | ||||
-rw-r--r-- | contrib/gperf/src/perfect.c | 350 | ||||
-rw-r--r-- | contrib/gperf/src/perfect.h | 45 | ||||
-rw-r--r-- | contrib/gperf/src/prototype.h | 15 | ||||
-rw-r--r-- | contrib/gperf/src/readline.c | 87 | ||||
-rw-r--r-- | contrib/gperf/src/readline.h | 31 | ||||
-rw-r--r-- | contrib/gperf/src/stderr.c | 96 | ||||
-rw-r--r-- | contrib/gperf/src/stderr.h | 29 | ||||
-rw-r--r-- | contrib/gperf/src/version.c | 22 | ||||
-rw-r--r-- | contrib/gperf/src/xmalloc.c | 78 |
23 files changed, 0 insertions, 3459 deletions
diff --git a/contrib/gperf/src/Makefile b/contrib/gperf/src/Makefile deleted file mode 100644 index 05f59a4..0000000 --- a/contrib/gperf/src/Makefile +++ /dev/null @@ -1,77 +0,0 @@ -# Copyright (C) 1989 Free Software Foundation, Inc. -# written by Douglas C. Schmidt (schmidt@ics.uci.edu) -# -# 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, 675 Mass Ave, Cambridge, MA 02139, USA. - -CC = gcc -DFLAGS= -DLO_CAL -DGATHER_STATISTICS #-DRLIMIT_STACK -OFLAGS= -O -p -g -fstrength-reduce -fomit-frame-pointer -fdelayed-branch -finline-functions # gcc options -CFLAGS= $(DFLAGS) $(OFLAGS) -OBJS = options.o iterator.o main.o perfect.o keylist.o listnode.o xmalloc.o \ - hashtable.o boolarray.o readline.o stderr.o version.o getopt.o -SOURCES = options.c iterator.c main.c perfect.c keylist.c listnode.c xmalloc.c \ - hashtable.c boolarray.c readline.c stderr.c version.c getopt.c - -all: gperf - -gperf: $(OBJS) - $(CC) $(CFLAGS) -o $@ $(OBJS) $(LIBS) - -clean: - -rm -f *.o core *~ #*# - -realclean: clean - -rm -f gperf - -# dependencies -# DO NOT DELETE THIS LINE -- mkdep uses it. -# DO NOT PUT ANYTHING AFTER THIS LINE, IT WILL GO AWAY. - -boolarray.o: boolarray.c /usr/include/stdio.h boolarray.h prototype.h options.h -boolarray.o: /usr/include/stdio.h prototype.h -getopt.o: getopt.c /usr/include/stdio.h -hashtable.o: hashtable.c /usr/include/stdio.h hashtable.h keylist.h -hashtable.o: /usr/include/stdio.h listnode.h prototype.h prototype.h options.h -hashtable.o: /usr/include/stdio.h prototype.h -iterator.o: iterator.c /usr/include/stdio.h /usr/include/ctype.h iterator.h -iterator.o: prototype.h -keylist.o: keylist.c /usr/include/assert.h /usr/include/stdio.h options.h -keylist.o: /usr/include/stdio.h prototype.h readline.h prototype.h keylist.h -keylist.o: /usr/include/stdio.h listnode.h prototype.h hashtable.h keylist.h -keylist.o: prototype.h stderr.h prototype.h /usr/include/varargs.h -listnode.o: listnode.c /usr/include/stdio.h options.h /usr/include/stdio.h -listnode.o: prototype.h listnode.h prototype.h stderr.h prototype.h -listnode.o: /usr/include/varargs.h -main.o: main.c /usr/include/stdio.h stderr.h prototype.h /usr/include/varargs.h -main.o: options.h /usr/include/stdio.h prototype.h perfect.h prototype.h -main.o: keylist.h /usr/include/stdio.h listnode.h prototype.h boolarray.h -main.o: prototype.h -options.o: options.c /usr/include/stdio.h /usr/include/assert.h options.h -options.o: /usr/include/stdio.h prototype.h iterator.h prototype.h stderr.h -options.o: prototype.h /usr/include/varargs.h -perfect.o: perfect.c /usr/include/stdio.h /usr/include/assert.h -perfect.o: /usr/include/ctype.h options.h /usr/include/stdio.h prototype.h -perfect.o: perfect.h prototype.h keylist.h /usr/include/stdio.h listnode.h -perfect.o: prototype.h boolarray.h prototype.h stderr.h prototype.h -perfect.o: /usr/include/varargs.h -readline.o: readline.c /usr/include/stdio.h readline.h prototype.h -stderr.o: stderr.c /usr/include/stdio.h stderr.h prototype.h -stderr.o: /usr/include/varargs.h -version.o: version.c -xmalloc.o: xmalloc.c /usr/include/stdio.h - -# IF YOU PUT ANYTHING HERE IT WILL GO AWAY diff --git a/contrib/gperf/src/boolarray.c b/contrib/gperf/src/boolarray.c deleted file mode 100644 index 8906134..0000000 --- a/contrib/gperf/src/boolarray.c +++ /dev/null @@ -1,90 +0,0 @@ -/* Fast lookup table abstraction implemented as a Guilmette Array - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include "boolarray.h" -#include "options.h" - -/* Locally visible BOOL_ARRAY object. */ - -static BOOL_ARRAY bool_array; - -/* Prints out debugging diagnostics. */ - -void -bool_array_destroy () -{ - if (OPTION_ENABLED (option, DEBUG)) - fprintf (stderr, "\ndumping boolean array information\niteration number = %d\nend of array dump\n", - bool_array.iteration_number); - free ((char *) bool_array.storage_array); -} - -void -bool_array_init (size) - int size; -{ - STORAGE_TYPE *xmalloc (); - bool_array.iteration_number = 1; - bool_array.size = size; - bool_array.storage_array = xmalloc (size * sizeof *bool_array.storage_array); - bzero (bool_array.storage_array, size * sizeof *bool_array.storage_array); - if (OPTION_ENABLED (option, DEBUG)) - fprintf (stderr, "\nbool array size = %d, total bytes = %d\n", - bool_array.size, bool_array.size * sizeof *bool_array.storage_array); -} - -bool -lookup (index) - int index; -{ - if (bool_array.storage_array[index] == bool_array.iteration_number) - return 1; - else - { - bool_array.storage_array[index] = bool_array.iteration_number; - return 0; - } -} - -/* Simple enough to reset, eh?! */ - -void -bool_array_reset () -{ - /* If we wrap around it's time to zero things out again! */ - - - if (++bool_array.iteration_number == 0) - { - if (OPTION_ENABLED (option, DEBUG)) - { - fprintf (stderr, "(re-initializing bool_array)..."); - fflush (stderr); - } - bool_array.iteration_number = 1; - bzero (bool_array.storage_array, bool_array.size * sizeof *bool_array.storage_array); - if (OPTION_ENABLED (option, DEBUG)) - { - fprintf (stderr, "done\n"); - fflush (stderr); - } - } -} diff --git a/contrib/gperf/src/boolarray.h b/contrib/gperf/src/boolarray.h deleted file mode 100644 index 4833975..0000000 --- a/contrib/gperf/src/boolarray.h +++ /dev/null @@ -1,48 +0,0 @@ -/* Simple lookup table abstraction implemented as a Guilmette Array. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -/* Define and implement a simple boolean array abstraction, - uses a Guilmette array implementation to save on initialization time. */ - -#ifndef _boolarray_h -#define _boolarray_h -#include "prototype.h" - -#ifdef LO_CAL -/* If we are on a memory diet then we'll only make these use a limited - amount of storage space. */ -typedef unsigned short STORAGE_TYPE; -#else -typedef int STORAGE_TYPE; -#endif -typedef struct bool_array -{ - STORAGE_TYPE *storage_array; /* Initialization of the index space. */ - STORAGE_TYPE iteration_number; /* Keep track of the current iteration. */ - int size; /* Size of the entire array (dynamically initialized). */ -} BOOL_ARRAY; - -extern void bool_array_init P ((int size)); -extern void bool_array_destroy P ((void)); -extern bool lookup P ((int hash_value)); -extern void bool_array_reset P ((void)); - -#endif /* _boolarray_h */ diff --git a/contrib/gperf/src/getopt.c b/contrib/gperf/src/getopt.c deleted file mode 100644 index 4eb3c20..0000000 --- a/contrib/gperf/src/getopt.c +++ /dev/null @@ -1,413 +0,0 @@ -/* Getopt for GNU. - Copyright (C) 1987, 1989 Free Software Foundation, Inc. - - 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ - - - -/* This version of `getopt' appears to the caller like standard Unix `getopt' - but it behaves differently for the user, since it allows the user - to intersperse the options with the other arguments. - - As `getopt' works, it permutes the elements of `argv' so that, - when it is done, all the options precede everything else. Thus - all application programs are extended to handle flexible argument order. - - Setting the environment variable _POSIX_OPTION_ORDER disables permutation. - Then the behavior is completely standard. - - GNU application programs can use a third alternative mode in which - they can distinguish the relative order of options and other arguments. */ - -#include <stdio.h> - -#ifdef sparc -#include <alloca.h> -#endif -#ifdef USG -#define bcopy(s, d, l) memcpy((d), (s), (l)) -#endif - -/* For communication from `getopt' to the caller. - When `getopt' finds an option that takes an argument, - the argument value is returned here. - Also, when `ordering' is RETURN_IN_ORDER, - each non-option ARGV-element is returned here. */ - -char *optarg = 0; - -/* Index in ARGV of the next element to be scanned. - This is used for communication to and from the caller - and for communication between successive calls to `getopt'. - - On entry to `getopt', zero means this is the first call; initialize. - - When `getopt' returns EOF, this is the index of the first of the - non-option elements that the caller should itself scan. - - Otherwise, `optind' communicates from one call to the next - how much of ARGV has been scanned so far. */ - -int optind = 0; - -/* The next char to be scanned in the option-element - in which the last option character we returned was found. - This allows us to pick up the scan where we left off. - - If this is zero, or a null string, it means resume the scan - by advancing to the next ARGV-element. */ - -static char *nextchar; - -/* Callers store zero here to inhibit the error message - for unrecognized options. */ - -int opterr = 1; - -/* Describe how to deal with options that follow non-option ARGV-elements. - - UNSPECIFIED means the caller did not specify anything; - the default is then REQUIRE_ORDER if the environment variable - _OPTIONS_FIRST is defined, PERMUTE otherwise. - - REQUIRE_ORDER means don't recognize them as options. - Stop option processing when the first non-option is seen. - This is what Unix does. - - PERMUTE is the default. We permute the contents of `argv' as we scan, - so that eventually all the options are at the end. This allows options - to be given in any order, even with programs that were not written to - expect this. - - RETURN_IN_ORDER is an option available to programs that were written - to expect options and other ARGV-elements in any order and that care about - the ordering of the two. We describe each non-option ARGV-element - as if it were the argument of an option with character code zero. - Using `-' as the first character of the list of option characters - requests this mode of operation. - - The special argument `--' forces an end of option-scanning regardless - of the value of `ordering'. In the case of RETURN_IN_ORDER, only - `--' can cause `getopt' to return EOF with `optind' != ARGC. */ - -static enum { REQUIRE_ORDER, PERMUTE, RETURN_IN_ORDER } ordering; - -/* Handle permutation of arguments. */ - -/* Describe the part of ARGV that contains non-options that have - been skipped. `first_nonopt' is the index in ARGV of the first of them; - `last_nonopt' is the index after the last of them. */ - -static int first_nonopt; -static int last_nonopt; - -/* Exchange two adjacent subsequences of ARGV. - One subsequence is elements [first_nonopt,last_nonopt) - which contains all the non-options that have been skipped so far. - The other is elements [last_nonopt,optind), which contains all - the options processed since those non-options were skipped. - - `first_nonopt' and `last_nonopt' are relocated so that they describe - the new indices of the non-options in ARGV after they are moved. */ - -static void -exchange (argv) - char **argv; -{ - int nonopts_size - = (last_nonopt - first_nonopt) * sizeof (char *); - char **temp = (char **) alloca (nonopts_size); - - /* Interchange the two blocks of data in argv. */ - - bcopy (&argv[first_nonopt], temp, nonopts_size); - bcopy (&argv[last_nonopt], &argv[first_nonopt], - (optind - last_nonopt) * sizeof (char *)); - bcopy (temp, &argv[first_nonopt + optind - last_nonopt], - nonopts_size); - - /* Update records for the slots the non-options now occupy. */ - - first_nonopt += (optind - last_nonopt); - last_nonopt = optind; -} - -/* Scan elements of ARGV (whose length is ARGC) for option characters - given in OPTSTRING. - - If an element of ARGV starts with '-', and is not exactly "-" or "--", - then it is an option element. The characters of this element - (aside from the initial '-') are option characters. If `getopt' - is called repeatedly, it returns successively each of theoption characters - from each of the option elements. - - If `getopt' finds another option character, it returns that character, - updating `optind' and `nextchar' so that the next call to `getopt' can - resume the scan with the following option character or ARGV-element. - - If there are no more option characters, `getopt' returns `EOF'. - Then `optind' is the index in ARGV of the first ARGV-element - that is not an option. (The ARGV-elements have been permuted - so that those that are not options now come last.) - - OPTSTRING is a string containing the legitimate option characters. - A colon in OPTSTRING means that the previous character is an option - that wants an argument. The argument is taken from the rest of the - current ARGV-element, or from the following ARGV-element, - and returned in `optarg'. - - If an option character is seen that is not listed in OPTSTRING, - return '?' after printing an error message. If you set `opterr' to - zero, the error message is suppressed but we still return '?'. - - If a char in OPTSTRING is followed by a colon, that means it wants an arg, - so the following text in the same ARGV-element, or the text of the following - ARGV-element, is returned in `optarg. Two colons mean an option that - wants an optional arg; if there is text in the current ARGV-element, - it is returned in `optarg'. - - If OPTSTRING starts with `-', it requests a different method of handling the - non-option ARGV-elements. See the comments about RETURN_IN_ORDER, above. */ - -int -getopt (argc, argv, optstring) - int argc; - char **argv; - char *optstring; -{ - /* Initialize the internal data when the first call is made. - Start processing options with ARGV-element 1 (since ARGV-element 0 - is the program name); the sequence of previously skipped - non-option ARGV-elements is empty. */ - - if (optind == 0) - { - first_nonopt = last_nonopt = optind = 1; - - nextchar = 0; - - /* Determine how to handle the ordering of options and nonoptions. */ - - if (optstring[0] == '-') - ordering = RETURN_IN_ORDER; - else if (getenv ("_POSIX_OPTION_ORDER") != 0) - ordering = REQUIRE_ORDER; - else - ordering = PERMUTE; - } - - if (nextchar == 0 || *nextchar == 0) - { - if (ordering == PERMUTE) - { - /* If we have just processed some options following some non-options, - exchange them so that the options come first. */ - - if (first_nonopt != last_nonopt && last_nonopt != optind) - exchange (argv); - else if (last_nonopt != optind) - first_nonopt = optind; - - /* Now skip any additional non-options - and extend the range of non-options previously skipped. */ - - while (optind < argc - && (argv[optind][0] != '-' - || argv[optind][1] == 0)) - optind++; - last_nonopt = optind; - } - - /* Special ARGV-element `--' means premature end of options. - Skip it like a null option, - then exchange with previous non-options as if it were an option, - then skip everything else like a non-option. */ - - if (optind != argc && !strcmp (argv[optind], "--")) - { - optind++; - - if (first_nonopt != last_nonopt && last_nonopt != optind) - exchange (argv); - else if (first_nonopt == last_nonopt) - first_nonopt = optind; - last_nonopt = argc; - - optind = argc; - } - - /* If we have done all the ARGV-elements, stop the scan - and back over any non-options that we skipped and permuted. */ - - if (optind == argc) - { - /* Set the next-arg-index to point at the non-options - that we previously skipped, so the caller will digest them. */ - if (first_nonopt != last_nonopt) - optind = first_nonopt; - return EOF; - } - - /* If we have come to a non-option and did not permute it, - either stop the scan or describe it to the caller and pass it by. */ - - if (argv[optind][0] != '-' || argv[optind][1] == 0) - { - if (ordering == REQUIRE_ORDER) - return EOF; - optarg = argv[optind++]; - return 0; - } - - /* We have found another option-ARGV-element. - Start decoding its characters. */ - - nextchar = argv[optind] + 1; - } - - /* Look at and handle the next option-character. */ - - { - char c = *nextchar++; - char *temp = (char *) index (optstring, c); - - /* Increment `optind' when we start to process its last character. */ - if (*nextchar == 0) - optind++; - - if (temp == 0 || c == ':') - { - if (opterr != 0) - { - if (c < 040 || c >= 0177) - fprintf (stderr, "%s: unrecognized option, character code 0%o\n", - argv[0], c); - else - fprintf (stderr, "%s: unrecognized option `-%c'\n", - argv[0], c); - } - return '?'; - } - if (temp[1] == ':') - { - if (temp[2] == ':') - { - /* This is an option that accepts an argument optionally. */ - if (*nextchar != 0) - { - optarg = nextchar; - optind++; - } - else - optarg = 0; - nextchar = 0; - } - else - { - /* This is an option that requires an argument. */ - if (*nextchar != 0) - { - optarg = nextchar; - /* If we end this ARGV-element by taking the rest as an arg, - we must advance to the next element now. */ - optind++; - } - else if (optind == argc) - { - if (opterr != 0) - fprintf (stderr, "%s: no argument for `-%c' option\n", - argv[0], c); - c = '?'; - } - else - /* We already incremented `optind' once; - increment it again when taking next ARGV-elt as argument. */ - optarg = argv[optind++]; - nextchar = 0; - } - } - return c; - } -} - -#ifdef TEST - -/* Compile with -DTEST to make an executable for use in testing - the above definition of `getopt'. */ - -int -main (argc, argv) - int argc; - char **argv; -{ - char c; - int digit_optind = 0; - - while (1) - { - int this_option_optind = optind; - if ((c = getopt (argc, argv, "abc:d:0123456789")) == EOF) - break; - - switch (c) - { - case '0': - case '1': - case '2': - case '3': - case '4': - case '5': - case '6': - case '7': - case '8': - case '9': - if (digit_optind != 0 && digit_optind != this_option_optind) - printf ("digits occur in two different argv-elements.\n"); - digit_optind = this_option_optind; - printf ("option %c\n", c); - break; - - case 'a': - printf ("option a\n"); - break; - - case 'b': - printf ("option b\n"); - break; - - case 'c': - printf ("option c with value `%s'\n", optarg); - break; - - case '?': - break; - - default: - printf ("?? getopt returned character code 0%o ??\n", c); - } - } - - if (optind < argc) - { - printf ("non-option ARGV-elements: "); - while (optind < argc) - printf ("%s ", argv[optind++]); - printf ("\n"); - } - - return 0; -} - -#endif /* TEST */ diff --git a/contrib/gperf/src/gperf-to-do b/contrib/gperf/src/gperf-to-do deleted file mode 100644 index 05caecc..0000000 --- a/contrib/gperf/src/gperf-to-do +++ /dev/null @@ -1,22 +0,0 @@ -1. provide output diagnostics that explain how many input keys total, - how many after dealing with static links, and finally, after the - algorithm is complete, how many dynamic duplicates do we now - have. -2. fix up GATHER_STATISTICS for all instrumentation. -3. Useful idea: - - a. Generate the wordlist as a contiguous block of keywords, as before. - This wordlist *must* be sorted by hash value. - - b. generate the lookup_array, which are an array of signed {chars,shorts,ints}, - which ever allows full coverage of the wordlist dimensions. If the - value v, where v = lookup_array[hash(str,len)], is >= 0, then we - simply use this result as a direct access into wordlist to snag - the keyword for comparison. - - c. Otherwise, if v is < 0 this is an indication that we'll need to - search through some number of duplicates hash values. Using a - hash linking scheme we'd then index into a duplicate_address - table that would provide the starting index and total length of - the duplicate entries to consider sequentially. - diff --git a/contrib/gperf/src/hashtable.c b/contrib/gperf/src/hashtable.c deleted file mode 100644 index c256add..0000000 --- a/contrib/gperf/src/hashtable.c +++ /dev/null @@ -1,132 +0,0 @@ -/* Hash table for checking keyword links. Implemented using double hashing. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include "hashtable.h" -#include "options.h" - -#ifdef GATHER_STATISTICS -/* Find out how well our double hashing is working! */ -static collisions = 0; -#endif - -/* Locally visible hash table. */ -static HASH_TABLE hash_table; - -/* Basically the algorithm from the Dragon book. */ - -static unsigned -hash_pjw (str) - char *str; -{ - char *temp; - unsigned g, h = 0; - - for (temp = str; *temp; temp++) - { - h = (h << 4) + (*temp * 13); - if (g = h & 0xf0000000) - { - h ^= (g >> 24); - h ^= g; - } - } - - return h; -} - -/* The size of the hash table is always the smallest power of 2 >= the size - indicated by the user. This allows several optimizations, including - the use of double hashing and elimination of the mod instruction. - Note that the size had better be larger than the number of items - in the hash table, else there's trouble!!! Note that the memory - for the hash table is allocated *outside* the intialization routine. - This compromises information hiding somewhat, but greatly reduces - memory fragmentation, since we can now use alloca! */ - -void -hash_table_init (table, s) - LIST_NODE **table; - int s; -{ - hash_table.size = s; - hash_table.table = table; - bzero ((char *) hash_table.table, hash_table.size * sizeof *hash_table.table); -} - -/* Frees the dynamically allocated table. Note that since we don't - really need this space anymore, and since it is potentially quite - big it is best to return it when we are done. */ - -void -hash_table_destroy () -{ - if (OPTION_ENABLED (option, DEBUG)) - { - int i; - - fprintf (stderr, "\ndumping the hash table\ntotal elements = %d, bytes = %d\n", - hash_table.size, hash_table.size * sizeof *hash_table.table); - - for (i = hash_table.size - 1; i >= 0; i--) - if (hash_table.table[i]) - fprintf (stderr, "location[%d] has charset \"%s\" and keyword \"%s\"\n", - i, hash_table.table[i]->char_set, hash_table.table[i]->key); - -#ifdef GATHER_STATISTICS - fprintf (stderr, "\ntotal collisions during hashing = %d\n", collisions); -#endif - fprintf (stderr, "end dumping hash table\n\n"); - } -} - -/* If the ITEM is already in the hash table return the item found - in the table. Otherwise inserts the ITEM, and returns FALSE. - Uses double hashing. */ - -LIST_NODE * -retrieve (item, ignore_length) - LIST_NODE *item; - int ignore_length; -{ - unsigned hash_val = hash_pjw (item->char_set); - int probe = hash_val & hash_table.size - 1; - int increment = (hash_val ^ item->length | 1) & hash_table.size - 1; - - while (hash_table.table[probe] - && (strcmp (hash_table.table[probe]->char_set, item->char_set) - || (!ignore_length && hash_table.table[probe]->length != item->length))) - { -#ifdef GATHER_STATISTICS - collisions++; -#endif - probe = probe + increment & hash_table.size - 1; - } - - if (hash_table.table[probe]) - return hash_table.table[probe]; - else - { - hash_table.table[probe] = item; - return 0; - } -} - - diff --git a/contrib/gperf/src/hashtable.h b/contrib/gperf/src/hashtable.h deleted file mode 100644 index 218e987..0000000 --- a/contrib/gperf/src/hashtable.h +++ /dev/null @@ -1,37 +0,0 @@ -/* Hash table used to check for duplicate keyword entries. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#ifndef _hashtable_h -#define _hashtable_h -#include "keylist.h" -#include "prototype.h" - -typedef struct hash_table -{ - LIST_NODE **table; /* Vector of pointers to linked lists of List_Node's. */ - int size; /* Size of the vector. */ -} HASH_TABLE; - -extern void hash_table_init P ((LIST_NODE **table, int size)); -extern void hash_table_destroy P ((void)); -extern LIST_NODE *retrieve P ((LIST_NODE *item, int ignore_length)); - -#endif /* _hashtable_h */ diff --git a/contrib/gperf/src/iterator.c b/contrib/gperf/src/iterator.c deleted file mode 100644 index b5930f0..0000000 --- a/contrib/gperf/src/iterator.c +++ /dev/null @@ -1,106 +0,0 @@ -/* Provides an Iterator for keyword characters. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include <ctype.h> -#include "iterator.h" - -/* Locally visible ITERATOR object. */ - -ITERATOR iterator; - -/* Constructor for ITERATOR. */ - -void -iterator_init (s, lo, hi, word_end, bad_val, key_end) - char *s; - int lo; - int hi; - int word_end; - int bad_val; - int key_end; -{ - iterator.end = key_end; - iterator.error_value = bad_val; - iterator.end_word = word_end; - iterator.str = s; - iterator.hi_bound = hi; - iterator.lo_bound = lo; -} - -/* Define several useful macros to clarify subsequent code. */ -#define ISPOSDIGIT(X) ((X)<='9'&&(X)>'0') -#define TODIGIT(X) ((X)-'0') - -/* Provide an Iterator, returning the ``next'' value from - the list of valid values given in the constructor. */ - -int -next () -{ -/* Variables to record the Iterator's status when handling ranges, e.g., 3-12. */ - - static int size; - static int curr_value; - static int upper_bound; - - if (size) - { - if (++curr_value >= upper_bound) - size = 0; - return curr_value; - } - else - { - while (*iterator.str) - { - if (*iterator.str == ',') - iterator.str++; - else if (*iterator.str == '$') - { - iterator.str++; - return iterator.end_word; - } - else if (ISPOSDIGIT (*iterator.str)) - { - - for (curr_value = 0; isdigit (*iterator.str); iterator.str++) - curr_value = curr_value * 10 + *iterator.str - '0'; - - if (*iterator.str == '-') - { - - for (size = 1, upper_bound = 0; - isdigit (*++iterator.str); - upper_bound = upper_bound * 10 + *iterator.str - '0'); - - if (upper_bound <= curr_value || upper_bound > iterator.hi_bound) - return iterator.error_value; - } - return curr_value >= iterator.lo_bound && curr_value <= iterator.hi_bound - ? curr_value : iterator.error_value; - } - else - return iterator.error_value; - } - - return iterator.end; - } -} diff --git a/contrib/gperf/src/keylist.c b/contrib/gperf/src/keylist.c deleted file mode 100644 index f92d975..0000000 --- a/contrib/gperf/src/keylist.c +++ /dev/null @@ -1,1033 +0,0 @@ -/* Routines for building, ordering, and printing the keyword list. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <assert.h> -#include <stdio.h> -#include "options.h" -#include "readline.h" -#include "keylist.h" -#include "hashtable.h" -#include "stderr.h" -#ifdef sparc -#include <alloca.h> -#endif - -/* Current release version. */ -extern char *version_string; - -/* See comments in perfect.cc. */ -extern int occurrences[ALPHABET_SIZE]; - -/* Ditto. */ -extern int asso_values[ALPHABET_SIZE]; - -/* Used in function reorder, below. */ -static bool determined[ALPHABET_SIZE]; - -/* Default type for generated code. */ -static char *default_array_type = "char *"; - -/* Generated function ``in_word_set'' default return type. */ -static char *default_return_type = "char *"; - -/* Largest positive integer value. */ -#define MAX_INT ((~(unsigned)0)>>1) - -/* Most negative integer value. */ -#define NEG_MAX_INT ((~(unsigned)0)^((~(unsigned)0)>>1)) - -/* Maximum value an unsigned char can take. */ -#define MAX_UNSIGNED_CHAR 256 - -/* Maximum value an unsigned short can take. */ -#define MAX_UNSIGNED_SHORT 65536 - -/* Make the hash table 5 times larger than the number of keyword entries. */ -#define TABLE_MULTIPLE 5 - -/* Efficiently returns the least power of two greater than or equal to X! */ -#define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X))) - -/* How wide the printed field width must be to contain the maximum hash value. */ -static int field_width = 2; - -/* Globally visible KEY_LIST object. */ - -KEY_LIST key_list; - -/* Gathers the input stream into a buffer until one of two things occur: - - 1. We read a '%' followed by a '%' - 2. We read a '%' followed by a '}' - - The first symbolizes the beginning of the keyword list proper, - The second symbolizes the end of the C source code to be generated - verbatim in the output file. - - I assume that the keys are separated from the optional preceding struct - declaration by a consecutive % followed by either % or } starting in - the first column. The code below uses an expandible buffer to scan off - and return a pointer to all the code (if any) appearing before the delimiter. */ - -static char * -get_special_input (delimiter) - char delimiter; -{ - char *xmalloc (); - int size = 80; - char *buf = xmalloc (size); - int c, i; - - for (i = 0; (c = getchar ()) != EOF; i++) - { - if (c == '%') - { - if ((c = getchar ()) == delimiter) - { - - while ((c = getchar ()) != '\n') - ; /* Discard newline. */ - - if (i == 0) - return ""; - else - { - buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0'; - return buf; - } - } - else - ungetc (c, stdin); - } - else if (i >= size) /* Yikes, time to grow the buffer! */ - { - char *temp = xmalloc (size *= 2); - int j; - - for (j = 0; j < i; j++) - temp[j] = buf[j]; - - free (buf); - buf = temp; - } - buf[i] = c; - } - - return NULL; /* Problem here. */ -} - -/* Stores any C text that must be included verbatim into the - generated code output. */ - -static char * -save_include_src () -{ - int c; - - if ((c = getchar ()) != '%') - { - ungetc (c, stdin); - return ""; - } - else if ((c = getchar ()) != '{') - report_error ("internal error, %c != '{' on line %d in file %s%a", c, __LINE__, __FILE__); - /*NOT REACHED*/ - else - return get_special_input ('}'); -} - -/* strcspn - find length of initial segment of s consisting entirely - of characters not from reject (borrowed from Henry Spencer's - ANSI string package). */ - -static int -strcspn (s, reject) - char *s; - char *reject; -{ - char *scan; - char *rej_scan; - int count = 0; - - for (scan = s; *scan; scan++) - { - - for (rej_scan = reject; *rej_scan;) - if (*scan == *rej_scan++) - return count; - - count++; - } - - return count; -} - -/* Determines from the input file whether the user wants to build a table - from a user-defined struct, or whether the user is content to simply - use the default array of keys. */ - -static char * -get_array_type () -{ - return get_special_input ('%'); -} - -/* Sets up the Return_Type, the Struct_Tag type and the Array_Type - based upon various user Options. */ - -static void -set_output_types () -{ - char *xmalloc (); - - if (OPTION_ENABLED (option, TYPE) && !(key_list.array_type = get_array_type ())) - return; /* Something's wrong, bug we'll catch it later on.... */ - else if (OPTION_ENABLED (option, TYPE)) /* Yow, we've got a user-defined type... */ - { - int struct_tag_length = strcspn (key_list.array_type, "{\n\0"); - - if (OPTION_ENABLED (option, POINTER)) /* And it must return a pointer... */ - { - key_list.return_type = xmalloc (struct_tag_length + 2); - strncpy (key_list.return_type, key_list.array_type, struct_tag_length); - key_list.return_type[struct_tag_length] = '\0'; - strcat (key_list.return_type, "*"); - } - - key_list.struct_tag = (char *) xmalloc (struct_tag_length + 1); - strncpy (key_list.struct_tag, key_list.array_type, struct_tag_length); - key_list.struct_tag[struct_tag_length] = '\0'; - } - else if (OPTION_ENABLED (option, POINTER)) /* Return a char *. */ - key_list.return_type = default_array_type; -} - -/* Reads in all keys from standard input and creates a linked list pointed - to by Head. This list is then quickly checked for ``links,'' i.e., - unhashable elements possessing identical key sets and lengths. */ - -void -read_keys () -{ - char *ptr; - - key_list.include_src = save_include_src (); - set_output_types (); - - /* Oops, problem with the input file. */ - if (! (ptr = read_line ())) - report_error ("No words in input file, did you forget\ - to prepend %s or use -t accidentally?\n%a", "%%"); - - /* Read in all the keywords from the input file. */ - else - { - LIST_NODE *temp, *trail; - char *delimiter = GET_DELIMITER (option); - - for (temp = key_list.head = make_list_node (ptr, strcspn (ptr, delimiter)); - (ptr = read_line ()) && strcmp (ptr, "%%"); - key_list.total_keys++, temp = temp->next) - temp->next = make_list_node (ptr, strcspn (ptr, delimiter)); - - /* See if any additional C code is included at end of this file. */ - if (ptr) - key_list.additional_code = TRUE; - { - /* If this becomes TRUE we've got a link. */ - bool link = FALSE; - - /* Make large hash table for efficiency. */ - int table_size = (key_list.list_len = key_list.total_keys) * TABLE_MULTIPLE; - - /* By allocating the memory here we save on dynamic allocation overhead. - Table must be a power of 2 for the hash function scheme to work. */ - LIST_NODE **table = (LIST_NODE **) alloca (POW (table_size) * sizeof (LIST_NODE *)); - - hash_table_init (table, table_size); - - /* Test whether there are any links and also set the maximum length of - an identifier in the keyword list. */ - - for (temp = key_list.head, trail = NULL; temp; temp = temp->next) - { - LIST_NODE *ptr = retrieve (temp, OPTION_ENABLED (option, NOLENGTH)); - - /* Check for links. We deal with these by building an equivalence class - of all duplicate values (i.e., links) so that only 1 keyword is - representative of the entire collection. This *greatly* simplifies - processing during later stages of the program. */ - - if (ptr) - { - key_list.list_len--; - trail->next = temp->next; - temp->link = ptr->link; - ptr->link = temp; - link = TRUE; - - /* Complain if user hasn't enabled the duplicate option. */ - if (!OPTION_ENABLED (option, DUP)) - fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n", - temp->key, ptr->key, temp->char_set); - else if (OPTION_ENABLED (option, DEBUG)) - fprintf (stderr, "Key link: \"%s\" = \"%s\", with key set \"%s\".\n", - temp->key, ptr->key, temp->char_set); - } - else - trail = temp; - - /* Update minimum and maximum keyword length, if needed. */ - if (temp->length > key_list.max_key_len) - key_list.max_key_len = temp->length; - if (temp->length < key_list.min_key_len) - key_list.min_key_len = temp->length; - } - - /* Free up the dynamic memory used in the hash table. */ - hash_table_destroy (); - - /* Exit program if links exists and option[DUP] not set, since we can't continue safely. */ - if (link) - report_error (OPTION_ENABLED (option, DUP) - ? "Some input keys have identical hash values, examine output carefully...\n" - : "Some input keys have identical hash values,\ntry different key positions or use option -D.\n%a"); - } - if (OPTION_ENABLED (option, ALLCHARS)) - SET_CHARSET_SIZE (option, key_list.max_key_len); - } -} - -/* Recursively merges two sorted lists together to form one sorted list. The - ordering criteria is by frequency of occurrence of elements in the key set - or by the hash value. This is a kludge, but permits nice sharing of - almost identical code without incurring the overhead of a function - call comparison. */ - -static LIST_NODE * -merge (list1, list2) - LIST_NODE *list1; - LIST_NODE *list2; -{ - if (!list1) - return list2; - else if (!list2) - return list1; - else if (key_list.occurrence_sort && list1->occurrence < list2->occurrence - || key_list.hash_sort && list1->hash_value > list2->hash_value) - { - list2->next = merge (list2->next, list1); - return list2; - } - else - { - list1->next = merge (list1->next, list2); - return list1; - } -} - -/* Applies the merge sort algorithm to recursively sort the key list by - frequency of occurrence of elements in the key set. */ - -static LIST_NODE * -merge_sort (head) - LIST_NODE *head; -{ - if (!head || !head->next) - return head; - else - { - LIST_NODE *middle = head; - LIST_NODE *temp = head->next->next; - - while (temp) - { - temp = temp->next; - middle = middle->next; - if (temp) - temp = temp->next; - } - - temp = middle->next; - middle->next = NULL; - return merge (merge_sort (head), merge_sort (temp)); - } -} - -/* Returns the frequency of occurrence of elements in the key set. */ - -static int -get_occurrence (ptr) - LIST_NODE *ptr; -{ - int value = 0; - char *temp; - - for (temp = ptr->char_set; *temp; temp++) - value += occurrences[*temp]; - - return value; -} - -/* Enables the index location of all key set elements that are now - determined. */ - -static void -set_determined (ptr) - LIST_NODE *ptr; -{ - char *temp; - - for (temp = ptr->char_set; *temp; temp++) - determined[*temp] = TRUE; - -} - -/* Returns TRUE if PTR's key set is already completely determined. */ - -static bool -already_determined (ptr) - LIST_NODE *ptr; -{ - bool is_determined = TRUE; - char *temp; - - for (temp = ptr->char_set; is_determined && *temp; temp++) - is_determined = determined[*temp]; - - return is_determined; -} - -/* Reorders the table by first sorting the list so that frequently occuring - keys appear first, and then the list is reorded so that keys whose values - are already determined will be placed towards the front of the list. This - helps prune the search time by handling inevitable collisions early in the - search process. See Cichelli's paper from Jan 1980 JACM for details.... */ - -void -reorder () -{ - LIST_NODE *ptr; - - for (ptr = key_list.head; ptr; ptr = ptr->next) - ptr->occurrence = get_occurrence (ptr); - - key_list.hash_sort = FALSE; - key_list.occurrence_sort = TRUE; - - for (ptr = key_list.head = merge_sort (key_list.head); ptr->next; ptr = ptr->next) - { - set_determined (ptr); - - if (already_determined (ptr->next)) - continue; - else - { - LIST_NODE *trail_ptr = ptr->next; - LIST_NODE *run_ptr = trail_ptr->next; - - for (; run_ptr; run_ptr = trail_ptr->next) - { - - if (already_determined (run_ptr)) - { - trail_ptr->next = run_ptr->next; - run_ptr->next = ptr->next; - ptr = ptr->next = run_ptr; - } - else - trail_ptr = run_ptr; - } - } - } -} - -/* Determines the maximum and minimum hash values. One notable feature is - Ira Pohl's optimal algorithm to calculate both the maximum and minimum - items in a list in O(3n/2) time (faster than the O (2n) method). - Returns the maximum hash value encountered. */ - -static int -print_min_max () -{ - int min_hash_value; - int max_hash_value; - LIST_NODE *temp; - - if (ODD (key_list.list_len)) /* Pre-process first item, list now has an even length. */ - { - min_hash_value = max_hash_value = key_list.head->hash_value; - temp = key_list.head->next; - } - else /* List is already even length, no extra work necessary. */ - { - min_hash_value = MAX_INT; - max_hash_value = NEG_MAX_INT; - temp = key_list.head; - } - - for ( ; temp; temp = temp->next) /* Find max and min in optimal o(3n/2) time. */ - { - static int i; - int key_2, key_1 = temp->hash_value; - temp = temp->next; - key_2 = temp->hash_value; - i++; - - if (key_1 < key_2) - { - if (key_1 < min_hash_value) - min_hash_value = key_1; - if (key_2 > max_hash_value) - max_hash_value = key_2; - } - else - { - if (key_2 < min_hash_value) - min_hash_value = key_2; - if (key_1 > max_hash_value) - max_hash_value = key_1; - } - } - - printf ("\n#define MIN_WORD_LENGTH %d\n#define MAX_WORD_LENGTH %d\ -\n#define MIN_HASH_VALUE %d\n#define MAX_HASH_VALUE %d\ -\n/*\n%5d keywords\n%5d is the maximum key range\n*/\n\n", - key_list.min_key_len == MAX_INT ? key_list.max_key_len : key_list.min_key_len, - key_list.max_key_len, min_hash_value, max_hash_value, - key_list.total_keys, (max_hash_value - min_hash_value + 1)); - return max_hash_value; -} - -/* Generates the output using a C switch. This trades increased search - time for decreased table space (potentially *much* less space for - sparse tables). It the user has specified their own struct in the - keyword file *and* they enable the POINTER option we have extra work to - do. The solution here is to maintain a local static array of user - defined struct's, as with the Print_Lookup_Function. Then we use for - switch statements to perform a strcmp or strncmp, returning 0 if the str - fails to match, and otherwise returning a pointer to appropriate index - location in the local static array. */ - -static void -print_switch () -{ - char *comp_buffer; - LIST_NODE *curr = key_list.head; - int pointer_and_type_enabled = OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE); - int total_switches = GET_TOTAL_SWITCHES (option); - int switch_size = keyword_list_length () / total_switches; - - if (pointer_and_type_enabled) - { - comp_buffer = (char *) alloca (strlen ("*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)") - + 2 * strlen (GET_KEY_NAME (option)) + 1); - sprintf (comp_buffer, OPTION_ENABLED (option, COMP) - ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)" - : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)", - GET_KEY_NAME (option), GET_KEY_NAME (option)); - } - else - comp_buffer = OPTION_ENABLED (option, COMP) - ? "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)" - : "*str == *resword && !strcmp (str + 1, resword + 1)"; - - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n\ - register int key = %s (str, len);\n\n\ - if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n {\n", GET_HASH_NAME (option)); - - /* Properly deal with user's who request multiple switch statements. */ - - while (curr) - { - LIST_NODE *temp = curr; - int lowest_case_value = curr->hash_value; - int number_of_cases = 0; - - /* Figure out a good cut point to end this switch. */ - - for (; temp && ++number_of_cases < switch_size; temp = temp->next) - if (temp->next && temp->hash_value == temp->next->hash_value) - while (temp->next && temp->hash_value == temp->next->hash_value) - temp = temp->next; - - if (temp) - printf (" if (key <= %d)\n {\n", temp->hash_value); - else - printf (" {\n"); - - /* Output each keyword as part of a switch statement indexed by hash value. */ - - if (OPTION_ENABLED (option, POINTER) || OPTION_ENABLED (option, DUP)) - { - int i = 0; - - printf (" %s%s *resword; %s\n\n", - OPTION_ENABLED (option, CONST) ? "const " : "", - pointer_and_type_enabled ? key_list.struct_tag : "char", - OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP) ? "int key_len;" : ""); - printf (" switch (key - %d)\n {\n", lowest_case_value); - - for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next) - { - printf (" case %*d:", field_width, temp->hash_value - lowest_case_value); - if (OPTION_ENABLED (option, DEBUG)) - printf (" /* hash value = %4d, keyword = \"%s\" */", temp->hash_value, temp->key); - putchar ('\n'); - - /* Handle `natural links,' i.e., those that occur statically. */ - - if (temp->link) - { - LIST_NODE *links; - - for (links = temp; links; links = links->link) - { - if (pointer_and_type_enabled) - printf (" resword = &wordlist[%d];\n", links->index); - else - printf (" resword = \"%s\";\n", links->key); - printf (" if (%s) return resword;\n", comp_buffer); - } - } - /* Handle unresolved duplicate hash values. These are guaranteed - to be adjacent since we sorted the keyword list by increasing - hash values. */ - if (temp->next && temp->hash_value == temp->next->hash_value) - { - - for ( ; temp->next && temp->hash_value == temp->next->hash_value; - temp = temp->next) - { - if (pointer_and_type_enabled) - printf (" resword = &wordlist[%d];\n", temp->index); - else - printf (" resword = \"%s\";\n", temp->key); - printf (" if (%s) return resword;\n", comp_buffer); - } - if (pointer_and_type_enabled) - printf (" resword = &wordlist[%d];\n", temp->index); - else - printf (" resword = \"%s\";\n", temp->key); - printf (" return %s ? resword : 0;\n", comp_buffer); - } - else if (temp->link) - printf (" return 0;\n"); - else - { - if (pointer_and_type_enabled) - printf (" resword = &wordlist[%d];", temp->index); - else - printf (" resword = \"%s\";", temp->key); - if (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP)) - printf (" key_len = %d;", temp->length); - printf (" break;\n"); - } - } - printf (" default: return 0;\n }\n"); - printf (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP) - ? " if (len == key_len && %s)\n return resword;\n" - : " if (%s)\n return resword;\n", comp_buffer); - printf (" return 0;\n }\n"); - curr = temp; - } - else /* Nothing special required here. */ - { - int i = 0; - printf (" char *s;\n\n switch (key - %d)\n {\n", - lowest_case_value); - - for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next) - if (OPTION_ENABLED (option, LENTABLE)) - printf (" case %*d: if (len == %d) s = \"%s\"; else return 0; break;\n", - field_width, temp->hash_value - lowest_case_value, - temp->length, temp->key); - else - printf (" case %*d: s = \"%s\"; break;\n", - field_width, temp->hash_value - lowest_case_value, temp->key); - - printf (" default: return 0;\n }\n "); - printf ("return *s == *str && !%s;\n }\n", - OPTION_ENABLED (option, COMP) - ? "strncmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)"); - curr = temp; - } - } - printf (" }\n }\n return 0;\n}\n"); -} - -/* Prints out a table of keyword lengths, for use with the - comparison code in generated function ``in_word_set.'' */ - -static void -print_keylength_table () -{ - int max_column = 15; - int index = 0; - int column = 0; - char *indent = OPTION_ENABLED (option, GLOBAL) ? "" : " "; - LIST_NODE *temp; - - if (!OPTION_ENABLED (option, DUP) && !OPTION_ENABLED (option, SWITCH)) - { - printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n ", - indent, OPTION_ENABLED (option, CONST) ? "const " : "", - key_list.max_key_len < MAX_UNSIGNED_CHAR ? "char" : - (key_list.max_key_len < MAX_UNSIGNED_SHORT ? "short" : "long"), - indent, indent); - - for (temp = key_list.head; temp; temp = temp->next, index++) - { - - if (index < temp->hash_value) - { - - for ( ; index < temp->hash_value; index++) - printf ("%3d%s", 0, ++column % (max_column - 1) ? "," : ",\n "); - } - - printf ("%3d%s", temp->length, ++column % (max_column - 1 ) ? "," : ",\n "); - } - - printf ("\n%s%s};\n\n", indent, indent); - } -} - -/* Prints out the array containing the key words for the Perfect - hash function. */ - -static void -print_keyword_table () -{ - char *l_brace = *key_list.head->rest ? "{" : ""; - char *r_brace = *key_list.head->rest ? "}," : ""; - int doing_switch = OPTION_ENABLED (option, SWITCH); - char *indent = OPTION_ENABLED (option, GLOBAL) ? "" : " "; - int index = 0; - LIST_NODE *temp; - - printf ("\n%sstatic %s%s wordlist[] =\n%s%s{\n", - indent, OPTION_ENABLED (option, CONST) ? "const " : "", - key_list.struct_tag, indent, indent); - - /* Generate an array of reserved words at appropriate locations. */ - - for (temp = key_list.head; temp; temp = temp->next, index++) - { - temp->index = index; - - if (!doing_switch && index < temp->hash_value) - { - int column; - - printf (" "); - - for (column = 1; index < temp->hash_value; index++, column++) - printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n "); - - if (column % 10) - printf ("\n"); - else - { - printf ("%s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace); - continue; - } - } - - printf (" %s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace); - - /* Deal with links specially. */ - if (temp->link) - { - LIST_NODE *links; - - for (links = temp->link; links; links = links->link) - { - links->index = ++index; - printf (" %s\"%s\", %s%s\n", l_brace, links->key, links->rest, r_brace); - } - } - - } - - printf ("%s%s};\n\n", indent, indent); -} - -/* Generates C code for the hash function that returns the - proper encoding for each key word. */ - -static void -print_hash_function (max_hash_value) - int max_hash_value; -{ - int max_column = 10; - int count = max_hash_value; - - /* Calculate maximum number of digits required for MAX_HASH_VALUE. */ - - while ((count /= 10) > 0) - field_width++; - - if (OPTION_ENABLED (option, GNU)) - printf ("#ifdef __GNUC__\ninline\n#endif\n"); - - printf (OPTION_ENABLED (option, ANSI) - ? "static int\n%s (register const char *str, register int len)\n{\n static %sunsigned %s hash_table[] =\n {" - : "static int\n%s (str, len)\n register char *str;\n register unsigned int len;\n{\n static %sunsigned %s hash_table[] =\n {", - GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "", - max_hash_value < MAX_UNSIGNED_CHAR - ? "char" : (max_hash_value < MAX_UNSIGNED_SHORT ? "short" : "int")); - - for (count = 0; count < ALPHABET_SIZE; ++count) - { - if (!(count % max_column)) - printf ("\n "); - - printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value); - } - - /* Optimize special case of ``-k 1,$'' */ - if (OPTION_ENABLED (option, DEFAULTCHARS)) - printf ("\n };\n return %s + hash_table[str[len - 1]] + hash_table[str[0]];\n}\n\n", - OPTION_ENABLED (option, NOLENGTH) ? "0" : "len"); - else - { - int key_pos; - - RESET (option); - - /* Get first (also highest) key position. */ - key_pos = GET (option); - - /* We can perform additional optimizations here. */ - if (!OPTION_ENABLED (option, ALLCHARS) && key_pos <= key_list.min_key_len) - { - printf ("\n };\n return %s", OPTION_ENABLED (option, NOLENGTH) ? "0" : "len"); - - for ( ; key_pos != EOS && key_pos != WORD_END; key_pos = GET (option)) - printf (" + hash_table[str[%d]]", key_pos - 1); - - printf ("%s;\n}\n\n", key_pos == WORD_END ? " + hash_table[str[len - 1]]" : ""); - } - - /* We've got to use the correct, but brute force, technique. */ - else - { - printf ("\n };\n register int hval = %s;\n\n switch (%s)\n {\n default:\n", - OPTION_ENABLED (option, NOLENGTH) - ? "0" : "len", OPTION_ENABLED (option, NOLENGTH) ? "len" : "hval"); - - /* User wants *all* characters considered in hash. */ - if (OPTION_ENABLED (option, ALLCHARS)) - { - int i; - - for (i = key_list.max_key_len; i > 0; i--) - printf (" case %d:\n hval += hash_table[str[%d]];\n", i, i - 1); - - printf (" }\n return hval;\n}\n\n"); - } - else /* do the hard part... */ - { - count = key_pos + 1; - - do - { - - while (--count > key_pos) - printf (" case %d:\n", count); - - printf (" case %d:\n hval += hash_table[str[%d]];\n", - key_pos, key_pos - 1); - } - while ((key_pos = GET (option)) != EOS && key_pos != WORD_END); - - printf (" }\n return hval%s ;\n}\n\n", key_pos == WORD_END - ? " + hash_table[str[len - 1]]" : ""); - } - } - } -} - -/* Generates C code to perform the keyword lookup. */ - -static void -print_lookup_function () -{ - printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n {\n\ - register int key = %s (str, len);\n\n\ - if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n {\n\ - register %schar *s = wordlist[key]", - GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : ""); - if (key_list.array_type != default_array_type) - printf (".%s", GET_KEY_NAME (option)); - - printf (";\n\n if (%s*s == *str && !%s)\n return %s", - OPTION_ENABLED (option, LENTABLE) ? "len == lengthtable[key]\n && " : "", - OPTION_ENABLED (option, COMP) ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)", - OPTION_ENABLED (option, TYPE) && OPTION_ENABLED (option, POINTER) ? "&wordlist[key]" : "s"); - printf (";\n }\n }\n return 0;\n}\n"); -} - -/* Generates the hash function and the key word recognizer function - based upon the user's Options. */ - -void -print_output () -{ - int global_table = OPTION_ENABLED (option, GLOBAL); - - printf ("%s\n", key_list.include_src); - - /* Potentially output type declaration now, reference it later on.... */ - if (OPTION_ENABLED (option, TYPE) && !OPTION_ENABLED (option, NOTYPE)) - printf ("%s;\n", key_list.array_type); - - print_hash_function (print_min_max ()); - - if (global_table) - if (OPTION_ENABLED (option, SWITCH)) - { - if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP)) - print_keylength_table (); - if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE)) - print_keyword_table (); - } - else - { - if (OPTION_ENABLED (option, LENTABLE)) - print_keylength_table (); - print_keyword_table (); - } - /* Use the inline keyword to remove function overhead. */ - if (OPTION_ENABLED (option, GNU)) - printf ("#ifdef __GNUC__\ninline\n#endif\n"); - - /* Use ANSI function prototypes. */ - printf (OPTION_ENABLED (option, ANSI) - ? "%s%s\n%s (register const char *str, register int len)\n{\n" - : "%s%s\n%s (str, len)\n register char *str;\n register unsigned int len;\n{\n", - OPTION_ENABLED (option, CONST) ? "const " : "", - key_list.return_type, GET_FUNCTION_NAME (option)); - - /* Use the switch in place of lookup table. */ - if (OPTION_ENABLED (option, SWITCH)) - { - if (!global_table) - { - if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP)) - print_keylength_table (); - if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE)) - print_keyword_table (); - } - print_switch (); - } - else /* Use the lookup table, in place of switch. */ - { - if (!global_table) - { - if (OPTION_ENABLED (option, LENTABLE)) - print_keylength_table (); - print_keyword_table (); - } - print_lookup_function (); - } - - if (key_list.additional_code) - { - int c; - - while ((c = getchar ()) != EOF) - putchar (c); - } - fflush (stdout); -} - -/* Sorts the keys by hash value. */ - -void -sort () -{ - key_list.hash_sort = TRUE; - key_list.occurrence_sort = FALSE; - - key_list.head = merge_sort (key_list.head); -} - -/* Dumps the key list to stderr stream. */ - -static void -dump () -{ - LIST_NODE *ptr; - - fprintf (stderr, "\nList contents are:\n(hash value, key length, index, key set, key):\n"); - - for (ptr = key_list.head; ptr; ptr = ptr->next) - fprintf (stderr, "%7d,%7d,%6d, %s, %s\n", - ptr->hash_value, ptr->length, ptr->index, - ptr->char_set, ptr->key); -} - -/* Simple-minded constructor action here... */ - -void -key_list_init () -{ - key_list.total_keys = 1; - key_list.max_key_len = NEG_MAX_INT; - key_list.min_key_len = MAX_INT; - key_list.return_type = default_return_type; - key_list.array_type = key_list.struct_tag = default_array_type; - key_list.head = NULL; - key_list.additional_code = FALSE; -} - -/* Returns the length of entire key list. */ - -int -keyword_list_length () -{ - return key_list.list_len; -} - -/* Returns length of longest key read. */ - -int -max_key_length () -{ - return key_list.max_key_len; -} - -/* DESTRUCTOR dumps diagnostics during debugging. */ - -void -key_list_destroy () -{ - if (OPTION_ENABLED (option, DEBUG)) - { - fprintf (stderr, "\nDumping key list information:\ntotal unique keywords = %d\ -\ntotal keywords = %d\nmaximum key length = %d.\n", - key_list.list_len, key_list.total_keys, key_list.max_key_len); - dump (); - fprintf (stderr, "End dumping list.\n\n"); - } -} - diff --git a/contrib/gperf/src/keylist.h b/contrib/gperf/src/keylist.h deleted file mode 100644 index 38143b7..0000000 --- a/contrib/gperf/src/keylist.h +++ /dev/null @@ -1,54 +0,0 @@ -/* Data and function member declarations for the keyword list class. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -/* The key word list is a useful abstraction that keeps track of - various pieces of information that enable that fast generation - of the Perfect.hash function. A Key_List is a singly-linked - list of List_Nodes. */ - -#ifndef _keylist_h -#define _keylist_h -#include <stdio.h> -#include "listnode.h" - -typedef struct key_list -{ - LIST_NODE *head; /* Points to the head of the linked list. */ - char *array_type; /* Pointer to the type for word list. */ - char *return_type; /* Pointer to return type for lookup function. */ - char *struct_tag; /* Shorthand for user-defined struct tag type. */ - char *include_src; /* C source code to be included verbatim. */ - int list_len; /* Length of head's Key_List, not counting duplicates. */ - int total_keys; /* Total number of keys, counting duplicates. */ - int max_key_len; /* Maximum length of the longest keyword. */ - int min_key_len; /* Minimum length of the shortest keyword. */ - bool occurrence_sort; /* True if sorting by occurrence. */ - bool hash_sort; /* True if sorting by hash value. */ - bool additional_code; /* True if any additional C code is included. */ -} KEY_LIST; - -extern void key_list_init P ((void)); -extern void key_list_destroy P ((void)); -extern void print_output P ((void)); -extern int keyword_list_length P ((void)); -extern int max_key_length P ((void)); -extern KEY_LIST key_list; -#endif /* _keylist_h */ diff --git a/contrib/gperf/src/listnode.c b/contrib/gperf/src/listnode.c deleted file mode 100644 index 2eec1a6..0000000 --- a/contrib/gperf/src/listnode.c +++ /dev/null @@ -1,111 +0,0 @@ -/* Creates and initializes a new list node. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include "options.h" -#include "listnode.h" -#include "stderr.h" - -/* See comments in perfect.cc. */ -extern int occurrences[ALPHABET_SIZE]; - -/* Sorts the key set alphabetically to speed up subsequent operations. - Uses insertion sort since the set is probably quite small. */ - -static void -set_sort (base, len) - char *base; - int len; -{ - int i, j; - - for (i = 0, j = len - 1; i < j; i++) - { - char curr, tmp; - - for (curr = i + 1, tmp = base[curr]; curr > 0 && tmp < base[curr-1]; curr--) - base[curr] = base[curr - 1]; - - base[curr] = tmp; - - } -} - -/* Initializes a List_Node. This requires obtaining memory for the KEY_SET - initializing them using the information stored in the - KEY_POSITIONS array in Options, and checking for simple errors. - It's important to note that KEY and REST are both pointers to - the different offsets into the same block of dynamic memory pointed to - by parameter K. The data member REST is used to store any additional fields - of the input file (it is set to the "" string if Option[TYPE] is not enabled). - This is useful if the user wishes to incorporate a lookup structure, - rather than just an array of keys. */ - -LIST_NODE * -make_list_node (k, len) - char *k; - int len; -{ - LIST_NODE *buffered_malloc (); - int char_set_size = OPTION_ENABLED (option, ALLCHARS) ? len : GET_CHARSET_SIZE (option) + 1; - LIST_NODE *temp = buffered_malloc (sizeof (LIST_NODE) + char_set_size); - char *ptr = temp->char_set; - - k[len] = '\0'; /* Null terminate KEY to separate it from REST. */ - temp->key = k; - temp->next = 0; - temp->index = 0; - temp->length = len; - temp->link = 0; - temp->rest = OPTION_ENABLED (option, TYPE) ? k + len + 1 : ""; - - if (OPTION_ENABLED (option, ALLCHARS)) /* Use all the character position in the KEY. */ - - for (; *k; k++, ptr++) - ++occurrences[*ptr = *k]; - - else /* Only use those character positions specified by the user. */ - { - int i; - - /* Iterate thru the list of key_positions, initializing occurrences table - and temp->char_set (via char * pointer ptr). */ - - for(RESET (option); (i = GET (option)) != EOS; ) - { - if (i == WORD_END) /* Special notation for last KEY position, i.e. '$'. */ - *ptr = temp->key[len - 1]; - else if (i <= len) /* Within range of KEY length, so we'll keep it. */ - *ptr = temp->key[i - 1]; - else /* Out of range of KEY length, so we'll just skip it. */ - continue; - ++occurrences[*ptr++]; - } - - if (ptr == temp->char_set) /* Didn't get any hits, i.e., no usable positions. */ - report_error ("can't hash keyword %s with chosen key positions\n%a", temp->key); - } - - *ptr = '\0'; /* Terminate this bastard.... */ - /* Sort the KEY_SET items alphabetically. */ - set_sort (temp->char_set, ptr - temp->char_set); - - return temp; -} diff --git a/contrib/gperf/src/listnode.h b/contrib/gperf/src/listnode.h deleted file mode 100644 index 3e64709..0000000 --- a/contrib/gperf/src/listnode.h +++ /dev/null @@ -1,43 +0,0 @@ -/* Data and function members for defining values and operations of a list node. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#ifndef _listnode_h -#define _listnode_h -#include "prototype.h" - -#define ALPHABET_SIZE 128 - -typedef struct list_node -{ - struct list_node *link; /* TRUE if key has an identical KEY_SET as another key. */ - struct list_node *next; /* Points to next element on the list. */ - int length; /* Length of the key. */ - int hash_value; /* Hash value for the key. */ - int occurrence; /* A metric for frequency of key set occurrences. */ - int index; /* Position of this node relative to other nodes. */ - char *key; /* Key string. */ - char *rest; /* Additional information for building hash function. */ - char char_set[1]; /* Set of characters to hash, specified by user. */ -} LIST_NODE; - -extern LIST_NODE *make_list_node P ((char *k, int len)); - -#endif _listnode_h diff --git a/contrib/gperf/src/main.c b/contrib/gperf/src/main.c deleted file mode 100644 index a54c1df..0000000 --- a/contrib/gperf/src/main.c +++ /dev/null @@ -1,96 +0,0 @@ -/* Driver program for the Perfect hash function generator. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -/* Simple driver program for the Perfect.hash function generator. - Most of the hard work is done in class Perfect and its class methods. */ - -#include <stdio.h> -#include <sys/types.h> -#include <time.h> -#include "stderr.h" -#include "options.h" -#include "perfect.h" - -/* Calls the appropriate intialization routines for each - ADT. Note that certain initialization routines require - initialization *after* certain values are computed. Therefore, - they cannot be called here. */ - -static void -init_all (argc, argv) - int argc; - char *argv[]; -{ -#ifdef RLIMIT_STACK - /* Get rid of any avoidable limit on stack size. */ - { - struct rlimit rlim; - - /* Set the stack limit huge so that alloca does not fail. */ - getrlimit (RLIMIT_STACK, &rlim); - rlim.rlim_cur = rlim.rlim_max; - setrlimit (RLIMIT_STACK, &rlim); - } -#endif /* RLIMIT_STACK */ - - options_init (argc, argv); - key_list_init (); - perfect_init (); -} - -/* Calls appropriate destruction routines for each ADT. These - routines print diagnostics if the debugging option is enabled. */ - -static void -destroy_all () -{ - options_destroy (); - key_list_destroy (); - perfect_destroy (); -} - -/* Driver for perfect hash function generation. */ - -int -main (argc, argv) - int argc; - char *argv[]; -{ - struct tm *tm; - time_t clock; - int status; - - time (&clock); - tm = localtime (&clock); - - fprintf (stderr, "/* starting time is %d:%d:%d */\n", tm->tm_hour, tm->tm_min, tm->tm_sec); - /* Sets the options. */ - init_all (argc, argv); - - /* Generates the perfect hash table. - Also prints generated code neatly to the output. */ - status = perfect_generate (); - destroy_all (); - - time (&clock); - tm = localtime (&clock); - fprintf (stderr, "/* ending time is %d:%d:%d */\n", tm->tm_hour, tm->tm_min, tm->tm_sec); - return status; -} diff --git a/contrib/gperf/src/options.c b/contrib/gperf/src/options.c deleted file mode 100644 index 40fdf0a..0000000 --- a/contrib/gperf/src/options.c +++ /dev/null @@ -1,444 +0,0 @@ -/* Handles parsing the Options provided to the user. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include <assert.h> -#include "options.h" -#include "iterator.h" -#include "stderr.h" - -/* Current program version. */ -extern char *version_string; - -/* Size to jump on a collision. */ -#define DEFAULT_JUMP_VALUE 5 - -/* Default name for generated lookup function. */ -#define DEFAULT_NAME "in_word_set" - -/* Default name for the key component. */ -#define DEFAULT_KEY "name" - -/* Default name for generated hash function. */ -#define DEFAULT_HASH_NAME "hash" - -/* Globally visible OPTIONS object. */ -OPTIONS option; - -/* Default delimiters that separate keywords from their attributes. */ -#define DEFAULT_DELIMITERS ",\n" - -/* Prints program usage to standard error stream. */ - -void -usage () -{ - report_error ("usage: %n [-acCdDef[num]gGhH<hashname>i<init>jk<keys>\ -K<keyname>lnN<name>oprs<size>S<switches>tTv].\n(type %n -h for help)\n"); -} - -/* Sorts the key positions *IN REVERSE ORDER!!* - This makes further routines more efficient. Especially when generating code. - Uses a simple Insertion Sort since the set is probably ordered. - Returns 1 if there are no duplicates, 0 otherwise. */ - -static int -key_sort (base, len) - char *base; - int len; -{ - int i, j; - - for (i = 0, j = len - 1; i < j; i++) - { - int curr, tmp; - - for (curr = i + 1,tmp = base[curr]; curr > 0 && tmp >= base[curr - 1]; curr--) - if ((base[curr] = base[curr - 1]) == tmp) /* oh no, a duplicate!!! */ - return 0; - - base[curr] = tmp; - } - - return 1; -} - -/* Dumps option status when debug is set. */ - -void -options_destroy () -{ - if (OPTION_ENABLED (option, DEBUG)) - { - char *ptr; - - fprintf (stderr, "\ndumping Options:\nDEBUG is.......: %s\nORDER is.......: %s\ -\nANSI is........: %s\nTYPE is........: %s\nGNU is.........: %s\nRANDOM is......: %s\ -\nDEFAULTCHARS is: %s\nSWITCH is......: %s\nPOINTER is.....: %s\nNOLENGTH is....: %s\ -\nLENTABLE is....: %s\nDUP is.........: %s\nCOMP is........: %s\nFAST is........: %s\ -\nNOTYPE is......: %s\nGLOBAL is......: %s\nCONST is.......: %s\niterations = %d\ -\nlookup function name = %s\nhash function name = %s\nkey name = %s\ -\njump value = %d\nmax associcated value = %d\ninitial associated value = %d\ -\ndelimiters = %s\nnumber of switch statements = %d\napproximate switch statement size = %d\n", - OPTION_ENABLED (option, DEBUG) ? "enabled" : "disabled", - OPTION_ENABLED (option, ORDER) ? "enabled" : "disabled", - OPTION_ENABLED (option, ANSI) ? "enabled" : "disabled", - OPTION_ENABLED (option, TYPE) ? "enabled" : "disabled", - OPTION_ENABLED (option, GNU) ? "enabled" : "disabled", - OPTION_ENABLED (option, RANDOM) ? "enabled" : "disabled", - OPTION_ENABLED (option, DEFAULTCHARS) ? "enabled" : "disabled", - OPTION_ENABLED (option, SWITCH) ? "enabled" : "disabled", - OPTION_ENABLED (option, POINTER) ? "enabled" : "disabled", - OPTION_ENABLED (option, NOLENGTH) ? "enabled" : "disabled", - OPTION_ENABLED (option, LENTABLE) ? "enabled" : "disabled", - OPTION_ENABLED (option, DUP) ? "enabled" : "disabled", - OPTION_ENABLED (option, COMP) ? "enabled" : "disabled", - OPTION_ENABLED (option, FAST) ? "enabled" : "disabled", - OPTION_ENABLED (option, NOTYPE) ? "enabled" : "disabled", - OPTION_ENABLED (option, GLOBAL) ? "enabled" : "disabled", - OPTION_ENABLED (option, CONST) ? "enabled" : "disabled", - option.iterations, option.function_name, option.hash_name, - option.key_name, option.jump, option.size - 1, - option.initial_asso_value, option.delimiters, option.total_switches, - keyword_list_length () / option.total_switches); - - if (OPTION_ENABLED (option, ALLCHARS)) - fprintf (stderr, "all characters are used in the hash function\n"); - fprintf (stderr, "maximum charset size = %d\nkey positions are: \n", - option.total_charset_size); - - for (ptr = option.key_positions; *ptr != EOS; ptr++) - if (*ptr == WORD_END) - fprintf (stderr, "$\n"); - else - fprintf (stderr, "%d\n", *ptr); - - fprintf (stderr, "finished dumping Options\n"); - } -} - -/* Parses the command line Options and sets appropriate flags in option.option_word. */ - -void -options_init (argc, argv) - int argc; - char *argv[]; -{ - extern int optind; - extern char *optarg; - int option_char; - - option.key_positions[0] = WORD_START; - option.key_positions[1] = WORD_END; - option.key_positions[2] = EOS; - option.total_charset_size = 2; - option.jump = DEFAULT_JUMP_VALUE; - option.option_word = (int) DEFAULTCHARS; - option.function_name = DEFAULT_NAME; - option.hash_name = DEFAULT_HASH_NAME; - option.key_name = DEFAULT_KEY; - option.delimiters = DEFAULT_DELIMITERS; - option.initial_asso_value = option.size = option.iterations = 0; - option.total_switches = 1; - option.argument_count = argc; - option.argument_vector = argv; - set_program_name (argv[0]); - - while ((option_char = getopt (argc, argv, "adcCDe:f:gGhH:i:j:k:K:lnN:oprs:S:tTv")) != EOF) - { - switch (option_char) - { - case 'a': /* Generated coded uses the ANSI prototype format. */ - { - SET_OPTION (option, ANSI); - break; - } - case 'c': /* Generate strncmp rather than strcmp. */ - { - SET_OPTION (option, COMP); - break; - } - case 'C': /* Make the generated tables readonly (const). */ - { - SET_OPTION (option, CONST); - break; - } - case 'd': /* Enable debugging option. */ - { - SET_OPTION (option, DEBUG); - report_error ("starting program %n, version %s, with debuggin on.\n", - version_string); - break; - } - case 'D': /* Enable duplicate option. */ - { - SET_OPTION (option, DUP); - break; - } - case 'e': /* Allows user to provide keyword/attribute separator */ - { - SET_DELIMITERS (option, optarg); - break; - } - case 'f': /* Generate the hash table ``fast.'' */ - { - SET_OPTION (option, FAST); - if ((option.iterations = atoi (optarg)) < 0) - { - report_error ("iterations value must not be negative, assuming 0\n"); - option.iterations = 0; - } - break; - } - case 'g': /* Use the ``inline'' keyword for generated sub-routines. */ - { - SET_OPTION (option, GNU); - break; - } - case 'G': /* Make the keyword table a global variable. */ - { - SET_OPTION (option, GLOBAL); - break; - } - case 'h': /* Displays a list of helpful Options to the user. */ - { - report_error ( -"-a\tGenerate ANSI standard C output code, i.e., function prototypes.\n\ --c\tGenerate comparison code using strncmp rather than strcmp.\n\ --C\tMake the contents of generated lookup tables constant, i.e., readonly.\n\ --d\tEnables the debugging option (produces verbose output to Std_Err).\n\ --D\tHandle keywords that hash to duplicate values. This is useful\n\ -\tfor certain highly redundant keyword sets. It enables the -S option.\n\ --e\tAllow user to provide a string containing delimiters used to separate\n\ -\tkeywords from their attributes. Default is \",\\n\"\n\ --f\tGenerate the perfect hash function ``fast.'' This decreases GPERF's\n\ -\trunning time at the cost of minimizing generated table-size.\n\ -\tThe numeric argument represents the number of times to iterate when\n\ -\tresolving a collision. `0' means ``iterate by the number of keywords''.\n\ --g\tAssume a GNU compiler, e.g., g++ or gcc. This makes all generated\n\ -\troutines use the ``inline'' keyword to remove cost of function calls.\n\ --G\tGenerate the static table of keywords as a static global variable,\n\ -\trather than hiding it inside of the lookup function (which is the\n\ -\tdefault behavior).\n\ --h\tPrints this mesage.\n"); - report_error ( -"-H\tAllow user to specify name of generated hash function. Default is `hash'.\n\ --i\tProvide an initial value for the associate values array. Default is 0.\n\ -\tSetting this value larger helps inflate the size of the final table.\n\ --j\tAffects the ``jump value,'' i.e., how far to advance the associated\n\ -\tcharacter value upon collisions. Must be an odd number, default is %d.\n\ --k\tAllows selection of the key positions used in the hash function.\n\ -\tThe allowable choices range between 1-%d, inclusive. The positions\n\ -\tare separated by commas, ranges may be used, and key positions may\n\ -\toccur in any order. Also, the meta-character '*' causes the generated\n\ -\thash function to consider ALL key positions, and $ indicates the\n\ -\t``final character'' of a key, e.g., $,1,2,4,6-10.\n\ --K\tAllow user to select name of the keyword component in the keyword structure.\n\ --l\tCompare key lengths before trying a string comparison. This helps\n\ -\tcut down on the number of string comparisons made during the lookup.\n\ --n\tDo not include the length of the keyword when computing the hash function\n\ --N\tAllow user to specify name of generated lookup function. Default\n\ -\tname is `in_word_set.'\n\ --o\tReorders input keys by frequency of occurrence of the key sets.\n\ -\tThis should decrease the search time dramatically.\n\ --p\tChanges the return value of the generated function ``in_word_set''\n\ -\tfrom its default boolean value (i.e., 0 or 1), to type ``pointer\n\ -\tto wordlist array'' This is most useful when the -t option, allowing\n\ -\tuser-defined structs, is used.\n", - DEFAULT_JUMP_VALUE, MAX_KEY_POS - 1); - report_error ( -"-r\tUtilizes randomness to initialize the associated values table.\n\ --s\tAffects the size of the generated hash table. The numeric argument\n\ -\tfor this option indicates ``how many times larger'' the table range\n\ -\tshould be, in relationship to the number of keys, e.g. a value of 3\n\ -\tmeans ``make the table about 3 times larger than the number of input\n\ -\tkeys.'' A larger table should decrease the time required for an\n\ -\tunsuccessful search, at the expense of extra table space. Default\n\ -\tvalue is 1. This actual table size may vary somewhat.\n\ --S\tCauses the generated C code to use a switch statement scheme, rather\n\ -\tthan an array lookup table. This can lead to a reduction in both\n\ -\ttime and space requirements for some keyfiles. The argument to\n\ -\tthis option determines how many switch statements are generated.\n\ -\tA value of 1 generates 1 switch containing all the elements, a value of 2\n\ -\tgenerates 2 tables with 1/2 the elements in each table, etc. This\n\ -\tis useful since many C compilers cannot correctly generate code for\n\ -\tlarge switch statements.\n\ -\tthe expense of longer time for each lookup. Mostly important for\n\ -\t*large* input sets, i.e., greater than around 100 items or so.\n\ --t\tAllows the user to include a structured type declaration for \n\ -\tgenerated code. Any text before %%%% is consider part of the type\n\ -\tdeclaration. Key words and additional fields may follow this, one\n\ -\tgroup of fields per line.\n\ --T\tPrevents the transfer of the type declaration to the output file.\n\ -\tUse this option if the type is already defined elsewhere.\n\ --v\tPrints out the current version number\n%e%a\n", - usage); - } - case 'H': /* Sets the name for the hash function */ - { - option.hash_name = optarg; - break; - } - case 'i': /* Sets the initial value for the associated values array. */ - { - if ((option.initial_asso_value = atoi (optarg)) < 0) - report_error ("initial value %d must be non-zero, ignoring and continuing\n", - option.initial_asso_value); - if (OPTION_ENABLED (option, RANDOM)) - report_error ("warning, -r option superceeds -i, ignoring -i option and continuing\n"); - break; - } - case 'j': /* Sets the jump value, must be odd for later algorithms. */ - { - if ((option.jump = atoi (optarg)) < 0) - report_error ("jump value %d must be a positive number\n%e%a", - option.jump, usage); - else if (option.jump && EVEN (option.jump)) - report_error ("jump value %d should be odd, adding 1 and continuing...\n", - option.jump++); - break; - } - case 'k': /* Sets key positions used for hash function. */ - { - int BAD_VALUE = -1; - int value; - - iterator_init (optarg, 1, MAX_KEY_POS - 1, WORD_END, BAD_VALUE, EOS); - - if (*optarg == '*') /* Use all the characters for hashing!!!! */ - { - UNSET_OPTION (option, DEFAULTCHARS); - SET_OPTION (option, ALLCHARS); - } - else - { - char *key_pos; - - for (key_pos = option.key_positions; (value = next ()) != EOS; key_pos++) - if (value == BAD_VALUE) - report_error ("illegal key value or range, use 1,2,3-%d,'$' or '*'.\n%e%a", - (MAX_KEY_POS - 1),usage); - else - *key_pos = value;; - - *key_pos = EOS; - - if (! (option.total_charset_size = (key_pos - option.key_positions))) - report_error ("no keys selected\n%e%a", usage); - else if (! key_sort (option.key_positions, option.total_charset_size)) - report_error ("duplicate keys selected\n%e%a", usage); - - if (option.total_charset_size != 2 - || (option.key_positions[0] != 1 || option.key_positions[1] != WORD_END)) - UNSET_OPTION (option, DEFAULTCHARS); - } - break; - } - case 'K': /* Make this the keyname for the keyword component field. */ - { - option.key_name = optarg; - break; - } - case 'l': /* Create length table to avoid extra string compares. */ - { - SET_OPTION (option, LENTABLE); - break; - } - case 'n': /* Don't include the length when computing hash function. */ - { - SET_OPTION (option, NOLENGTH); - break; - } - case 'N': /* Make generated lookup function name be optarg */ - { - option.function_name = optarg; - break; - } - case 'o': /* Order input by frequency of key set occurrence. */ - { - SET_OPTION (option, ORDER); - break; - } - case 'p': /* Generated lookup function now a pointer instead of int. */ - { - SET_OPTION (option, POINTER); - break; - } - case 'r': /* Utilize randomness to initialize the associated values table. */ - { - SET_OPTION (option, RANDOM); - if (option.initial_asso_value != 0) - report_error ("warning, -r option superceeds -i, disabling -i option and continuing\n"); - break; - } - case 's': /* Range of associated values, determines size of final table. */ - { - if ((option.size = atoi (optarg)) <= 0) - report_error ("improper range argument %s\n%e%a", optarg, usage); - else if (option.size > 50) - report_error ("%d is excessive, did you really mean this?! (type %n -h for help)\n", - option.size); - break; - } - case 'S': /* Generate switch statement output, rather than lookup table. */ - { - SET_OPTION (option, SWITCH); - if ((option.total_switches = atoi (optarg)) <= 0) - report_error ("number of switches %s must be a positive number\n%e%a", optarg, usage); - break; - } - case 't': /* Enable the TYPE mode, allowing arbitrary user structures. */ - { - SET_OPTION (option, TYPE); - break; - } - case 'T': /* Don't print structure definition. */ - { - SET_OPTION (option, NOTYPE); - break; - } - case 'v': /* Print out the version and quit. */ - report_error ("%n: version %s\n%e%a\n", version_string, usage); - default: - report_error ("%e%a", usage); - } - } - - if (argv[optind] && ! freopen (argv[optind], "r", stdin)) - report_error ("unable to read key word file %s\n%e%a", argv[optind], usage); - - if (++optind < argc) - report_error ("extra trailing arguments to %n\n%e%a", usage); -} - -/* Output command-line Options. */ -void -print_options () -{ - int i; - - printf ("/* Command-line: "); - - for (i = 0; i < option.argument_count; i++) - printf ("%s ", option.argument_vector[i]); - - printf (" */\n\n"); -} - diff --git a/contrib/gperf/src/perfect.c b/contrib/gperf/src/perfect.c deleted file mode 100644 index 25b958e..0000000 --- a/contrib/gperf/src/perfect.c +++ /dev/null @@ -1,350 +0,0 @@ -/* Provides high-level routines to manipulate the keywork list - structures the code generation output. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include <assert.h> -#include <ctype.h> -#include "options.h" -#include "perfect.h" -#include "stderr.h" - -/* Current release version. */ -extern char *version_string; - -/* Counts occurrences of each key set character. */ -int occurrences[ALPHABET_SIZE]; - -/* Value associated with each character. */ -int asso_values[ALPHABET_SIZE]; - -/* Locally visible PERFECT object. */ -PERFECT perfect; - -/* Efficiently returns the least power of two greater than or equal to X! */ -#define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X))) - -/* Reads input keys, possibly applies the reordering heuristic, sets the - maximum associated value size (rounded up to the nearest power of 2), - may initialize the associated values array, and determines the maximum - hash table size. Note: using the random numbers is often helpful, - though not as deterministic, of course! */ - -void -perfect_init () -{ - int asso_value_max; - int len; - - perfect.num_done = 1; - perfect.fewest_collisions = 0; - read_keys (); - if (OPTION_ENABLED (option, ORDER)) - reorder (); - asso_value_max = GET_ASSO_MAX (option); - len = keyword_list_length (); - asso_value_max = (asso_value_max ? asso_value_max * len : len); - SET_ASSO_MAX (option, POW (asso_value_max)); - - if (OPTION_ENABLED (option, RANDOM)) - { - int i; - - srandom (time (0)); - - for (i = 0; i < ALPHABET_SIZE; i++) - asso_values[i] = (random () & asso_value_max - 1); - } - else - { - int asso_value = INITIAL_VALUE (option); - if (asso_value) /* Initialize array if user requests non-zero default. */ - { - int i; - - for (i = ALPHABET_SIZE - 1; i >= 0; i--) - asso_values[i] = asso_value & GET_ASSO_MAX (option) - 1; - } - } - perfect.max_hash_value = max_key_length () + GET_ASSO_MAX (option) * - GET_CHARSET_SIZE (option); - - printf ("/* C code produced by gperf version %s */\n", version_string); - print_options (); - - if (OPTION_ENABLED (option, DEBUG)) - { - int i; - fprintf (stderr, "\nnumber of keys = %d\nmaximum associated value is %d\ -\nmaximum possible size of generated hash table is %d\n", - len, asso_value_max, perfect.max_hash_value); - } -} - -/* Merge two hash key multisets to form the ordered disjoint union of the sets. - (In a multiset, an element can occur multiple times). Precondition: both - set_1 and set_2 must be ordered. Returns the length of the combined set. */ - -static int -compute_disjoint_union (set_1, set_2, set_3) - char *set_1; - char *set_2; - char *set_3; -{ - char *base = set_3; - - while (*set_1 && *set_2) - if (*set_1 == *set_2) - set_1++, set_2++; - else - { - *set_3 = *set_1 < *set_2 ? *set_1++ : *set_2++; - if (set_3 == base || *set_3 != *(set_3-1)) set_3++; - } - - while (*set_1) - { - *set_3 = *set_1++; - if (set_3 == base || *set_3 != *(set_3-1)) set_3++; - } - - while (*set_2) - { - *set_3 = *set_2++; - if (set_3 == base || *set_3 != *(set_3-1)) set_3++; - } - *set_3 = '\0'; - return set_3 - base; -} - -/* Sort the UNION_SET in increasing frequency of occurrence. - This speeds up later processing since we may assume the resulting - set (Set_3, in this case), is ordered. Uses insertion sort, since - the UNION_SET is typically short. */ - -static void -sort_set (union_set, len) - char *union_set; - int len; -{ - int i, j; - - for (i = 0, j = len - 1; i < j; i++) - { - char curr, tmp; - - for (curr = i+1, tmp = union_set[curr]; - curr > 0 && occurrences[tmp] < occurrences[union_set[curr-1]]; - curr--) - union_set[curr] = union_set[curr - 1]; - - union_set[curr] = tmp; - } -} - -/* Generate a key set's hash value. */ - -static int -hash (key_node) - LIST_NODE *key_node; -{ - int sum = OPTION_ENABLED (option, NOLENGTH) ? 0 : key_node->length; - char *ptr; - - for (ptr = key_node->char_set; *ptr; ptr++) - sum += asso_values[*ptr]; - - return key_node->hash_value = sum; -} - -/* Find out how associated value changes affect successfully hashed items. - Returns FALSE if no other hash values are affected, else returns TRUE. - Note that because GET_ASSO_MAX (option) is a power of two we can guarantee - that all legal ASSO_VALUES are visited without repetition since - GET_JUMP (option) was forced to be an odd value! */ - -static bool -affects_prev (c, curr) - char c; - LIST_NODE *curr; -{ - int original_char = asso_values[c]; - int i = !OPTION_ENABLED (option, FAST) ? GET_ASSO_MAX (option) : - GET_ITERATIONS (option) == 0 ? key_list.list_len : GET_ITERATIONS (option); - - /* Try all asso_values. */ - - while (--i >= 0) - { - int collisions = 0; - LIST_NODE *ptr; - - asso_values[c] = asso_values[c] + (GET_JUMP (option) ? GET_JUMP (option) : random ()) - & GET_ASSO_MAX (option) - 1; - bool_array_reset (); - - /* See how this asso_value change affects previous keywords. If - it does better than before we'll take it! */ - - for (ptr = key_list.head; - !lookup (hash (ptr)) || ++collisions < perfect.fewest_collisions; - ptr = ptr->next) - if (ptr == curr) - { - perfect.fewest_collisions = collisions; - return FALSE; - } - } - - asso_values[c] = original_char; /* Restore original values, no more tries. */ - return TRUE; /* If we're this far it's time to try the next character.... */ -} - -/* Change a character value, try least-used characters first. */ - -static void -change (prior, curr) - LIST_NODE *prior; - LIST_NODE *curr; -{ - char *xmalloc (); - static char *union_set = 0; - char *temp; - LIST_NODE *ptr; - - if (!union_set) - union_set = xmalloc (2 * GET_CHARSET_SIZE (option) + 1); - - if (OPTION_ENABLED (option, DEBUG)) /* Very useful for debugging. */ - { - fprintf (stderr, "collision on keyword #%d, prior=\"%s\", curr=\"%s\", hash=%d\n", - perfect.num_done, prior->key, curr->key, curr->hash_value); - fflush (stderr); - } - sort_set (union_set, compute_disjoint_union (prior->char_set, curr->char_set, union_set)); - - /* Try changing some values, if change doesn't alter other values continue normal action. */ - - perfect.fewest_collisions++; - - for (temp = union_set; *temp; temp++) - if (!affects_prev (*temp, curr)) - { - if (OPTION_ENABLED (option, DEBUG)) - { - fprintf (stderr, "- resolved by changing asso_value['%c'] (char #%d) to %d\n", - *temp, temp - union_set + 1, asso_values[*temp]); - fflush (stderr); - } - return; /* Good, doesn't affect previous hash values, we'll take it. */ - } - - for (ptr = key_list.head; ptr != curr; ptr = ptr->next) - hash (ptr); - - hash (curr); - - if (OPTION_ENABLED (option, DEBUG)) - { - fprintf (stderr, "** collision not resolved, %d duplicates remain, continuing...\n", - perfect.fewest_collisions); - fflush (stderr); - } -} - -/* Does the hard stuff.... - Initializes the Iteration Number boolean array, and then trys to find a - perfect function that will hash all the key words without getting any - duplications. This is made much easier since we aren't attempting - to generate *minimum* functions, only perfect ones. - If we can't generate a perfect function in one pass *and* the user - hasn't enabled the DUP option, we'll inform the user to try the - randomization option, use -D, or choose alternative key positions. - The alternatives (e.g., back-tracking) are too time-consuming, i.e, - exponential in the number of keys. */ - -int -perfect_generate () -{ - LIST_NODE *curr; - bool_array_init (perfect.max_hash_value); - - for (curr = key_list.head; curr; curr = curr->next) - { - LIST_NODE *ptr; - hash (curr); - - for (ptr = key_list.head; ptr != curr; ptr = ptr->next) - if (ptr->hash_value == curr->hash_value) - { - change (ptr, curr); - break; - } - perfect.num_done++; - } - - - /* Make one final check, just to make sure nothing weird happened.... */ - bool_array_reset (); - - for (curr = key_list.head; curr; curr = curr->next) - if (lookup (hash (curr))) - if (OPTION_ENABLED (option, DUP)) /* We'll try to deal with this later..... */ - break; - else /* Yow, big problems. we're outta here! */ - { - report_error ("\nInternal error, duplicate value %d:\n\ -try options -D or -r, or use new key positions.\n\n", - hash (curr)); - return 1; - } - - bool_array_destroy (); - - /* First sorts the key word list by hash value, and the outputs the - list to the proper ostream. The generated hash table code is only - output if the early stage of processing turned out O.K. */ - - sort (); - print_output (); - return 0; -} - -/* Prints out some diagnostics upon completion. */ - -void -perfect_destroy () -{ - if (OPTION_ENABLED (option, DEBUG)) - { - int i; - - fprintf (stderr, "\ndumping occurrence and associated values tables\n"); - - for (i = 0; i < ALPHABET_SIZE; i++) - if (occurrences[i]) - fprintf (stderr, "asso_values[%c] = %3d, occurrences[%c] = %3d\n", - i, asso_values[i], i, occurrences[i]); - - fprintf (stderr, "end table dumping\n"); - - } -} - diff --git a/contrib/gperf/src/perfect.h b/contrib/gperf/src/perfect.h deleted file mode 100644 index c5b9443..0000000 --- a/contrib/gperf/src/perfect.h +++ /dev/null @@ -1,45 +0,0 @@ -/* Provides high-level routines to manipulate the keyword list - structures the code generation output. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#ifndef _perfect_h -#define _perfect_h - -#include "prototype.h" -#include "keylist.h" -#include "boolarray.h" - -typedef struct perfect -{ - KEY_LIST list; /* List of key words provided by the user. */ - BOOL_ARRAY duplicate; /* Speeds up check for redundant hash values. */ - int max_hash_value; /* Maximum possible hash value. */ - int fewest_collisions; /* Records fewest # of collisions for asso value. */ - int num_done; /* Number of keywords processed without a collision. */ -} PERFECT; - -extern void perfect_init P ((void)); -extern void perfect_destroy P ((void)); -extern int perfect_generate P ((void)); -extern void perfect_print P ((void)); -#endif /* _perfect_h */ - - diff --git a/contrib/gperf/src/prototype.h b/contrib/gperf/src/prototype.h deleted file mode 100644 index a6077b65..0000000 --- a/contrib/gperf/src/prototype.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef _prototype_h -#define _prototype_h -#ifdef __STDC__ -#define P(X) X -#else -#define P(X) () -#endif - -typedef char bool; -#define FALSE 0 -#define TRUE 1 - -#define ODD(X) ((X) & 1) -#define EVEN(X) (!((X) & 1)) -#endif /* _prototype_h */ diff --git a/contrib/gperf/src/readline.c b/contrib/gperf/src/readline.c deleted file mode 100644 index 19ac5e5..0000000 --- a/contrib/gperf/src/readline.c +++ /dev/null @@ -1,87 +0,0 @@ -/* Correctly reads an arbitrarily size string. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include "readline.h" - -/* Size of each chunk. */ -#define CHUNK_SIZE BUFSIZ - -/* Recursively fills up the buffer. */ - -static char * -readln_aux (chunks) - int chunks; -{ - char *buffered_malloc (); - char buf[CHUNK_SIZE]; - register char *bufptr = buf; - register char *ptr; - int c; - - while ((c = getchar ()) != EOF && c != '\n') /* fill the current buffer */ - { - *bufptr++ = c; - if (bufptr - buf >= CHUNK_SIZE) /* prepend remainder to ptr buffer */ - { - if (ptr = readln_aux (chunks + 1)) - - for (; bufptr != buf; *--ptr = *--bufptr); - - return ptr; - } - } - - if (c == EOF && bufptr == buf) - return NULL; - - c = (chunks * CHUNK_SIZE + bufptr - buf) + 1; - - if (ptr = buffered_malloc (c)) - { - - for (*(ptr += (c - 1)) = '\0'; bufptr != buf; *--ptr = *--bufptr) - ; - - return ptr; - } - else - return NULL; -} - -/* Returns the ``next'' line, ignoring comments beginning with '#'. */ - -char *read_line () -{ - int c; - if ((c = getchar ()) == '#') - { - while ((c = getchar ()) != '\n' && c != EOF) - ; - - return c != EOF ? read_line () : NULL; - } - else - { - ungetc (c, stdin); - return readln_aux (0); - } -} diff --git a/contrib/gperf/src/readline.h b/contrib/gperf/src/readline.h deleted file mode 100644 index 13164d9..0000000 --- a/contrib/gperf/src/readline.h +++ /dev/null @@ -1,31 +0,0 @@ -/* Reads arbitrarily long string from input file, returning it as a dynamic buffer. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -/* Returns a pointer to an arbitrary length string. Returns NULL on error or EOF - The storage for the string is dynamically allocated by new. */ - -#ifndef _readline_h -#define _readline_h -#include "prototype.h" - -extern char *read_line P ((void)); -#endif /* _readline_h */ - diff --git a/contrib/gperf/src/stderr.c b/contrib/gperf/src/stderr.c deleted file mode 100644 index c24cf6e..0000000 --- a/contrib/gperf/src/stderr.c +++ /dev/null @@ -1,96 +0,0 @@ -/* Provides a useful variable-length argument error handling abstraction. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> -#include <errno.h> -#ifdef _HAVE_PARAM_H -#include <sys/param.h> -#endif -#include "stderr.h" - -/* Holds the name of the currently active program. */ -static char *program_name; - -/* Sets name of program. */ - -void -set_program_name (prog_name) - char *prog_name; -{ - program_name = prog_name; -} - -/* Valid Options (prefixed by '%', as in printf format strings) include: - 'a': exit the program at this point - 'c': print a character - 'd': print a decimal number - 'e': call the function pointed to by the corresponding argument - 'f','g': print a double - 'n': print the name of the program (NULL if not set in constructor or elsewhere) - 'p': print out the appropriate errno value from sys_errlist - 's': print out a character string - '%': print out a single percent sign, '%' */ - -void -report_error (va_alist) - va_dcl -{ - extern int errno, sys_nerr; -#if (! defined(BSD) || (BSD < 199103)) - extern char *sys_errlist[]; -#endif /* not 4.3 Net2 based */ - typedef void (*PTF)(); - typedef char *CHARP; - va_list argp; - int abort_flag = 0; - char *format; - - va_start (argp); - - for (format = va_arg (argp, char *); *format; format++) - { - if (*format != '%') - putc (*format, stderr); - else - { - switch(*++format) - { - case '%' : putc ('%', stderr); break; - case 'a' : abort_flag = 1; break; - case 'c' : putc (va_arg (argp, int), stderr); break; - case 'd' : fprintf (stderr, "%d", va_arg (argp, int)); break; - case 'e' : (*va_arg (argp, PTF))(); break; - case 'f' : fprintf (stderr, "%g", va_arg (argp, double)); break; - case 'n' : fputs (program_name ? program_name : "error", stderr); break; - case 'p' : - if (errno < sys_nerr) - fprintf (stderr, "%s: %s", va_arg (argp, CHARP), sys_errlist[errno]); - else - fprintf (stderr, "<unknown error> %d", errno); - break; - case 's' : fputs (va_arg (argp, CHARP), stderr); break; - } - } - if (abort_flag) - exit (1); - } - va_end (argp); -} diff --git a/contrib/gperf/src/stderr.h b/contrib/gperf/src/stderr.h deleted file mode 100644 index a94255e..0000000 --- a/contrib/gperf/src/stderr.h +++ /dev/null @@ -1,29 +0,0 @@ -/* Provides a useful variable-length argument error handling abstraction. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#ifndef _stderr_h -#define _stderr_h -#include "prototype.h" -#include <varargs.h> - -extern void set_program_name P ((char *prog_name)); -extern void report_error (); -#endif /* _stderr_h */ diff --git a/contrib/gperf/src/version.c b/contrib/gperf/src/version.c deleted file mode 100644 index 7fa142c..0000000 --- a/contrib/gperf/src/version.c +++ /dev/null @@ -1,22 +0,0 @@ -/* Current program version number. - - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -char *version_string = "2.1 (K&R C version)"; diff --git a/contrib/gperf/src/xmalloc.c b/contrib/gperf/src/xmalloc.c deleted file mode 100644 index 09cc022..0000000 --- a/contrib/gperf/src/xmalloc.c +++ /dev/null @@ -1,78 +0,0 @@ -/* Provide a useful malloc sanity checker and an efficient buffered memory - allocator that reduces calls to malloc. - Copyright (C) 1989 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) - -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, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include <stdio.h> - -/* Grabs SIZE bytes of dynamic memory or dies trying! */ - -char * -xmalloc (size) - int size; -{ - char *malloc (); - char *temp = malloc (size); - - if (temp == 0) - { - fprintf (stderr, "out of virtual memory\n"); - exit (1); - } - return temp; -} - -/* Determine default alignment. If your C compiler does not - like this then try something like #define DEFAULT_ALIGNMENT 8. */ -struct fooalign {char x; double d;}; -#define ALIGNMENT ((char *)&((struct fooalign *) 0)->d - (char *)0) - -/* Provide an abstraction that cuts down on the number of - calls to MALLOC by buffering the memory pool from which - items are allocated. */ - -char * -buffered_malloc (size) - int size; -{ - char *temp; - static char *buf_start = 0; /* Large array used to reduce calls to NEW. */ - static char *buf_end = 0; /* Indicates end of BUF_START. */ - static int buf_size = 4 * BUFSIZ; /* Size of buffer pointed to by BUF_START. */ - - /* Align this on correct boundaries, just to be safe... */ - size = ((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT; - - /* If we are about to overflow our buffer we'll just grab another - chunk of memory. Since we never free the original memory it - doesn't matter that no one points to the beginning of that - chunk. Furthermore, as a heuristic, we double the - size of the new buffer! */ - - if (buf_start + size >= buf_end) - { - buf_size = buf_size * 2 > size ? buf_size * 2 : size; - buf_start = xmalloc (buf_size); - buf_end = buf_start + buf_size; - } - - temp = buf_start; - buf_start += size; - return temp; -} |