Line data Source code
1 : /*
2 : * Copyright (C) 2005 The Android Open Source Project
3 : *
4 : * Licensed under the Apache License, Version 2.0 (the "License");
5 : * you may not use this file except in compliance with the License.
6 : * You may obtain a copy of the License at
7 : *
8 : * http://www.apache.org/licenses/LICENSE-2.0
9 : *
10 : * Unless required by applicable law or agreed to in writing, software
11 : * distributed under the License is distributed on an "AS IS" BASIS,
12 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : * See the License for the specific language governing permissions and
14 : * limitations under the License.
15 : */
16 :
17 : //
18 : // Templated list class. Normally we'd use STL, but we don't have that.
19 : // This class mimics STL's interfaces.
20 : //
21 : // Objects are copied into the list with the '=' operator or with copy-
22 : // construction, so if the compiler's auto-generated versions won't work for
23 : // you, define your own.
24 : //
25 : // The only class you want to use from here is "List".
26 : //
27 : #ifndef _LIBS_UTILS_LIST_H
28 : #define _LIBS_UTILS_LIST_H
29 :
30 : #include <stddef.h>
31 : #include <stdint.h>
32 :
33 : namespace stagefright {
34 :
35 : /*
36 : * Doubly-linked list. Instantiate with "List<MyClass> myList".
37 : *
38 : * Objects added to the list are copied using the assignment operator,
39 : * so this must be defined.
40 : */
41 : template<typename T>
42 : class List
43 : {
44 : protected:
45 : /*
46 : * One element in the list.
47 : */
48 : class _Node {
49 : public:
50 0 : explicit _Node(const T& val) : mVal(val) {}
51 0 : ~_Node() {}
52 0 : inline T& getRef() { return mVal; }
53 0 : inline const T& getRef() const { return mVal; }
54 0 : inline _Node* getPrev() const { return mpPrev; }
55 3195 : inline _Node* getNext() const { return mpNext; }
56 : inline void setVal(const T& val) { mVal = val; }
57 2514 : inline void setPrev(_Node* ptr) { mpPrev = ptr; }
58 2514 : inline void setNext(_Node* ptr) { mpNext = ptr; }
59 : #ifndef _MSC_VER
60 : private:
61 : friend class List;
62 : friend class _ListIterator;
63 : #endif
64 : T mVal;
65 : _Node* mpPrev;
66 : _Node* mpNext;
67 : };
68 :
69 : /*
70 : * Iterator for walking through the list.
71 : */
72 :
73 : template <typename TYPE>
74 : struct CONST_ITERATOR {
75 : typedef _Node const * NodePtr;
76 : typedef const TYPE Type;
77 : };
78 :
79 : template <typename TYPE>
80 : struct NON_CONST_ITERATOR {
81 : typedef _Node* NodePtr;
82 : typedef TYPE Type;
83 : };
84 :
85 : template<
86 : typename U,
87 : template <class> class Constness
88 : >
89 : class _ListIterator {
90 : typedef _ListIterator<U, Constness> _Iter;
91 : typedef typename Constness<U>::NodePtr _NodePtr;
92 : typedef typename Constness<U>::Type _Type;
93 :
94 3195 : explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
95 :
96 : public:
97 : _ListIterator() {}
98 0 : _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
99 3195 : ~_ListIterator() {}
100 :
101 : // this will handle conversions from iterator to const_iterator
102 : // (and also all convertible iterators)
103 : // Here, in this implementation, the iterators can be converted
104 : // if the nodes can be converted
105 : template<typename V> explicit
106 : _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
107 :
108 :
109 : /*
110 : * Dereference operator. Used to get at the juicy insides.
111 : */
112 0 : _Type& operator*() const { return mpNode->getRef(); }
113 : _Type* operator->() const { return &(mpNode->getRef()); }
114 :
115 : /*
116 : * Iterator comparison.
117 : */
118 : inline bool operator==(const _Iter& right) const {
119 : return mpNode == right.mpNode; }
120 :
121 1065 : inline bool operator!=(const _Iter& right) const {
122 1065 : return mpNode != right.mpNode; }
123 :
124 : /*
125 : * handle comparisons between iterator and const_iterator
126 : */
127 : template<typename OTHER>
128 : inline bool operator==(const OTHER& right) const {
129 : return mpNode == right.mpNode; }
130 :
131 : template<typename OTHER>
132 : inline bool operator!=(const OTHER& right) const {
133 : return mpNode != right.mpNode; }
134 :
135 : /*
136 : * Incr/decr, used to move through the list.
137 : */
138 0 : inline _Iter& operator++() { // pre-increment
139 0 : mpNode = mpNode->getNext();
140 0 : return *this;
141 : }
142 : const _Iter operator++(int) { // post-increment
143 : _Iter tmp(*this);
144 : mpNode = mpNode->getNext();
145 : return tmp;
146 : }
147 0 : inline _Iter& operator--() { // pre-increment
148 0 : mpNode = mpNode->getPrev();
149 0 : return *this;
150 : }
151 : const _Iter operator--(int) { // post-increment
152 : _Iter tmp(*this);
153 : mpNode = mpNode->getPrev();
154 : return tmp;
155 : }
156 :
157 0 : inline _NodePtr getNode() const { return mpNode; }
158 :
159 : _NodePtr mpNode; /* should be private, but older gcc fails */
160 : private:
161 : friend class List;
162 : };
163 :
164 : public:
165 384 : List() {
166 384 : prep();
167 384 : }
168 1065 : List(const List<T>& src) { // copy-constructor
169 1065 : prep();
170 1065 : insert(begin(), src.begin(), src.end());
171 1065 : }
172 1065 : virtual ~List() {
173 1065 : clear();
174 1065 : delete[] (unsigned char*) mpMiddle;
175 2130 : }
176 :
177 : typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
178 : typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
179 :
180 : List<T>& operator=(const List<T>& right);
181 :
182 : /* returns true if the list is empty */
183 : inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
184 :
185 : /* return #of elements in list */
186 : size_t size() const {
187 : return size_t(distance(begin(), end()));
188 : }
189 :
190 : /*
191 : * Return the first element or one past the last element. The
192 : * _Node* we're returning is converted to an "iterator" by a
193 : * constructor in _ListIterator.
194 : */
195 1065 : inline iterator begin() {
196 1065 : return iterator(mpMiddle->getNext());
197 : }
198 1065 : inline const_iterator begin() const {
199 1065 : return const_iterator(const_cast<_Node const*>(mpMiddle->getNext()));
200 : }
201 0 : inline iterator end() {
202 0 : return iterator(mpMiddle);
203 : }
204 1065 : inline const_iterator end() const {
205 1065 : return const_iterator(const_cast<_Node const*>(mpMiddle));
206 : }
207 :
208 : /* add the object to the head or tail of the list */
209 : void push_front(const T& val) { insert(begin(), val); }
210 0 : void push_back(const T& val) { insert(end(), val); }
211 :
212 : /* insert before the current node; returns iterator at new node */
213 0 : iterator insert(iterator posn, const T& val)
214 : {
215 0 : _Node* newNode = new _Node(val); // alloc & copy-construct
216 0 : newNode->setNext(posn.getNode());
217 0 : newNode->setPrev(posn.getNode()->getPrev());
218 0 : posn.getNode()->getPrev()->setNext(newNode);
219 0 : posn.getNode()->setPrev(newNode);
220 0 : return iterator(newNode);
221 : }
222 :
223 : /* insert a range of elements before the current node */
224 1065 : void insert(iterator posn, const_iterator first, const_iterator last) {
225 1065 : for ( ; first != last; ++first)
226 0 : insert(posn, *first);
227 1065 : }
228 :
229 : /* remove one entry; returns iterator at next node */
230 : iterator erase(iterator posn) {
231 : _Node* pNext = posn.getNode()->getNext();
232 : _Node* pPrev = posn.getNode()->getPrev();
233 : pPrev->setNext(pNext);
234 : pNext->setPrev(pPrev);
235 : delete posn.getNode();
236 : return iterator(pNext);
237 : }
238 :
239 : /* remove a range of elements */
240 : iterator erase(iterator first, iterator last) {
241 : while (first != last)
242 : erase(first++); // don't erase than incr later!
243 : return iterator(last);
244 : }
245 :
246 : /* remove all contents of the list */
247 1065 : void clear() {
248 1065 : _Node* pCurrent = mpMiddle->getNext();
249 : _Node* pNext;
250 :
251 1065 : while (pCurrent != mpMiddle) {
252 0 : pNext = pCurrent->getNext();
253 0 : delete pCurrent;
254 0 : pCurrent = pNext;
255 : }
256 1065 : mpMiddle->setPrev(mpMiddle);
257 1065 : mpMiddle->setNext(mpMiddle);
258 1065 : }
259 :
260 : /*
261 : * Measure the distance between two iterators. On exist, "first"
262 : * will be equal to "last". The iterators must refer to the same
263 : * list.
264 : *
265 : * FIXME: This is actually a generic iterator function. It should be a
266 : * template function at the top-level with specializations for things like
267 : * vector<>, which can just do pointer math). Here we limit it to
268 : * _ListIterator of the same type but different constness.
269 : */
270 : template<
271 : typename U,
272 : template <class> class CL,
273 : template <class> class CR
274 : >
275 : ptrdiff_t distance(
276 : _ListIterator<U, CL> first, _ListIterator<U, CR> last) const
277 : {
278 : ptrdiff_t count = 0;
279 : while (first != last) {
280 : ++first;
281 : ++count;
282 : }
283 : return count;
284 : }
285 :
286 : private:
287 : /*
288 : * I want a _Node but don't need it to hold valid data. More
289 : * to the point, I don't want T's constructor to fire, since it
290 : * might have side-effects or require arguments. So, we do this
291 : * slightly uncouth storage alloc.
292 : */
293 1449 : void prep() {
294 1449 : mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
295 1449 : mpMiddle->setPrev(mpMiddle);
296 1449 : mpMiddle->setNext(mpMiddle);
297 1449 : }
298 :
299 : /*
300 : * This node plays the role of "pointer to head" and "pointer to tail".
301 : * It sits in the middle of a circular list of nodes. The iterator
302 : * runs around the circle until it encounters this one.
303 : */
304 : _Node* mpMiddle;
305 : };
306 :
307 : /*
308 : * Assignment operator.
309 : *
310 : * The simplest way to do this would be to clear out the target list and
311 : * fill it with the source. However, we can speed things along by
312 : * re-using existing elements.
313 : */
314 : template<class T>
315 : List<T>& List<T>::operator=(const List<T>& right)
316 : {
317 : if (this == &right)
318 : return *this; // self-assignment
319 : iterator firstDst = begin();
320 : iterator lastDst = end();
321 : const_iterator firstSrc = right.begin();
322 : const_iterator lastSrc = right.end();
323 : while (firstSrc != lastSrc && firstDst != lastDst)
324 : *firstDst++ = *firstSrc++;
325 : if (firstSrc == lastSrc) // ran out of elements in source?
326 : erase(firstDst, lastDst); // yes, erase any extras
327 : else
328 : insert(lastDst, firstSrc, lastSrc); // copy remaining over
329 : return *this;
330 : }
331 :
332 : }; // namespace stagefright
333 :
334 : #endif // _LIBS_UTILS_LIST_H
|
