Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-06-12 03:09:55

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