#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>
#include <limits.h>
#include "options.h"
#include "read-line.h"
#include "hash-table.h"
#include "key-list.h"
#include "trace.h"
#include "version.h"
static const int TABLE_MULTIPLE = 10;
#define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
int Key_List::determined[MAX_ALPHA_SIZE];
Key_List::~Key_List (void)
{
T (Trace t ("Key_List::~Key_List");)
if (option[DEBUG])
{
fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d"
"\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n",
list_len, total_keys, total_duplicates, max_key_len);
dump ();
fprintf (stderr, "End dumping list.\n\n");
}
}
const char *
Key_List::get_special_input (char delimiter)
{
T (Trace t ("Key_List::get_special_input");)
int size = 80;
char *buf = new char[size];
int c, i;
for (i = 0; (c = getchar ()) != EOF; i++)
{
if (c == '%')
{
if ((c = getchar ()) == delimiter)
{
while ((c = getchar ()) != '\n')
;
if (i == 0)
return "";
else
{
buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
return buf;
}
}
else
buf[i++] = '%';
}
else if (i >= size)
{
char *temp = new char[size *= 2];
int j;
for (j = 0; j < i; j++)
temp[j] = buf[j];
buf = temp;
}
buf[i] = c;
}
return 0;
}
const char *
Key_List::save_include_src (void)
{
T (Trace t ("Key_List::save_include_src");)
int c;
if ((c = getchar ()) != '%')
ungetc (c, stdin);
else if ((c = getchar ()) != '{')
{
fprintf (stderr, "internal error, %c != '{' on line %d in file %s", c, __LINE__, __FILE__);
exit (1);
}
else
return get_special_input ('}');
return "";
}
const char *
Key_List::get_array_type (void)
{
T (Trace t ("Key_List::get_array_type");)
return get_special_input ('%');
}
#ifndef strcspn
inline int
Key_List::strcspn (const char *s, const char *reject)
{
T (Trace t ("Key_List::strcspn");)
const char *scan;
const char *rej_scan;
int count = 0;
for (scan = s; *scan; scan++)
{
for (rej_scan = reject; *rej_scan; rej_scan++)
if (*scan == *rej_scan)
return count;
count++;
}
return count;
}
#endif
void
Key_List::set_output_types (void)
{
T (Trace t ("Key_List::set_output_types");)
if (option[TYPE])
{
array_type = get_array_type ();
if (!array_type)
return;
int i = strcspn (array_type, "{\n\0");
while (i > 0 && strchr (" \t", array_type[i-1]))
i--;
int struct_tag_length = i;
char *structtag = new char[struct_tag_length + 1];
strncpy (structtag, array_type, struct_tag_length);
structtag[struct_tag_length] = '\0';
struct_tag = structtag;
char *rettype = new char[struct_tag_length + 3];
strncpy (rettype, array_type, struct_tag_length);
rettype[struct_tag_length] = ' ';
rettype[struct_tag_length + 1] = '*';
rettype[struct_tag_length + 2] = '\0';
return_type = rettype;
}
}
static List_Node *
parse_line (const char *line, const char *delimiters)
{
if (*line == '"')
{
char *key = new char[strlen(line)];
char *kp = key;
const char *lp = line + 1;
for (; *lp;)
{
char c = *lp;
if (c == '\0')
{
fprintf (stderr, "unterminated string: %s\n", line);
exit (1);
}
else if (c == '\\')
{
c = *++lp;
switch (c)
{
case '0': case '1': case '2': case '3':
case '4': case '5': case '6': case '7':
{
int code = 0;
int count = 0;
while (count < 3 && *lp >= '0' && *lp <= '7')
{
code = (code << 3) + (*lp - '0');
lp++;
count++;
}
if (code > UCHAR_MAX)
fprintf (stderr, "octal escape out of range: %s\n", line);
*kp = (char) code;
break;
}
case 'x':
{
int code = 0;
int count = 0;
lp++;
while ((*lp >= '0' && *lp <= '9')
|| (*lp >= 'A' && *lp <= 'F')
|| (*lp >= 'a' && *lp <= 'f'))
{
code = (code << 4)
+ (*lp >= 'A' && *lp <= 'F' ? *lp - 'A' + 10 :
*lp >= 'a' && *lp <= 'f' ? *lp - 'a' + 10 :
*lp - '0');
lp++;
count++;
}
if (count == 0)
fprintf (stderr, "hexadecimal escape without any hex digits: %s\n", line);
if (code > UCHAR_MAX)
fprintf (stderr, "hexadecimal escape out of range: %s\n", line);
*kp = (char) code;
break;
}
case '\\': case '\'': case '"':
*kp = c;
lp++;
break;
case 'n':
*kp = '\n';
lp++;
break;
case 't':
*kp = '\t';
lp++;
break;
case 'r':
*kp = '\r';
lp++;
break;
case 'f':
*kp = '\f';
lp++;
break;
case 'b':
*kp = '\b';
lp++;
break;
case 'a':
*kp = '\a';
lp++;
break;
case 'v':
*kp = '\v';
lp++;
break;
default:
fprintf (stderr, "invalid escape sequence in string: %s\n", line);
exit (1);
}
}
else if (c == '"')
break;
else
{
*kp = c;
lp++;
}
kp++;
}
lp++;
if (*lp != '\0')
{
if (strchr (delimiters, *lp) == NULL)
{
fprintf (stderr, "string not followed by delimiter: %s\n", line);
exit (1);
}
lp++;
}
return new List_Node (key, kp - key, option[TYPE] ? lp : "");
}
else
{
int len = strcspn (line, delimiters);
const char *rest;
if (line[len] == '\0')
rest = "";
else
rest = &line[len + 1];
return new List_Node (line, len, option[TYPE] ? rest : "");
}
}
void
Key_List::read_keys (void)
{
T (Trace t ("Key_List::read_keys");)
char *ptr;
include_src = save_include_src ();
set_output_types ();
if (! (ptr = Read_Line::get_line ()))
{
fprintf (stderr, "No words in input file, did you forget to prepend %s or use -t accidentally?\n", "%%");
exit (1);
}
else
{
const char *delimiter = option.get_delimiter ();
List_Node *temp, *trail = 0;
head = parse_line (ptr, delimiter);
for (temp = head;
(ptr = Read_Line::get_line ()) && strcmp (ptr, "%%");
temp = temp->next)
{
temp->next = parse_line (ptr, delimiter);
total_keys++;
}
if (ptr)
additional_code = 1;
int table_size = (list_len = total_keys) * TABLE_MULTIPLE;
#if LARGE_STACK_ARRAYS
List_Node *table[POW (table_size)];
#else
int malloc_size = POW (table_size) * sizeof(List_Node*);
if (malloc_size == 0) malloc_size = 1;
List_Node **table = (List_Node**)malloc(malloc_size);
if (table == NULL)
abort ();
#endif
Hash_Table found_link (table, table_size, option[NOLENGTH]);
for (temp = head; temp; temp = temp->next)
{
List_Node *ptr = found_link.insert (temp);
if (ptr)
{
total_duplicates++;
list_len--;
trail->next = temp->next;
temp->link = ptr->link;
ptr->link = temp;
if (!option[DUP] || option[DEBUG])
fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"%.*s\".\n",
temp->key_length, temp->key,
ptr->key_length, ptr->key,
temp->char_set_length, temp->char_set);
}
else
trail = temp;
if (max_key_len < temp->key_length)
max_key_len = temp->key_length;
if (min_key_len > temp->key_length)
min_key_len = temp->key_length;
}
#if !LARGE_STACK_ARRAYS
free ((char *) table);
#endif
if (total_duplicates)
{
if (option[DUP])
fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n",
total_duplicates);
else
{
fprintf (stderr, "%d input keys have identical hash values,\ntry different key positions or use option -D.\n",
total_duplicates);
exit (1);
}
}
if (min_key_len == 0)
{
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");
exit (1);
}
if (option[ALLCHARS])
option.set_keysig_size (max_key_len);
}
}
List_Node *
Key_List::merge (List_Node *list1, List_Node *list2)
{
T (Trace t ("Key_List::merge");)
List_Node *result;
List_Node **resultp = &result;
for (;;)
{
if (!list1)
{
*resultp = list2;
break;
}
if (!list2)
{
*resultp = list1;
break;
}
if (occurrence_sort && list1->occurrence < list2->occurrence
|| hash_sort && list1->hash_value > list2->hash_value)
{
*resultp = list2;
resultp = &list2->next; list2 = list1; list1 = *resultp;
}
else
{
*resultp = list1;
resultp = &list1->next; list1 = *resultp;
}
}
return result;
}
List_Node *
Key_List::merge_sort (List_Node *head)
{
T (Trace t ("Key_List::merge_sort");)
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 = 0;
return merge (merge_sort (head), merge_sort (temp));
}
}
inline int
Key_List::get_occurrence (List_Node *ptr)
{
T (Trace t ("Key_List::get_occurrence");)
int value = 0;
const char *p = ptr->char_set;
unsigned int i = ptr->char_set_length;
for (; i > 0; p++, i--)
value += occurrences[(unsigned char)(*p)];
return value;
}
inline void
Key_List::set_determined (List_Node *ptr)
{
T (Trace t ("Key_List::set_determined");)
const char *p = ptr->char_set;
unsigned int i = ptr->char_set_length;
for (; i > 0; p++, i--)
determined[(unsigned char)(*p)] = 1;
}
inline int
Key_List::already_determined (List_Node *ptr)
{
T (Trace t ("Key_List::already_determined");)
int is_determined = 1;
const char *p = ptr->char_set;
unsigned int i = ptr->char_set_length;
for (; is_determined && i > 0; p++, i--)
is_determined = determined[(unsigned char)(*p)];
return is_determined;
}
void
Key_List::reorder (void)
{
T (Trace t ("Key_List::reorder");)
List_Node *ptr;
for (ptr = head; ptr; ptr = ptr->next)
ptr->occurrence = get_occurrence (ptr);
hash_sort = 0;
occurrence_sort = 1;
for (ptr = head = merge_sort (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;
}
}
}
}
static const char *const_always;
static const char *const_readonly_array;
static const char *const_for_struct;
static const char *
smallest_integral_type (int n)
{
if (n <= UCHAR_MAX) return "unsigned char";
if (n <= USHRT_MAX) return "unsigned short";
return "unsigned int";
}
static const char *
smallest_integral_type (int min, int max)
{
if (option[ANSIC] | option[CPLUSPLUS])
if (min >= SCHAR_MIN && max <= SCHAR_MAX) return "signed char";
if (min >= SHRT_MIN && max <= SHRT_MAX) return "short";
return "int";
}
static const char *char_to_index;
void
Key_List::compute_min_max (void)
{
T (Trace t ("Key_List::compute_min_max");)
List_Node *temp;
for (temp = head; temp->next; temp = temp->next)
;
min_hash_value = head->hash_value;
max_hash_value = temp->hash_value;
}
int
Key_List::num_hash_values (void)
{
T (Trace t ("Key_List::num_hash_values");)
int count = 1;
List_Node *temp;
int value;
for (temp = head, value = temp->hash_value; temp->next; )
{
temp = temp->next;
if (value != temp->hash_value)
{
value = temp->hash_value;
count++;
}
}
return count;
}
struct Output_Constants
{
virtual void output_start () = 0;
virtual void output_item (const char *name, int value) = 0;
virtual void output_end () = 0;
Output_Constants () {}
virtual ~Output_Constants () {}
};
struct Output_Defines : public Output_Constants
{
virtual void output_start ();
virtual void output_item (const char *name, int value);
virtual void output_end ();
Output_Defines () {}
virtual ~Output_Defines () {}
};
void Output_Defines::output_start ()
{
T (Trace t ("Output_Defines::output_start");)
printf ("\n");
}
void Output_Defines::output_item (const char *name, int value)
{
T (Trace t ("Output_Defines::output_item");)
printf ("#define %s %d\n", name, value);
}
void Output_Defines::output_end ()
{
T (Trace t ("Output_Defines::output_end");)
}
struct Output_Enum : public Output_Constants
{
virtual void output_start ();
virtual void output_item (const char *name, int value);
virtual void output_end ();
Output_Enum (const char *indent) : indentation (indent) {}
virtual ~Output_Enum () {}
private:
const char *indentation;
int pending_comma;
};
void Output_Enum::output_start ()
{
T (Trace t ("Output_Enum::output_start");)
printf ("%senum\n"
"%s {\n",
indentation, indentation);
pending_comma = 0;
}
void Output_Enum::output_item (const char *name, int value)
{
T (Trace t ("Output_Enum::output_item");)
if (pending_comma)
printf (",\n");
printf ("%s %s = %d", indentation, name, value);
pending_comma = 1;
}
void Output_Enum::output_end ()
{
T (Trace t ("Output_Enum::output_end");)
if (pending_comma)
printf ("\n");
printf ("%s };\n\n", indentation);
}
void
Key_List::output_constants (struct Output_Constants& style)
{
T (Trace t ("Key_List::output_constants");)
style.output_start ();
style.output_item ("TOTAL_KEYWORDS", total_keys);
style.output_item ("MIN_WORD_LENGTH", min_key_len);
style.output_item ("MAX_WORD_LENGTH", max_key_len);
style.output_item ("MIN_HASH_VALUE", min_hash_value);
style.output_item ("MAX_HASH_VALUE", max_hash_value);
style.output_end ();
}
static void
output_string (const char *key, int len)
{
T (Trace t ("output_string");)
putchar ('"');
for (; len > 0; len--)
{
unsigned char c = (unsigned char) *key++;
if (isprint (c))
{
if (c == '"' || c == '\\')
putchar ('\\');
putchar (c);
}
else
{
putchar ('\\');
putchar ('0' + ((c >> 6) & 7));
putchar ('0' + ((c >> 3) & 7));
putchar ('0' + (c & 7));
}
}
putchar ('"');
}
static void
output_const_type (const char *const_string, const char *type_string)
{
if (type_string[strlen(type_string)-1] == '*')
printf ("%s %s", type_string, const_string);
else
printf ("%s%s ", const_string, type_string);
}
struct Output_Expr
{
virtual void output_expr () const = 0;
Output_Expr () {}
virtual ~Output_Expr () {}
};
struct Output_Expr1 : public Output_Expr
{
virtual void output_expr () const;
Output_Expr1 (const char *piece1) : p1 (piece1) {}
virtual ~Output_Expr1 () {}
private:
const char *p1;
};
void Output_Expr1::output_expr () const
{
T (Trace t ("Output_Expr1::output_expr");)
printf ("%s", p1);
}
#if 0
struct Output_Expr2 : public Output_Expr
{
virtual void output_expr () const;
Output_Expr2 (const char *piece1, const char *piece2)
: p1 (piece1), p2 (piece2) {}
virtual ~Output_Expr2 () {}
private:
const char *p1;
const char *p2;
};
void Output_Expr2::output_expr () const
{
T (Trace t ("Output_Expr2::output_expr");)
printf ("%s%s", p1, p2);
}
#endif
struct Output_Compare
{
virtual void output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const = 0;
Output_Compare () {}
virtual ~Output_Compare () {}
};
struct Output_Compare_Strcmp : public Output_Compare
{
virtual void output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const;
Output_Compare_Strcmp () {}
virtual ~Output_Compare_Strcmp () {}
};
void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const
{
T (Trace t ("Output_Compare_Strcmp::output_comparison");)
printf ("*");
expr1.output_expr ();
printf (" == *");
expr2.output_expr ();
printf (" && !strcmp (");
expr1.output_expr ();
printf (" + 1, ");
expr2.output_expr ();
printf (" + 1)");
}
struct Output_Compare_Strncmp : public Output_Compare
{
virtual void output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const;
Output_Compare_Strncmp () {}
virtual ~Output_Compare_Strncmp () {}
};
void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const
{
T (Trace t ("Output_Compare_Strncmp::output_comparison");)
printf ("*");
expr1.output_expr ();
printf (" == *");
expr2.output_expr ();
printf (" && !strncmp (");
expr1.output_expr ();
printf (" + 1, ");
expr2.output_expr ();
printf (" + 1, len - 1) && ");
expr2.output_expr ();
printf ("[len] == '\\0'");
}
struct Output_Compare_Memcmp : public Output_Compare
{
virtual void output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const;
Output_Compare_Memcmp () {}
virtual ~Output_Compare_Memcmp () {}
};
void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
const Output_Expr& expr2) const
{
T (Trace t ("Output_Compare_Memcmp::output_comparison");)
printf ("*");
expr1.output_expr ();
printf (" == *");
expr2.output_expr ();
printf (" && !memcmp (");
expr1.output_expr ();
printf (" + 1, ");
expr2.output_expr ();
printf (" + 1, len - 1)");
}
void
Key_List::output_hash_function (void)
{
T (Trace t ("Key_List::output_hash_function");)
const int max_column = 10;
int field_width;
field_width = 2;
for (int trunc = max_hash_value; (trunc /= 10) > 0;)
field_width++;
if (option[CPLUSPLUS])
printf ("inline ");
else if (option[KRC] | option[C] | option[ANSIC])
printf ("#ifdef __GNUC__\n"
"__inline\n"
"#else\n"
"#ifdef __cplusplus\n"
"inline\n"
"#endif\n"
"#endif\n");
if (option[KRC] | option[C] | option[ANSIC])
printf ("static ");
printf ("unsigned int\n");
if (option[CPLUSPLUS])
printf ("%s::", option.get_class_name ());
printf ("%s ", option.get_hash_name ());
printf (option[KRC] ?
"(str, len)\n"
" register char *str;\n"
" register unsigned int len;\n" :
option[C] ?
"(str, len)\n"
" register const char *str;\n"
" register unsigned int len;\n" :
option[ANSIC] | option[CPLUSPLUS] ?
"(register const char *str, register unsigned int len)\n" :
"");
printf ("{\n");
printf (" static %s%s asso_values[] =\n"
" {",
const_readonly_array,
smallest_integral_type (max_hash_value + 1));
for (int count = 0; count < ALPHA_SIZE; count++)
{
if (count > 0)
printf (",");
if (!(count % max_column))
printf ("\n ");
printf ("%*d", field_width,
occurrences[count] ? asso_values[count] : max_hash_value + 1);
}
printf ("\n"
" };\n");
if (option[DEFAULTCHARS])
printf (" return %sasso_values[%sstr[len - 1]] + asso_values[%sstr[0]];\n",
option[NOLENGTH] ? "" : "len + ",
char_to_index, char_to_index);
else
{
int key_pos;
option.reset ();
key_pos = option.get ();
if (!option[ALLCHARS] && (key_pos == WORD_END || key_pos <= min_key_len))
{
printf (" return %s",
option[NOLENGTH] ? "" : "len + ");
for (; key_pos != WORD_END; )
{
printf ("asso_values[%sstr[%d]]", char_to_index, key_pos - 1);
if ((key_pos = option.get ()) != EOS)
printf (" + ");
else
break;
}
if (key_pos == WORD_END)
printf ("asso_values[%sstr[len - 1]]", char_to_index);
printf (";\n");
}
else
{
printf (" register int hval = %s;\n\n"
" switch (%s)\n"
" {\n"
" default:\n",
option[NOLENGTH] ? "0" : "len",
option[NOLENGTH] ? "len" : "hval");
if (option[ALLCHARS])
{
for (int i = max_key_len; i > 0; i--)
printf (" case %d:\n"
" hval += asso_values[%sstr[%d]];\n",
i, char_to_index, i - 1);
printf (" break;\n"
" }\n"
" return hval;\n");
}
else
{
while (key_pos != WORD_END && key_pos > max_key_len)
if ((key_pos = option.get ()) == EOS)
break;
if (key_pos != EOS && key_pos != WORD_END)
{
int i = key_pos;
do
{
for ( ; i >= key_pos; i--)
printf (" case %d:\n", i);
printf (" hval += asso_values[%sstr[%d]];\n",
char_to_index, key_pos - 1);
key_pos = option.get ();
}
while (key_pos != EOS && key_pos != WORD_END);
for ( ; i >= min_key_len; i--)
printf (" case %d:\n", i);
}
printf (" break;\n"
" }\n"
" return hval");
if (key_pos == WORD_END)
printf (" + asso_values[%sstr[len - 1]]", char_to_index);
printf (";\n");
}
}
}
printf ("}\n\n");
}
void
Key_List::output_keylength_table (void)
{
T (Trace t ("Key_List::output_keylength_table");)
const int columns = 14;
int index;
int column;
const char *indent = option[GLOBAL] ? "" : " ";
List_Node *temp;
printf ("%sstatic %s%s lengthtable[] =\n%s {",
indent, const_readonly_array,
smallest_integral_type (max_key_len),
indent);
column = 0;
for (temp = head, index = 0; temp; temp = temp->next)
{
if (option[SWITCH] && !option[TYPE]
&& !(temp->link
|| (temp->next && temp->hash_value == temp->next->hash_value)))
continue;
if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
{
for ( ; index < temp->hash_value; index++)
{
if (index > 0)
printf (",");
if ((column++ % columns) == 0)
printf ("\n%s ", indent);
printf ("%3d", 0);
}
}
if (index > 0)
printf (",");
if ((column++ % columns) == 0)
printf("\n%s ", indent);
printf ("%3d", temp->key_length);
if (temp->link) for (List_Node *links = temp->link; links; links = links->link)
{
++index;
printf (",");
if ((column++ % columns) == 0)
printf("\n%s ", indent);
printf ("%3d", links->key_length);
}
index++;
}
printf ("\n%s };\n", indent);
if (option[GLOBAL])
printf ("\n");
}
static void
output_keyword_entry (List_Node *temp, const char *indent)
{
printf ("%s ", indent);
if (option[TYPE])
printf ("{");
output_string (temp->key, temp->key_length);
if (option[TYPE])
{
if (strlen (temp->rest) > 0)
printf (",%s", temp->rest);
printf ("}");
}
if (option[DEBUG])
printf (" /* hash value = %d, index = %d */",
temp->hash_value, temp->index);
}
static void
output_keyword_blank_entries (int count, const char *indent)
{
int columns;
if (option[TYPE])
{
columns = 58 / (6 + strlen (option.get_initializer_suffix()));
if (columns == 0)
columns = 1;
}
else
{
columns = 9;
}
int column = 0;
for (int i = 0; i < count; i++)
{
if ((column % columns) == 0)
{
if (i > 0)
printf (",\n");
printf ("%s ", indent);
}
else
{
if (i > 0)
printf (", ");
}
if (option[TYPE])
printf ("{\"\"%s}", option.get_initializer_suffix());
else
printf ("\"\"");
column++;
}
}
void
Key_List::output_keyword_table (void)
{
T (Trace t ("Key_List::output_keyword_table");)
const char *indent = option[GLOBAL] ? "" : " ";
int index;
List_Node *temp;
printf ("%sstatic ",
indent);
output_const_type (const_readonly_array, struct_tag);
printf ("%s[] =\n"
"%s {\n",
option.get_wordlist_name (),
indent);
for (temp = head, index = 0; temp; temp = temp->next)
{
if (option[SWITCH] && !option[TYPE]
&& !(temp->link
|| (temp->next && temp->hash_value == temp->next->hash_value)))
continue;
if (index > 0)
printf (",\n");
if (index < temp->hash_value && !option[SWITCH] && !option[DUP])
{
output_keyword_blank_entries (temp->hash_value - index, indent);
printf (",\n");
index = temp->hash_value;
}
temp->index = index;
output_keyword_entry (temp, indent);
if (temp->link) for (List_Node *links = temp->link; links; links = links->link)
{
links->index = ++index;
printf (",\n");
output_keyword_entry (links, indent);
}
index++;
}
if (index > 0)
printf ("\n");
printf ("%s };\n\n", indent);
}
void
Key_List::output_lookup_array (void)
{
T (Trace t ("Key_List::output_lookup_array");)
if (option[DUP])
{
const int DEFAULT_VALUE = -1;
struct duplicate_entry
{
int hash_value;
int index;
int count;
};
#if LARGE_STACK_ARRAYS
duplicate_entry duplicates[total_duplicates];
int lookup_array[max_hash_value + 1 + 2*total_duplicates];
#else
duplicate_entry *duplicates = (duplicate_entry *)
malloc (total_duplicates * sizeof(duplicate_entry) + 1);
int *lookup_array = (int *)
malloc ((max_hash_value + 1 + 2*total_duplicates) * sizeof(int));
if (duplicates == NULL || lookup_array == NULL)
abort();
#endif
int lookup_array_size = max_hash_value + 1;
duplicate_entry *dup_ptr = &duplicates[0];
int *lookup_ptr = &lookup_array[max_hash_value + 1 + 2*total_duplicates];
while (lookup_ptr > lookup_array)
*--lookup_ptr = DEFAULT_VALUE;
for (List_Node *temp = head; temp; temp = temp->next)
{
int hash_value = temp->hash_value;
lookup_array[hash_value] = temp->index;
if (option[DEBUG])
fprintf (stderr, "keyword = %.*s, index = %d\n",
temp->key_length, temp->key, temp->index);
if (temp->link
|| (temp->next && hash_value == temp->next->hash_value))
{
dup_ptr->hash_value = hash_value;
dup_ptr->index = temp->index;
dup_ptr->count = 1;
for (;;)
{
for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
{
dup_ptr->count++;
if (option[DEBUG])
fprintf (stderr,
"static linked keyword = %.*s, index = %d\n",
ptr->key_length, ptr->key, ptr->index);
}
if (!(temp->next && hash_value == temp->next->hash_value))
break;
temp = temp->next;
dup_ptr->count++;
if (option[DEBUG])
fprintf (stderr, "dynamic linked keyword = %.*s, index = %d\n",
temp->key_length, temp->key, temp->index);
}
assert (dup_ptr->count >= 2);
dup_ptr++;
}
}
while (dup_ptr > duplicates)
{
dup_ptr--;
if (option[DEBUG])
fprintf (stderr,
"dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n",
dup_ptr - duplicates,
dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
int i;
for (i = dup_ptr->hash_value; i < lookup_array_size-1; i++)
if (lookup_array[i] == DEFAULT_VALUE
&& lookup_array[i + 1] == DEFAULT_VALUE)
goto found_i;
for (i = dup_ptr->hash_value-1; i >= 0; i--)
if (lookup_array[i] == DEFAULT_VALUE
&& lookup_array[i + 1] == DEFAULT_VALUE)
goto found_i;
i = lookup_array_size;
lookup_array_size += 2;
found_i:
assert (lookup_array[dup_ptr->hash_value] == dup_ptr->index);
lookup_array[dup_ptr->hash_value] = - 1 - total_keys - i;
lookup_array[i] = - total_keys + dup_ptr->index;
lookup_array[i + 1] = - dup_ptr->count;
}
int min = INT_MAX;
int max = INT_MIN;
lookup_ptr = lookup_array + lookup_array_size;
while (lookup_ptr > lookup_array)
{
int val = *--lookup_ptr;
if (min > val)
min = val;
if (max < val)
max = val;
}
const char *indent = option[GLOBAL] ? "" : " ";
printf ("%sstatic %s%s lookup[] =\n"
"%s {",
indent, const_readonly_array, smallest_integral_type (min, max),
indent);
int field_width;
{
field_width = 2;
for (int trunc = max; (trunc /= 10) > 0;)
field_width++;
}
if (min < 0)
{
int neg_field_width = 2;
for (int trunc = -min; (trunc /= 10) > 0;)
neg_field_width++;
neg_field_width++;
if (field_width < neg_field_width)
field_width = neg_field_width;
}
const int columns = 42 / field_width;
int column;
column = 0;
for (int i = 0; i < lookup_array_size; i++)
{
if (i > 0)
printf (",");
if ((column++ % columns) == 0)
printf("\n%s ", indent);
printf ("%*d", field_width, lookup_array[i]);
}
printf ("\n%s };\n\n", indent);
#if !LARGE_STACK_ARRAYS
free ((char *) duplicates);
free ((char *) lookup_array);
#endif
}
}
void
Key_List::output_lookup_tables (void)
{
T (Trace t ("Key_List::output_lookup_tables");)
if (option[SWITCH])
{
if (option[LENTABLE] && (option[DUP] && total_duplicates > 0))
output_keylength_table ();
if (option[TYPE] || (option[DUP] && total_duplicates > 0))
output_keyword_table ();
}
else
{
if (option[LENTABLE])
output_keylength_table ();
output_keyword_table ();
output_lookup_array ();
}
}
static List_Node *
output_switch_case (List_Node *list, int indent, int *jumps_away)
{
T (Trace t ("output_switch_case");)
if (option[DEBUG])
printf ("%*s/* hash value = %4d, keyword = \"%.*s\" */\n",
indent, "", list->hash_value, list->key_length, list->key);
if (option[DUP]
&& (list->link
|| (list->next && list->hash_value == list->next->hash_value)))
{
if (option[LENTABLE])
printf ("%*slengthptr = &lengthtable[%d];\n",
indent, "", list->index);
printf ("%*swordptr = &%s[%d];\n",
indent, "", option.get_wordlist_name (), list->index);
int count = 0;
for (List_Node *temp = list; ; temp = temp->next)
{
for (List_Node *links = temp; links; links = links->link)
count++;
if (!(temp->next && temp->hash_value == temp->next->hash_value))
break;
}
printf ("%*swordendptr = wordptr + %d;\n"
"%*sgoto multicompare;\n",
indent, "", count,
indent, "");
*jumps_away = 1;
}
else
{
if (option[LENTABLE])
{
printf ("%*sif (len == %d)\n"
"%*s {\n",
indent, "", list->key_length,
indent, "");
indent += 4;
}
printf ("%*sresword = ",
indent, "");
if (option[TYPE])
printf ("&%s[%d]", option.get_wordlist_name (), list->index);
else
output_string (list->key, list->key_length);
printf (";\n");
printf ("%*sgoto compare;\n",
indent, "");
if (option[LENTABLE])
{
indent -= 4;
printf ("%*s }\n",
indent, "");
}
else
*jumps_away = 1;
}
while (list->next && list->hash_value == list->next->hash_value)
list = list->next;
list = list->next;
return list;
}
static void
output_switches (List_Node *list, int num_switches, int size, int min_hash_value, int max_hash_value, int indent)
{
T (Trace t ("output_switches");)
if (option[DEBUG])
printf ("%*s/* know %d <= key <= %d, contains %d cases */\n",
indent, "", min_hash_value, max_hash_value, size);
if (num_switches > 1)
{
int part1 = num_switches / 2;
int part2 = num_switches - part1;
int size1 = (int)((double)size / (double)num_switches * (double)part1 + 0.5);
int size2 = size - size1;
List_Node *temp = list;
for (int count = size1; count > 0; count--)
{
while (temp->hash_value == temp->next->hash_value)
temp = temp->next;
temp = temp->next;
}
printf ("%*sif (key < %d)\n"
"%*s {\n",
indent, "", temp->hash_value,
indent, "");
output_switches (list, part1, size1, min_hash_value, temp->hash_value-1, indent+4);
printf ("%*s }\n"
"%*selse\n"
"%*s {\n",
indent, "", indent, "", indent, "");
output_switches (temp, part2, size2, temp->hash_value, max_hash_value, indent+4);
printf ("%*s }\n",
indent, "");
}
else
{
int lowest_case_value = list->hash_value;
if (size == 1)
{
int jumps_away = 0;
assert (min_hash_value <= lowest_case_value);
assert (lowest_case_value <= max_hash_value);
if (min_hash_value == max_hash_value)
output_switch_case (list, indent, &jumps_away);
else
{
printf ("%*sif (key == %d)\n"
"%*s {\n",
indent, "", lowest_case_value,
indent, "");
output_switch_case (list, indent+4, &jumps_away);
printf ("%*s }\n",
indent, "");
}
}
else
{
if (lowest_case_value == 0)
printf ("%*sswitch (key)\n", indent, "");
else
printf ("%*sswitch (key - %d)\n", indent, "", lowest_case_value);
printf ("%*s {\n",
indent, "");
for (; size > 0; size--)
{
int jumps_away = 0;
printf ("%*s case %d:\n",
indent, "", list->hash_value - lowest_case_value);
list = output_switch_case (list, indent+6, &jumps_away);
if (!jumps_away)
printf ("%*s break;\n",
indent, "");
}
printf ("%*s }\n",
indent, "");
}
}
}
void
Key_List::output_lookup_function_body (const Output_Compare& comparison)
{
T (Trace t ("Key_List::output_lookup_function_body");)
printf (" if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n"
" {\n"
" register int key = %s (str, len);\n\n",
option.get_hash_name ());
if (option[SWITCH])
{
int switch_size = num_hash_values ();
int num_switches = option.get_total_switches ();
if (num_switches > switch_size)
num_switches = switch_size;
printf (" if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n"
" {\n");
if (option[DUP])
{
if (option[LENTABLE])
printf (" register %s%s *lengthptr;\n",
const_always, smallest_integral_type (max_key_len));
printf (" register ");
output_const_type (const_readonly_array, struct_tag);
printf ("*wordptr;\n");
printf (" register ");
output_const_type (const_readonly_array, struct_tag);
printf ("*wordendptr;\n");
}
if (option[TYPE])
{
printf (" register ");
output_const_type (const_readonly_array, struct_tag);
printf ("*resword;\n\n");
}
else
printf (" register %sresword;\n\n",
struct_tag);
output_switches (head, num_switches, switch_size, min_hash_value, max_hash_value, 10);
if (option[DUP])
{
int indent = 8;
printf ("%*s return 0;\n"
"%*smulticompare:\n"
"%*s while (wordptr < wordendptr)\n"
"%*s {\n",
indent, "", indent, "", indent, "", indent, "");
if (option[LENTABLE])
{
printf ("%*s if (len == *lengthptr)\n"
"%*s {\n",
indent, "", indent, "");
indent += 4;
}
printf ("%*s register %schar *s = ",
indent, "", const_always);
if (option[TYPE])
printf ("wordptr->%s", option.get_key_name ());
else
printf ("*wordptr");
printf (";\n\n"
"%*s if (",
indent, "");
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
printf (")\n"
"%*s return %s;\n",
indent, "",
option[TYPE] ? "wordptr" : "s");
if (option[LENTABLE])
{
indent -= 4;
printf ("%*s }\n",
indent, "");
}
if (option[LENTABLE])
printf ("%*s lengthptr++;\n",
indent, "");
printf ("%*s wordptr++;\n"
"%*s }\n",
indent, "", indent, "");
}
printf (" return 0;\n"
" compare:\n");
if (option[TYPE])
{
printf (" {\n"
" register %schar *s = resword->%s;\n\n"
" if (",
const_always, option.get_key_name ());
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
printf (")\n"
" return resword;\n"
" }\n");
}
else
{
printf (" if (");
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("resword"));
printf (")\n"
" return resword;\n");
}
printf (" }\n");
}
else
{
printf (" if (key <= MAX_HASH_VALUE && key >= 0)\n");
if (option[DUP])
{
int indent = 8;
printf ("%*s{\n"
"%*s register int index = lookup[key];\n\n"
"%*s if (index >= 0)\n",
indent, "", indent, "", indent, "");
if (option[LENTABLE])
{
printf ("%*s {\n"
"%*s if (len == lengthtable[index])\n",
indent, "", indent, "");
indent += 4;
}
printf ("%*s {\n"
"%*s register %schar *s = %s[index]",
indent, "",
indent, "", const_always, option.get_wordlist_name ());
if (option[TYPE])
printf (".%s", option.get_key_name ());
printf (";\n\n"
"%*s if (",
indent, "");
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
printf (")\n"
"%*s return ",
indent, "");
if (option[TYPE])
printf ("&%s[index]", option.get_wordlist_name ());
else
printf ("s");
printf (";\n"
"%*s }\n",
indent, "");
if (option[LENTABLE])
{
indent -= 4;
printf ("%*s }\n", indent, "");
}
if (total_duplicates > 0)
{
printf ("%*s else if (index < -TOTAL_KEYWORDS)\n"
"%*s {\n"
"%*s register int offset = - 1 - TOTAL_KEYWORDS - index;\n",
indent, "", indent, "", indent, "");
if (option[LENTABLE])
printf ("%*s register %s%s *lengthptr = &lengthtable[TOTAL_KEYWORDS + lookup[offset]];\n",
indent, "", const_always, smallest_integral_type (max_key_len));
printf ("%*s register ",
indent, "");
output_const_type (const_readonly_array, struct_tag);
printf ("*wordptr = &%s[TOTAL_KEYWORDS + lookup[offset]];\n",
option.get_wordlist_name ());
printf ("%*s register ",
indent, "");
output_const_type (const_readonly_array, struct_tag);
printf ("*wordendptr = wordptr + -lookup[offset + 1];\n\n");
printf ("%*s while (wordptr < wordendptr)\n"
"%*s {\n",
indent, "", indent, "");
if (option[LENTABLE])
{
printf ("%*s if (len == *lengthptr)\n"
"%*s {\n",
indent, "", indent, "");
indent += 4;
}
printf ("%*s register %schar *s = ",
indent, "", const_always);
if (option[TYPE])
printf ("wordptr->%s", option.get_key_name ());
else
printf ("*wordptr");
printf (";\n\n"
"%*s if (",
indent, "");
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
printf (")\n"
"%*s return %s;\n",
indent, "",
option[TYPE] ? "wordptr" : "s");
if (option[LENTABLE])
{
indent -= 4;
printf ("%*s }\n",
indent, "");
}
if (option[LENTABLE])
printf ("%*s lengthptr++;\n",
indent, "");
printf ("%*s wordptr++;\n"
"%*s }\n"
"%*s }\n",
indent, "", indent, "", indent, "");
}
printf ("%*s}\n",
indent, "");
}
else
{
int indent = 8;
if (option[LENTABLE])
{
printf ("%*sif (len == lengthtable[key])\n",
indent, "");
indent += 2;
}
printf ("%*s{\n"
"%*s register %schar *s = %s[key]",
indent, "",
indent, "", const_always, option.get_wordlist_name ());
if (option[TYPE])
printf (".%s", option.get_key_name ());
printf (";\n\n"
"%*s if (",
indent, "");
comparison.output_comparison (Output_Expr1 ("str"), Output_Expr1 ("s"));
printf (")\n"
"%*s return ",
indent, "");
if (option[TYPE])
printf ("&%s[key]", option.get_wordlist_name ());
else
printf ("s");
printf (";\n"
"%*s}\n",
indent, "");
}
}
printf (" }\n"
" return 0;\n");
}
void
Key_List::output_lookup_function (void)
{
T (Trace t ("Key_List::output_lookup_function");)
if (option[KRC] | option[C] | option[ANSIC])
printf ("#ifdef __GNUC__\n"
"__inline\n"
"#endif\n");
printf ("%s%s\n",
const_for_struct, return_type);
if (option[CPLUSPLUS])
printf ("%s::", option.get_class_name ());
printf ("%s ", option.get_function_name ());
printf (option[KRC] ?
"(str, len)\n"
" register char *str;\n"
" register unsigned int len;\n" :
option[C] ?
"(str, len)\n"
" register const char *str;\n"
" register unsigned int len;\n" :
option[ANSIC] | option[CPLUSPLUS] ?
"(register const char *str, register unsigned int len)\n" :
"");
printf ("{\n");
if (option[ENUM] && !option[GLOBAL])
{
Output_Enum style (" ");
output_constants (style);
}
if (!option[GLOBAL])
output_lookup_tables ();
if (option[LENTABLE])
output_lookup_function_body (Output_Compare_Memcmp ());
else
{
if (option[COMP])
output_lookup_function_body (Output_Compare_Strncmp ());
else
output_lookup_function_body (Output_Compare_Strcmp ());
}
printf ("}\n");
}
void
Key_List::output (void)
{
T (Trace t ("Key_List::output");)
compute_min_max ();
if (option[C] | option[ANSIC] | option[CPLUSPLUS])
{
const_always = "const ";
const_readonly_array = (option[CONST] ? "const " : "");
const_for_struct = ((option[CONST] && option[TYPE]) ? "const " : "");
}
else
{
const_always = "";
const_readonly_array = "";
const_for_struct = "";
}
if (!option[TYPE])
{
return_type = (const_always[0] ? "const char *" : "char *");
struct_tag = (const_always[0] ? "const char *" : "char *");
}
char_to_index = (option[SEVENBIT] ? "" : "(unsigned char)");
printf ("/* ");
if (option[KRC])
printf ("KR-C");
else if (option[C])
printf ("C");
else if (option[ANSIC])
printf ("ANSI-C");
else if (option[CPLUSPLUS])
printf ("C++");
printf (" code produced by gperf version %s */\n", version_string);
Options::print_options ();
printf ("%s\n", include_src);
if (option[TYPE] && !option[NOTYPE])
printf ("%s;\n", array_type);
if (option[INCLUDE])
printf ("#include <string.h>\n");
if (!option[ENUM])
{
Output_Defines style;
output_constants (style);
}
else if (option[GLOBAL])
{
Output_Enum style ("");
output_constants (style);
}
printf ("/* maximum key range = %d, duplicates = %d */\n\n",
max_hash_value - min_hash_value + 1, total_duplicates);
if (option[CPLUSPLUS])
printf ("class %s\n"
"{\n"
"private:\n"
" static inline unsigned int %s (const char *str, unsigned int len);\n"
"public:\n"
" static %s%s%s (const char *str, unsigned int len);\n"
"};\n"
"\n",
option.get_class_name (), option.get_hash_name (),
const_for_struct, return_type, option.get_function_name ());
output_hash_function ();
if (option[GLOBAL])
output_lookup_tables ();
output_lookup_function ();
if (additional_code)
for (int c; (c = getchar ()) != EOF; putchar (c))
;
fflush (stdout);
}
void
Key_List::sort (void)
{
T (Trace t ("Key_List::sort");)
hash_sort = 1;
occurrence_sort = 0;
head = merge_sort (head);
}
void
Key_List::dump ()
{
T (Trace t ("Key_List::dump");)
int field_width = option.get_max_keysig_size ();
fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
field_width, "char_set");
for (List_Node *ptr = head; ptr; ptr = ptr->next)
fprintf (stderr, "%11d,%11d,%6d, %*.*s, %.*s\n",
ptr->hash_value, ptr->key_length, ptr->index,
field_width, ptr->char_set_length, ptr->char_set,
ptr->key_length, ptr->key);
}
Key_List::Key_List (void)
{
T (Trace t ("Key_List::Key_List");)
total_keys = 1;
max_key_len = INT_MIN;
min_key_len = INT_MAX;
array_type = 0;
return_type = 0;
struct_tag = 0;
head = 0;
total_duplicates = 0;
additional_code = 0;
}
int
Key_List::keyword_list_length (void)
{
T (Trace t ("Key_List::keyword_list_length");)
return list_len;
}
int
Key_List::max_key_length (void)
{
T (Trace t ("Key_List::max_key_length");)
return max_key_len;
}