key_list.cpp

最新的版本ACE-5.6.8,刚从外文网上搬下,与大家分享.

List_Node *
Key_List::merge (List_Node *list1, List_Node *list2)
{
  if (list1 == 0)
    {
      return list2;
    }
  else if (list2 == 0)
    {
      return list1;
    }
  else if ((occurrence_sort && list1->occurrence < list2->occurrence)
           || (hash_sort && list1->hash_value > list2->hash_value)
           || (key_sort && ACE_OS::strcmp (list1->key, list2->key) >= 0))
    {
      list2->next = merge (list2->next, list1);
      return list2;
    }
  else
    {
      list1->next = merge (list1->next, list2);
      return list1;
    }
}

// Applies the merge sort algorithm to recursively sort the key list
// by frequency of occurrence of elements in the key set.

List_Node *
Key_List::merge_sort (List_Node *a_head)
{
  if (!a_head || !a_head->next)
    return a_head;
  else
    {
      List_Node *middle = a_head;
      List_Node *temp = a_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 (a_head), merge_sort (temp));
    }
}

// Returns the frequency of occurrence of elements in the key set.

inline int
Key_List::occurrence (List_Node *ptr)
{
  int value = 0;

  for (char *temp = ptr->keysig; *temp; temp++)
    value += Vectors::occurrences[(int) *temp];

  return value;
}

// Sets the index location for all keysig characters that are now
// determined.

inline void
Key_List::determined (List_Node *ptr)
{
  for (char *temp = ptr->keysig; *temp; temp++)
    Key_List::determined_[(int) *temp] = 1;
}

// Returns TRUE if PTR's key set is already completely determined.

inline int
Key_List::already_determined (List_Node *ptr)
{
  int is_determined = 1;

  for (char *temp = ptr->keysig; is_determined && *temp; temp++)
    is_determined = determined_[(int) *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)
{
  List_Node *ptr;

  for (ptr = head; ptr; ptr = ptr->next)
    ptr->occurrence = occurrence (ptr);

  // Switch to sorting by occurrence.
  hash_sort = 0;
  occurrence_sort = 1;

  for (ptr = head = merge_sort (head); ptr->next; ptr = ptr->next)
    {
      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 (void)
{
  List_Node *temp;
  for (temp = head; temp->next; temp = temp->next)
    continue;

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

  if (!option[ENUM])
    ACE_OS::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#define HASH_VALUE_RANGE %d"
            "\n#define DUPLICATES %d\n#define WORDLIST_SIZE %d\n\n",
            total_keys, min_key_len, max_key_len, min_hash_value,
            max_hash_value, max_hash_value - min_hash_value + 1,
            total_duplicates ? total_duplicates + 1 : 0, total_keys + min_hash_value);
  else if (option[GLOBAL])
    ACE_OS::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"
            "  HASH_VALUE_RANGE = %d,\n"
            "  DUPLICATES = %d\n"
            "  WORDLIST_SIZE = %d};\n\n",
            total_keys, min_key_len, max_key_len, min_hash_value,
            max_hash_value, max_hash_value - min_hash_value + 1,
            total_duplicates ? total_duplicates + 1 : 0, total_keys + min_hash_value);
}

// 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 (int use_keyword_table)
{
  if (!option[GLOBAL] && use_keyword_table == 0)
    {
      if (option[LENTABLE] && option[DUP])
        output_keylength_table ();
      if (option[POINTER] && option[TYPE])
        output_keyword_table ();
    }

  ACE_Auto_Basic_Array_Ptr<char> safe_comp_buffer;
  char * comp_buffer;

  List_Node *curr = head;
  int pointer_and_type_enabled = option[POINTER] && option[TYPE];
  int total_switches = option.total_switches ();
  int switch_size = keyword_list_length () / total_switches;

  if (pointer_and_type_enabled)
    {
      // Keep track of the longest string we'll need!
      const char *s = "charmap[*str] == *resword->%s && !ACE_OS::strncasecmp (str + 1, resword->%s + 1, len - 1)";

      char * const tmp =
        new char[ACE_OS::strlen (s)
                 + 2 * ACE_OS::strlen (option.key_name ()) + 1];
      safe_comp_buffer.reset (tmp);

      comp_buffer = safe_comp_buffer.get ();

      if (option[COMP])
        ACE_OS::sprintf (comp_buffer, "%s == *resword->%s && !ACE_OS::%s (str + 1, resword->%s + 1, len - 1)",
                         option[STRCASECMP] ? "charmap[*str]" : "*str", option.key_name (),
                         option[STRCASECMP] ? "strncasecmp" : "strncmp", option.key_name ());
      else
        ACE_OS::sprintf (comp_buffer, "%s == *resword->%s && !ACE_OS::%s (str + 1, resword->%s + 1)",
                         option[STRCASECMP] ? "charmap[*str]" : "*str", option.key_name (),
                         option[STRCASECMP] ? "strcasecmp" : "strcmp", option.key_name ());
    }
  else
    {
      if (option[COMP])
        comp_buffer = option[STRCASECMP]
          ? (char *) "charmap[*str] == *resword && !ACE_OS::strncasecmp (str + 1, resword + 1, len - 1)"
          : (char *) "*str == *resword && !ACE_OS::strncmp (str + 1, resword + 1, len - 1)";
      else
        comp_buffer = option[STRCASECMP]
          ? (char *) "charmap[*str] == *resword && !ACE_OS::strncasecmp (str + 1, resword + 1, len - 1)"
          : (char *) "*str == *resword && !ACE_OS::strcmp (str + 1, resword + 1)";
    }
  if (!option[OPTIMIZE])
    ACE_OS::printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n");
  ACE_OS::printf ("      unsigned int key = %s (str, len);\n\n", option.hash_name ());
  if (!option[OPTIMIZE])
    ACE_OS::printf ("      if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n");

  ACE_OS::printf ("        {\n");

  // 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)
        ACE_OS::printf ("          if (key <= %d)\n            {\n", temp->hash_value);
      else
        ACE_OS::printf ("            {\n");

      // Output each keyword as part of a switch statement indexed by
      // hash value.

      if (option[POINTER] || option[DUP] || use_keyword_table)
        {
          int i = 0;

          ACE_OS::printf ("              %s%s *resword; %s\n\n",
                  option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "",
                  pointer_and_type_enabled ? struct_tag : "char",
                  option[LENTABLE] && !option[DUP] ? "unsigned int key_len;" : "");
          if (total_switches == 1)
            {
              ACE_OS::printf ("              switch (key)\n                {\n");
              lowest_case_value = 0;
            }
          else
            ACE_OS::printf ("              switch (key - %d)\n                {\n", lowest_case_value);

          for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
            {
              ACE_OS::printf ("                case %*d:\n",
                      Key_List::field_width,
                      temp->hash_value - lowest_case_value);

              // Handle `static links,' i.e., those that occur during
              // the initial preprocessing.

              if (temp->link == 0)
                {
                  if (option[DEBUGGING])
                    ACE_OS::printf ("                  /* hash value = %4d, keyword = \"%s\" */\n",
                            temp->hash_value,
                            temp->key);
                }
              else
                {
                  List_Node *links;

                  for (links = temp; links; links = links->link)
                    {
                      if (option[DEBUGGING])
                        ACE_OS::printf ("                  /* hash value = %4d, keyword = \"%s\" */\n",
                                temp->hash_value,
                                links->key);
                      if (pointer_and_type_enabled)
                        ACE_OS::printf ("                  resword = &wordlist[%d];\n", links->slot);
                      else if (use_keyword_table)
                        ACE_OS::printf ("                  resword = wordlist[%d];\n", links->slot);
                      else
                        ACE_OS::printf ("                  resword = \"%s\";\n", links->key);
                      ACE_OS::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)
                        ACE_OS::printf ("                  resword = &wordlist[%d];\n", temp->slot);
                      else if (use_keyword_table)
                        ACE_OS::printf ("                  resword = wordlist[%d];", temp->slot);
                      else
                        ACE_OS::printf ("                  resword = \"%s\";\n", temp->key);
                      ACE_OS::printf ("                  if (%s) return resword;\n", comp_buffer);
                    }
                  if (pointer_and_type_enabled)
                    ACE_OS::printf ("                  resword = &wordlist[%d];\n", temp->slot);
                  else if (use_keyword_table)
                    ACE_OS::printf ("                  resword = wordlist[%d];", temp->slot);
                  else
                    ACE_OS::printf ("                  resword = \"%s\";\n", temp->key);
                  ACE_OS::printf ("                  return %s ? resword : 0;\n", comp_buffer);
                }
              else if (temp->link)
                ACE_OS::printf ("                  return 0;\n");
              else
                {
                  if (pointer_and_type_enabled)
                    ACE_OS::printf ("                  resword = &wordlist[%d];", temp->slot);
                  else if (use_keyword_table)
                    ACE_OS::printf ("                  resword = wordlist[%d];", temp->slot);
                  else
                    ACE_OS::printf ("                  resword = \"%s\";", temp->key);
                  if (option[LENTABLE] && !option[DUP])
                    ACE_OS::printf (" key_len = %d;", temp->length);
                  ACE_OS::printf (" break;\n");
                }
            }
          ACE_OS::printf ("                default: return 0;\n                }\n");