base_lis.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,366 行 · 第 1/4 页

  return FALSE;
}


// describe() -- Describes internal structure of each node of this CoolBase_List
// Input:        The output stream to display description on.
// Output:       None.

void CoolBase_List::describe(ostream& os) {
  os << "\nCoolBase_List " << this << ":\n";
  int count = 0;
  for (CoolBase_List_Node* np = this->node_ptr; np != NULL; np = np->next, count++) 
  {
    os << "Node" << count << ":\n";
    os << " Data = ";
    this->output_data(os,np);
    os << "\n";
    os << " Ref count = " << np->ref_count << "\n";
  }
}


// operator<<() -- Overload output operator for CoolBase_List objects
// Input:          An output stream reference and CoolBase_List reference
// Output:         An output stream reference.

ostream& operator<<(ostream& os, const CoolBase_List& l) {
  os << "(";
  CoolBase_List_Node* np = l.node_ptr;
  if (np != NULL) {
    l.output_data(os, np);
    for (np = np->next; np != NULL; np = np->next) {
      os << " ";
      l.output_data(os,np);
    }
  }
  return os << ")";
}


// new_list() -- Returns new CoolBase_List with head node initialized to specified node
// Input:        The node pointer.
// Output:       A pointer to the new CoolBase_List.

CoolBase_List* CoolBase_List::new_list(CoolBase_List_Node*) {
#if ERROR_CHECKING
  //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::new_list(): Method called is redundant.\n");
#endif
  return (CoolBase_List*)NULL;  
}


// insert_before_node() -- Inserts a new node before the specified node.
// Input:                  A Type reference and a Node pointer.
// Output:                 A pointer to the new node.

CoolBase_List_Node* CoolBase_List::insert_before_node(const void*, CoolBase_List_Node*) {
#if ERROR_CHECKING
  //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::insert_before_node(): Method called is redundant.\n");
#endif
 return NULL;
}


// insert_after_node() -- Inserts a new node after the specified node.
// Input:                 A Type reference and a Node pointer.
// Output:                A pointer to the new node.

CoolBase_List_Node* CoolBase_List::insert_after_node(const void*, CoolBase_List_Node*) const {
#if ERROR_CHECKING
  //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::insert_after_node(): Method called is redundant.\n");
#endif
 return NULL;
}


// compare_data() -- Compares data using default compare function of this CoolBase_List
// Input:            Two const void* pointers which will be type cast.
// Output:           None.

Boolean CoolBase_List::compare_data(const void*, const void*) const {
#if ERROR_CHECKING
  //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::compare_data(): Method called is redundant.\n");
#endif
  return FALSE;
}


// output_data()  -- Outputs node data from specified stream.
// Input:            An output stream reference and node pointer.
// Output:           A void* pointer of data.

void CoolBase_List::output_data(ostream&, const CoolBase_List_Node*) const {

#if ERROR_CHECKING
  //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::output_data(): Method called is redundant.\n");
#endif
}


// copy_nodes() -- Returns a copy of nodes in THIS CoolBase_List.
// Input:          NONE.
// Output:         The first node pointer of copy.

CoolBase_List_Node* CoolBase_List::copy_nodes() const {
  CoolBase_List_Node *np, *first_np;
  if ((np = this->node_ptr) == NULL)  
     first_np = NULL;
  else {
    // copy first node of this CoolBase_List
    first_np = this->insert_after_node(np->get_data(), NULL);
    CoolBase_List_Node* rest_np = first_np;

    // copy rest of nodes of this CoolBase_List
    for (np = np->next; np != NULL; np = np->next) {
      rest_np = this->insert_after_node(np->get_data(), rest_np);
    }
  }
  return first_np;
}


void CoolBase_List::free_nodes(CoolBase_List_Node* np) {
  do {
    if (np->ref_count < 0) {
      cout << "\nWarning: negative ref count of " << np->ref_count;
      cout << " for data ";
      this->output_data(cout, np);
      cout << " and ";
#if GENERIC_TYPECHECK
      cout << (this->type_of())->name() << " = ";
#endif
      cout << this << ".\n";
    } 
    // no longer sharing this node with other CoolBase_Lists
    CoolBase_List_Node* next_np = np->next;     // save pointer to next node
    np->next = NULL;
//  delete np->data;                        // not nec. data is ptr or obj
    delete np;                              // delete node structure
    np = next_np;                           // check reference of next node
  }
  while (np != NULL && --(np->ref_count) <= 0);
}

// operator= -- Assigns THIS to the specified CoolBase_List.
// Input:       A reference to a CoolBase_List which THIS will be assigned to.
// Output:      The modified THIS.

CoolBase_List* CoolBase_List::operator=(const CoolBase_List& l) {
  this->reset();                                // make current position invalid
  this->reference(l.node_ptr);                  // will point to new stuff
  this->dereference(this->node_ptr);            // delete old stuff
  this->node_ptr = l.node_ptr;
  return this;
}


// operator[]() -- Returns the nth node of this CoolBase_List
// Input:          A positive integer index.
// Output:         A pointer to the nth node.

CoolBase_List_Node* CoolBase_List::operator[] (int n) {
  int count = n;
  CoolBase_List_Node *np, *prev_np;
  for (np = this->node_ptr, prev_np = NULL;
      np != NULL && count > 0;
      prev_np = np, np = np->next, count--);

  // if n<length,  found nth node
  if (np != NULL && count == 0) {
    this->curpos = np;
    this->prevpos = prev_np;
    return np;
  }
  else return (CoolBase_List_Node*)NULL;  // or error
}


// position() -- Returns the position of the specified data item in this CoolBase_List,
//               else returns -1 if not found
// Input:        A void* pointer of a data item.
// Output:       The integer position.

int CoolBase_List::position(const void* x) {
  int index = 0;
  // NOTE: It's faster to call do_find, then count the position,
  // than to do the search ourselves using compare_data and get_data.
  if(!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
    return -1;
  else {
    int index = 0;
    CoolBase_List_Node* cp = this->curpos;
    CoolBase_List_Node* np = this->node_ptr;
    while (np != cp) np = np->next, index++;
    return index;
  }
}


// do_find() -- Returns TRUE if the specified element is a member of THIS CoolBase_List.
// Input:       A void* pointer of data item to be searched.
// Output:      TRUE or FALSE.

Boolean CoolBase_List::do_find(CoolBase_List_Node*, const void*,
                      CoolBase_List_Node*&, CoolBase_List_Node*&) const {
  cout << "\nWarning:  CoolBase_List_Node::find(x) has been called.\n";
  return FALSE;
}

// member() -- Returns TRUE if THIS CoolBase_List contains the specified element and
//             sets the specified CoolBase_List to a subList in THIS CoolBase_List starting
//             at the first occurence of element.
// Input:      A reference to the CoolBase_List which will be set to a subCoolBase_List within
//             THIS CoolBase_List, and a void* pointer of data item to be searched.
// Output:     A CoolBase_List pointer to some tail of THIS.

Boolean CoolBase_List::member(CoolBase_List& l,const void* x) {
  this->dereference(l.node_ptr);
  if (this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
    this->reference(this->curpos);
    l.node_ptr = this->curpos;
    return TRUE;
  } else {
    l.node_ptr = NULL;
    return FALSE;
  }
}


// push() -- Prepends the specified data item to the front of CoolBase_List
// Input:    A void* pointer of the data item to be prepended.
// Output:   Always TRUE.

Boolean CoolBase_List::push(const void* x) {
  this->curpos = this->insert_before_node(x, this->node_ptr);
  this->node_ptr = this->curpos;
  this->prevpos = NULL;
  return TRUE;
}


// push_new() -- Pushes a new element at head of THIS CoolBase_List if it is not already
//               a member of the CoolBase_List.
// Input:        A void* pointer of new data.
// Output:       TRUE if item not on CoolBase_List, FALSE otherwise.

Boolean CoolBase_List::push_new(const void* x) {
  CoolBase_List_Node* cp;
  CoolBase_List_Node* pp;
  if (!this->do_find(this->node_ptr, x, cp, pp)) // don't change curpos
    return push(x);
  else
    return FALSE;
}


// push_end() -- Appends the specified data item to the end of this CoolBase_List
// Input:        A void* pointer of the data item to be appended.
// Output:       Always TRUE.

Boolean CoolBase_List::push_end(const void* x) {
  CoolBase_List_Node* last_np = this->node_ptr;
  if (last_np == NULL) {  
    // there arn't any nodes in this CoolBase_List; x will be the head node
    this->node_ptr = this->curpos = this->insert_after_node(x, NULL);
    this->prevpos = NULL;
  }
  else {
    CoolBase_List_Node* cp = this->curpos;
    // find last node of this CoolBase_List
    if (cp != NULL && cp->next == NULL)
      last_np = cp;
    else
      while(last_np->next != NULL) last_np = last_np->next;
    // insert x after last node
    this->curpos = this->insert_after_node(x, last_np);  
    this->prevpos = last_np;
  }
 return TRUE;
}


// push_end_new() -- Pushes a new element at end of THIS CoolBase_List if it is not
//                   already a member of the CoolBase_List.
// Input:            A void* pointer of new data.
// Output:           TRUE if item not on CoolBase_List, FALSE otherwise.

Boolean CoolBase_List::push_end_new(const void* x) {
  if (!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
    return this->push_end(x);
  else
    return FALSE;
}


// pop() -- Removes and returns head element of THIS CoolBase_List.
// Input:   None.
// Output:  Node pointer containing head data element of THIS CoolBase_List.

CoolBase_List_Node* CoolBase_List::pop() {
  CoolBase_List_Node* old_head = this->node_ptr;
  if (old_head != NULL) {
    this->reset();                              // make current position invalid
    this->node_ptr = old_head->next;
    this->reference(old_head->next);
    return old_head;
  }
  else return NULL;
}


// remove() -- Removes item at current position.
// Input:      None.
// Output:     The node pointer of item removed.

CoolBase_List_Node*  CoolBase_List::remove() {
  if (this->curpos == NULL)
    return NULL;
  CoolBase_List_Node* np = this->prevpos;
  CoolBase_List_Node* cp = this->curpos;
  if (np == NULL || np->next != cp) { 
    np  = this->node_ptr;
    if (np == cp) {                             // node to remove is head node
      this->curpos = np->next;
      this->node_ptr = np->next;                // this points to next of head
      this->reference(np->next);                
      return np;
    }
    // find previous node current position
    while (np != NULL && np->next != this->curpos) np = np->next;
    if (np == NULL) return NULL;                // error: curpos was not in list
    else this->prevpos = np;
  }
  np->next = cp->next;
  this->curpos = cp->next;
  this->reference(cp->next);
  return cp;