1 /* Routines for building, ordering, and printing the keyword list.
2 Copyright (C) 1989-1998, 2000 Free Software Foundation, Inc.
3 written by Douglas C. Schmidt (schmidt@ics.uci.edu)
5 This file is part of GNU GPERF.
7 GNU GPERF is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 1, or (at your option)
12 GNU GPERF is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU GPERF; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */
22 #include <string.h> /* declares strncpy(), strchr() */
23 #include <stdlib.h> /* declares malloc(), free(), abs(), exit(), abort() */
24 #include <ctype.h> /* declares isprint() */
25 #include <assert.h> /* defines assert() */
26 #include <limits.h> /* defines SCHAR_MAX etc. */
28 #include "read-line.h"
29 #include "hash-table.h"
34 /* Make the hash table 8 times larger than the number of keyword entries. */
35 static const int TABLE_MULTIPLE = 10;
37 /* Efficiently returns the least power of two greater than or equal to X! */
38 #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
40 int Key_List::determined[MAX_ALPHA_SIZE];
42 /* Destructor dumps diagnostics during debugging. */
44 Key_List::~Key_List (void)
46 T (Trace t ("Key_List::~Key_List");)
49 fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d"
50 "\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n",
51 list_len, total_keys, total_duplicates, max_key_len);
53 fprintf (stderr, "End dumping list.\n\n");
57 /* Gathers the input stream into a buffer until one of two things occur:
59 1. We read a '%' followed by a '%'
60 2. We read a '%' followed by a '}'
62 The first symbolizes the beginning of the keyword list proper,
63 The second symbolizes the end of the C source code to be generated
64 verbatim in the output file.
66 I assume that the keys are separated from the optional preceding struct
67 declaration by a consecutive % followed by either % or } starting in
68 the first column. The code below uses an expandible buffer to scan off
69 and return a pointer to all the code (if any) appearing before the delimiter. */
72 Key_List::get_special_input (char delimiter)
74 T (Trace t ("Key_List::get_special_input");)
76 char *buf = new char[size];
79 for (i = 0; (c = getchar ()) != EOF; i++)
83 if ((c = getchar ()) == delimiter)
86 while ((c = getchar ()) != '\n')
87 ; /* discard newline */
93 buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
100 else if (i >= size) /* Yikes, time to grow the buffer! */
102 char *temp = new char[size *= 2];
105 for (j = 0; j < i; j++)
113 return 0; /* Problem here. */
116 /* Stores any C text that must be included verbatim into the
117 generated code output. */
120 Key_List::save_include_src (void)
122 T (Trace t ("Key_List::save_include_src");)
125 if ((c = getchar ()) != '%')
127 else if ((c = getchar ()) != '{')
129 fprintf (stderr, "internal error, %c != '{' on line %d in file %s", c, __LINE__, __FILE__);
133 return get_special_input ('}');
137 /* Determines from the input file whether the user wants to build a table
138 from a user-defined struct, or whether the user is content to simply
139 use the default array of keys. */
142 Key_List::get_array_type (void)
144 T (Trace t ("Key_List::get_array_type");)
145 return get_special_input ('%');
148 /* strcspn - find length of initial segment of S consisting entirely
149 of characters not from REJECT (borrowed from Henry Spencer's
150 ANSI string package, when GNU libc comes out I'll replace this...). */
154 Key_List::strcspn (const char *s, const char *reject)
156 T (Trace t ("Key_List::strcspn");)
158 const char *rej_scan;
161 for (scan = s; *scan; scan++)
164 for (rej_scan = reject; *rej_scan; rej_scan++)
165 if (*scan == *rej_scan)
175 /* Sets up the Return_Type, the Struct_Tag type and the Array_Type
176 based upon various user Options. */
179 Key_List::set_output_types (void)
181 T (Trace t ("Key_List::set_output_types");)
184 array_type = get_array_type ();
186 /* Something's wrong, but we'll catch it later on, in read_keys()... */
188 /* Yow, we've got a user-defined type... */
189 int i = strcspn (array_type, "{\n\0");
190 /* Remove trailing whitespace. */
191 while (i > 0 && strchr (" \t", array_type[i-1]))
193 int struct_tag_length = i;
195 /* Set `struct_tag' to a naked "struct something". */
196 char *structtag = new char[struct_tag_length + 1];
197 strncpy (structtag, array_type, struct_tag_length);
198 structtag[struct_tag_length] = '\0';
199 struct_tag = structtag;
201 /* The return type of the lookup function is "struct something *".
202 No "const" here, because if !option[CONST], some user code might want
203 to modify the structure. */
204 char *rettype = new char[struct_tag_length + 3];
205 strncpy (rettype, array_type, struct_tag_length);
206 rettype[struct_tag_length] = ' ';
207 rettype[struct_tag_length + 1] = '*';
208 rettype[struct_tag_length + 2] = '\0';
209 return_type = rettype;
213 /* Extracts a key from an input line and creates a new List_Node for it. */
216 parse_line (const char *line, const char *delimiters)
220 /* Parse a string in ANSI C syntax. */
221 char *key = new char[strlen(line)];
223 const char *lp = line + 1;
231 fprintf (stderr, "unterminated string: %s\n", line);
239 case '0': case '1': case '2': case '3':
240 case '4': case '5': case '6': case '7':
244 while (count < 3 && *lp >= '0' && *lp <= '7')
246 code = (code << 3) + (*lp - '0');
250 if (code > UCHAR_MAX)
251 fprintf (stderr, "octal escape out of range: %s\n", line);
260 while ((*lp >= '0' && *lp <= '9')
261 || (*lp >= 'A' && *lp <= 'F')
262 || (*lp >= 'a' && *lp <= 'f'))
265 + (*lp >= 'A' && *lp <= 'F' ? *lp - 'A' + 10 :
266 *lp >= 'a' && *lp <= 'f' ? *lp - 'a' + 10 :
272 fprintf (stderr, "hexadecimal escape without any hex digits: %s\n", line);
273 if (code > UCHAR_MAX)
274 fprintf (stderr, "hexadecimal escape out of range: %s\n", line);
278 case '\\': case '\'': case '"':
311 fprintf (stderr, "invalid escape sequence in string: %s\n", line);
327 if (strchr (delimiters, *lp) == NULL)
329 fprintf (stderr, "string not followed by delimiter: %s\n", line);
334 return new List_Node (key, kp - key, option[TYPE] ? lp : "");
338 /* Not a string. Look for the delimiter. */
339 int len = strcspn (line, delimiters);
342 if (line[len] == '\0')
345 /* Skip the first delimiter. */
346 rest = &line[len + 1];
347 return new List_Node (line, len, option[TYPE] ? rest : "");
351 /* Reads in all keys from standard input and creates a linked list pointed
352 to by Head. This list is then quickly checked for ``links,'' i.e.,
353 unhashable elements possessing identical key sets and lengths. */
356 Key_List::read_keys (void)
358 T (Trace t ("Key_List::read_keys");)
361 include_src = save_include_src ();
364 /* Oops, problem with the input file. */
365 if (! (ptr = Read_Line::get_line ()))
367 fprintf (stderr, "No words in input file, did you forget to prepend %s or use -t accidentally?\n", "%%");
371 /* Read in all the keywords from the input file. */
374 const char *delimiter = option.get_delimiter ();
375 List_Node *temp, *trail = 0;
377 head = parse_line (ptr, delimiter);
380 (ptr = Read_Line::get_line ()) && strcmp (ptr, "%%");
383 temp->next = parse_line (ptr, delimiter);
387 /* See if any additional C code is included at end of this file. */
391 /* Hash table this number of times larger than keyword number. */
392 int table_size = (list_len = total_keys) * TABLE_MULTIPLE;
394 #if LARGE_STACK_ARRAYS
395 /* By allocating the memory here we save on dynamic allocation overhead.
396 Table must be a power of 2 for the hash function scheme to work. */
397 List_Node *table[POW (table_size)];
399 // Note: we don't use new, because that invokes a custom operator new.
400 int malloc_size = POW (table_size) * sizeof(List_Node*);
401 if (malloc_size == 0) malloc_size = 1;
402 List_Node **table = (List_Node**)malloc(malloc_size);
407 /* Make large hash table for efficiency. */
408 Hash_Table found_link (table, table_size, option[NOLENGTH]);
410 /* Test whether there are any links and also set the maximum length of
411 an identifier in the keyword list. */
413 for (temp = head; temp; temp = temp->next)
415 List_Node *ptr = found_link.insert (temp);
417 /* Check for links. We deal with these by building an equivalence class
418 of all duplicate values (i.e., links) so that only 1 keyword is
419 representative of the entire collection. This *greatly* simplifies
420 processing during later stages of the program. */
426 trail->next = temp->next;
427 temp->link = ptr->link;
430 /* Complain if user hasn't enabled the duplicate option. */
431 if (!option[DUP] || option[DEBUG])
432 fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"%.*s\".\n",
433 temp->key_length, temp->key,
434 ptr->key_length, ptr->key,
435 temp->char_set_length, temp->char_set);
440 /* Update minimum and maximum keyword length, if needed. */
441 if (max_key_len < temp->key_length)
442 max_key_len = temp->key_length;
443 if (min_key_len > temp->key_length)
444 min_key_len = temp->key_length;
447 #if !LARGE_STACK_ARRAYS
448 free ((char *) table);
451 /* Exit program if links exists and option[DUP] not set, since we can't continue */
452 if (total_duplicates)
455 fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n",
459 fprintf (stderr, "%d input keys have identical hash values,\ntry different key positions or use option -D.\n",
464 /* Exit program if an empty string is used as key, since the comparison
465 expressions don't work correctly for looking up an empty string. */
466 if (min_key_len == 0)
468 fprintf (stderr, "Empty input key is not allowed.\nTo recognize an empty input key, your code should check for\nlen == 0 before calling the gperf generated lookup function.\n");
471 if (option[ALLCHARS])
472 option.set_keysig_size (max_key_len);
476 /* Recursively merges two sorted lists together to form one sorted list. The
477 ordering criteria is by frequency of occurrence of elements in the key set
478 or by the hash value. This is a kludge, but permits nice sharing of
479 almost identical code without incurring the overhead of a function
483 Key_List::merge (List_Node *list1, List_Node *list2)
485 T (Trace t ("Key_List::merge");)
487 List_Node **resultp = &result;
500 if (occurrence_sort && list1->occurrence < list2->occurrence
501 || hash_sort && list1->hash_value > list2->hash_value)
504 resultp = &list2->next; list2 = list1; list1 = *resultp;
509 resultp = &list1->next; list1 = *resultp;
515 /* Applies the merge sort algorithm to recursively sort the key list by
516 frequency of occurrence of elements in the key set. */
519 Key_List::merge_sort (List_Node *head)
521 T (Trace t ("Key_List::merge_sort");)
522 if (!head || !head->next)
526 List_Node *middle = head;
527 List_Node *temp = head->next->next;
532 middle = middle->next;
539 return merge (merge_sort (head), merge_sort (temp));
543 /* Returns the frequency of occurrence of elements in the key set. */
546 Key_List::get_occurrence (List_Node *ptr)
548 T (Trace t ("Key_List::get_occurrence");)
551 const char *p = ptr->char_set;
552 unsigned int i = ptr->char_set_length;
553 for (; i > 0; p++, i--)
554 value += occurrences[(unsigned char)(*p)];
559 /* Enables the index location of all key set elements that are now
563 Key_List::set_determined (List_Node *ptr)
565 T (Trace t ("Key_List::set_determined");)
567 const char *p = ptr->char_set;
568 unsigned int i = ptr->char_set_length;
569 for (; i > 0; p++, i--)
570 determined[(unsigned char)(*p)] = 1;
573 /* Returns TRUE if PTR's key set is already completely determined. */
576 Key_List::already_determined (List_Node *ptr)
578 T (Trace t ("Key_List::already_determined");)
579 int is_determined = 1;
581 const char *p = ptr->char_set;
582 unsigned int i = ptr->char_set_length;
583 for (; is_determined && i > 0; p++, i--)
584 is_determined = determined[(unsigned char)(*p)];
586 return is_determined;
589 /* Reorders the table by first sorting the list so that frequently occuring
590 keys appear first, and then the list is reorded so that keys whose values
591 are already determined will be placed towards the front of the list. This
592 helps prune the search time by handling inevitable collisions early in the
593 search process. See Cichelli's paper from Jan 1980 JACM for details.... */
596 Key_List::reorder (void)
598 T (Trace t ("Key_List::reorder");)
600 for (ptr = head; ptr; ptr = ptr->next)
601 ptr->occurrence = get_occurrence (ptr);
606 for (ptr = head = merge_sort (head); ptr->next; ptr = ptr->next)
608 set_determined (ptr);
610 if (already_determined (ptr->next))
614 List_Node *trail_ptr = ptr->next;
615 List_Node *run_ptr = trail_ptr->next;
617 for (; run_ptr; run_ptr = trail_ptr->next)
620 if (already_determined (run_ptr))
622 trail_ptr->next = run_ptr->next;
623 run_ptr->next = ptr->next;
624 ptr = ptr->next = run_ptr;
633 /* ============================ Output routines ============================ */
635 /* The "const " qualifier. */
636 static const char *const_always;
638 /* The "const " qualifier, for read-only arrays. */
639 static const char *const_readonly_array;
641 /* The "const " qualifier, for the array type. */
642 static const char *const_for_struct;
644 /* Returns the smallest unsigned C type capable of holding integers up to N. */
647 smallest_integral_type (int n)
649 if (n <= UCHAR_MAX) return "unsigned char";
650 if (n <= USHRT_MAX) return "unsigned short";
651 return "unsigned int";
654 /* Returns the smallest signed C type capable of holding integers
658 smallest_integral_type (int min, int max)
660 if (option[ANSIC] | option[CPLUSPLUS])
661 if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char";
662 if (min >= SHRT_MIN && max <= SHRT_MAX) return "short";
666 /* A cast from `char' to a valid array index. */
667 static const char *char_to_index;
669 /* ------------------------------------------------------------------------- */
671 /* Computes the maximum and minimum hash values. Since the
672 list is already sorted by hash value all we need to do is
673 find the final item! */
676 Key_List::compute_min_max (void)
678 T (Trace t ("Key_List::compute_min_max");)
680 for (temp = head; temp->next; temp = temp->next)
683 min_hash_value = head->hash_value;
684 max_hash_value = temp->hash_value;
687 /* ------------------------------------------------------------------------- */
689 /* Returns the number of different hash values. */
692 Key_List::num_hash_values (void)
694 T (Trace t ("Key_List::num_hash_values");)
699 for (temp = head, value = temp->hash_value; temp->next; )
702 if (value != temp->hash_value)
704 value = temp->hash_value;
711 /* -------------------- Output_Constants and subclasses -------------------- */
713 /* This class outputs an enumeration defining some constants. */
715 struct Output_Constants
717 virtual void output_start () = 0;
718 virtual void output_item (const char *name, int value) = 0;
719 virtual void output_end () = 0;
720 Output_Constants () {}
721 virtual ~Output_Constants () {}
724 /* This class outputs an enumeration in #define syntax. */
726 struct Output_Defines : public Output_Constants
728 virtual void output_start ();
729 virtual void output_item (const char *name, int value);
730 virtual void output_end ();
732 virtual ~Output_Defines () {}
735 void Output_Defines::output_start ()
737 T (Trace t ("Output_Defines::output_start");)
741 void Output_Defines::output_item (const char *name, int value)
743 T (Trace t ("Output_Defines::output_item");)
744 printf ("#define %s %d\n", name, value);
747 void Output_Defines::output_end ()
749 T (Trace t ("Output_Defines::output_end");)
752 /* This class outputs an enumeration using `enum'. */
754 struct Output_Enum : public Output_Constants
756 virtual void output_start ();
757 virtual void output_item (const char *name, int value);
758 virtual void output_end ();
759 Output_Enum (const char *indent) : indentation (indent) {}
760 virtual ~Output_Enum () {}
762 const char *indentation;
766 void Output_Enum::output_start ()
768 T (Trace t ("Output_Enum::output_start");)
771 indentation, indentation);
775 void Output_Enum::output_item (const char *name, int value)
777 T (Trace t ("Output_Enum::output_item");)
780 printf ("%s %s = %d", indentation, name, value);
784 void Output_Enum::output_end ()
786 T (Trace t ("Output_Enum::output_end");)
789 printf ("%s };\n\n", indentation);
792 /* Outputs the maximum and minimum hash values etc. */
795 Key_List::output_constants (struct Output_Constants& style)
797 T (Trace t ("Key_List::output_constants");)
799 style.output_start ();
800 style.output_item ("TOTAL_KEYWORDS", total_keys);
801 style.output_item ("MIN_WORD_LENGTH", min_key_len);
802 style.output_item ("MAX_WORD_LENGTH", max_key_len);
803 style.output_item ("MIN_HASH_VALUE", min_hash_value);
804 style.output_item ("MAX_HASH_VALUE", max_hash_value);
808 /* ------------------------------------------------------------------------- */
810 /* Outputs a keyword, as a string: enclosed in double quotes, escaping
811 backslashes, double quote and unprintable characters. */
814 output_string (const char *key, int len)
816 T (Trace t ("output_string");)
819 for (; len > 0; len--)
821 unsigned char c = (unsigned char) *key++;
824 if (c == '"' || c == '\\')
830 /* Use octal escapes, not hexadecimal escapes, because some old
831 C compilers didn't understand hexadecimal escapes, and because
832 hexadecimal escapes are not limited to 2 digits, thus needing
833 special care if the following character happens to be a digit. */
835 putchar ('0' + ((c >> 6) & 7));
836 putchar ('0' + ((c >> 3) & 7));
837 putchar ('0' + (c & 7));
843 /* ------------------------------------------------------------------------- */
845 /* Outputs a type and a const specifier.
846 The output is terminated with a space. */
849 output_const_type (const char *const_string, const char *type_string)
851 if (type_string[strlen(type_string)-1] == '*')
852 printf ("%s %s", type_string, const_string);
854 printf ("%s%s ", const_string, type_string);
857 /* ----------------------- Output_Expr and subclasses ----------------------- */
859 /* This class outputs a general expression. */
863 virtual void output_expr () const = 0;
865 virtual ~Output_Expr () {}
868 /* This class outputs an expression formed by a single string. */
870 struct Output_Expr1 : public Output_Expr
872 virtual void output_expr () const;
873 Output_Expr1 (const char *piece1) : p1 (piece1) {}
874 virtual ~Output_Expr1 () {}
879 void Output_Expr1::output_expr () const
881 T (Trace t ("Output_Expr1::output_expr");)
887 /* This class outputs an expression formed by the concatenation of two
890 struct Output_Expr2 : public Output_Expr
892 virtual void output_expr () const;
893 Output_Expr2 (const char *piece1, const char *piece2)
894 : p1 (piece1), p2 (piece2) {}
895 virtual ~Output_Expr2 () {}
901 void Output_Expr2::output_expr () const
903 T (Trace t ("Output_Expr2::output_expr");)
904 printf ("%s%s", p1, p2);
909 /* --------------------- Output_Compare and subclasses --------------------- */
911 /* This class outputs a comparison expression. */
913 struct Output_Compare
915 virtual void output_comparison (const Output_Expr& expr1,
916 const Output_Expr& expr2) const = 0;
918 virtual ~Output_Compare () {}
921 /* This class outputs a comparison using strcmp. */
923 struct Output_Compare_Strcmp : public Output_Compare
925 virtual void output_comparison (const Output_Expr& expr1,
926 const Output_Expr& expr2) const;
927 Output_Compare_Strcmp () {}
928 virtual ~Output_Compare_Strcmp () {}
931 void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
932 const Output_Expr& expr2) const
934 T (Trace t ("Output_Compare_Strcmp::output_comparison");)
936 expr1.output_expr ();
938 expr2.output_expr ();
939 printf (" && !strcmp (");
940 expr1.output_expr ();
942 expr2.output_expr ();
946 /* This class outputs a comparison using strncmp.
947 Note that the length of expr1 will be available through the local variable
950 struct Output_Compare_Strncmp : public Output_Compare
952 virtual void output_comparison (const Output_Expr& expr1,
953 const Output_Expr& expr2) const;
954 Output_Compare_Strncmp () {}
955 virtual ~Output_Compare_Strncmp () {}
958 void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
959 const Output_Expr& expr2) const
961 T (Trace t ("Output_Compare_Strncmp::output_comparison");)
963 expr1.output_expr ();
965 expr2.output_expr ();
966 printf (" && !strncmp (");
967 expr1.output_expr ();
969 expr2.output_expr ();
970 printf (" + 1, len - 1) && ");
971 expr2.output_expr ();
972 printf ("[len] == '\\0'");
975 /* This class outputs a comparison using memcmp.
976 Note that the length of expr1 (available through the local variable `len')
977 must be verified to be equal to the length of expr2 prior to this
980 struct Output_Compare_Memcmp : public Output_Compare
982 virtual void output_comparison (const Output_Expr& expr1,
983 const Output_Expr& expr2) const;
984 Output_Compare_Memcmp () {}
985 virtual ~Output_Compare_Memcmp () {}
988 void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
989 const Output_Expr& expr2) const
991 T (Trace t ("Output_Compare_Memcmp::output_comparison");)
993 expr1.output_expr ();
995 expr2.output_expr ();
996 printf (" && !memcmp (");
997 expr1.output_expr ();
999 expr2.output_expr ();
1000 printf (" + 1, len - 1)");
1003 /* ------------------------------------------------------------------------- */
1005 /* Generates C code for the hash function that returns the
1006 proper encoding for each key word. */
1009 Key_List::output_hash_function (void)
1011 T (Trace t ("Key_List::output_hash_function");)
1012 const int max_column = 10;
1015 /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
1017 for (int trunc = max_hash_value; (trunc /= 10) > 0;)
1020 /* Output the function's head. */
1021 if (option[CPLUSPLUS])
1023 else if (option[KRC] | option[C] | option[ANSIC])
1024 printf ("#ifdef __GNUC__\n"
1027 "#ifdef __cplusplus\n"
1032 if (option[KRC] | option[C] | option[ANSIC])
1034 printf ("unsigned int\n");
1035 if (option[CPLUSPLUS])
1036 printf ("%s::", option.get_class_name ());
1037 printf ("%s ", option.get_hash_name ());
1038 printf (option[KRC] ?
1040 " register char *str;\n"
1041 " register unsigned int len;\n" :
1044 " register const char *str;\n"
1045 " register unsigned int len;\n" :
1046 option[ANSIC] | option[CPLUSPLUS] ?
1047 "(register const char *str, register unsigned int len)\n" :
1050 /* Note that when the hash function is called, it has already been verified
1051 that min_key_len <= len <= max_key_len. */
1053 /* Output the function's body. */
1056 /* First the asso_values array. */
1057 printf (" static %s%s asso_values[] =\n"
1059 const_readonly_array,
1060 smallest_integral_type (max_hash_value + 1));
1062 for (int count = 0; count < ALPHA_SIZE; count++)
1066 if (!(count % max_column))
1068 printf ("%*d", field_width,
1069 occurrences[count] ? asso_values[count] : max_hash_value + 1);
1075 /* Optimize special case of ``-k 1,$'' */
1076 if (option[DEFAULTCHARS])
1077 printf (" return %sasso_values[%sstr[len - 1]] + asso_values[%sstr[0]];\n",
1078 option[NOLENGTH] ? "" : "len + ",
1079 char_to_index, char_to_index);
1086 /* Get first (also highest) key position. */
1087 key_pos = option.get ();
1089 if (!option[ALLCHARS] && (key_pos == WORD_END || key_pos <= min_key_len))
1091 /* We can perform additional optimizations here:
1092 Write it out as a single expression. Note that the values
1093 are added as `int's even though the asso_values array may
1094 contain `unsigned char's or `unsigned short's. */
1096 printf (" return %s",
1097 option[NOLENGTH] ? "" : "len + ");
1099 for (; key_pos != WORD_END; )
1101 printf ("asso_values[%sstr[%d]]", char_to_index, key_pos - 1);
1102 if ((key_pos = option.get ()) != EOS)
1108 if (key_pos == WORD_END)
1109 printf ("asso_values[%sstr[len - 1]]", char_to_index);
1115 /* We've got to use the correct, but brute force, technique. */
1116 printf (" register int hval = %s;\n\n"
1120 option[NOLENGTH] ? "0" : "len",
1121 option[NOLENGTH] ? "len" : "hval");
1123 /* User wants *all* characters considered in hash. */
1124 if (option[ALLCHARS])
1126 for (int i = max_key_len; i > 0; i--)
1127 printf (" case %d:\n"
1128 " hval += asso_values[%sstr[%d]];\n",
1129 i, char_to_index, i - 1);
1135 else /* do the hard part... */
1137 while (key_pos != WORD_END && key_pos > max_key_len)
1138 if ((key_pos = option.get ()) == EOS)
1141 if (key_pos != EOS && key_pos != WORD_END)
1146 for ( ; i >= key_pos; i--)
1147 printf (" case %d:\n", i);
1149 printf (" hval += asso_values[%sstr[%d]];\n",
1150 char_to_index, key_pos - 1);
1152 key_pos = option.get ();
1154 while (key_pos != EOS && key_pos != WORD_END);
1156 for ( ; i >= min_key_len; i--)
1157 printf (" case %d:\n", i);
1163 if (key_pos == WORD_END)
1164 printf (" + asso_values[%sstr[len - 1]]", char_to_index);
1172 /* ------------------------------------------------------------------------- */
1174 /* Prints out a table of keyword lengths, for use with the
1175 comparison code in generated function ``in_word_set''. */
1178 Key_List::output_keylength_table (void)
1180 T (Trace t ("Key_List::output_keylength_table");)
1181 const int columns = 14;
1184 const char *indent = option[GLOBAL] ? "" : " ";
1187 printf ("%sstatic %s%s lengthtable[] =\n%s {",
1188 indent, const_readonly_array,
1189 smallest_integral_type (max_key_len),
1192 /* Generate an array of lengths, similar to output_keyword_table. */
1195 for (temp = head, index = 0; temp; temp = temp->next)
1197 if (option[SWITCH] && !option[TYPE]
1199 || (temp->next && temp->hash_value == temp->next->hash_value)))
1202 if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1204 /* Some blank entries. */
1205 for ( ; index < temp->hash_value; index++)
1209 if ((column++ % columns) == 0)
1210 printf ("\n%s ", indent);
1217 if ((column++ % columns) == 0)
1218 printf("\n%s ", indent);
1219 printf ("%3d", temp->key_length);
1221 /* Deal with links specially. */
1222 if (temp->link) // implies option[DUP]
1223 for (List_Node *links = temp->link; links; links = links->link)
1227 if ((column++ % columns) == 0)
1228 printf("\n%s ", indent);
1229 printf ("%3d", links->key_length);
1235 printf ("\n%s };\n", indent);
1240 /* ------------------------------------------------------------------------- */
1243 output_keyword_entry (List_Node *temp, const char *indent)
1245 printf ("%s ", indent);
1248 output_string (temp->key, temp->key_length);
1251 if (strlen (temp->rest) > 0)
1252 printf (",%s", temp->rest);
1256 printf (" /* hash value = %d, index = %d */",
1257 temp->hash_value, temp->index);
1261 output_keyword_blank_entries (int count, const char *indent)
1266 columns = 58 / (6 + strlen (option.get_initializer_suffix()));
1275 for (int i = 0; i < count; i++)
1277 if ((column % columns) == 0)
1281 printf ("%s ", indent);
1289 printf ("{\"\"%s}", option.get_initializer_suffix());
1296 /* Prints out the array containing the key words for the hash function. */
1299 Key_List::output_keyword_table (void)
1301 T (Trace t ("Key_List::output_keyword_table");)
1302 const char *indent = option[GLOBAL] ? "" : " ";
1306 printf ("%sstatic ",
1308 output_const_type (const_readonly_array, struct_tag);
1311 option.get_wordlist_name (),
1314 /* Generate an array of reserved words at appropriate locations. */
1316 for (temp = head, index = 0; temp; temp = temp->next)
1318 if (option[SWITCH] && !option[TYPE]
1320 || (temp->next && temp->hash_value == temp->next->hash_value)))
1326 if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
1328 /* Some blank entries. */
1329 output_keyword_blank_entries (temp->hash_value - index, indent);
1331 index = temp->hash_value;
1334 temp->index = index;
1336 output_keyword_entry (temp, indent);
1338 /* Deal with links specially. */
1339 if (temp->link) // implies option[DUP]
1340 for (List_Node *links = temp->link; links; links = links->link)
1342 links->index = ++index;
1344 output_keyword_entry (links, indent);
1352 printf ("%s };\n\n", indent);
1355 /* ------------------------------------------------------------------------- */
1357 /* Generates the large, sparse table that maps hash values into
1358 the smaller, contiguous range of the keyword table. */
1361 Key_List::output_lookup_array (void)
1363 T (Trace t ("Key_List::output_lookup_array");)
1366 const int DEFAULT_VALUE = -1;
1368 /* Because of the way output_keyword_table works, every duplicate set is
1369 stored contiguously in the wordlist array. */
1370 struct duplicate_entry
1372 int hash_value; /* Hash value for this particular duplicate set. */
1373 int index; /* Index into the main keyword storage array. */
1374 int count; /* Number of consecutive duplicates at this index. */
1377 #if LARGE_STACK_ARRAYS
1378 duplicate_entry duplicates[total_duplicates];
1379 int lookup_array[max_hash_value + 1 + 2*total_duplicates];
1381 // Note: we don't use new, because that invokes a custom operator new.
1382 duplicate_entry *duplicates = (duplicate_entry *)
1383 malloc (total_duplicates * sizeof(duplicate_entry) + 1);
1384 int *lookup_array = (int *)
1385 malloc ((max_hash_value + 1 + 2*total_duplicates) * sizeof(int));
1386 if (duplicates == NULL || lookup_array == NULL)
1389 int lookup_array_size = max_hash_value + 1;
1390 duplicate_entry *dup_ptr = &duplicates[0];
1391 int *lookup_ptr = &lookup_array[max_hash_value + 1 + 2*total_duplicates];
1393 while (lookup_ptr > lookup_array)
1394 *--lookup_ptr = DEFAULT_VALUE;
1396 /* Now dup_ptr = &duplicates[0] and lookup_ptr = &lookup_array[0]. */
1398 for (List_Node *temp = head; temp; temp = temp->next)
1400 int hash_value = temp->hash_value;
1401 lookup_array[hash_value] = temp->index;
1403 fprintf (stderr, "keyword = %.*s, index = %d\n",
1404 temp->key_length, temp->key, temp->index);
1406 || (temp->next && hash_value == temp->next->hash_value))
1408 /* Start a duplicate entry. */
1409 dup_ptr->hash_value = hash_value;
1410 dup_ptr->index = temp->index;
1415 for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
1420 "static linked keyword = %.*s, index = %d\n",
1421 ptr->key_length, ptr->key, ptr->index);
1424 if (!(temp->next && hash_value == temp->next->hash_value))
1431 fprintf (stderr, "dynamic linked keyword = %.*s, index = %d\n",
1432 temp->key_length, temp->key, temp->index);
1434 assert (dup_ptr->count >= 2);
1439 while (dup_ptr > duplicates)
1445 "dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n",
1446 dup_ptr - duplicates,
1447 dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
1450 /* Start searching for available space towards the right part
1451 of the lookup array. */
1452 for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
1453 if (lookup_array[i] == DEFAULT_VALUE
1454 && lookup_array[i + 1] == DEFAULT_VALUE)
1456 /* If we didn't find it to the right look to the left instead... */
1457 for (i = dup_ptr->hash_value-1; i >= 0; i--)
1458 if (lookup_array[i] == DEFAULT_VALUE
1459 && lookup_array[i + 1] == DEFAULT_VALUE)
1461 /* Append to the end of lookup_array. */
1462 i = lookup_array_size;
1463 lookup_array_size += 2;
1465 /* Put in an indirection from dup_ptr->hash_value to i.
1466 At i and i+1 store dup_ptr->index and dup_ptr->count. */
1467 assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
1468 lookup_array[dup_ptr->hash_value] = - 1 - total_keys - i;
1469 lookup_array[i] = - total_keys + dup_ptr->index;
1470 lookup_array[i + 1] = - dup_ptr->count;
1471 /* All these three values are <= -2, distinct from DEFAULT_VALUE. */
1474 /* The values of the lookup array are now known. */
1478 lookup_ptr = lookup_array + lookup_array_size;
1479 while (lookup_ptr > lookup_array)
1481 int val = *--lookup_ptr;
1488 const char *indent = option[GLOBAL] ? "" : " ";
1489 printf ("%sstatic %s%s lookup[] =\n"
1491 indent, const_readonly_array, smallest_integral_type (min, max),
1495 /* Calculate maximum number of digits required for MIN..MAX. */
1498 for (int trunc = max; (trunc /= 10) > 0;)
1503 int neg_field_width = 2;
1504 for (int trunc = -min; (trunc /= 10) > 0;)
1506 neg_field_width++; /* account for the minus sign */
1507 if (field_width < neg_field_width)
1508 field_width = neg_field_width;
1511 const int columns = 42 / field_width;
1515 for (int i = 0; i < lookup_array_size; i++)
1519 if ((column++ % columns) == 0)
1520 printf("\n%s ", indent);
1521 printf ("%*d", field_width, lookup_array[i]);
1523 printf ("\n%s };\n\n", indent);
1525 #if !LARGE_STACK_ARRAYS
1526 free ((char *) duplicates);
1527 free ((char *) lookup_array);
1532 /* ------------------------------------------------------------------------- */
1534 /* Generate all the tables needed for the lookup function. */
1537 Key_List::output_lookup_tables (void)
1539 T (Trace t ("Key_List::output_lookup_tables");)
1543 /* Use the switch in place of lookup table. */
1544 if (option[LENTABLE] && (option[DUP] && total_duplicates > 0))
1545 output_keylength_table ();
1546 if (option[TYPE] || (option[DUP] && total_duplicates > 0))
1547 output_keyword_table ();
1551 /* Use the lookup table, in place of switch. */
1552 if (option[LENTABLE])
1553 output_keylength_table ();
1554 output_keyword_table ();
1555 output_lookup_array ();
1559 /* ------------------------------------------------------------------------- */
1561 /* Output a single switch case (including duplicates). Advance list. */
1564 output_switch_case (List_Node *list, int indent, int *jumps_away)
1566 T (Trace t ("output_switch_case");)
1569 printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
1570 indent, "", list->hash_value, list->key_length, list->key);
1574 || (list->next && list->hash_value == list->next->hash_value)))
1576 if (option[LENTABLE])
1577 printf ("%*slengthptr = &lengthtable[%d];\n",
1578 indent, "", list->index);
1579 printf ("%*swordptr = &%s[%d];\n",
1580 indent, "", option.get_wordlist_name (), list->index);
1583 for (List_Node *temp = list; ; temp = temp->next)
1585 for (List_Node *links = temp; links; links = links->link)
1587 if (!(temp->next && temp->hash_value == temp->next->hash_value))
1591 printf ("%*swordendptr = wordptr + %d;\n"
1592 "%*sgoto multicompare;\n",
1599 if (option[LENTABLE])
1601 printf ("%*sif (len == %d)\n"
1603 indent, "", list->key_length,
1607 printf ("%*sresword = ",
1610 printf ("&%s[%d]", option.get_wordlist_name (), list->index);
1612 output_string (list->key, list->key_length);
1614 printf ("%*sgoto compare;\n",
1616 if (option[LENTABLE])
1626 while (list->next && list->hash_value == list->next->hash_value)
1632 /* Output a total of size cases, grouped into num_switches switch statements,
1633 where 0 < num_switches <= size. */
1636 output_switches (List_Node *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
1638 T (Trace t ("output_switches");)
1641 printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
1642 indent, "", min_hash_value, max_hash_value, size);
1644 if (num_switches > 1)
1646 int part1 = num_switches / 2;
1647 int part2 = num_switches - part1;
1648 int size1 = (int)((double)size / (double)num_switches * (double)part1 + 0.5);
1649 int size2 = size - size1;
1651 List_Node *temp = list;
1652 for (int count = size1; count > 0; count--)
1654 while (temp->hash_value == temp->next->hash_value)
1659 printf ("%*sif (key < %d)\n"
1661 indent, "", temp->hash_value,
1664 output_switches (list, part1, size1, min_hash_value, temp->hash_value-1, indent+4);
1669 indent, "", indent, "", indent, "");
1671 output_switches (temp, part2, size2, temp->hash_value, max_hash_value, indent+4);
1678 /* Output a single switch. */
1679 int lowest_case_value = list->hash_value;
1683 assert (min_hash_value <= lowest_case_value);
1684 assert (lowest_case_value <= max_hash_value);
1685 if (min_hash_value == max_hash_value)
1686 output_switch_case (list, indent, &jumps_away);
1689 printf ("%*sif (key == %d)\n"
1691 indent, "", lowest_case_value,
1693 output_switch_case (list, indent+4, &jumps_away);
1700 if (lowest_case_value == 0)
1701 printf ("%*sswitch (key)\n", indent, "");
1703 printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
1706 for (; size > 0; size--)
1709 printf ("%*s case %d:\n",
1710 indent, "", list->hash_value - lowest_case_value);
1711 list = output_switch_case (list, indent+6, &jumps_away);
1713 printf ("%*s break;\n",
1722 /* Generates C code to perform the keyword lookup. */
1725 Key_List::output_lookup_function_body (const Output_Compare& comparison)
1727 T (Trace t ("Key_List::output_lookup_function_body");)
1729 printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
1731 " register int key = %s (str, len);\n\n",
1732 option.get_hash_name ());
1736 int switch_size = num_hash_values ();
1737 int num_switches = option.get_total_switches ();
1738 if (num_switches > switch_size)
1739 num_switches = switch_size;
1741 printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
1745 if (option[LENTABLE])
1746 printf (" register %s%s *lengthptr;\n",
1747 const_always, smallest_integral_type (max_key_len));
1748 printf (" register ");
1749 output_const_type (const_readonly_array, struct_tag);
1750 printf ("*wordptr;\n");
1751 printf (" register ");
1752 output_const_type (const_readonly_array, struct_tag);
1753 printf ("*wordendptr;\n");
1757 printf (" register ");
1758 output_const_type (const_readonly_array, struct_tag);
1759 printf ("*resword;\n\n");
1762 printf (" register %sresword;\n\n",
1765 output_switches (head, num_switches, switch_size, min_hash_value, max_hash_value, 10);
1770 printf ("%*s return 0;\n"
1771 "%*smulticompare:\n"
1772 "%*s while (wordptr < wordendptr)\n"
1774 indent, "", indent, "", indent, "", indent, "");
1775 if (option[LENTABLE])
1777 printf ("%*s if (len == *lengthptr)\n"
1779 indent, "", indent, "");
1782 printf ("%*s register %schar *s = ",
1783 indent, "", const_always);
1785 printf ("wordptr->%s", option.get_key_name ());
1787 printf ("*wordptr");
1791 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1795 option[TYPE] ? "wordptr" : "s");
1796 if (option[LENTABLE])
1802 if (option[LENTABLE])
1803 printf ("%*s lengthptr++;\n",
1805 printf ("%*s wordptr++;\n"
1807 indent, "", indent, "");
1809 printf (" return 0;\n"
1814 " register %schar *s = resword->%s;\n\n"
1816 const_always, option.get_key_name ());
1817 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1819 " return resword;\n"
1825 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
1827 " return resword;\n");
1833 printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n");
1839 "%*s register int index = lookup[key];\n\n"
1840 "%*s if (index >= 0)\n",
1841 indent, "", indent, "", indent, "");
1842 if (option[LENTABLE])
1845 "%*s if (len == lengthtable[index])\n",
1846 indent, "", indent, "");
1850 "%*s register %schar *s = %s[index]",
1852 indent, "", const_always, option.get_wordlist_name ());
1854 printf (".%s", option.get_key_name ());
1858 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1863 printf ("&%s[index]", option.get_wordlist_name ());
1869 if (option[LENTABLE])
1872 printf ("%*s }\n", indent, "");
1874 if (total_duplicates > 0)
1876 printf ("%*s else if (index < -TOTAL_KEYWORDS)\n"
1878 "%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
1879 indent, "", indent, "", indent, "");
1880 if (option[LENTABLE])
1881 printf ("%*s register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n",
1882 indent, "", const_always, smallest_integral_type (max_key_len));
1883 printf ("%*s register ",
1885 output_const_type (const_readonly_array, struct_tag);
1886 printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
1887 option.get_wordlist_name ());
1888 printf ("%*s register ",
1890 output_const_type (const_readonly_array, struct_tag);
1891 printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
1892 printf ("%*s while (wordptr < wordendptr)\n"
1894 indent, "", indent, "");
1895 if (option[LENTABLE])
1897 printf ("%*s if (len == *lengthptr)\n"
1899 indent, "", indent, "");
1902 printf ("%*s register %schar *s = ",
1903 indent, "", const_always);
1905 printf ("wordptr->%s", option.get_key_name ());
1907 printf ("*wordptr");
1911 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1915 option[TYPE] ? "wordptr" : "s");
1916 if (option[LENTABLE])
1922 if (option[LENTABLE])
1923 printf ("%*s lengthptr++;\n",
1925 printf ("%*s wordptr++;\n"
1928 indent, "", indent, "", indent, "");
1936 if (option[LENTABLE])
1938 printf ("%*sif (len == lengthtable[key])\n",
1944 "%*s register %schar *s = %s[key]",
1946 indent, "", const_always, option.get_wordlist_name ());
1949 printf (".%s", option.get_key_name ());
1954 comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
1959 printf ("&%s[key]", option.get_wordlist_name ());
1971 /* Generates C code for the lookup function. */
1974 Key_List::output_lookup_function (void)
1976 T (Trace t ("Key_List::output_lookup_function");)
1978 /* Output the function's head. */
1979 if (option[KRC] | option[C] | option[ANSIC])
1980 printf ("#ifdef __GNUC__\n"
1985 const_for_struct, return_type);
1986 if (option[CPLUSPLUS])
1987 printf ("%s::", option.get_class_name ());
1988 printf ("%s ", option.get_function_name ());
1989 printf (option[KRC] ?
1991 " register char *str;\n"
1992 " register unsigned int len;\n" :
1995 " register const char *str;\n"
1996 " register unsigned int len;\n" :
1997 option[ANSIC] | option[CPLUSPLUS] ?
1998 "(register const char *str, register unsigned int len)\n" :
2001 /* Output the function's body. */
2004 if (option[ENUM] && !option[GLOBAL])
2006 Output_Enum style (" ");
2007 output_constants (style);
2010 if (!option[GLOBAL])
2011 output_lookup_tables ();
2013 if (option[LENTABLE])
2014 output_lookup_function_body (Output_Compare_Memcmp ());
2018 output_lookup_function_body (Output_Compare_Strncmp ());
2020 output_lookup_function_body (Output_Compare_Strcmp ());
2026 /* ------------------------------------------------------------------------- */
2028 /* Generates the hash function and the key word recognizer function
2029 based upon the user's Options. */
2032 Key_List::output (void)
2034 T (Trace t ("Key_List::output");)
2038 if (option[C] | option[ANSIC] | option[CPLUSPLUS])
2040 const_always = "const ";
2041 const_readonly_array = (option[CONST] ? "const " : "");
2042 const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : "");
2047 const_readonly_array = "";
2048 const_for_struct = "";
2053 return_type = (const_always[0] ? "const char *" : "char *");
2054 struct_tag = (const_always[0] ? "const char *" : "char *");
2057 char_to_index = (option[SEVENBIT] ? "" : "(unsigned char)");
2064 else if (option[ANSIC])
2066 else if (option[CPLUSPLUS])
2068 printf (" code produced by gperf version %s */\n", version_string);
2069 Options::print_options ();
2071 printf ("%s\n", include_src);
2073 if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
2074 printf ("%s;\n", array_type);
2076 if (option[INCLUDE])
2077 printf ("#include <string.h>\n"); /* Declare strlen(), strcmp(), strncmp(). */
2081 Output_Defines style;
2082 output_constants (style);
2084 else if (option[GLOBAL])
2086 Output_Enum style ("");
2087 output_constants (style);
2090 printf ("/* maximum key range = %d, duplicates = %d */\n\n",
2091 max_hash_value - min_hash_value + 1, total_duplicates);
2093 if (option[CPLUSPLUS])
2094 printf ("class %s\n"
2097 " static inline unsigned int %s (const char *str, unsigned int len);\n"
2099 " static %s%s%s (const char *str, unsigned int len);\n"
2102 option.get_class_name (), option.get_hash_name (),
2103 const_for_struct, return_type, option.get_function_name ());
2105 output_hash_function ();
2108 output_lookup_tables ();
2110 output_lookup_function ();
2112 if (additional_code)
2113 for (int c; (c = getchar ()) != EOF; putchar (c))
2119 /* ========================= End of Output routines ========================= */
2121 /* Sorts the keys by hash value. */
2124 Key_List::sort (void)
2126 T (Trace t ("Key_List::sort");)
2128 occurrence_sort = 0;
2130 head = merge_sort (head);
2133 /* Dumps the key list to stderr stream. */
2138 T (Trace t ("Key_List::dump");)
2139 int field_width = option.get_max_keysig_size ();
2141 fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
2142 field_width, "char_set");
2144 for (List_Node *ptr = head; ptr; ptr = ptr->next)
2145 fprintf (stderr, "%11d,%11d,%6d, %*.*s, %.*s\n",
2146 ptr->hash_value, ptr->key_length, ptr->index,
2147 field_width, ptr->char_set_length, ptr->char_set,
2148 ptr->key_length, ptr->key);
2151 /* Simple-minded constructor action here... */
2153 Key_List::Key_List (void)
2155 T (Trace t ("Key_List::Key_List");)
2157 max_key_len = INT_MIN;
2158 min_key_len = INT_MAX;
2163 total_duplicates = 0;
2164 additional_code = 0;
2167 /* Returns the length of entire key list. */
2170 Key_List::keyword_list_length (void)
2172 T (Trace t ("Key_List::keyword_list_length");)
2176 /* Returns length of longest key read. */
2179 Key_List::max_key_length (void)
2181 T (Trace t ("Key_List::max_key_length");)