key_list.cpp

ACE源码

                  : "%s (str, len)\n     char *str;\n     unsigned int len;\n{\n",
                  option.hash_name ());

  // Generate the asso_values table.
  ACE_OS::printf ("  static %sunsigned %s asso_values[] =\n    {",
                  option[CONSTANT] ? "const " : "",
                  max_hash_value <= ((int) UCHAR_MAX) ? "char" : (max_hash_value <= ((int) USHRT_MAX) ? "short" : "int"));

  ACE_OS::printf ("\n#if defined (ACE_MVS)");
#if ACE_STANDARD_CHARACTER_SET_SIZE == ACE_EBCDIC_SIZE
    {
      // We are running in EBCDIC environment.
      for (count = 0; count < ACE_EBCDIC_SIZE; ++count)
        {
          if (!(count % max_column))
            ACE_OS::printf ("\n    ");

          ACE_OS::printf ("%*d,",
 			  Key_List::field_width,
 			  Vectors::occurrences[count] ? Vectors::asso_values[count] : max_hash_value + 1);
        }

      ACE_OS::printf ("\n#else");

      for (count = 0; count < ACE_ASCII_SIZE; ++count)
        {
          if (!(count % max_column))
            ACE_OS::printf ("\n    ");

          target = ascii_to_ebcdic[count];
          ACE_OS::printf ("%*d,",
			  Key_List::field_width,
 			  Vectors::occurrences[target] ? Vectors::asso_values[target] : max_hash_value + 1);
        }
    }
#  else
    {
      // We are running in ASCII environment.
      for (count = 0; count < ACE_EBCDIC_SIZE; ++count)
        ebcdic_to_ascii[count] = 0;

      for (count = 0; count < ACE_ASCII_SIZE; ++count)
        {
          target = ascii_to_ebcdic[count];
          ebcdic_to_ascii[target] = count;
        }

      for (count = 0; count < ACE_EBCDIC_SIZE; ++count)
        {
          if (!(count % max_column))
            ACE_OS::printf ("\n    ");

          target = ebcdic_to_ascii[count];
          ACE_OS::printf ("%*d,",
 			  Key_List::field_width,
 			  Vectors::occurrences[target] ? Vectors::asso_values[target] : max_hash_value + 1);
        }
      ACE_OS::printf ("\n#else");

      for (count = 0; count < ACE_ASCII_SIZE; ++count)
        {
          if (!(count % max_column))
            ACE_OS::printf ("\n    ");

          ACE_OS::printf ("%*d,",
 			  Key_List::field_width,
 			  Vectors::occurrences[count] ? Vectors::asso_values[count] : max_hash_value + 1);
        }
    }
#endif /* ACE_STANDARD_CHARACTER_SET_SIZE == ACE_EBCDIC_SIZE */
   ACE_OS::printf ("\n#endif /* ACE_MVS */");

  // Optimize special case of ``-k 1,$''
  if (option[DEFAULTCHARS])
    {
      if (option[STRCASECMP])
        ACE_OS::printf ("\n    };\n  return %sasso_values[(int) charmap[str[len - 1]]] + asso_values[(int) charmap[str[0]]];\n}\n\n",
                option[NOLENGTH] ? "" : "len + ");
      else
        ACE_OS::printf ("\n    };\n  return %sasso_values[(int) str[len - 1]] + asso_values[(int) str[0]];\n}\n\n",
                option[NOLENGTH] ? "" : "len + ");
    }
  else
    {
      int key_pos;

      option.reset ();

      // Get first (also highest) key position.
      key_pos = option.get ();

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

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

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

      // We've got to use the correct, but brute force, technique.
      else
        {
          ACE_OS::printf ("\n    };\n  unsigned 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;

              // Break these options up for speed (gee, is this misplaced efficiency or what?!
              if (option[STRCASECMP])

                for (i = max_key_len; i > 0; i--)
                  ACE_OS::printf ("      case %d:\n        hval += asso_values[(int) charmap[(int) str[%d]]];\n", i, i - 1);

              else

                for (i = max_key_len; i > 0; i--)
                  ACE_OS::printf ("      case %d:\n        hval += asso_values[(int) str[%d]];\n", i, i - 1);

              ACE_OS::printf ("    }\n  return hval;\n}\n\n");
            }
          else                  // do the hard part...
            {
              count = key_pos + 1;

              do
                {

                  while (--count > key_pos)
                    ACE_OS::printf ("      case %d:\n", count);

                  ACE_OS::printf (option[STRCASECMP]
                          ? "      case %d:\n        hval += asso_values[(int) charmap[(int) str[%d]]];\n"
                          : "      case %d:\n        hval += asso_values[(int) str[%d]];\n",
                          key_pos, key_pos - 1);
                }
              while ((key_pos = option.get ()) != EOS && key_pos != WORD_END);

              ACE_OS::printf ("    }\n  return hval%s;\n}\n\n",
                      key_pos == WORD_END
                      ? (option[STRCASECMP] ? " + asso_values[(int) charmap[(int) str[len - 1]]]" : " + asso_values[(int) str[len - 1]]")
                      : "");
            }
        }
    }
}

int
Key_List::count_duplicates (List_Node *link,
                            const char *type)
{
  int count = 0;

  // Count the number of "static" duplicates for this hash value.
  for (List_Node *ptr = link;
       ptr != 0;
       ptr = ptr->link)
    {
      count++;

      if (option[DEBUGGING])
        ACE_DEBUG ((LM_DEBUG,
                    "%s linked keyword = %s, slot = %d, hash_value = %d\n",
                    type,
                    ptr->key,
                    ptr->slot,
                    ptr->hash_value));
    }

  return count;
}

void
Key_List::update_lookup_array (int lookup_array[],
                               int i1,
                               int i2,
                               Duplicate_Entry *dup_ptr,
                               int value)
{
  lookup_array[i1] = -dup_ptr->slot;
  lookup_array[i2] = -dup_ptr->count;
  lookup_array[dup_ptr->hash_value] = value;
}

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

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

      Duplicate_Entry *duplicates = 0;
      ACE_NEW_RETURN (duplicates,
                      Duplicate_Entry[total_duplicates],
                      -1);

      int *lookup_array = 0;
      ACE_NEW_RETURN (lookup_array,
                      int[max_hash_value + 1],
                      -1);

      Duplicate_Entry *dup_ptr = duplicates;
      int *lookup_ptr = lookup_array + max_hash_value + 1;

      // Initialize the lookup array to the DEFAULT_VALUE (-1).
      while (lookup_ptr > lookup_array)
        *--lookup_ptr = DEFAULT_VALUE;

      // Iterate through the keylist and handle the static and dynamic
      // duplicate entries.
      for (List_Node *temp = head; temp; temp = temp->next)
        {
          int hash_value = temp->hash_value;
          // Store the keyword's slot location into the
          // <lookup_array> at the <hash_value>.  If this is a
          // non-duplicate, then this value will point directly to the
          // keyword.
          lookup_array[hash_value] = temp->slot;

          if (option[DEBUGGING])
            ACE_DEBUG ((LM_DEBUG,
                        "keyword = %s, slot = %d, hash_value = %d, lookup_array[hash_value] = %d\n",
                        temp->key,
                        temp->slot,
                        temp->hash_value,
                        lookup_array[temp->hash_value]));

          if (temp->link == 0 &&
              (temp->next == 0 || hash_value != temp->next->hash_value))
            // This isn't a duplicate.  Note that we know this because
            // we sorted the keys by their hash value.
            continue;
          else
            {
              // We'll handle the duplicates here.
              dup_ptr->hash_value = hash_value;
              dup_ptr->slot = temp->slot;
              dup_ptr->count = 1;

              // Count the number of "static" duplicates, i.e.,
              // keywords that had the same keysig when the keyfile
              // was first read.
              dup_ptr->count += this->count_duplicates (temp->link,
                                                        "static");

              // Count the number of "dynamic" duplicates, i.e.,
              // keywords that ended up with the same hash value as a
              // result of the <asso_values> contents.
              for (;
                   temp->next && hash_value == temp->next->hash_value;
                   temp = temp->next)
                dup_ptr->count += this->count_duplicates (temp->next,
                                                          "dynamic");
              dup_ptr++;
            }
        }

      // Compute the values in the lookup array.
      while (--dup_ptr >= duplicates)
        {
          if (option[DEBUGGING])
            ACE_DEBUG ((LM_DEBUG,
                        "dup_ptr[%d]: hash_value = %d, slot = %d, count = %d\n",
                        dup_ptr - duplicates,
                        dup_ptr->hash_value,
                        dup_ptr->slot,
                        dup_ptr->count));
          int i;

          // Look to the left first.
          for (i = dup_ptr->hash_value; i > 0; i--)
            if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i - 1] == DEFAULT_VALUE)
              {
                this->update_lookup_array (lookup_array,
                                           i - 1,
                                           i,
                                           dup_ptr,
                                           -(max_hash_value + (dup_ptr->hash_value - i + 1)));
                break;
              }

          // If we didn't find it to the left look to the right
          // instead...
          if (i == 0)
            {
              for (i = dup_ptr->hash_value; i < max_hash_value; i++)
                if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i + 1] == DEFAULT_VALUE)
                  {
                    this->update_lookup_array (lookup_array,
                                               i,
                                               i + 1,
                                               dup_ptr,
                                               max_hash_value + (i - dup_ptr->hash_value));
                    break;
                  }

              // If this happens, we can't use the output array scheme...
              if (i >= max_hash_value)
                {
                  option = SWITCH;
                  ACE_DEBUG ((LM_DEBUG,
                              "GPERF: Automatically changing to -S1 switch option\n"));
                  // Since we've already generated the keyword table
                  // we need to use it!
                  this->output_switch (1);
                  return 1; // 1 indicates that we've changed our mind...
                }
            }
        }

      lookup_ptr = lookup_array + max_hash_value + 1;
      int max = INT_MIN;

      while (lookup_ptr > lookup_array)
        {
          int val = abs (*--lookup_ptr);
          if (max < val)
            max = val;
        }

      const char *indent = option[GLOBAL] ? "" : "  ";

      ACE_OS::printf ("%sstatic %ssigned %s lookup[] =\n%s%s{\n%s", indent, option[CONSTANT] ? "const " : "",
              max <= SCHAR_MAX ? "char" : (max <= SHRT_MAX ? "short" : "int"),
              indent, indent, option[DEBUGGING] ? "" : "      ");

      int count = max;

      // Calculate maximum number of digits required for LOOKUP_ARRAY_SIZE.

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

      const int max_column = 15;
      int column = 0;

      for (lookup_ptr = lookup_array;
           lookup_ptr < lookup_array + max_hash_value + 1;
           lookup_ptr++)
        {
          if (option[DEBUGGING])
            ACE_OS::printf ("      %*d, /* slot = %d */\n",
                            Key_List::field_width,
                            *lookup_ptr,
                            (int)(lookup_ptr - lookup_array));
          else
            ACE_OS::printf ("%*d, %s",
                            Key_List::field_width,
                            *lookup_ptr,
                            ++column % (max_column - 1) ? "" : "\n      ");
        }
      ACE_OS::printf ("%s%s%s};\n\n", option[DEBUGGING] ? "" : "\n", indent, indent);

      delete [] duplicates;
      delete [] lookup_array;
    }
  return 0;