ListImplem.H

Go to the documentation of this file.

/*   _______              __
    / ___/ /  ___  __ _  / /  ___
   / /__/ _ \/ _ \/  V \/ _ \/ _ \
   \___/_//_/\___/_/_/_/_.__/\___/
*/
// CHOMBO Copyright (c) 2000-2004, The Regents of the University of
// California, through Lawrence Berkeley National Laboratory (subject to
// receipt of any required approvals from U.S. Dept. of Energy).  All
// rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// (1) Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// (2) Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// (3) Neither the name of Lawrence Berkeley National Laboratory, U.S.
// Dept. of Energy nor the names of its contributors may be used to endorse
// or promote products derived from this software without specific prior
// written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// You are under no obligation whatsoever to provide any bug fixes,
// patches, or upgrades to the features, functionality or performance of
// the source code ("Enhancements") to anyone; however, if you choose to
// make your Enhancements available either publicly, or directly to
// Lawrence Berkeley National Laboratory, without imposing a separate
// written license agreement for such Enhancements, then you hereby grant
// the following license: a non-exclusive, royalty-free perpetual license
// to install, use, modify, prepare derivative works, incorporate into
// other computer software, distribute, and sublicense such Enhancements or
// derivative works thereof, in binary and source code form.
//
// TRADEMARKS. Product and company names mentioned herein may be the
// trademarks of their respective owners.  Any rights not expressly granted
// herein are reserved.
//

#ifndef _LISTIMPLEM_H_
#define _LISTIMPLEM_H_

#include "MayDay.H"

//
// List members
//
template <class T>
Pool List<T>::linkPool(sizeof(ListLink<T>), typeid(T).name(), 300);

template <class T>
List<T>::List (const List<T>& source)
    : head(0),
      tail(0)
{
    if (source.isEmpty())
        tail = head = 0;
    else
        for (ListIterator<T> li(source); li; ++li)
            append(li());
}

//
// This isn't inlined as it's declared virtual.
//

template <class T>
void
List<T>::add (const T& value)
{
    append(value);
}

template <class T>
int
List<T>::length () const
{
    int len = 0;
    for (ListIterator<T> li(*this); li; ++li)
        len++;
    return len;
}

template <class T>
List<T>&
List<T>::operator= (const List<T>& source)
{
    if (!(this == &source))
    {
        clear();
        for (ListIterator<T> li(source); li; ++li)
            append(li());
    }
    return *this;
}

template <class T>
ListLink<T> *
List<T>::addBefore (ListLink<T>* ln,
                    const T&     val)
{
    CH_assert(ln != 0 || head == 0);

    ListLink<T>* newlink;

    if (ln == head)
    {
      //head = newlink = new ListLink<T>(val, 0, head);
      head = newlink = new (linkPool.getPtr()) ListLink<T>(val, 0, head);
        if (tail == 0)
            tail = head;
        else
            head->suc->pre = newlink;
    }
    else
    {
      //newlink = new ListLink<T>(val, ln->pre, ln);
      newlink = new (linkPool.getPtr()) ListLink<T>(val, ln->pre, ln);
      ln->pre->suc = newlink;
      ln->pre = newlink;
    }

    if (newlink == 0)
      MayDay::Error("Out of memory in ListLink::addBefore");

    return newlink;
}

template <class T>
ListLink<T>*
List<T>::addAfter (ListLink<T>* ln,
                   const T&     val)
{
    CH_assert(ln != 0 || tail == 0);

    ListLink<T>* newlink;

    if (ln == tail)
    {
      //tail = newlink = new ListLink<T>(val,tail,0);
      tail  = newlink = new (linkPool.getPtr()) ListLink<T>(val,tail,0);
        if (head == 0)
            head = tail;
        else
            tail->pre->suc = newlink;
    }
    else
    {
      //newlink = new ListLink<T>(val, ln, ln->suc);
      newlink = new (linkPool.getPtr()) ListLink<T>(val, ln, ln->suc);
        ln->suc->pre = newlink;
        ln->suc = newlink;
    }

    if (newlink == 0)
      MayDay::Error("Out of memory in ListLink::addAfter");

    return newlink;
}

template <class T>
void
List<T>::join (const List<T>& list2)
{
    for (ListIterator<T> li2(list2); li2; ++li2)
        append(li2());
}

template <class T>
void
List<T>::catenate (List<T>& list2)
{
    if (list2.isEmpty())
        //
        // Do nothing.
        //
        ;
    else if (isEmpty())
    {
       head = list2.head;
       tail = list2.tail;
       list2.head = 0;
       list2.tail = 0;
    }
    else
    {
        tail->suc = list2.head;
        list2.head->pre = tail;
        tail = list2.tail;
        list2.head = 0;
        list2.tail = 0;
    }
}

template <class T>
void
List<T>::clear ()
{
    ListLink<T>* next = 0;

    for (ListLink<T>* p = head; p != 0; p = next)
    {
        next = p->suc;
        p->suc = 0;
        //delete p;
        p->val.~T();
        linkPool.returnPtr(p);

    }
    tail = head = 0;
}

template <class T>
bool
List<T>::includes (const T& v) const
{
    bool rc = false;
    for (ListIterator<T> li(*this); li && !rc; ++li)
        if (v == li())
            rc = true;
    return rc;
}

template<class T>
bool
List<T>::operator== (const List<T>& rhs) const
{
    if (length() == rhs.length())
    {
        for (ListIterator<T> li(*this), ri(rhs); li; ++li, ++ri)
            if (li() != ri())
                return false;
        return true;
    }

    return false;
}

template<class T>
bool
List<T>::operator!= (const List<T>& rhs) const
{
    return !operator==(rhs);
}

template <class T>
void
List<T>::transfer(ListIterator<T>& li)
{

  CH_assert(&(li.list) != this);
  List<T>& other = (List<T>&)(li.list);

  ListLink<T>* p = li.p;
  li.p = p->suc; //push iterator ahead;

  // remove p from other list.
  other.removeLink(p);

  if(head == 0){
    head = tail = p;
    p->pre=0;
    p->suc=0;
  }
  else {
    p->suc=0;
    tail->suc = p;
    p->pre = tail;
    tail = p;
  }

}

template <class T>
void
List<T>::remove (ListIterator<T>& li)
{
    ListLink<T> *np = li.p->suc;
    remove(li.p);
    li.p = np;
}

template <class T>
void
List<T>::remove (const T& _v)
{
    for (ListIterator<T> litr(*this); litr; ++litr)
        if (litr() == _v)
            remove(litr);
}

template <class T>
void
List<T>::remove (const List<T>& _lv)
{
    for (ListIterator<T> litr(_lv); litr; ++litr)
        remove(litr());
}

template <class T>
void
List<T>::removeLink (ListLink<T>* ln)
{
    CH_assert(head !=0 && tail != 0);

    if (head == tail)
      {
        CH_assert(head == ln);
        head = tail = 0;
      }
    else if (head == ln)
    {
        CH_assert(ln->pre == 0);
        head = ln->suc;
        head->pre = 0;
    }
    else if (tail == ln)
    {
        CH_assert(ln->suc == 0);
        tail = ln->pre;
        tail->suc  = 0;
    }
    else
    {
        CH_assert(ln->suc != 0 && ln->pre != 0);
        ln->suc->pre = ln->pre;
        ln->pre->suc = ln->suc;
    }

}

template <class T>
void
List<T>::remove(ListLink<T>* ln)
{
  removeLink(ln);
  //delete ln;
  ln->val.~T();
  linkPool.returnPtr(ln);

  ln = 0;
}

#endif  /* CH_LISTIMPLEM_H */

---