chain.hpp

Go to the documentation of this file.

#ifndef _CSDBG_CHAIN
#define _CSDBG_CHAIN 1

#include "./node.hpp"
#include "./exception.hpp"

namespace csdbg {

template <class T>
class chain: virtual public object
{
protected:

  /* Protected variables */

  node<T> *m_head;                  
  node<T> *m_tail;                  
  u32 m_size;                       
  /* Protected generic methods */

  virtual node<T>* node_at(u32) const;

  virtual node<T>* node_with(const T*) const;

  virtual node<T>* detach_node(u32);

public:

  /* Constructors, copy constructors and destructor */

  chain();

  chain(const chain&);

  virtual ~chain();

  virtual chain* clone() const;


  /* Accessor methods */

  virtual u32 size() const;


  /* Operator overloading methods */

  virtual chain& operator=(const chain&);

  virtual T* operator[](u32) const;


  /* Generic methods */

  virtual chain& add(T*);

  virtual chain& remove(u32);

  virtual chain& clear();

  virtual T* at(u32) const;

  virtual T* detach(u32);

  virtual chain& foreach(void (*)(u32, T*)) const;
};


template <class T>
node<T>* chain<T>::node_at(u32 i) const
{
  if ( unlikely(i >= m_size) )
    throw exception("offset out of chain bounds (%d >= %d)", i, m_size);

  /* Select traversal direction */
  node<T> *cur = m_head;
  i32 j = i, mid = m_size / 2;
  if (j >= mid) {
    j = m_size - i - 1;
    cur = m_tail;
  }

  node<T> *prev = NULL, *next;
  while ( likely(j-- > 0) ) {
    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  return cur;
}


template <class T>
node<T>* chain<T>::node_with(const T *d) const
{
  __D_ASSERT(d != NULL);
  if ( unlikely(d == NULL) )
    return NULL;

  node<T> *cur = m_head, *prev = NULL, *next;
  while ( likely(cur != NULL) ) {
    if ( unlikely(cur->m_data == d) )
      return cur;

    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  return NULL;
}


template <class T>
node<T>* chain<T>::detach_node(u32 i)
{
  if ( unlikely(i >= m_size) )
    throw exception("offset out of chain bounds (%d >= %d)", i, m_size);

  node<T> *cur = m_head, *prev = NULL, *next;
  while ( likely(i-- > 0) ) {
    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  next = cur->link(prev);

  /* If it's the first in the chain */
  if ( unlikely(cur == m_head) ) {
    m_head = next;

    /* If the chain is left empty */
    if ( unlikely(m_head == NULL) )
      m_tail = NULL;
    else
      m_head->unlink_from(cur);
  }

  /* If it's the last in the chain */
  else if ( unlikely(cur == m_tail) ) {
    m_tail = prev;
    m_tail->unlink_from(cur);
  }

  /* Relink previous and next nodes */
  else {
    prev->unlink_from(cur);
    prev->link_to(next);

    next->unlink_from(cur);
    next->link_to(prev);
  }

  m_size--;
  return cur;
}


template <class T>
inline chain<T>::chain():
m_head(NULL),
m_tail(NULL),
m_size(0)
{
}


template <class T>
inline chain<T>::chain(const chain &src)
try:
m_head(NULL),
m_tail(NULL),
m_size(0)
{
  *this = src;
}

catch (...) {
  clear();
}


template <class T>
inline chain<T>::~chain()
{
  clear();
}


template <class T>
inline chain<T>* chain<T>::clone() const
{
  return new chain(*this);
}


template <class T>
inline u32 chain<T>::size() const
{
  return m_size;
}


template <class T>
chain<T>& chain<T>::operator=(const chain &rval)
{
  if ( unlikely(this == &rval) )
    return *this;

  /* Check if the chains overlap and detach shared data pointers */
  node<T> *cur = m_head, *prev = NULL, *next;
  while ( likely(cur != NULL) ) {
    if ( unlikely(rval.node_with(cur->m_data) != NULL) )
      cur->detach();

    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  clear();
  cur = rval.m_head;
  prev = NULL;
  while ( likely(cur != NULL) ) {
    T *copy = NULL;
    try {
      copy = new T(*cur->m_data);
      add(copy);
    }

    catch (...) {
      delete copy;
      throw;
    }

    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  return *this;
}


template <class T>
inline T* chain<T>::operator[](u32 i) const
{
  return at(i);
}


template <class T>
chain<T>& chain<T>::add(T *d)
{
  if ( unlikely(d == NULL) )
    throw exception("invalid argument: d (=%p)", d);

  /* If the data pointer already exists in the chain */
  if ( unlikely(node_with(d) != NULL) )
    throw exception("chain @ %p already has a node with data @ %p", this, d);

  node<T> *n = new node<T>(d);

  /* Add the node to the chain tail */
  if ( likely(m_head != NULL) ) {
    n->m_link = m_tail;
    m_tail->link_to(n);
    m_tail = n;
  }

  /* If it is the first node */
  else
    m_head = m_tail = n;

  m_size++;
  return *this;
}


template <class T>
inline chain<T>& chain<T>::remove(u32 i)
{
  delete detach_node(i);
  return *this;
}


template <class T>
chain<T>& chain<T>::clear()
{
  node<T> *cur = m_head, *prev = NULL, *next;
  while ( likely(cur != NULL) ) {
    next = cur->link(prev);
    prev = cur;

    delete cur;
    cur = next;
  }

  m_head = m_tail = NULL;
  m_size = 0;
  return *this;
}


template <class T>
inline T* chain<T>::at(u32 i) const
{
  return node_at(i)->m_data;
}


template <class T>
inline T* chain<T>::detach(u32 i)
{
  node<T> *n = detach_node(i);
  T *d = n->detach();
  delete n;
  return d;
}


template <class T>
chain<T>& chain<T>::foreach(void (*pfunc)(u32, T*)) const
{
  __D_ASSERT(pfunc != NULL);
  if ( unlikely(pfunc == NULL) )
    return const_cast<chain<T>&> (*this);

  u32 i = 0;
  node<T> *cur = m_head, *prev = NULL, *next;
  while ( likely(cur != NULL) ) {
    pfunc(i++, cur->m_data);

    next = cur->link(prev);
    prev = cur;
    cur = next;
  }

  return const_cast<chain<T>&> (*this);
}

}

#endif