PatternTools/interface/bqueue.h

#ifndef CMSUTILS_BEUEUE_H
#define CMSUTILS_BEUEUE_H
#include <boost/intrusive_ptr.hpp>
#include "DataFormats/GeometrySurface/interface/BlockWipedAllocator.h"

/**  Backwards linked queue with "head sharing"

     Author: Giovanni Petrucciani
     
     For use in trajectory building, where we want to "fork" a trajectory candidate in two
     without copying around all the hits before the fork.

     Supported operations (mimics a std container):
       - push_back()
       - fork() which returns a new queue that shares the head part with the old one
       - copy constructor, which just does fork()
       - rbegin(), rend(): return iterators which can work only backwards
            for (cmsutils::bqueue<T>::const_iterator it = queue.rbegin(), end = queue.rend();
                        it != end; --it) { ... }
       - front() and back(): returns a reference to the first and last element
       - size(), empty(): as expected. size() does not count the items
     
     Note that boost::intrusive_ptr is used for items, so they are deleted automatically
     while avoiding problems if one deletes a queue which shares the head with another one

     Disclaimer: I'm not sure the const_iterator is really const-correct..
*/
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 : public BlockWipedAllocated<_bqueue_item<T> > {
        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) { }
#if defined( __GXX_EXPERIMENTAL_CXX0X__)
        _bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, T &&val) : 
          back(tail), value(std::move(val)), refCount(0) { }
#endif
        boost::intrusive_ptr< _bqueue_item<T> > back;
        T 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; 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> *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 const _bqueue_itr<value_type> const_iterator;

        bqueue() : m_size(0), m_bound(), m_head(m_bound), m_tail(m_bound) { }
        ~bqueue() { }
        bqueue(const bqueue<T> &cp) : m_size(cp.m_size), m_bound(cp.m_bound), m_head(cp.m_head), m_tail(cp.m_tail) { }

#if defined( __GXX_EXPERIMENTAL_CXX0X__)
  bqueue(bqueue<T> &&cp) : 
    m_size(cp.m_size),
    m_bound(std::move(cp.m_bound)), m_head(std::move(cp.m_head)), m_tail(std::move(cp.m_tail)) { }

  bqueue & operator=(bqueue<T> &&cp) {
    using std::swap;
    m_size=cp.m_size;
    swap(m_bound,cp.m_bound);
    swap(m_head,cp.m_head); 
    swap(m_tail,cp.m_tail);
    return *this;
    }
#endif

      void swap(bqueue<T> &cp) {
          using std::swap;
          swap(m_size,cp.m_size);
          swap(m_bound,cp.m_bound);
          swap(m_head,cp.m_head); 
          swap(m_tail,cp.m_tail);
      }

        bqueue<T> fork() {
            return bqueue<T>(m_size,m_bound,m_head,m_tail);
        }

        void push_back(const T& val) {
            m_tail = itemptr(new item(this->m_tail, val)); 
            if ((++m_size) == 1) { m_head = m_tail; };
        }

#if defined( __GXX_EXPERIMENTAL_CXX0X__)
        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; };
        }
#endif
        void pop_back() {
            assert(m_size > 0);
            --m_size;
            m_tail = m_tail->back;
            if (m_size == 0) m_head = m_bound; 
        }
        T & front() { return m_head->value; }
        const T & front() const { return m_head->value; }
        T & 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 m_bound.get(); }
        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
        void join(bqueue<T> &other) {
            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.m_head = other.m_tail = other.m_bound;
                other.m_size = 0;
            }
        }
        void clear() { 
            m_head = m_bound; 
            m_tail = m_bound;
            m_size = 0;
        }
    private:
        bqueue(size_type size, itemptr bound, itemptr head, itemptr tail) :
            m_size(size), m_bound(bound), m_head(head), m_tail(tail) { }

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

}

#endif
Revision:	1.1
Committed:	Fri Nov 25 16:38:24 2011 UTC (13 years, 5 months ago) by econte
Content type:	text/plain
Branch:	MAIN
CVS Tags:	TBD2011, TBD_2011, HEAD
Log Message:	new IPHC alignment
#	User	Rev	Content
1	econte	1.1	#ifndef CMSUTILS_BEUEUE_H
2			#define CMSUTILS_BEUEUE_H
3			#include <boost/intrusive_ptr.hpp>
4			#include "DataFormats/GeometrySurface/interface/BlockWipedAllocator.h"
5
6			/** Backwards linked queue with "head sharing"
7
8			Author: Giovanni Petrucciani
9
10			For use in trajectory building, where we want to "fork" a trajectory candidate in two
11			without copying around all the hits before the fork.
12
13			Supported operations (mimics a std container):
14			- push_back()
15			- fork() which returns a new queue that shares the head part with the old one
16			- copy constructor, which just does fork()
17			- rbegin(), rend(): return iterators which can work only backwards
18			for (cmsutils::bqueue<T>::const_iterator it = queue.rbegin(), end = queue.rend();
19			it != end; --it) { ... }
20			- front() and back(): returns a reference to the first and last element
21			- size(), empty(): as expected. size() does not count the items
22
23			Note that boost::intrusive_ptr is used for items, so they are deleted automatically
24			while avoiding problems if one deletes a queue which shares the head with another one
25
26			Disclaimer: I'm not sure the const_iterator is really const-correct..
27			*/
28			namespace cmsutils {
29
30			template<class T> class _bqueue_itr;
31			template<class T> class bqueue;
32			template<class T> class _bqueue_item;
33			template<class T> void intrusive_ptr_add_ref(_bqueue_item<T> *it) ;
34			template<class T> void intrusive_ptr_release(_bqueue_item<T> *it) ;
35
36			template <class T>
37			class _bqueue_item : public BlockWipedAllocated<_bqueue_item<T> > {
38			friend class bqueue<T>;
39			friend class _bqueue_itr<T>;
40			friend void intrusive_ptr_add_ref<T>(_bqueue_item<T> *it);
41			friend void intrusive_ptr_release<T>(_bqueue_item<T> *it);
42			void addRef() { ++refCount; }
43			void delRef() { if ((--refCount) == 0) delete this; }
44			private:
45			_bqueue_item() : back(0), value(), refCount(0) { }
46			_bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, const T &val) : back(tail), value(val), refCount(0) { }
47			#if defined( __GXX_EXPERIMENTAL_CXX0X__)
48			_bqueue_item(boost::intrusive_ptr< _bqueue_item<T> > tail, T &&val) :
49			back(tail), value(std::move(val)), refCount(0) { }
50			#endif
51			boost::intrusive_ptr< _bqueue_item<T> > back;
52			T value;
53			unsigned int refCount;
54			};
55
56			template<class T> inline void intrusive_ptr_add_ref(_bqueue_item<T> *it) { it->addRef(); }
57			template<class T> inline void intrusive_ptr_release(_bqueue_item<T> *it) { it->delRef(); }
58			//inline void intrusive_ptr_add_ref(const _bqueue_item *it) { it->addRef(); }
59			//inline void intrusive_ptr_release(const _bqueue_item *it) { it->delRef(); }
60
61			template<class T>
62			class _bqueue_itr {
63			public:
64			T* operator->() { return &it->value; }
65			T& operator*() { return it->value; }
66			const T* operator->() const { return &it->value; }
67			const T& operator*() const { return it->value; }
68			_bqueue_itr<T> & operator--() { it = it->back; return *this; }
69			const _bqueue_itr<T> & operator--() const { it = it->back.get(); return *this; }
70			bool operator==(const _bqueue_itr<T> &t2) const { return t2.it == it; }
71			bool operator!=(const _bqueue_itr<T> &t2) const { return t2.it != it; }
72			// so that I can assign a const_iterator to a const_iterator
73			const _bqueue_itr<T> & operator=(const _bqueue_itr<T> &t2) const { it = t2.it; return *this; }
74			friend class bqueue<T>;
75			private:
76			_bqueue_itr(_bqueue_item<T> *t) : it(t) { }
77			_bqueue_itr(const _bqueue_item<T> *t) : it(t) { }
78			mutable _bqueue_item<T> *it;
79			};
80
81			template<class T>
82			class bqueue {
83			public:
84			typedef T value_type;
85			typedef unsigned short int size_type;
86			typedef _bqueue_item<value_type> item;
87			typedef boost::intrusive_ptr< _bqueue_item<value_type> > itemptr;
88			typedef _bqueue_itr<value_type> iterator;
89			typedef const _bqueue_itr<value_type> const_iterator;
90
91			bqueue() : m_size(0), m_bound(), m_head(m_bound), m_tail(m_bound) { }
92			~bqueue() { }
93			bqueue(const bqueue<T> &cp) : m_size(cp.m_size), m_bound(cp.m_bound), m_head(cp.m_head), m_tail(cp.m_tail) { }
94
95			#if defined( __GXX_EXPERIMENTAL_CXX0X__)
96			bqueue(bqueue<T> &&cp) :
97			m_size(cp.m_size),
98			m_bound(std::move(cp.m_bound)), m_head(std::move(cp.m_head)), m_tail(std::move(cp.m_tail)) { }
99
100			bqueue & operator=(bqueue<T> &&cp) {
101			using std::swap;
102			m_size=cp.m_size;
103			swap(m_bound,cp.m_bound);
104			swap(m_head,cp.m_head);
105			swap(m_tail,cp.m_tail);
106			return *this;
107			}
108			#endif
109
110			void swap(bqueue<T> &cp) {
111			using std::swap;
112			swap(m_size,cp.m_size);
113			swap(m_bound,cp.m_bound);
114			swap(m_head,cp.m_head);
115			swap(m_tail,cp.m_tail);
116			}
117
118			bqueue<T> fork() {
119			return bqueue<T>(m_size,m_bound,m_head,m_tail);
120			}
121
122			void push_back(const T& val) {
123			m_tail = itemptr(new item(this->m_tail, val));
124			if ((++m_size) == 1) { m_head = m_tail; };
125			}
126
127			#if defined( __GXX_EXPERIMENTAL_CXX0X__)
128			void push_back(T&& val) {
129			m_tail = itemptr(new item(this->m_tail, std::forward<T>(val)));
130			if ((++m_size) == 1) { m_head = m_tail; };
131			}
132			#endif
133			void pop_back() {
134			assert(m_size > 0);
135			--m_size;
136			m_tail = m_tail->back;
137			if (m_size == 0) m_head = m_bound;
138			}
139			T & front() { return m_head->value; }
140			const T & front() const { return m_head->value; }
141			T & back() { return m_tail->value; }
142			const T & back() const { return m_tail->value; }
143			iterator rbegin() { return m_tail.get(); }
144			const_iterator rbegin() const { return m_tail.get(); }
145			const_iterator rend() const { return m_bound.get(); }
146			size_type size() const { return m_size; }
147			bool empty() const { return m_size == 0; }
148			const T & operator[](size_type i) const {
149			int idx = m_size - i - 1;
150			const_iterator it = rbegin();
151			while (idx-- > 0) --it;
152			return *it;
153			}
154			bool shared() {
155			// size = 0: never shared
156			// size = 1: shared if head->refCount > 2 (m_head and m_tail)
157			// size > 1: shared if head->refCount > 2 (m_head and second_hit->back)
158			return (m_size > 0) && (m_head->refCount > 2);
159			}
160			// connect 'other' at the tail of this. will reset 'other' to an empty sequence
161			void join(bqueue<T> &other) {
162			using std::swap;
163			if (m_size == 0) {
164			swap(m_head,other.m_head);
165			swap(m_tail,other.m_tail);
166			swap(m_size,other.m_size);
167			} else {
168			other.m_head->back = this->m_tail;
169			m_tail = other.m_tail;
170			m_size += other.m_size;
171			other.m_head = other.m_tail = other.m_bound;
172			other.m_size = 0;
173			}
174			}
175			void clear() {
176			m_head = m_bound;
177			m_tail = m_bound;
178			m_size = 0;
179			}
180			private:
181			bqueue(size_type size, itemptr bound, itemptr head, itemptr tail) :
182			m_size(size), m_bound(bound), m_head(head), m_tail(tail) { }
183
184			size_type m_size;
185			itemptr m_bound, m_head, m_tail;
186
187			};
188			template<typename T>
189			void swap(bqueue<T> &rh, bqueue<T> &lh) {
190			rh.swap(lh);
191			}
192
193			}
194
195			#endif