key-list.cc

早期freebsd实现

  T (Trace t ("Key_List::already_determined");)
  int is_determined = 1;

  for (char *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 
Key_List::reorder (void)
{
  T (Trace t ("Key_List::reorder");)
  for (List_Node *ptr = head; ptr; ptr = ptr->next)
    ptr->occurrence = get_occurrence (ptr);
  
  occurrence_sort = !(hash_sort = 0); /* Pretty gross, eh?! */
  
  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;
            }
        }
    }     
}

/* Outputs the maximum and minimum hash values.  Since the
   list is already sorted by hash value all we need to do is
   find the final item! */
  
void
Key_List::output_min_max ()
{
  T (Trace t ("Key_List::output_min_max");)
  for (List_Node *temp = head; temp->next; temp = temp->next)
    ;

  min_hash_value = head->hash_value;
  max_hash_value = temp->hash_value;

  if (!option[ENUM])
    printf ("\n#define TOTAL_KEYWORDS %d\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", total_keys, min_key_len,
            max_key_len, min_hash_value, max_hash_value);
  printf ("/* maximum key range = %d, duplicates = %d */\n\n",
          max_hash_value - min_hash_value + 1, total_duplicates);
}

/* 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 Output_Lookup_Function.  Then we use for
   switch statements to perform either 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. */

void 
Key_List::output_switch (void)
{
  T (Trace t ("Key_List::output_switch");)
  char      *comp_buffer;
  List_Node *curr                     = head;
  int        pointer_and_type_enabled = option[POINTER] && option[TYPE];
  int        total_switches           = option.get_total_switches ();
  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 (option.get_key_name ()) + 1);
      sprintf (comp_buffer, option[COMP]
               ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
               : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)",
               option.get_key_name (), option.get_key_name ());
    }
  else
    comp_buffer = 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",
          option.get_hash_name ());
  
  /* 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 && total_switches != 1)
        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[POINTER] || option[DUP])
        {
          int i = 0;

          printf ("              %s%s *resword; %s\n\n",
                  option[CONST] ? "const " : "",
                  pointer_and_type_enabled ? struct_tag : "char",
                  option[LENTABLE] && !option[DUP] ? "int key_len;" : "");
          if (total_switches == 1)
            {
              printf ("              switch (key)\n                {\n");
              lowest_case_value = 0;
            }
          else
            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[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[LENTABLE] && !option[DUP])
                    printf (" key_len = %d;", temp->length);
                  printf (" break;\n");
                }
            }
          printf ("                default: return 0;\n                }\n");
          printf (option[LENTABLE] && !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[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[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.'' */

void 
Key_List::output_keylength_table (void)
{
  T (Trace t ("Key_List::output_keylength_table");)
  const int  max_column = 15;
  int        index      = 0;
  int        column     = 0;
  char      *indent     = option[GLOBAL] ? "" : "  ";
  List_Node *temp;

  if (!option[DUP] && !option[SWITCH]) 
    {
      printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n    ",
              indent, option[CONST] ? "const " : "",
              max_key_len <= UCHAR_MAX ? "char" : (max_key_len <= USHRT_MAX ? "short" : "long"),
              indent, indent);
  
      for (temp = 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", indent, indent);
    }
}
/* Prints out the array containing the key words for the Gen_Perf
   hash function. */
  
void 
Key_List::output_keyword_table (void)
{
  T (Trace t ("Key_List::output_keyword_table");)
  char      *l_brace = *head->rest ? "{" : "";
  char      *r_brace = *head->rest ? "}," : "";
  char      *indent  = option[GLOBAL] ? "" : "  ";
  int        index   = 0;
  List_Node *temp;

  printf ("%sstatic %s%swordlist[] =\n%s%s{\n",
          indent, option[CONST] ? "const " : "", struct_tag, indent, indent);

  /* Skip over leading blank entries if there are no duplicates. */

  printf ("      ");
  for (int column = 1; index < head->hash_value; index++, column++)
    printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n      ");      
  if (column % 10)
    printf ("\n");

          
  /* Generate an array of reserved words at appropriate locations. */
  
  for (temp = head ; temp; temp = temp->next, index++)
    {
      temp->index = index;

      if (!option[SWITCH] && (total_duplicates == 0 || !option[DUP]) && 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", l_brace, temp->key, temp->rest, r_brace);
              if (option[DEBUG])
                printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index);
              putchar ('\n');
              continue;
            }
        }

      printf ("      %s\"%s\", %s%s", l_brace, temp->key, temp->rest, r_brace);
      if (option[DEBUG])
        printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index);
      putchar ('\n');

      /* Deal with links specially. */
      if (temp->link)
        for (List_Node *links = temp->link; links; links = links->link)
          {
            links->index = ++index;
            printf ("      %s\"%s\", %s%s", l_brace, links->key, links->rest, r_brace);
            if (option[DEBUG])
              printf (" /* hash value = %d, index = %d */", links->hash_value, links->index);
            putchar ('\n');
          }
    }
  printf ("%s%s};\n\n", indent, indent);
}

/* Generates C code for the hash function that returns the
   proper encoding for each key word. */

void 
Key_List::output_hash_function (void)
{
  T (Trace t ("Key_List::output_hash_function");)
  const int max_column  = 10;
  int       count       = max_hash_value;

  /* Calculate maximum number of digits required for MAX_HASH_VALUE. */

  for (field_width = 2; (count /= 10) > 0; field_width++)
    ;

  if (option[GNU])
    printf ("#ifdef __GNUC__\ninline\n#endif\n");
  
  if (option[C])
    printf ("static ");
  printf ("unsigned int\n");
  if (option[CPLUSPLUS])
    printf ("%s::", option.get_class_name ());

  printf (option[ANSI] 
          ? "%s (register const char *str, register int len)\n{\n  static %sunsigned %s asso_values[] =\n    {"
          : "%s (str, len)\n     register char *str;\n     register int unsigned len;\n{\n  static %sunsigned %s asso_values[] =\n    {",
          option.get_hash_name (), option[CONST] ? "const " : "",
          max_hash_value <= UCHAR_MAX ? "char" : (max_hash_value <= USHRT_MAX ? "short" : "int"));
  
  for (count = 0; count < ALPHA_SIZE; ++count)
    {
      if (!(count % max_column))
        printf ("\n    ");
      
      printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value + 1);
    }
  
  /* Optimize special case of ``-k 1,$'' */
  if (option[DEFAULTCHARS]) 
    printf ("\n    };\n  return %sasso_values[str[len - 1]] + asso_values[str[0]];\n}\n\n",
            option[NOLENGTH] ? "" : "len + ");
  else
    {
      int key_pos;

      option.reset ();