key_list.cpp

ace开发环境 用来开发网络程序 其运用了设计模式、多平台、C++等多种知识

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

// Generates C code to perform the keyword lookup.

void
Key_List::output_lookup_function (void)
{
  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");

  if (option[DUP] && total_duplicates > 0)
    {
      int pointer_and_type_enabled = option[POINTER] && option[TYPE];

      ACE_OS::printf ("          int slot = lookup[key];\n\n"
              "          if (slot >= 0 && slot < WORDLIST_SIZE)\n");
      if (option[OPTIMIZE])
        ACE_OS::printf ("            return %swordlist[slot];\n", option[TYPE] && option[POINTER] ? "&" : "");
      else
        {
          ACE_OS::printf ("            {\n"
                  "              %schar *s = wordlist[slot]", option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "");
          if (array_type_ != Key_List::default_array_type)
            ACE_OS::printf (".%s", option.key_name ());

          ACE_OS::printf (";\n\n              if (%s%s == *s && !%s)\n                return %s;\n            }\n",
                  option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
                  option[STRCASECMP] ? "charmap[*str]" : "*str",
                  option[COMP] ? (option[STRCASECMP] ? "strncasecmp (str + 1, s + 1, len - 1)" : "strncmp (str + 1, s + 1, len - 1)")
                  : (option[STRCASECMP] ? "strcasecmp (str + 1, s + 1)" : "strcmp (str + 1, s + 1)"),
                  option[TYPE] && option[POINTER] ? "&wordlist[slot]" : "s");
          ACE_OS::printf ("          else if (slot < 0 && slot >= -MAX_HASH_VALUE)\n"
                  "            return 0;\n");
        }
      ACE_OS::printf ("          else\n            {\n"
              "              unsigned int offset = key + slot + (slot > 0 ? -MAX_HASH_VALUE : MAX_HASH_VALUE);\n"
              "              %s%s*base = &wordlist[-lookup[offset]];\n"
              "              %s%s*ptr = base + -lookup[offset + 1];\n\n"
              "              while (--ptr >= base)\n                ",
              option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "", struct_tag,
              option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "", struct_tag);
      if (array_type_ != Key_List::default_array_type)
        {
          if (option[COMP])
              ACE_OS::printf ("if (%s == *ptr->%s && !%s (str + 1, ptr->%s + 1, len - 1",
                      option[STRCASECMP] ? "charmap[*str]" : "*str", option.key_name (),
                      option[STRCASECMP] ? "strncasecmp" : "strncmp", option.key_name ());
          else
              ACE_OS::printf ("if (%s == *ptr->%s && !%s (str + 1, ptr->%s + 1",
                      option[STRCASECMP] ? "charmap[*str]" : "*str", option.key_name (),
                      option[STRCASECMP] ? "strcasecmp" : "strcmp", option.key_name ());
        }
      else
        ACE_OS::printf (option[STRCASECMP] ? "if (charmap[*str] == **ptr && !%s" : "if (*str == **ptr && !%s",
                option[COMP]
                ? (option[STRCASECMP] ? "strncasecmp (str + 1, *ptr + 1, len - 1" : "strncmp (str + 1, *ptr + 1, len - 1")
                : (option[STRCASECMP] ? "strcasecmp (str + 1, *ptr + 1" : "strcmp (str + 1, *ptr + 1"));
      ACE_OS::printf ("))\n                  return %sptr;"
              "\n            }\n        }\n    %s\n}\n", array_type_ ==
              Key_List::default_array_type ? "*" : "", option[OPTIMIZE] ? "" : "}\n  return 0;");
    }
  else
    {
      if (option[OPTIMIZE])
        ACE_OS::printf ("          return %swordlist[key]", option[TYPE] && option[POINTER] ? "&" : "");
      else
        {
          int pointer_and_type_enabled = option[POINTER] && option[TYPE];

          ACE_OS::printf ("          %schar *s = wordlist[key]", option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "");

          if (array_type_ != Key_List::default_array_type)
            ACE_OS::printf (".%s", option.key_name ());

          ACE_OS::printf (";\n\n          if (%s%s == *s && !%s)\n            return %s",
                  option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
                  option[STRCASECMP] ? "charmap[*str]" : "*str",
                  option[COMP]
                  ? (option[STRCASECMP] ? "strncasecmp (str + 1, s + 1, len - 1)" : "strncmp (str + 1, s + 1, len - 1)")
                  : (option[STRCASECMP] ? "strcasecmp (str + 1, s + 1)" : "strcmp (str + 1, s + 1)"),
                  option[TYPE] && option[POINTER] ? "&wordlist[key]" : "s");
        }
      ACE_OS::printf (";\n        }\n    %s\n}\n", option[OPTIMIZE] ? "" : "}\n  return 0;");
    }
}

// Output the table and the functions that map upper case into lower case!

void
Key_List::output_strcasecmp (void)
{
  ACE_OS::printf ("%s",
          "/* This array is designed for mapping upper and lower case letter\n"
          " * together for a case independent comparison.  The mappings are\n"
          " * based upon ascii character sequences.\n */"
          "static char charmap[] = {\n"
          "   '\\000', '\\001', '\\002', '\\003', '\\004', '\\005', '\\006', '\\007',\n"
          "   '\\010', '\\011', '\\012', '\\013', '\\014', '\\015', '\\016', '\\017',\n"
          "   '\\020', '\\021', '\\022', '\\023', '\\024', '\\025', '\\026', '\\027',\n"
          "   '\\030', '\\031', '\\032', '\\033', '\\034', '\\035', '\\036', '\\037',\n"
          "   '\\040', '\\041', '\\042', '\\043', '\\044', '\\045', '\\046', '\\047',\n"
          "   '\\050', '\\051', '\\052', '\\053', '\\054', '\\055', '\\056', '\\057',\n"
          "   '\\060', '\\061', '\\062', '\\063', '\\064', '\\065', '\\066', '\\067',\n"
          "   '\\070', '\\071', '\\072', '\\073', '\\074', '\\075', '\\076', '\\077',\n"
          "   '\\100', '\\141', '\\142', '\\143', '\\144', '\\145', '\\146', '\\147',\n"
          "   '\\150', '\\151', '\\152', '\\153', '\\154', '\\155', '\\156', '\\157',\n"
          "   '\\160', '\\161', '\\162', '\\163', '\\164', '\\165', '\\166', '\\167',\n"
          "   '\\170', '\\171', '\\172', '\\133', '\\134', '\\135', '\\136', '\\137',\n"
          "   '\\140', '\\141', '\\142', '\\143', '\\144', '\\145', '\\146', '\\147',\n"
          "   '\\150', '\\151', '\\152', '\\153', '\\154', '\\155', '\\156', '\\157',\n"
          "   '\\160', '\\161', '\\162', '\\163', '\\164', '\\165', '\\166', '\\167',\n"
          "   '\\170', '\\171', '\\172', '\\173', '\\174', '\\175', '\\176', '\\177',\n"
          "   '\\200', '\\201', '\\202', '\\203', '\\204', '\\205', '\\206', '\\207',\n"
          "   '\\210', '\\211', '\\212', '\\213', '\\214', '\\215', '\\216', '\\217',\n"
          "   '\\220', '\\221', '\\222', '\\223', '\\224', '\\225', '\\226', '\\227',\n"
          "   '\\230', '\\231', '\\232', '\\233', '\\234', '\\235', '\\236', '\\237',\n"
          "   '\\240', '\\241', '\\242', '\\243', '\\244', '\\245', '\\246', '\\247',\n"
          "   '\\250', '\\251', '\\252', '\\253', '\\254', '\\255', '\\256', '\\257',\n"
          "   '\\260', '\\261', '\\262', '\\263', '\\264', '\\265', '\\266', '\\267',\n"
          "   '\\270', '\\271', '\\272', '\\273', '\\274', '\\275', '\\276', '\\277',\n"
          "   '\\300', '\\341', '\\342', '\\343', '\\344', '\\345', '\\346', '\\347',\n"
          "   '\\350', '\\351', '\\352', '\\353', '\\354', '\\355', '\\356', '\\357',\n"
          "   '\\360', '\\361', '\\362', '\\363', '\\364', '\\365', '\\366', '\\367',\n"
          "   '\\370', '\\371', '\\372', '\\333', '\\334', '\\335', '\\336', '\\337',\n"
          "   '\\340', '\\341', '\\342', '\\343', '\\344', '\\345', '\\346', '\\347',\n"
          "   '\\350', '\\351', '\\352', '\\353', '\\354', '\\355', '\\356', '\\357',\n"
          "   '\\360', '\\361', '\\362', '\\363', '\\364', '\\365', '\\366', '\\367',\n"
          "   '\\370', '\\371', '\\372', '\\373', '\\374', '\\375', '\\376', '\\377',\n};\n\nstatic int\n");
  if (option[COMP])
    {
      ACE_OS::printf ("%s", option[ANSI]
              ? "strncasecmp (char *s1, char *s2, int n)"
              : "strncasecmp (s1, s2, n)\n     char *s1, *s2;\n     int n;");
      ACE_OS::printf ("\n{\n  char *cm = charmap;\n\n  while (--n >= 0 && cm[*s1] == cm[*s2++])\n"
              "    if (*s1++ == '\\0')\n      return 0;\n"
              "\n  return n < 0 ? 0 : cm[*s1] - cm[*--s2];\n}\n\n");
    }
  else
    {
      ACE_OS::printf ("%s", option[ANSI]
              ? "strcasecmp (char *s1, char *s2)"
              : "strcasecmp (s1, s2)\n     char *s1, *s2;");
      ACE_OS::printf ("\n{\n  char *cm = charmap;\n\n  while (cm[*s1] == cm[*s2++])\n"
              "    if (*s1++ == '\\0')\n      return 0;\n"
              "\n  return cm[*s1] - cm[*--s2];\n}\n\n");
    }
}

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

int
Key_List::output (void)
{
  if (option[BINARYSEARCH])
    // Generate code binary search.
    this->output_binary_search_function ();
  else if (option[LINEARSEARCH])
    // Generate code for linear search.
    this->output_linear_search_function ();
  else
    {
      // Generate the usual GPERF things.
      ACE_OS::printf ("%s\n", include_src);

      // Get prototype for strncmp() and strcmp().
      if (!option[SKIPSTRINGH])
        ACE_OS::printf ("#include \"ace/OS_NS_string.h\"\n");

      // Output type declaration now, reference it later on....
      if (option[TYPE] && !option[NOTYPE])
        ACE_OS::printf ("%s;\n",
                array_type_);

      output_min_max ();

      if (option[STRCASECMP])
        output_strcasecmp ();

      // Class definition if -M is *not* enabled.
      if (option[CPLUSPLUS] && !option[SKIPCLASS])
        ACE_OS::printf ("class %s\n{\nprivate:\n"
                "  static unsigned int %s (const char *str, unsigned int len);\npublic:\n"
                "  static %s%s%s (const char *str, unsigned int len);\n};\n\n",
                option.class_name (),
                option.hash_name (),
                option[CONSTANT] ? "const " : "",
                return_type,
                option.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 ();
            if (output_lookup_array () == -1)
              ACE_ERROR_RETURN ((LM_DEBUG,
                                 "%p\n",
                                 "output_lookup_array"),
                                -1);
          }

      // Use the inline keyword to remove function overhead.
      if (option[INLINE])
        ACE_OS::printf ("inline\n");

      int pointer_and_type_enabled = option[POINTER] && option[TYPE];

      ACE_OS::printf ("%s%s\n",
                      option[CONSTANT] || pointer_and_type_enabled == 0 ? "const " : "",
                      return_type);
      if (option[CPLUSPLUS])
        ACE_OS::printf ("%s::", option.class_name ());

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

      if (option[ENUM] && !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\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);
      // Use the switch in place of lookup table.
      if (option[SWITCH])
        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])
            {
              switch (output_lookup_array ())
                {
                case -1:
                  ACE_ERROR_RETURN ((LM_DEBUG,
                                     "%p\n",
                                     "output_lookup_array"),
                                    -1);
                  /* NOTREACHED */
                case 0:
                  output_lookup_function ();
                  break;
                  /* NOTREACHED */
                default:
                  break;
                  /* NOTREACHED */
                }
            }
          else
            output_lookup_function ();
        }

      if (additional_code)
        {
          for (;;)
            {
              int c = getchar ();

              if (c == EOF)
                break;
              else
                putchar (c);
            }
        }
      ACE_OS::fflush (stdout);
    }
  return 0;
  }

// Sorts the keys by hash value.

void
Key_List::sort (void)
{
  // By default, we sort via hashing.
  hash_sort = 1;
  occurrence_sort = 0;

  this->head = merge_sort (this->head);
}

// Sorts the keys by normal strcmp.
void
Key_List::string_sort (void)
{

  // Flatten the equivalence class list to a linear list.

  List_Node *ptr;
  for(ptr=head;ptr;ptr=ptr->next)
    {
      List_Node *curr;
      if(ptr->link)
        {
          List_Node *last_node = 0;

          for(curr = ptr->link; curr; curr = curr->link)
            {
              // Chnage the link to next pointer.
              curr->next = curr->link;

              // Save the pointer for the last node.
              if (curr->link == 0)
                last_node = curr;
            }

          // Set the pointers, correctly.
          last_node->next = ptr->next;
          ptr->next = ptr->link;
          ptr = last_node;
        }
    }

  // Set all links to Null.

  for(ptr=head;ptr;ptr=ptr->next)
    {
      ptr->link = 0;
    }

  // Set the sorting options.

  key_sort = 1;
  hash_sort = 0;
  occurrence_sort = 0;

  // Sort.

  this->head = merge_sort (head);
  key_sort = 0;
}


// Dumps the key list to stderr stream.

void
Key_List::dump (void)
{
  ACE_D