//-----------------------------------------------------------------------------
// Copyright (c) 1994,1995 Southeastern Universities Research Association,
//                         Continuous Electron Beam Accelerator Facility
//
// This software was developed under a United States Government license
// described in the NOTICE file included as part of this distribution.
//
//-----------------------------------------------------------------------------
// 
// Description:
//	 Single Linked List for void *
//
//       Note: remove and clean operations on the list
//             will only remove link nodes without removal of
//             the content inside the nodes. It is callers' 
//             responsiblity to clean up those contents
//
//       This is unsafe C++ practice, use this list at you own risk
//       
//       Reason for this list: It is very difficult to instantiate
//       a template class in a stand alone shared library
//	
// Author:  Jie Chen
//       CEBAF Data Acquisition Group
//
// Revision History:
//   rsvcSlist.cc,v
// Revision 1.1  1998/01/22  17:08:22  akers
// Addition of new NameServer
//
//
//
#include "rsvcSlist.h"

//======================================================================
//	class rsvcSlist implementation
//======================================================================
rsvcSlist::rsvcSlist (void)
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
:ptrToFirstLink(0), count_ (0), lock_ ()
#else
:ptrToFirstLink(0), count_ (0)
#endif
{
#ifdef _TRACE_OBJECTS
  printf ("Create rsvcSlist Class Object\n");
#endif
  // no further initialization
}

rsvcSlist::rsvcSlist (const rsvcSlist & source)
:count_ (source.count_)
{
#ifdef _TRACE_OBJECTS
  printf ("Create rsvcSlist Class Object\n");
#endif

  // duplicate elements from source list
  if (source.isEmpty_i())
    ptrToFirstLink = 0;
  else{
    rsvcSlistLink * firstLink = source.ptrToFirstLink;
    ptrToFirstLink = firstLink->duplicate();
  }
}

rsvcSlist::~rsvcSlist (void)
{
  // empty all elements from the list
#ifdef _TRACE_OBJECTS
  printf ("Delete rsvcSlist Class Object\n");
#endif
  deleteAllValues();
}

void
rsvcSlist::add (rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // add a new value to the front of a linked list
  ptrToFirstLink = new rsvcSlistLink(val, ptrToFirstLink);
  count_ ++;
  assert(ptrToFirstLink != 0);
}

void
rsvcSlist::addToEnd (rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  count_ ++;
  if (ptrToFirstLink == 0) {
    ptrToFirstLink = new rsvcSlistLink(val, ptrToFirstLink); 
    return;
  }

  // loop through until last element
  rsvcSlistLink *p = 0;
  for (p = ptrToFirstLink; p->ptrToNextLink; p = p->ptrToNextLink)
    ;

  rsvcSlistLink* q = new rsvcSlistLink (val, 0);
  p->ptrToNextLink = q;
}

void
rsvcSlist::add_i (rsvcSlistItem val)
{
  // add a new value to the front of a linked list
  count_ ++;
  ptrToFirstLink = new rsvcSlistLink(val, ptrToFirstLink);
  assert(ptrToFirstLink != 0);
}

int
rsvcSlist::remove (rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // remove an element from the list
  // loop to test each element
  rsvcSlistLink *q = ptrToFirstLink;
  for (rsvcSlistLink * p = ptrToFirstLink; p; p = p->ptrToNextLink){
    if (val == p->value){
      if (q == p){
	// remove first element
	ptrToFirstLink = p->ptrToNextLink;
	delete p;
      }
      else{
        q->ptrToNextLink = p->ptrToNextLink;
	delete p;
      }
      count_ --;
      return 1;
    }
    q = p;
  }
  // not found
  return 0; 
}

void
rsvcSlist::deleteAllValues (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // clear all items from the list
  rsvcSlistLink * next;

  for (rsvcSlistLink * p = ptrToFirstLink; p != 0; p = next){
    // delete the element pointed to by p
    next = p->ptrToNextLink;
    p->ptrToNextLink = 0;
    delete p;
  }
  
  // set count to zero
  count_ = 0;
  // mark that the list contains no elements
  ptrToFirstLink = 0;
}

void
rsvcSlist::deleteAllValues_i (void)
{
  // clear all items from the list
  rsvcSlistLink * next;

  for (rsvcSlistLink * p = ptrToFirstLink; p != 0; p = next){
    // delete the element pointed to by p
    next = p->ptrToNextLink;
    p->ptrToNextLink = 0;
    delete p;
  }
  
  // set count to zero
  count_ = 0;

  // mark that the list contains no elements
  ptrToFirstLink = 0;
}

int
rsvcSlist::count (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  return count_;
}

rsvcSlist*
rsvcSlist::duplicate (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  rsvcSlist * newlist = new rsvcSlist;
  assert(newlist != 0);

  // copy list
  if (ptrToFirstLink)
    newlist->ptrToFirstLink = ptrToFirstLink->duplicate();

  // set new list count
  newlist->count_ = count_;
  // return the new list
  return newlist;
}

rsvcSlistItem
rsvcSlist::firstElement (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // return first value in list
  assert(ptrToFirstLink != 0);
  return ptrToFirstLink->value;
}

rsvcSlistItem
rsvcSlist::firstElement_i (void)
{
  // return first value in list
  assert(ptrToFirstLink != 0);
  return ptrToFirstLink->value;
}

rsvcSlistItem
rsvcSlist::lastElement (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  assert(ptrToFirstLink != 0);
  // loop through until last element
  rsvcSlistLink *p = 0;
  for (p = ptrToFirstLink; p->ptrToNextLink; p = p->ptrToNextLink)
    ;
  return p->value;
}

rsvcSlistItem
rsvcSlist::lastElement_i (void)
{
  assert(ptrToFirstLink != 0);
  // loop through until last element
  rsvcSlistLink *p = 0;
  for (p = ptrToFirstLink; p->ptrToNextLink; p = p->ptrToNextLink)
    ;
  return p->value;
}

int
rsvcSlist::includes(rsvcSlistItem v)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // loop to test each element
  for (rsvcSlistLink * p = ptrToFirstLink; p; p = p->ptrToNextLink)
    if (v == p->value)
      return 1;
  
  // not found
  return 0;
}

int
rsvcSlist::isEmpty (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // test to see if the list is empty
  // list is empty if the pointer to the first link is null
  return ptrToFirstLink == 0;
}

int
rsvcSlist::isEmpty_i (void) const
{
  // test to see if the list is empty
  // list is empty if the pointer to the first link is null
  return ptrToFirstLink == 0;
}

void
rsvcSlist::removeFirst (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // make sure there is a first element
  assert(ptrToFirstLink != 0);
  
  // save pointer to the removed node
  rsvcSlistLink * p = ptrToFirstLink;

  // reassign the ptrToFirstLink node
  ptrToFirstLink = p->ptrToNextLink;

  // decrease the count
  count_ --;
  // recover memory used by the first element
  delete p;
}

void
rsvcSlist::removeFirst_i (void)
{
  // make sure there is a first element
  assert(ptrToFirstLink != 0);
  
  // save pointer to the removed node
  rsvcSlistLink * p = ptrToFirstLink;

  // reassign the ptrToFirstLink node
  ptrToFirstLink = p->ptrToNextLink;

  // decrease the count
  count_ --;

  // recover memory used by the first element
  delete p;
}

//======================================================================
//	class slink implementation
//           No need to add any mutex protection since all member
//           functions are called with lock held
//======================================================================
rsvcSlistLink* 
rsvcSlistLink::insert(rsvcSlistItem val)
{
  // insert a new link after current node
  ptrToNextLink = new rsvcSlistLink(val, ptrToNextLink);

  // check that allocation was successful
  assert(ptrToNextLink != 0);
  return ptrToNextLink;
}

rsvcSlistLink::rsvcSlistLink (rsvcSlistItem val, rsvcSlistLink * nxt)
:value(val), ptrToNextLink(nxt)
{
  // create and initialize a new link field
}

rsvcSlistLink* 
rsvcSlistLink::duplicate (void)
{
  rsvcSlistLink * newlink;

  // if there is a next field. copy remainder of list
  if (ptrToNextLink != 0)
    newlink = new rsvcSlistLink(value, ptrToNextLink->duplicate());
  else
    newlink = new rsvcSlistLink (value, 0);

  // check that allocation was successful
  assert(newlink != 0);
  return newlink;
}

rsvcSlistLink*
rsvcSlistLink::next (void)
{
  return ptrToNextLink;
}

rsvcSlistItem
rsvcSlistLink::data (void)
{
  return value;
}

//======================================================================
//	class listIterator implementation
//======================================================================
rsvcSlistIterator::rsvcSlistIterator(rsvcSlist & aList)
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
:theList(aList), lock_ ()
#else
:theList(aList)
#endif
{
  // create and initialize a new list
  init_i();
}

int
rsvcSlistIterator::init_i()
{
  // set the iterator to the first element in the list
  previousLink = 0;
  currentLink = theList.ptrToFirstLink;
  return currentLink != 0;
}

int
rsvcSlistIterator::init()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // set the iterator to the first element in the list
  previousLink = 0;
  currentLink = theList.ptrToFirstLink;
  return currentLink != 0;
}

rsvcSlistItem
rsvcSlistIterator::operator () (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif
  // return value of current element
  // check to see if there is a current element
  assert(currentLink != 0);

  // return value associated with current element
  return currentLink->value;
}

int rsvcSlistIterator::operator ! (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif
  // test for termination of the iterator
  // if current link references a removed value,
  // update current to point to next position
  if (currentLink == 0)
    if (previousLink != 0)
      currentLink = previousLink->ptrToNextLink;

  // now see if currentLink is valid
  return currentLink != 0;
}

int rsvcSlistIterator::forward_i (void)
{
  // move current pointer to nect element
  // special processing if current link is deleted
  if (currentLink == 0){
    if (previousLink == 0)
      currentLink = theList.ptrToFirstLink;
    else
      currentLink = previousLink->ptrToNextLink;
  }
  else{
    // advance pointer
    previousLink = currentLink;
    currentLink = currentLink->ptrToNextLink;
  }

  // return true if we have a valid current element
  return currentLink != 0;
}


int rsvcSlistIterator::operator ++()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // move current pointer to nect element
  // special processing if current link is deleted
  if (currentLink == 0){
    if (previousLink == 0)
      currentLink = theList.ptrToFirstLink;
    else
      currentLink = previousLink->ptrToNextLink;
  }
  else{
    // advance pointer
    previousLink = currentLink;
    currentLink = currentLink->ptrToNextLink;
  }

  // return true if we have a valid current element
  return currentLink != 0;
}

void rsvcSlistIterator::operator = (rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // modify value of current element
  assert(currentLink != 0);

  // modify value of the current link
  currentLink->value = val;
}

void rsvcSlistIterator::removeCurrent_i (void)
{
  // remove the current element from a list
  // make sure there is a current element
  assert(currentLink != 0);

  // case 1, removing first element
  if (previousLink == 0)
    theList.ptrToFirstLink = currentLink->ptrToNextLink;
  
  // case 2, not removing the first element
  else
    previousLink->ptrToNextLink = currentLink->ptrToNextLink;
  
  // delete current node
  delete currentLink;

  // and set current pointer to null
  currentLink = 0;

  // decrease list count element
  theList.count_ --;
}

void rsvcSlistIterator::removeCurrent (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // remove the current element from a list
  // make sure there is a current element
  assert(currentLink != 0);

  // case 1, removing first element
  if (previousLink == 0)
    theList.ptrToFirstLink = currentLink->ptrToNextLink;
  
  // case 2, not removing the first element
  else
    previousLink->ptrToNextLink = currentLink->ptrToNextLink;
  
  // delete current node
  delete currentLink;

  // and set current pointer to null
  currentLink = 0;

  // decrease list count element
  theList.count_ --;
}

void rsvcSlistIterator::addBefore(rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // add a new element to list before current value
  // case 1, not at start
  if (previousLink)
    previousLink = previousLink->insert(val);

  // case 2, at start of list
  else{
    theList.rsvcSlist::add(val);
    previousLink = theList.ptrToFirstLink;
    currentLink = previousLink->ptrToNextLink;
  }

  // increase the count
  theList.count_ ++;
}

void rsvcSlistIterator::addAfter(rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // a a new element to list after current value
  // case 1, not at start
  if (currentLink != 0)
    currentLink->insert(val);

  // case 2, at end of list
  else if (previousLink != 0)
    currentLink = previousLink->insert(val);
  
  // case 3, start of list
  else
    theList.rsvcSlist::add(val);

  // increase the count
  theList.count_ ++;
}

int rsvcSlistIterator::searchSame(rsvcSlistItem &val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // search the list to find out whether we have this element
  // if we do, move cursor to this element return 1
  // if we don't return 0
  init_i();

  if (currentLink == 0){
  // empty link 
    return 0;
  }
  while (currentLink != 0){
    // advance pointer
    if (currentLink->value == val)
      break;
    previousLink = currentLink;
    currentLink = currentLink->ptrToNextLink;
  }

  // return true if we have a valid current element
  return currentLink != 0;
}

//========================================================================
//          Implementation of rsvcSlistCursor
//                 Implements of cursor without changing list
//========================================================================
rsvcSlistCursor::rsvcSlistCursor(const rsvcSlist & aList)
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
:theList(aList), lock_ ()
#else
:theList(aList)
#endif
{
  // create and initialize a new list
  init_i();
}

int
rsvcSlistCursor::init_i()
{
  // set the iterator to the first element in the list
  previousLink = 0;
  currentLink = theList.ptrToFirstLink;
  return currentLink != 0;
}

int
rsvcSlistCursor::init()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // set the iterator to the first element in the list
  previousLink = 0;
  currentLink = theList.ptrToFirstLink;
  return currentLink != 0;
}

rsvcSlistItem
rsvcSlistCursor::operator () (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // return value of current element
  // check to see if there is a current element
  assert(currentLink != 0);

  // return value associated with current element
  return currentLink->value;
}

int rsvcSlistCursor::operator ! (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // test for termination of the iterator
  // if current link references a removed value,
  // update current to point to next position
  if (currentLink == 0)
    if (previousLink != 0)
      currentLink = previousLink->ptrToNextLink;
  
  // now see if currentLink is valid
  return currentLink != 0;
}

int rsvcSlistCursor::operator ++ (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // move current pointer to nect element
  // special processing if current link is deleted
  if (currentLink == 0){
    if (previousLink == 0)
      currentLink = theList.ptrToFirstLink;
    else
      currentLink = previousLink->ptrToNextLink;
  }
  else{
    // advance pointer
    previousLink = currentLink;
    currentLink = currentLink->ptrToNextLink;
  }

  // return true if we have a valid current element
  return currentLink != 0;
}

int rsvcSlistCursor::searchSame (rsvcSlistItem &val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif
  // search the list to find out whether we have this element
  // if we do, move cursor to this element return 1
  // if we don't return 0
  init_i();

  if (currentLink == 0){
    // empty link 
    return 0;
  }
  while (currentLink != 0){
    // advance pointer
    if (currentLink->value == val)
      break;
    previousLink = currentLink;
    currentLink = currentLink->ptrToNextLink;
  }

  // return true if we have a valid current element
  return currentLink != 0;
}

void rsvcSlistCursor::operator = (rsvcSlistItem )
{
  // empty
}


//========================================================================
//          Implementation of doubleEndedList
//========================================================================
rsvcDoubleEndedSlist::rsvcDoubleEndedSlist()
:rsvcSlist()
{
  ptrToLastLink = 0;
}

rsvcDoubleEndedSlist::rsvcDoubleEndedSlist(const rsvcDoubleEndedSlist &v)
:rsvcSlist(v)
{
  ptrToLastLink = v.ptrToLastLink;
}

void
rsvcDoubleEndedSlist::add(rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  // add method needs to check one special case when the first element
  // is added to the list
  if (isEmpty_i()) {
    // call parent method
    rsvcSlist::add_i (val);
    ptrToLastLink = ptrToFirstLink;
  }
  else{
    // always add to the head
    rsvcSlist::add_i(val);
  }
}

void 
rsvcDoubleEndedSlist::addToEnd (rsvcSlistItem val)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif

  //add new value T to the end of the list
  // if there is an end, add to it
  if(ptrToLastLink != 0) {
    ptrToLastLink = ptrToLastLink->insert(val);
    count_ ++;
  }
  else {
    assert (isEmpty_i ());
    // call parent method
    rsvcSlist::add_i (val);
    ptrToLastLink = ptrToFirstLink;
  }
}

void
rsvcDoubleEndedSlist::deleteAllValues()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif
  //delete all values from the list
  rsvcSlist::deleteAllValues_i();
  ptrToLastLink = 0;
}

void
rsvcDoubleEndedSlist::removeFirst()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard(lock_);
#endif
  //remove the first element from the list
  // invoke the parent method
  rsvcSlist::removeFirst_i();
  
  // only do something if we removed last element
  if(isEmpty_i())
    ptrToLastLink = 0;
}


//========================================================================
//          Implementation of queue
//========================================================================
rsvcQueue::rsvcQueue (void)
:rsvcDoubleEndedSlist ()
{
#ifdef _TRACE_OBJECTS
  printf ("         Create rsvcQueue Class Object\n");
#endif
}

rsvcSlistItem
rsvcQueue::front (void)
{
  return firstElement ();
}

void
rsvcQueue::enqueue (rsvcSlistItem val)
{
  // add new value val to the end of the list
  // if there is an end, add to it
  if(ptrToLastLink != 0) {
    ptrToLastLink = ptrToLastLink->insert(val);
    count_ ++;
  }
  else {
    assert (isEmpty_i ());
    // call parent method
    rsvcSlist::add_i (val);
    ptrToLastLink = ptrToFirstLink;
  }
}  

rsvcSlistItem
rsvcQueue::dequeue (void)
{
  if (isEmpty_i ())
    return 0;

 // get first element
  rsvcSlistItem result = firstElement_i ();
  //remove the first element from the list
  // invoke the parent method
  rsvcSlist::removeFirst_i();
  
  // only do something if we removed last element
  if(isEmpty_i())
    ptrToLastLink = 0;

  return result;
}
