1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#ifndef QPID_ILIST_H
#define QPID_ILIST_H
/*
*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*
*/
#include <qpid/RefCounted.h>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/cast.hpp>
#include <assert.h>
namespace qpid {
template <class T, int N> class IList;
/**
* Base class providing links for a node in an IList.
*
* Derived classes can inheirt multiple IListNode bases provided each
* has a unique value for N. This allows objects to be linked in
* multiple independent lists. For example:
*
* @code
* class Foo : public IListNode<0>, public IListNode<1> {};
* IList<Foo, 0> - uses the 0 links
* IList<Foo, 1> - uses the 1 links
*@endcode
*
*@param T The derived class.
*@param N ID for multiple inheritance.
*/
template<class T, int N=0> class IListNode : public virtual RefCounted {
intrusive_ptr<IListNode> prev;
intrusive_ptr<IListNode> next;
void insert(IListNode*);
void erase();
virtual T* self() const { // Virutal so anchor can hide.
return boost::polymorphic_downcast<T*>(const_cast<IListNode*>(this));
}
friend class IList<T,N>;
public:
typedef IList<T,N> IListType;
IListNode(IListNode* p=0) : prev(p), next(p) {}
T* getNext() { return next ? next->self() : 0; }
T* getPrev() { return prev ? prev->self() : 0; }
const T* getNext() const { return next ? next->self() : 0; }
const T* getPrev() const { return prev ? prev->self() : 0; }
};
/**
* Intrusive doubly linked list of reference counted nodes.
*
*@param T must inherit from IListNode<N>
*@param N Identifies which links to use. @see IListNode.
*/
template <class T, int N=0> class IList {
private:
typedef IListNode<T,N> Node;
template <class R>
class Iterator :
public boost::iterator_facade<Iterator<R>, R, boost::bidirectional_traversal_tag>
{
Node* ptr; // Iterators do not own their pointees.
void increment() { assert(ptr); ptr = ptr->next.get(); }
void decrement() { assert(ptr); ptr = ptr->prev.get(); }
R& dereference() const { assert(ptr); return *boost::polymorphic_downcast<R*>(ptr); }
bool equal(const Iterator<R>& x) const { return ptr == x.ptr; }
Node* cast(const Node* p) { return const_cast<Node*>(p); }
explicit Iterator(const Node* p=0) : ptr(cast(p)) {}
explicit Iterator(const T* p=0) : ptr(cast(p)) {}
friend class boost::iterator_core_access;
friend class IList;
public:
template <class S> Iterator(const Iterator<S>& x) : ptr(x.ptr) {}
};
public:
IList() {}
~IList() { clear(); anchor.erase(); }
typedef size_t size_type;
typedef T value_type;
/// pointer type is an intrusive_ptr
typedef intrusive_ptr<T> pointer;
/// pointer type is an intrusive_ptr
typedef intrusive_ptr<const T> const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef Iterator<value_type> iterator;
typedef Iterator<const value_type> const_iterator;
iterator begin() { return iterator(anchor.next.get()); }
iterator end() { return iterator(&anchor); }
const_iterator begin() const { return const_iterator(anchor.next.get()); }
const_iterator end() const { return const_iterator(&anchor); }
/// Iterator to the last element or end() if empty
iterator last() { return iterator(anchor.prev.get()); }
/// Iterator to the last element or end() if empty
const_iterator last() const { return const_iterator(anchor.prev.get()); }
/// Note: takes a non-const reference, unlike standard containers.
void insert(iterator pos, reference x) { x.Node::insert(pos.ptr); }
void insert(iterator pos, pointer x) { x->Node::insert(pos.ptr); }
void erase(iterator pos) { pos.ptr->erase(); }
void swap(IList &x) { anchor.swap(x.anchor); }
reference back() { assert(!empty()); return *last(); }
const_reference back() const { assert(!empty()); return *last(); }
void pop_back() { assert(!empty()); erase(last()); }
/// Note: takes a non-const reference, unlike standard containers.
void push_back(reference x) { insert(end(), x); }
void push_back(pointer x) { insert(end(), x); }
reference front() { assert(!empty()); return *begin(); }
const_reference front() const { assert(!empty()); return *begin(); }
void pop_front() { assert(!empty()); erase(begin()); }
/// Note: takes a non-const reference, unlike standard containers.
void push_front(reference x) { insert(begin(), x); }
void push_front(pointer x) { insert(begin(), x); }
bool empty() const { return begin() == end(); }
void clear() { while (!empty()) { pop_front(); } }
size_type size() const {
size_type s=0;
for (const_iterator i = begin(); i != end(); ++i) ++s;
return s;
}
iterator erase(iterator from, iterator to) {
while(from != to) erase(from);
}
private:
// The list is circular and always contains an anchor node.
// end() points to the anchor, anchor.next is the first
// iterator, anchor.prev is the last iterator.
struct Anchor : public Node {
Anchor() : Node(this) {}
// Suppress refcounting for the anchor node.
void release() const {}
// Hide anchor from public get functions.
T* self() const { return 0; }
} anchor;
};
template <class T, int N>
void IListNode<T,N>::insert(IListNode* node) {
assert(!next && !prev); // Not already in a list.
assert(node);
assert(node->next && node->prev);
next=node;
prev=node->prev;
prev->next = this;
next->prev = this;
}
template <class T, int N>
void IListNode<T,N>::erase() {
assert(prev && next);
intrusive_ptr<IListNode> save(this); // Protect till exit.
prev->next = next;
next->prev = prev;
prev = next = 0;
}
} // namespace qpid
#endif /*!QPID_ILIST_H*/
|
