PatternTools/interface/bqueue.h

0001 #ifndef CMSUTILS_BEUEUE_H
0002 #define CMSUTILS_BEUEUE_H
0003 #include <boost/intrusive_ptr.hpp>
0004 #include <cassert>
0005
0006 /**  Backwards linked queue with "head sharing"
0007
0008      Author: Giovanni Petrucciani
0009
0010      For use in trajectory building, where we want to "fork" a trajectory candidate in two
0011      without copying around all the hits before the fork.
0012
0013      Supported operations (mimics a std container):
0014        - push_back()
0015        - fork() which returns a new queue that shares the head part with the old one
0016        - copy constructor, which just does fork()
0017        - rbegin(), rend(): return iterators which can work only backwards
0018             for (cmsutils::bqueue<T>::const_iterator it = queue.rbegin(), end = queue.rend();
0019                         it != end; --it) { ... }
0020        - front() and back(): returns a reference to the first and last element
0021        - size(), empty(): as expected. size() does not count the items
0022
0023      Note that boost::intrusive_ptr is used for items, so they are deleted automatically
0024      while avoiding problems if one deletes a queue which shares the head with another one
0025
0026      Disclaimer: I'm not sure the const_iterator is really const-correct..
0027
0028      V.I. 22/08/2012 As the bqueue is made to be shared its content ahs been forced to be constant.
0029      This avoids that accidentally an update in one Trajectory modifies the content of onother!
0030
0031     to support c++11 begin,end and operator++ has been added with the same semantics of rbegin,rend and operator--
0032     Highly confusing, still the bqueue is a sort of reversed slist: provided the user knows should work....
0033
0034
0035 */
0036 namespace cmsutils {
0037
0038   template <class T>
0039   class _bqueue_itr;
0040   template <class T>
0041   class bqueue;
0042   template <class T>
0043   class _bqueue_item;
0044   template <class T>
0045   void intrusive_ptr_add_ref(_bqueue_item<T> *it);
0046   template <class T>
0047   void intrusive_ptr_release(_bqueue_item<T> *it);
0048
0049   template <class T>
0050   class _bqueue_item {
0051     friend class bqueue<T>;
0052     friend class _bqueue_itr<T>;
0053     friend void intrusive_ptr_add_ref<T>(_bqueue_item<T> *it);
0054     friend void intrusive_ptr_release<T>(_bqueue_item<T> *it);
0055     void addRef() { ++refCount; }
0056     void delRef() {
0057       if ((--refCount) == 0)
0058         delete this;
0059     }
0060
0061   private:
0062     _bqueue_item() : back(0), value(), refCount(0) {}
0063     _bqueue_item(boost::intrusive_ptr<_bqueue_item<T> > tail, const T &val) : back(tail), value(val), refCount(0) {}
0064     // move
0065     _bqueue_item(boost::intrusive_ptr<_bqueue_item<T> > tail, T &&val)
0066         : back(tail), value(std::move(val)), refCount(0) {}
0067     // emplace
0068     template <typename... Args>
0069     _bqueue_item(boost::intrusive_ptr<_bqueue_item<T> > tail, Args &&...args)
0070         : back(tail), value(std::forward<Args>(args)...), refCount(0) {}
0071     boost::intrusive_ptr<_bqueue_item<T> > back;
0072     T const value;
0073     unsigned int refCount;
0074   };
0075
0076   template <class T>
0077   inline void intrusive_ptr_add_ref(_bqueue_item<T> *it) {
0078     it->addRef();
0079   }
0080   template <class T>
0081   inline void intrusive_ptr_release(_bqueue_item<T> *it) {
0082     it->delRef();
0083   }
0084   //inline void intrusive_ptr_add_ref(const _bqueue_item *it) { it->addRef(); }
0085   //inline void intrusive_ptr_release(const _bqueue_item *it) { it->delRef(); }
0086
0087   template <class T>
0088   class _bqueue_itr {
0089   public:
0090     // T* operator->() { return &it->value; }
0091     // T& operator*() { return it->value; }
0092     const T *operator->() const { return &it->value; }
0093     const T &operator*() const { return it->value; }
0094     _bqueue_itr<T> &operator--() {
0095       it = it->back.get();
0096       return *this;
0097     }
0098     _bqueue_itr<T> &operator++() {
0099       it = it->back.get();
0100       return *this;
0101     }
0102     const _bqueue_itr<T> &operator--() const {
0103       it = it->back.get();
0104       return *this;
0105     }
0106     bool operator==(const _bqueue_itr<T> &t2) const { return t2.it == it; }
0107     bool operator!=(const _bqueue_itr<T> &t2) const { return t2.it != it; }
0108     // so that I can assign a const_iterator to a const_iterator
0109     const _bqueue_itr<T> &operator=(const _bqueue_itr<T> &t2) {
0110       it = t2.it;
0111       return *this;
0112     }
0113     friend class bqueue<T>;
0114
0115   private:
0116     // _bqueue_itr(_bqueue_item<T> *t) : it(t) { }
0117     _bqueue_itr(const _bqueue_item<T> *t) : it(t) {}
0118     _bqueue_item<T> const *it;
0119   };
0120
0121   template <class T>
0122   class bqueue {
0123   public:
0124     typedef T value_type;
0125     typedef unsigned short int size_type;
0126     typedef _bqueue_item<value_type> item;
0127     typedef boost::intrusive_ptr<_bqueue_item<value_type> > itemptr;
0128     typedef _bqueue_itr<value_type> iterator;
0129     typedef _bqueue_itr<value_type> const_iterator;
0130
0131     bqueue() : m_size(0), m_head(), m_tail() {}
0132     ~bqueue() {}
0133
0134     bqueue(const bqueue<T> &cp) : m_size(cp.m_size), m_head(cp.m_head), m_tail(cp.m_tail) {}
0135
0136     // move
0137     bqueue(bqueue<T> &&cp) noexcept : m_size(cp.m_size), m_head(std::move(cp.m_head)), m_tail(std::move(cp.m_tail)) {
0138       cp.m_size = 0;
0139     }
0140
0141     bqueue &operator=(bqueue<T> const &) = default;
0142     bqueue &operator=(bqueue<T> &&cp) noexcept {
0143       using std::swap;
0144       swap(m_size, cp.m_size);
0145       swap(m_head, cp.m_head);
0146       swap(m_tail, cp.m_tail);
0147       return *this;
0148     }
0149
0150     void swap(bqueue<T> &cp) {
0151       using std::swap;
0152       swap(m_size, cp.m_size);
0153       swap(m_head, cp.m_head);
0154       swap(m_tail, cp.m_tail);
0155     }
0156
0157     bqueue<T> fork() const { return *this; }
0158
0159     // copy
0160     void push_back(const T &val) {
0161       m_tail = itemptr(new item(this->m_tail, val));
0162       if ((++m_size) == 1) {
0163         m_head = m_tail;
0164       };
0165     }
0166
0167     //move
0168     void push_back(T &&val) {
0169       m_tail = itemptr(new item(this->m_tail, std::forward<T>(val)));
0170       if ((++m_size) == 1) {
0171         m_head = m_tail;
0172       };
0173     }
0174
0175     // emplace
0176     template <typename... Args>
0177     void emplace_back(Args &&...args) {
0178       m_tail = itemptr(new item(this->m_tail, std::forward<Args>(args)...));
0179       if ((++m_size) == 1) {
0180         m_head = m_tail;
0181       };
0182     }
0183
0184     void pop_back() {
0185       assert(m_size > 0);
0186       --m_size;
0187       m_tail = m_tail->back;
0188       if (m_size == 0)
0189         m_head = nullptr;
0190     }
0191
0192     // T & front() { return m_head->value; }
0193     const T &front() const { return m_head->value; }
0194     //vT & back() { return m_tail->value; }
0195     const T &back() const { return m_tail->value; }
0196     // iterator rbegin() { return m_tail.get(); }
0197     const_iterator rbegin() const { return m_tail.get(); }
0198     const_iterator rend() const { return nullptr; }
0199     const_iterator begin() const { return m_tail.get(); }
0200     const_iterator end() const { return nullptr; }
0201     size_type size() const { return m_size; }
0202     bool empty() const { return m_size == 0; }
0203     const T &operator[](size_type i) const {
0204       int idx = m_size - i - 1;
0205       const_iterator it = rbegin();
0206       while (idx-- > 0)
0207         --it;
0208       return *it;
0209     }
0210
0211     bool shared() {
0212       // size = 0: never shared
0213       // size = 1: shared if head->refCount > 2 (m_head and m_tail)
0214       // size > 1: shared if head->refCount > 2 (m_head and second_hit->back)
0215       return (m_size > 0) && (m_head->refCount > 2);
0216     }
0217
0218     // connect 'other' at the tail of this. will reset 'other' to an empty sequence
0219     // other better not to be shared!
0220     void join(bqueue<T> &other) {
0221       assert(!other.shared());
0222       using std::swap;
0223       if (m_size == 0) {
0224         swap(m_head, other.m_head);
0225         swap(m_tail, other.m_tail);
0226         swap(m_size, other.m_size);
0227       } else {
0228         other.m_head->back = this->m_tail;
0229         m_tail = other.m_tail;
0230         m_size += other.m_size;
0231         other.clear();
0232       }
0233     }
0234
0235     void clear() {
0236       m_head = m_tail = nullptr;
0237       m_size = 0;
0238     }
0239
0240   private:
0241     size_type m_size;
0242     itemptr m_head, m_tail;
0243   };
0244
0245   template <typename T>
0246   void swap(bqueue<T> &rh, bqueue<T> &lh) {
0247     rh.swap(lh);
0248   }
0249
0250 }  // namespace cmsutils
0251
0252 #endif