key-list.cc

早期freebsd实现

      /* Get first (also highest) key position. */
      key_pos = option.get (); 
      
      /* We can perform additional optimizations here. */
      if (!option[ALLCHARS] && key_pos <= min_key_len) 
        { 
          printf ("\n    };\n  return %s", option[NOLENGTH] ? "" : "len + ");

          for (; key_pos != WORD_END; )
            {
              printf ("asso_values[str[%d]]", key_pos - 1);
              if ((key_pos = option.get ()) != EOS)
                printf (" + ");
              else
                break;
            }

          printf ("%s;\n}\n\n", key_pos == WORD_END ? "asso_values[str[len - 1]]" : "");
        }

      /* We've got to use the correct, but brute force, technique. */
      else 
        {                    
          printf ("\n    };\n  register int hval = %s;\n\n  switch (%s)\n    {\n      default:\n",
                  option[NOLENGTH] ? "0" : "len", option[NOLENGTH] ? "len" : "hval");
          
          /* User wants *all* characters considered in hash. */
          if (option[ALLCHARS]) 
            { 
              int i;

              for (i = max_key_len; i > 0; i--)
                printf ("      case %d:\n        hval += asso_values[str[%d]];\n", i, i - 1);
              
              printf ("    }\n  return hval;\n}\n\n");
            }
          else                  /* do the hard part... */
            {                
              count = key_pos + 1;
              
              do
                {
                  
                  while (--count > key_pos)
                    printf ("      case %d:\n", count);
                  
                  printf ("      case %d:\n        hval += asso_values[str[%d]];\n",
                          key_pos, key_pos - 1);
                }
              while ((key_pos = option.get ()) != EOS && key_pos != WORD_END);
              
              printf ("    }\n  return hval%s;\n}\n\n",
                      key_pos == WORD_END ? " + asso_values[str[len - 1]]" : "");
            }
        }
    }
}

/* Generates the large, sparse table that maps hash values into
   the smaller, contiguous range of the keyword table. */

void
Key_List::output_lookup_array (void)
{
  T (Trace t ("Key_List::output_lookup_array");)
  if (total_duplicates > 0)
    {
      const int DEFAULT_VALUE = -1;

      struct 
        {
          int hash_value;       /* Hash value for this particular duplicate set. */
          int index;            /* Index into the main keyword storage array. */
          int count;            /* Number of consecutive duplicates at this index. */
        } duplicates[total_duplicates], *dup_ptr = duplicates;
      int lookup_array[max_hash_value + 1], *lookup_ptr = lookup_array + max_hash_value + 1;

      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, temp->index);
          if (!temp->link &&
              (!temp->next || hash_value != temp->next->hash_value))
            continue;
          *dup_ptr = (typeof (*dup_ptr)) { hash_value, temp->index, 1 };
          
          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, ptr->index);            
            }

          while (temp->next && hash_value == temp->next->hash_value)
            {
              temp = temp->next;
              dup_ptr->count++;
              if (option[DEBUG])
                fprintf (stderr, "dynamic linked keyword = %s, index = %d\n", temp->key, temp->index);

              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, ptr->index);            
                }
            }
          dup_ptr++;
        }
  
      while (--dup_ptr >= duplicates)
        {
          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);

          /* Start searching for available space towards the right part of the lookup array. */
          for (int i = dup_ptr->hash_value; i < max_hash_value; i++)
            if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i + 1] == DEFAULT_VALUE)
              {
                lookup_array[i] = -dup_ptr->index;
                lookup_array[i + 1] = -dup_ptr->count;
                lookup_array[dup_ptr->hash_value] = max_hash_value + (i - dup_ptr->hash_value);
                break;
              }

          /* If we didn't find it to the right look to the left instead... */
          if (i == max_hash_value)
            {

              for (i = dup_ptr->hash_value; i > 0; i--)
                if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i - 1] == DEFAULT_VALUE)
                  {
                    lookup_array[i - 1] = -dup_ptr->index;
                    lookup_array[i] = -dup_ptr->count;
                    lookup_array[dup_ptr->hash_value] = -(max_hash_value + (dup_ptr->hash_value - i + 1));
                    break;
                  }

              /* We are in *big* trouble if this happens! */
              assert (i != 0);
            }
        }

      int max = INT_MIN;

      for (lookup_ptr = lookup_array + max_hash_value + 1; lookup_ptr > lookup_array; max >?= abs (*--lookup_ptr))
        ;

      char *indent = option[GLOBAL] ? "" : "  ";
      printf ("%sstatic %s%s lookup[] =\n%s%s{\n      ", indent, option[CONST] ? "const " : "",
              max <= SCHAR_MAX ? "char" : (max <= USHRT_MAX ? "short" : "int"),
              indent, indent);

      int count = max;

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

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

      const int max_column = 15;
      int column = 0;

      for (lookup_ptr = lookup_array; 
           lookup_ptr < lookup_array + max_hash_value + 1;
           lookup_ptr++)
        printf ("%*d,%s", field_width, *lookup_ptr, ++column % (max_column - 1) ? "" : "\n      ");

      printf ("\n%s%s};\n\n", indent, indent);
    }
}
/* Generates C code to perform the keyword lookup. */

void 
Key_List::output_lookup_function (void)
{ 
  T (Trace t ("Key_List::output_lookup_function");)
  printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n"
          "      register int key = %s (str, len);\n\n"
          "      if (key <= MAX_HASH_VALUE && key >= 0)\n        {\n",
          option.get_hash_name ());
  
  if (option[DUP] && total_duplicates > 0)
    {
      printf ("          register int index = lookup[key];\n\n"
              "          if (index >= 0 && index < MAX_HASH_VALUE)\n"
              "            {\n"
              "              register %schar *s = wordlist[index]", option[CONST] ? "const " : "");
      if (array_type != default_array_type)
        printf (".%s", option.get_key_name ());
  
      printf (";\n\n              if (%s*s == *str && !%s)\n                return %s;\n            }\n",
              option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
              option[COMP] ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
              option[TYPE] && option[POINTER] ? "&wordlist[index]" : "s");
      printf ("          else if (index < 0 && index >= -MAX_HASH_VALUE)\n"
              "            return 0;\n          else\n            {\n"
              "              register int offset = key + index + (index > 0 ? -MAX_HASH_VALUE : MAX_HASH_VALUE);\n"
              "              register %s%s*base = &wordlist[-lookup[offset]];\n"
              "              register %s%s*ptr = base + -lookup[offset + 1];\n\n"
              "              while (--ptr >= base)\n                ",
              option[CONST] ? "const " : "", struct_tag,
              option[CONST] ? "const " : "", struct_tag);
      if (array_type != default_array_type)
        printf ("if (*str == *ptr->%s && !strcmp (str + 1, ptr->%s + 1",
                option.get_key_name (), option.get_key_name ());
      else
        printf ("if (*str == **ptr && !strcmp (str + 1, *ptr + 1");

      printf ("))\n                  return %sptr;"
              "\n            }\n        }\n    }\n  return 0;\n}\n", array_type == default_array_type ? "*" : "");
              
    }
  else
    {
      printf ("          register %schar *s = wordlist[key]", option[CONST] ? "const " : "");

      if (array_type != default_array_type)
        printf (".%s", option.get_key_name ());
  
      printf (";\n\n          if (%s*s == *str && !%s)\n            return %s",
              option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
              option[COMP] ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
              option[TYPE] && option[POINTER] ? "&wordlist[key]" : "s");
      printf (";\n        }\n    }\n  return 0;\n}\n");
    }
}

/* Generates the hash function and the key word recognizer function
   based upon the user's Options. */

void 
Key_List::output (void)
{
  T (Trace t ("Key_List::output");)
  printf ("%s\n", include_src);
  
  if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
    printf ("%s;\n", array_type);
  
  output_min_max ();

  if (option[CPLUSPLUS])
    printf ("class %s\n{\nprivate:\n"
            "  static unsigned int hash (const char *str, int len);\npublic:\n"
            "  static %s%s%s (const char *str, int len);\n};\n\n",
            option.get_class_name (), option[CONST] ? "const " : "", 
            return_type, option.get_function_name ());

  output_hash_function ();
  
  if (option[GLOBAL])
    if (option[SWITCH])
      {
        if (option[LENTABLE] && option[DUP])
          output_keylength_table ();
        if (option[POINTER] && option[TYPE])
          output_keyword_table ();
      }
    else
      {
        if (option[LENTABLE])
          output_keylength_table ();
        output_keyword_table ();
        output_lookup_array ();
      }
  
  if (option[GNU])          /* Use the inline keyword to remove function overhead. */
    printf ("#ifdef __GNUC__\ninline\n#endif\n");
  
  printf ("%s%s\n", option[CONST] ? "const " : "", return_type);
  if (option[CPLUSPLUS])
    printf ("%s::", option.get_class_name ());

  printf (option[ANSI] 
          ? "%s (register const char *str, register int len)\n{\n"
          : "%s (str, len)\n     register char *str;\n     register unsigned int len;\n{\n",
          option.get_function_name ());

  if (option[ENUM])
    printf ("  enum\n    {\n"
            "      TOTAL_KEYWORDS = %d,\n"
            "      MIN_WORD_LENGTH = %d,\n"
            "      MAX_WORD_LENGTH = %d,\n"
            "      MIN_HASH_VALUE = %d,\n"
            "      MAX_HASH_VALUE = %d,\n"
            "    };\n\n",
            total_keys, min_key_len, max_key_len, min_hash_value, max_hash_value);

  /* Use the switch in place of lookup table. */
  if (option[SWITCH])
    {               
      if (!option[GLOBAL])
        {
          if (option[LENTABLE] && option[DUP])
            output_keylength_table ();
          if (option[POINTER] && option[TYPE]) 
            output_keyword_table ();
        }
      output_switch ();
    }
  /* Use the lookup table, in place of switch. */
  else                
    {           
      if (!option[GLOBAL])
        {
          if (option[LENTABLE])
            output_keylength_table ();
          output_keyword_table ();
        }
      if (!option[GLOBAL])
        output_lookup_array ();
      output_lookup_function ();
    }
  
  if (additional_code)
    for (int c; (c = getchar ()) != EOF; putchar (c))
      ;

  fflush (stdout);
}

/* Sorts the keys by hash value. */

void 
Key_List::sort (void) 
{ 
  T (Trace t ("Key_List::sort");)
  hash_sort       = 1;
  occurrence_sort = 0;
  
  head = merge_sort (head);
}

/* Dumps the key list to stderr stream. */

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->length, ptr->index,
             field_width, ptr->char_set, ptr->key);
}

/* Simple-minded constructor action here... */

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;
  return_type      = default_return_type;
  array_type       = struct_tag  = default_array_type;
  head             = 0;
  total_duplicates = 0;
  additional_code  = 0;
}

/* Returns the length of entire key list. */

int 
Key_List::keyword_list_length (void) 
{ 
  T (Trace t ("Key_List::keyword_list_length");)
  return list_len;
}

/* Returns length of longest key read. */

int 
Key_List::max_key_length (void) 
{ 
  T (Trace t ("Key_List::max_key_length");)
  return max_key_len;
}