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     _bqueue_itr(const _bqueue_itr<T> &t2) = default;
0114     friend class bqueue<T>;
0115
0116   private:
0117     // _bqueue_itr(_bqueue_item<T> *t) : it(t) { }
0118     _bqueue_itr(const _bqueue_item<T> *t) : it(t) {}
0119     _bqueue_item<T> const *it;
0120   };
0121
0122   template <class T>
0123   class bqueue {
0124   public:
0125     typedef T value_type;
0126     typedef unsigned short int size_type;
0127     typedef _bqueue_item<value_type> item;
0128     typedef boost::intrusive_ptr<_bqueue_item<value_type> > itemptr;
0129     typedef _bqueue_itr<value_type> iterator;
0130     typedef _bqueue_itr<value_type> const_iterator;
0131
0132     bqueue() : m_size(0), m_head(), m_tail() {}
0133     ~bqueue() {}
0134
0135     bqueue(const bqueue<T> &cp) : m_size(cp.m_size), m_head(cp.m_head), m_tail(cp.m_tail) {}
0136
0137     // move
0138     bqueue(bqueue<T> &&cp) noexcept : m_size(cp.m_size), m_head(std::move(cp.m_head)), m_tail(std::move(cp.m_tail)) {
0139       cp.m_size = 0;
0140     }
0141
0142     bqueue &operator=(bqueue<T> const &) = default;
0143     bqueue &operator=(bqueue<T> &&cp) noexcept {
0144       using std::swap;
0145       swap(m_size, cp.m_size);
0146       swap(m_head, cp.m_head);
0147       swap(m_tail, cp.m_tail);
0148       return *this;
0149     }
0150
0151     void swap(bqueue<T> &cp) {
0152       using std::swap;
0153       swap(m_size, cp.m_size);
0154       swap(m_head, cp.m_head);
0155       swap(m_tail, cp.m_tail);
0156     }
0157
0158     bqueue<T> fork() const { return *this; }
0159
0160     // copy
0161     void push_back(const T &val) {
0162       m_tail = itemptr(new item(this->m_tail, val));
0163       if ((++m_size) == 1) {
0164         m_head = m_tail;
0165       };
0166     }
0167
0168     //move
0169     void push_back(T &&val) {
0170       m_tail = itemptr(new item(this->m_tail, std::forward<T>(val)));
0171       if ((++m_size) == 1) {
0172         m_head = m_tail;
0173       };
0174     }
0175
0176     // emplace
0177     template <typename... Args>
0178     void emplace_back(Args &&...args) {
0179       m_tail = itemptr(new item(this->m_tail, std::forward<Args>(args)...));
0180       if ((++m_size) == 1) {
0181         m_head = m_tail;
0182       };
0183     }
0184
0185     void pop_back() {
0186       assert(m_size > 0);
0187       --m_size;
0188       m_tail = m_tail->back;
0189       if (m_size == 0)
0190         m_head = nullptr;
0191     }
0192
0193     // T & front() { return m_head->value; }
0194     const T &front() const { return m_head->value; }
0195     //vT & back() { return m_tail->value; }
0196     const T &back() const { return m_tail->value; }
0197     // iterator rbegin() { return m_tail.get(); }
0198     const_iterator rbegin() const { return m_tail.get(); }
0199     const_iterator rend() const { return nullptr; }
0200     const_iterator begin() const { return m_tail.get(); }
0201     const_iterator end() const { return nullptr; }
0202     size_type size() const { return m_size; }
0203     bool empty() const { return m_size == 0; }
0204     const T &operator[](size_type i) const {
0205       int idx = m_size - i - 1;
0206       const_iterator it = rbegin();
0207       while (idx-- > 0)
0208         --it;
0209       return *it;
0210     }
0211
0212     bool shared() {
0213       // size = 0: never shared
0214       // size = 1: shared if head->refCount > 2 (m_head and m_tail)
0215       // size > 1: shared if head->refCount > 2 (m_head and second_hit->back)
0216       return (m_size > 0) && (m_head->refCount > 2);
0217     }
0218
0219     // connect 'other' at the tail of this. will reset 'other' to an empty sequence
0220     // other better not to be shared!
0221     void join(bqueue<T> &other) {
0222       assert(!other.shared());
0223       using std::swap;
0224       if (m_size == 0) {
0225         swap(m_head, other.m_head);
0226         swap(m_tail, other.m_tail);
0227         swap(m_size, other.m_size);
0228       } else {
0229         other.m_head->back = this->m_tail;
0230         m_tail = other.m_tail;
0231         m_size += other.m_size;
0232         other.clear();
0233       }
0234     }
0235
0236     void clear() {
0237       m_head = m_tail = nullptr;
0238       m_size = 0;
0239     }
0240
0241   private:
0242     size_type m_size;
0243     itemptr m_head, m_tail;
0244   };
0245
0246   template <typename T>
0247   void swap(bqueue<T> &rh, bqueue<T> &lh) {
0248     rh.swap(lh);
0249   }
0250
0251 }  // namespace cmsutils
0252
0253 #endif