key_list.cpp

ACE源码

// -*- C++ -*-

// Key_List.cpp,v 4.57 2003/11/01 11:15:22 dhinton Exp

// Copyright (C) 1989 Free Software Foundation, Inc.
// written by Douglas C. Schmidt ([e-mail])

// This file is part of GNU GPERF.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#include "Key_List.h"

ACE_RCSID(src, Key_List, "Key_List.cpp,v 4.57 2003/11/01 11:15:22 dhinton Exp")

#if defined (ACE_HAS_GPERF)

#include "ace/Read_Buffer.h"
#include "Hash_Table.h"
#include "ace/OS_Memory.h"
#include "ace/OS_NS_stdio.h"
#include "ace/OS_NS_string.h"

// Default type for generated code.
const char *const Key_List::default_array_type = "char *";

// in_word_set return type, by default.
const char *const Key_List::default_return_type = "char *";

// How wide the printed field width must be to contain the maximum
// hash value.
int Key_List::field_width = 0;
int Key_List::determined_[ACE_STANDARD_CHARACTER_SET_SIZE];

// Destructor dumps diagnostics during debugging.

Key_List::~Key_List (void)
{
  if (option[DEBUGGING])
    this->dump ();

  // Free up all the nodes in the list.
  while (this->head != 0)
    {
      List_Node *temp;

      // Make sure to delete the linked nodes, as well.
      for (List_Node *ptr = this->head->link;
           ptr != 0;
           ptr = temp)
        {
          temp = ptr->link;
          delete ptr;
        }

      temp = this->head->next;
      delete this->head;
      this->head = temp;
    }
}

// Gathers the input stream into a buffer until one of two things occur:
//
// 1. We read a '%' followed by a '%'
// 2. We read a '%' followed by a '}'
//
// The first symbolizes the beginning of the keyword list proper, The
// second symbolizes the end of the C source code to be generated
// verbatim in the output file.
//
// I assume that the keys are separated from the optional preceding
// struct declaration by a consecutive % followed by either % or }
// starting in the first column. The code below uses an expandible
// buffer to scan off and return a pointer to all the code (if any)
// appearing before the delimiter.

char *
Key_List::special_input (char delimiter)
{
  int size = 80;
  char *buf = 0;
  ACE_NEW_RETURN (buf,
                  char[size],
                  0);
  int c;

  for (int i = 0; (c = getchar ()) != EOF; i++)
    {
      if (c == '%')
        {
          c = getchar ();
          if (c == delimiter)
            {
              // Discard newline...
              while ((c = getchar ()) != '\n')
                continue;

              if (i == 0)
                {
                  buf[0] = '\0';
                  return buf;
                }
              else
                {
                  buf[delimiter == '%' && buf[i - 2] == ';'
                     ? i - 2
                     : i - 1] = '\0';
                  return buf;
                }
            }
          else
            buf[i++] = '%';
        }
      else if (i >= size)
        {
          // Yikes, time to grow the buffer!

          char *temp = 0;
          ACE_NEW_RETURN (temp,
                          char[size *= 2],
                          0);
          for (int j = 0; j < i; j++)
            temp[j] = buf[j];

          delete [] buf;
          buf = temp;
        }
      buf[i] = c;
    }

  return 0;
}

// Stores any C/C++ source code that must be included verbatim into
// the generated code output.

char *
Key_List::save_include_src (void)
{
  int c = getchar ();

  if (c != '%')
    ungetc (c, stdin);
  else if ((c = getchar ()) != '{')
    ACE_ERROR_RETURN ((LM_ERROR,
                       "internal error, %c != '{' on line %l in file %N",
                       c),
                       0);
  else
    return special_input ('}');
  return (char *) "";
}

// Determines from the input file whether the user wants to build a
// table from a user-defined struct, or whether the user is content to
// simply use the default array of keys.

char *
Key_List::array_type (void)
{
  return special_input ('%');
}

// Sets up the Return_Type, the Struct_Tag type and the Array_Type
// based upon various user Options.

int
Key_List::output_types (void)
{
  if (option[TYPE])
    {
      array_type_ = array_type ();
      if (array_type_ == 0)
        // Something's wrong, but we'll catch it later on....
        return -1;
      else
        {
          // Yow, we've got a user-defined type...
          size_t struct_tag_length = ACE_OS::strcspn (array_type_,
                                                      "{\n\0");
          if (option[POINTER])      // And it must return a pointer...
            {
              ACE_NEW_RETURN (return_type,
                              char[struct_tag_length + 2],
                              -1);
              ACE_OS::strncpy (return_type,
                               array_type_,
                               struct_tag_length);
              return_type[struct_tag_length] = '*';
              return_type[struct_tag_length + 1] = '\0';
            }

          ACE_NEW_RETURN (struct_tag,
                          char[struct_tag_length + 2],
                          -1);
          ACE_OS::strncpy (struct_tag,
                           array_type_,
                           struct_tag_length);
          if (struct_tag[struct_tag_length] != ' ')
            {
              struct_tag[struct_tag_length] = ' ';
              struct_tag_length++;
            }
          struct_tag[struct_tag_length] = '\0';
        }
    }
  else if (option[POINTER])     // Return a char *.
    return_type = (char *) Key_List::default_array_type;
  return 0;
}

// Reads in all keys from standard input and creates a linked list
// pointed to by Head.  This list is then quickly checked for
// ``links,'' i.e., unhashable elements possessing identical key sets
// and lengths.

int
Key_List::read_keys (void)
{
  this->include_src = this->save_include_src ();
  if (this->include_src == 0)
    return -1;
  else if (this->output_types () == -1)
    return -1;
  else
    {
      ACE_Read_Buffer input (stdin);

      char *buffer = input.read ('\n');

      if (buffer == 0)
        ACE_ERROR_RETURN ((LM_ERROR,
                           "No words in input file, did you forget to prepend %%%%"
                           " or use -t accidentally?\n"),
                          -1);
      // Read in all the keywords from the input file.
      else
        {
          List_Node *temp;
          const char *delimiter = option.delimiter ();
          ACE_NEW_RETURN (this->head,
                          List_Node (buffer,
                                     ACE_static_cast (int,
                                       ACE_OS::strcspn (buffer,
                                                        delimiter))),
                          -1);
          for (temp = this->head;
               (buffer = input.read ('\n'))
                 && ACE_OS::strcmp (buffer, "%%");
               temp = temp->next)
            {
              ACE_NEW_RETURN (temp->next,
                              List_Node (buffer,
                                         ACE_static_cast (int,
                                           ACE_OS::strcspn (buffer,
                                                            delimiter))),
                              -1);
              this->total_keys++;
            }

          // See if any additional source code is included at end of
          // this file.
          if (buffer)
            additional_code = 1;

          this->list_len = this->total_keys;

          // Make large hash table for efficiency.
          Hash_Table table (this->list_len * Key_List::TABLE_MULTIPLE);
          List_Node *trail = 0;

          // Test whether there are any links and also set the maximum
          // length an identifier in the keyword list.

          for (temp = head;
               temp != 0;
               temp = temp->next)
            {
              List_Node *ptr = table.find (temp, option[NOLENGTH]);

              // Check for static key links.  We deal with these by
              // building an equivalence class of all duplicate values
              // (i.e., links) so that only 1 keyword is
              // representative of the entire collection.  This
              // *greatly* simplifies processing during later stages
              // of the program.

              if (ptr == 0)
                trail = temp;
              else
                {
                  total_duplicates++;
                  list_len--;
                  trail->next = temp->next;
                  temp->link = ptr->link;
                  ptr->link = temp;

                  // Complain if user hasn't enabled the duplicate
                  // option.
                  if (!option[DUP] || option[DEBUGGING])
                    ACE_ERROR ((LM_ERROR,
                                "Static key link: \"%s\" = \"%s\", with key set \"%s\".\n",
                                temp->key,
                                ptr->key,
                                temp->keysig));
                }

              // Update minimum and maximum keyword length, if needed.
              if (max_key_len < temp->length)
                max_key_len = temp->length;
              if (min_key_len > temp->length)
                min_key_len = temp->length;
            }
        }

      // Exit program if links exists and option[DUP] not set, since
      // we can't continue.
      if (total_duplicates)
        {
          if (option[DUP])
            {
              if (!option[MUTE])
                ACE_ERROR_RETURN ((LM_ERROR,
                                   "%d input keysigs have identical hash values, examine output carefully...\n",
                                   total_duplicates),
                                   0);
            }
          else
            ACE_ERROR_RETURN ((LM_ERROR,
                               "%d input keysigs have identical hash values,\ntry different key positions or use option -D.\n",
                               total_duplicates),
                              -1);
        }
      if (option[ALLCHARS])
        option.keysig_size (max_key_len);
    }

  return 0;
}

// Recursively merges two sorted lists together to form one sorted
// list. The ordering criteria is by frequency of occurrence of
// elements in the key set or by the hash value.  This is a kludge,
// but permits nice sharing of almost identical code without incurring
// the overhead of a function call comparison.

List_Node *
Key_List::merge (List_Node *list1, List_Node *list2)
{
  if (!list1)
    return list2;
  else if (!list2)
    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