bqueue.h

Go to the documentation of this file.

#ifndef CMSUTILS_BEUEUE_H
#define CMSUTILS_BEUEUE_H
#include <boost/intrusive_ptr.hpp>
#include<cassert>

namespace cmsutils {

  template<class T> class _bqueue_itr;
  template<class T> class bqueue;
  template<class T> class _bqueue_item;
  template<class T> void intrusive_ptr_add_ref(_bqueue_item<T> *it) ;
  template<class T> void intrusive_ptr_release(_bqueue_item<T> *it) ;
  
  template <class T> 
  class _bqueue_item  {
    friend class bqueue<T>;
    friend class _bqueue_itr<T>;
    friend void intrusive_ptr_add_ref<T>(_bqueue_item<T> *it);
    friend void intrusive_ptr_release<T>(_bqueue_item<T> *it);
    void addRef() { ++refCount; }
    void delRef() { if ((--refCount) == 0) delete this; }
  private:
    _bqueue_item() : back(0), value(), refCount(0) { }
    _bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, const T &val) : back(tail), value(val), refCount(0) { }
    // move
    _bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, T &&val) : 
      back(tail), value(std::move(val)), refCount(0) { }
    // emplace
    template<typename... Args>
    _bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, Args && ...args) : 
      back(tail), value(std::forward<Args>(args)...), refCount(0) { }
    boost::intrusive_ptr< _bqueue_item<T> > back;
    T const value;
    unsigned int refCount;
  };
  
  template<class T> inline void intrusive_ptr_add_ref(_bqueue_item<T> *it) { it->addRef(); }
  template<class T> inline void intrusive_ptr_release(_bqueue_item<T> *it) { it->delRef(); }
  //inline void intrusive_ptr_add_ref(const _bqueue_item *it) { it->addRef(); }
  //inline void intrusive_ptr_release(const _bqueue_item *it) { it->delRef(); }
  
  template<class T>
  class _bqueue_itr {
  public:
    // T* operator->() { return &it->value; }
    // T& operator*() { return it->value; }
    const T* operator->() const { return &it->value; }
    const T& operator*() const { return it->value; }
    _bqueue_itr<T> & operator--() { it = it->back.get(); return *this; }
    _bqueue_itr<T> & operator++() { it = it->back.get(); return *this; }
    const _bqueue_itr<T> & operator--() const { it = it->back.get(); return *this; }
    bool operator==(const _bqueue_itr<T> &t2) const  { return t2.it == it; }
    bool operator!=(const _bqueue_itr<T> &t2) const { return t2.it != it; }
    // so that I can assign a const_iterator to a const_iterator
    const _bqueue_itr<T> & operator=(const _bqueue_itr<T> &t2) const { it = t2.it; return *this; }
    friend class bqueue<T>;
  private:
    // _bqueue_itr(_bqueue_item<T> *t) : it(t) { }
    _bqueue_itr(const _bqueue_item<T> *t) : it(t) { }
    mutable _bqueue_item<T> const * it;
  };
  
  template<class T>
  class bqueue {
  public:
    typedef T value_type;
    typedef unsigned short int size_type;
    typedef _bqueue_item<value_type>       item;
    typedef boost::intrusive_ptr< _bqueue_item<value_type> >  itemptr;
    typedef _bqueue_itr<value_type>       iterator;
    typedef _bqueue_itr<value_type> const_iterator;
    
    bqueue() : m_size(0),  m_head(), m_tail() { }
    ~bqueue() { }

    bqueue(const bqueue<T> &cp) : m_size(cp.m_size), m_head(cp.m_head), m_tail(cp.m_tail) { }
    
    // move
    bqueue(bqueue<T> &&cp) noexcept : 
    m_size(cp.m_size),
      m_head(std::move(cp.m_head)), m_tail(std::move(cp.m_tail)) {cp.m_size=0; }
    
    bqueue & operator=(bqueue<T> &&cp) noexcept {
      using std::swap;
      swap(m_size,cp.m_size);
      swap(m_head,cp.m_head); 
      swap(m_tail,cp.m_tail);
      return *this;
    }
    
    void swap(bqueue<T> &cp) {
      using std::swap;
      swap(m_size,cp.m_size);
      swap(m_head,cp.m_head); 
      swap(m_tail,cp.m_tail);
    }
    
    bqueue<T> fork() const {
      return *this;
    }
    
    // copy
    void push_back(const T& val) {
      m_tail = itemptr(new item(this->m_tail, val)); 
      if ((++m_size) == 1) { m_head = m_tail; };
    }
    
    //move 
    void push_back(T&& val) {
      m_tail = itemptr(new item(this->m_tail, std::forward<T>(val))); 
      if ((++m_size) == 1) { m_head = m_tail; };
    }
    
    // emplace
    template<typename... Args>
    void emplace_back(Args && ...args){
      m_tail = itemptr(new item(this->m_tail, std::forward<Args>(args)...)); 
      if ((++m_size) == 1) { m_head = m_tail; };
    }
    
    void pop_back() {
      assert(m_size > 0);
      --m_size;
      m_tail = m_tail->back;
      if (m_size == 0) m_head = nullptr; 
    }
    
    // T & front() { return m_head->value; }
    const T & front() const { return m_head->value; }
    //vT & back() { return m_tail->value; }
    const T & back() const { return m_tail->value; }
    // iterator rbegin() { return m_tail.get(); }
    const_iterator rbegin() const { return m_tail.get(); }
    const_iterator rend() const { return nullptr; }
    const_iterator begin() const { return m_tail.get(); }
    const_iterator end() const { return nullptr; }
    size_type size() const { return m_size; }
    bool empty() const { return m_size == 0; }
    const T & operator[](size_type i) const {
      int idx = m_size - i - 1;
      const_iterator it = rbegin();
      while (idx-- > 0) --it;
      return *it;
    }
    
    bool shared() { 
      // size = 0: never shared
      // size = 1: shared if head->refCount > 2 (m_head and m_tail)
      // size > 1: shared if head->refCount > 2 (m_head and second_hit->back)
      return (m_size > 0) && (m_head->refCount > 2);
    }


    // connect 'other' at the tail of this. will reset 'other' to an empty sequence
    // other better not to be shared!
    void join(bqueue<T> &other) {
      assert(!other.shared());
      using std::swap;
      if (m_size == 0) {
    swap(m_head,other.m_head);
    swap(m_tail,other.m_tail);
    swap(m_size,other.m_size);
      } else {
    other.m_head->back = this->m_tail;
    m_tail = other.m_tail;
    m_size += other.m_size;
    other.clear();
      }
    }

    void clear() { 
      m_head = m_tail = nullptr;
      m_size = 0;
    }

  private:
    
    size_type m_size;
    itemptr m_head, m_tail;
    
  };
  
  template<typename T>
  void swap(bqueue<T> &rh, bqueue<T> &lh) {
    rh.swap(lh);
  }
  
}

#endif