stack.hpp

Go to the documentation of this file.

#ifndef _CSDBG_STACK
#define _CSDBG_STACK 1

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

namespace csdbg {

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

  /* Protected variables */

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

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

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

public:

  /* Constructors, copy constructors and destructor */

  stack();

  stack(const stack&);

  virtual ~stack();

  virtual stack* clone() const;


  /* Accessor methods */

  virtual u32 size() const;


  /* Operator overloading methods */

  virtual stack& operator=(const stack&);

  virtual T* operator[](u32) const;


  /* Generic methods */

  virtual stack& push(T*);

  virtual stack& pop();

  virtual stack& clear();

  virtual T* peek(u32) const;

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


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

  node<T> *n = m_top;
  while ( likely(i-- > 0) )
    n = n->m_link;

  return n;
}


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

  for (node<T> *n = m_top; likely(n != NULL); n = n->m_link)
    if ( unlikely(n->m_data == d) )
      return n;

  return NULL;
}


template <class T>
inline stack<T>::stack():
m_top(NULL),
m_size(0)
{
}


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

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


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


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


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


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

  /* Check if the stacks overlap and detach shared data pointers */
  for (node<T> *n = m_top; likely(n != NULL); n = n->m_link)
    if ( unlikely(rval.node_with(n->m_data) != NULL) )
      n->detach();

  clear();
  for (node<T> *n = rval.m_top; likely(n != NULL); n = n->m_link) {
    T *copy = NULL;
    try {
      copy = new T(*n->m_data);
      push(copy);
    }

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

  return *this;
}


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


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

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

  node<T> *n = new node<T>(d);
  n->m_link = m_top;
  m_top = n;
  m_size++;

  return *this;
}


template <class T>
stack<T>& stack<T>::pop()
{
  __D_ASSERT(m_size > 0);
  if ( likely(m_size != 0) ) {
    node<T> *n = m_top;
    m_top = m_top->m_link;
    m_size--;
    delete n;
  }

  return *this;
}


template <class T>
stack<T>& stack<T>::clear()
{
  node<T> *n = m_top;
  while ( likely(n != NULL) ) {
    node<T> *tmp = n->m_link;
    delete n;
    n = tmp;
  }

  m_top = NULL;
  m_size = 0;
  return *this;
}


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


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

  u32 i = 0;
  for (node<T> *n = m_top; likely(n != NULL); n = n->m_link)
    pfunc(i++, n->m_data);

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

}

#endif