LQueue.cpp

Go to the documentation of this file.

#ifndef _LQUEUE_CPP
#define _LQUEUE_CPP
 
#include <memory>
#include <algorithm>
#include "madara/utility/LQueue.h"
 
#ifdef _MSC_VER
// It's fine to use "this" in base-member initializations.
#pragma warning(disable : 4355)
#endif
 
namespace madara
{
namespace utility
{
template<class T>
class LQueueNode
{
  friend class LQueue<T>;
  friend class LQueueIterator<T>;
  friend class LQueueConstIterator<T>;
 
public:
  LQueueNode(const T& item, LQueueNode<T>* next = 0);
 
  LQueueNode(LQueueNode<T>* next);
 
  LQueueNode(void);
 
  void* operator new(size_t bytes);
 
  void operator delete(void* ptr);
 
  LQueueNode* next(void);
 
  static void free_list_allocate(size_t n);
 
  static void free_list_release(void);
 
private:
  static LQueueNode<T>* free_list_;
 
  T item_;
 
  LQueueNode<T>* next_;
};
}
}
 
/* static */
template<class T>
madara::utility::LQueueNode<T>* madara::utility::LQueueNode<T>::free_list_ = 0;
 
// Allocate a new <LQueueNode>, trying first from the
// <free_list_> and if that's empty try from the global <::operator
// new>.
 
template<class T>
void* madara::utility::LQueueNode<T>::operator new(size_t)
{
  // extract element from the free_list_ if there is one left
  if (LQueueNode<T>::free_list_ != 0)
  {
    // get the top element of the list
    LQueueNode<T>* new_node = LQueueNode<T>::free_list_;
 
    // "remove" the element from the list and pass it to the caller
    LQueueNode<T>::free_list_ = new_node->next_;
 
    return new_node;
  }
 
  return ::operator new(sizeof(LQueueNode<T>));
}
 
// Return <ptr> to the <free_list_>.
 
template<class T>
void madara::utility::LQueueNode<T>::operator delete(void* ptr)
{
  // do nothing on a null pointer
  if (ptr != 0)
  {
    // cast to a node pointer
    LQueueNode<T>* node = static_cast<LQueueNode<T>*>(ptr);
 
    // put the node back into the list
    node->next_ = LQueueNode<T>::free_list_;
 
    LQueueNode<T>::free_list_ = node;
  }
}
 
// Returns the next node to which this node points.
template<class T>
madara::utility::LQueueNode<T>* madara::utility::LQueueNode<T>::next(void)
{
  return next_;
}
 
// Returns all dynamic memory on the free list to the free store.
 
template<class T>
void madara::utility::LQueueNode<T>::free_list_release(void)
{
  // delete free list element by element
  while (LQueueNode<T>::free_list_ != 0)
  {
    LQueueNode<T>* node = LQueueNode<T>::free_list_;
    LQueueNode<T>::free_list_ = node->next_;
    ::operator delete(node);
  }
}
 
// Preallocate <n> <LQueueNodes> and store them on the
// <free_list_>.
 
template<class T>
void madara::utility::LQueueNode<T>::free_list_allocate(size_t n)
{
  // add a new element to the stack n times
  for (size_t node_number = 0; node_number < n; ++node_number)
  {
    // create a new element avoiding the overwritten new operator
    LQueueNode<T>* new_node =
        reinterpret_cast<LQueueNode<T>*>(::operator new(sizeof(LQueueNode<T>)));
 
    new_node->next_ = LQueueNode<T>::free_list_;
 
    // make the new element the top of the list
    LQueueNode<T>::free_list_ = new_node;
  }
}
 
template<class T>
madara::utility::LQueueNode<T>::LQueueNode(
    const T& item, madara::utility::LQueueNode<T>* next)
  : item_(item), next_(next)
{
}
 
template<class T>
madara::utility::LQueueNode<T>::LQueueNode(madara::utility::LQueueNode<T>* next)
  : next_(next)
{
}
 
// This method is helpful to implement the dummy node in a concise
// way.
template<class T>
madara::utility::LQueueNode<T>::LQueueNode(void) : next_(this)
{
}
 
// Returns the current size.
template<class T>
size_t madara::utility::LQueue<T>::size(void) const
{
  return count_;
}
 
// Constructor.
 
template<class T>
madara::utility::LQueue<T>::LQueue(size_t size_hint)
  // Initialize fields here.
  : tail_(0), count_(0)
{
  // use the size_hint to preallocate  memory for nodes
  LQueueNode<T>::free_list_allocate(size_hint);
 
  // create the dummy node
  tail_ = new LQueueNode<T>();
}
 
// Copy constructor.
 
template<class T>
madara::utility::LQueue<T>::LQueue(const madara::utility::LQueue<T>& rhs)
  // Initialize fields here.
  : tail_(0), count_(0)  // count_ will be set correctly by copy_list
{
  // insert a dummy node first and keep it as an auto_ptr for exception
  // safety issues
  ::std::unique_ptr<LQueueNode<T> > tail(new LQueueNode<T>());
  tail_ = tail.get();
 
  // copy_list has strong exception safety, so no try catch block
  // is necessary here
  copy_list(rhs);
 
  // from here on, the auto_ptr should not try to delete the
  // tail pointer anymore.
  tail.release();
}
 
// Copy a linked list of nodes
template<class T>
void madara::utility::LQueue<T>::copy_list(
    const madara::utility::LQueue<T>& rhs)
{
  LQueue<T> temp;
 
  // enqueue the elements into the temporary list
  for (typename LQueue<T>::const_iterator it = rhs.begin(); it != rhs.end();
       ++it)
  {
    temp.enqueue(*it);
  }
 
  // we only swap the lists if the temporary list has been successfully
  // created. This ensures strong exception guarantees.
  ::std::swap(tail_, temp.tail_);
 
  // swap the counts too
  ::std::swap(count_, temp.count_);
}
 
// Delete a linked list of nodes
template<class T>
void madara::utility::LQueue<T>::delete_list()
{
  // we do not delete the dummy node here. This will be done in the destructor
  // we dequeue all elements until the queue is empty again
  while (!is_empty())
  {
    dequeue_i();
  }
}
 
// Assignment operator.
template<class T>
madara::utility::LQueue<T>& madara::utility::LQueue<T>::operator=(
    const madara::utility::LQueue<T>& rhs)
{
  // test for self assignment first
  if (this != &rhs)
  {
    // delete old data of the rhs
    delete_list();
 
    // copy new data
    copy_list(rhs);
  }
 
  return *this;
}
 
// Perform actions needed when queue goes out of scope.
 
template<class T>
madara::utility::LQueue<T>::~LQueue<T>(void)
{
  // delete all elements of the list
  delete_list();
 
  // delete the last dummy node here
  delete tail_;
}
 
// Compare this queue with <rhs> for equality.  Returns true if the
// size()'s of the two queues are equal and all the elements from 0
// .. size() are equal, else false.
template<class T>
bool madara::utility::LQueue<T>::operator==(
    const madara::utility::LQueue<T>& rhs) const
{
  return (size() == rhs.size()) && ::std::equal(begin(), end(), rhs.begin());
}
 
// Compare this queue with <rhs> for inequality such that <*this> !=
// <s> is always the complement of the boolean return value of
// <*this> == <s>.
 
template<class T>
bool madara::utility::LQueue<T>::operator!=(
    const madara::utility::LQueue<T>& rhs) const
{
  return !(*this == rhs);
}
 
// Place a <new_item> at the tail of the queue.  Throws
// the <Overflow> exception if the queue is full.
 
template<class T>
void madara::utility::LQueue<T>::enqueue(const T& new_item)
{
  try
  {
    // assign the value to the tail element before the new allocation
    // to make sure that exceptions thrown in the assignment operator
    // of T does leave the queue structure altered
    tail_->item_ = new_item;
 
    // integrate the new node into the list
    tail_->next_ = new LQueueNode<T>(tail_->next_);
    tail_ = tail_->next_;
 
    // increment the element count
    ++count_;
  }
  catch (const ::std::bad_alloc&)
  {
    // we transform a bad_alloc excption into an overflow exception,
    // because it basically means, that it is no longer possible
    // to enqueue new elements
    throw Overflow();
  }
}
 
// Remove and return the front item on the queue.
// Throws the <Underflow> exception if the queue is empty.
 
template<class T>
T madara::utility::LQueue<T>::dequeue(void)
{
  // check for empty queue first
  if (is_empty())
  {
    throw Underflow();
  }
 
  // extract the value of the head node. This is done before we actually
  // remove the element for exceptions could be thrown in the assignment
  // operator.
  T item = tail_->next_->item_;
 
  // call actual dequeue implementation
  dequeue_i();
 
  return item;
}
 
template<class T>
void madara::utility::LQueue<T>::dequeue_i(void)
{
  // remember the current queue head
  LQueueNode<T>* head = tail_->next_;
 
  // remove the head from the queue
  tail_->next_ = head->next_;
 
  // decrement the element count
  --count_;
 
  // delete the old head node
  delete head;
}
 
// Returns the front queue item without removing it.
// Throws the <Underflow> exception if the queue is empty.
 
template<class T>
T madara::utility::LQueue<T>::front(void) const
{
  // check for empty queue first
  if (is_empty())
    throw Underflow();
 
  // return the item in head
  return tail_->next_->item_;
}
 
// Returns true if the queue is empty, otherwise returns false.
 
template<class T>
bool madara::utility::LQueue<T>::is_empty(void) const
{
  return count_ == 0;
}
 
// Returns true if the queue is full, otherwise returns false.
 
template<class T>
bool madara::utility::LQueue<T>::is_full(void) const
{
  // there is no upper limit for the queue
  return false;
}
 
// Get an iterator to the begining of the queue
template<typename T>
typename madara::utility::LQueue<T>::iterator madara::utility::LQueue<T>::begin(
    void)
{
  // iterator starts at the head element
  return typename LQueue<T>::iterator(*this, tail_->next_);
}
 
// Get an iterator pointing past the end of the queue
template<typename T>
typename madara::utility::LQueue<T>::iterator madara::utility::LQueue<T>::end(
    void)
{
  // iterator starts at the tail element
  return typename LQueue<T>::iterator(*this, tail_);
}
 
// Get an iterator to the begining of the queue
template<typename T>
typename madara::utility::LQueue<T>::const_iterator
madara::utility::LQueue<T>::begin(void) const
{
  // iterator starts at the head element
  return typename LQueue<T>::const_iterator(*this, tail_->next_);
}
 
// Get an iterator pointing past the end of the queue
template<typename T>
typename madara::utility::LQueue<T>::const_iterator
madara::utility::LQueue<T>::end(void) const
{
  // iterator starts at the tail element
  return typename LQueue<T>::const_iterator(*this, tail_);
}
 
template<typename T>
T& madara::utility::LQueueIterator<T>::operator*(void)
{
  return pos_->item_;
}
 
template<typename T>
const T& madara::utility::LQueueIterator<T>::operator*(void)const
{
  return pos_->item_;
}
 
template<typename T>
madara::utility::LQueueIterator<T>& madara::utility::LQueueIterator<T>::
operator++(void)
{
  // advance to the next position
  pos_ = pos_->next_;
 
  return *this;
}
 
// Post-increment.
template<typename T>
madara::utility::LQueueIterator<T> madara::utility::LQueueIterator<T>::
operator++(int)
{
  // keep copy of the original iterator
  LQueueIterator<T> copy = *this;
 
  // advance to the next position
  pos_ = pos_->next_;
 
  // return original iterator
  return copy;
}
 
template<typename T>
bool madara::utility::LQueueIterator<T>::operator==(
    const madara::utility::LQueueIterator<T>& rhs) const
{
  // check if the iterator points to the same position in the same queue
  // (we could even omit the check for queue equality, because it is
  //  very unlikely that two queues share the same node pointer)
  return (pos_ == rhs.pos_);
}
 
template<typename T>
bool madara::utility::LQueueIterator<T>::operator!=(
    const madara::utility::LQueueIterator<T>& rhs) const
{
  // implement != in terms of ==
  return !(*this == rhs);
}
 
template<typename T>
madara::utility::LQueueIterator<T>::LQueueIterator(
    madara::utility::LQueue<T>& queue, size_t pos)
  : queue_(queue), pos_(queue.tail_->next_)
{
  // iterator over the queue unto the right position
  // we save iterations for values > count_ by doing modulo calculations
  for (pos = pos % (queue_.count_ - 1); pos > 0; --pos)
  {
    // advance one position each time
    pos_ = pos_->next_;
  }
}
 
template<typename T>
madara::utility::LQueueIterator<T>::LQueueIterator(
    madara::utility::LQueue<T>& queue, madara::utility::LQueueNode<T>* pos)
  : queue_(queue), pos_(pos)
{
}
 
template<typename T>
const T& madara::utility::LQueueConstIterator<T>::operator*(void)const
{
  return pos_->item_;
}
 
template<typename T>
const madara::utility::LQueueConstIterator<T>&
    madara::utility::LQueueConstIterator<T>::operator++(void)const
{
  // advance to the next position
  pos_ = pos_->next_;
 
  return *this;
}
 
template<typename T>
madara::utility::LQueueConstIterator<T>
    madara::utility::LQueueConstIterator<T>::operator++(int)const
{
  // keep copy of the original iterator
  LQueueConstIterator<T> copy = *this;
 
  // advance to the next position
  pos_ = pos_->next_;
 
  // return original iterator
  return copy;
}
 
template<typename T>
bool madara::utility::LQueueConstIterator<T>::operator==(
    const madara::utility::LQueueConstIterator<T>& rhs) const
{
  // check if the iterator points to the same position in the same queue
  return (pos_ == rhs.pos_);
}
 
template<typename T>
bool madara::utility::LQueueConstIterator<T>::operator!=(
    const madara::utility::LQueueConstIterator<T>& rhs) const
{
  return !(*this == rhs);
}
 
template<typename T>
madara::utility::LQueueConstIterator<T>::LQueueConstIterator(
    const madara::utility::LQueue<T>& queue, size_t pos)
  : queue_(queue), pos_(queue.tail_->next_)
{
  // iterator over the queue unto the right position
  // we save iterations for values > count_ by doing modulo calculations
  for (pos = pos % (queue_.count_ - 1); pos > 0; --pos)
  {
    // advance one position each time
    pos_ = pos_->next_;
  }
}
 
template<typename T>
madara::utility::LQueueConstIterator<T>::LQueueConstIterator(
    const LQueue<T>& queue, LQueueNode<T>* pos)
  : queue_(queue), pos_(pos)
{
}
 
#endif /* _LQUEUE_CPP */