The Tor Browser / file comparison

comparison: media/omx-plugin/include/ics/utils/List.h

media/omx-plugin/include/ics/utils/List.h

branch
TOR_BUG_9701
changeset 15
b8a032363ba2
equal deleted inserted replaced
-1:000000000000 0:bb3f801e1f2e
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 android {
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 explicit _Node(const T& val) : mVal(val) {}
51 ~_Node() {}
52 inline T& getRef() { return mVal; }
53 inline const T& getRef() const { return mVal; }
54 inline _Node* getPrev() const { return mpPrev; }
55 inline _Node* getNext() const { return mpNext; }
56 inline void setVal(const T& val) { mVal = val; }
57 inline void setPrev(_Node* ptr) { mpPrev = ptr; }
58 inline void setNext(_Node* ptr) { mpNext = ptr; }
59 private:
60 friend class List;
61 friend class _ListIterator;
62 T mVal;
63 _Node* mpPrev;
64 _Node* mpNext;
65 };
66
67 /*
68 * Iterator for walking through the list.
69 */
70
71 template <typename TYPE>
72 struct CONST_ITERATOR {
73 typedef _Node const * NodePtr;
74 typedef const TYPE Type;
75 };
76
77 template <typename TYPE>
78 struct NON_CONST_ITERATOR {
79 typedef _Node* NodePtr;
80 typedef TYPE Type;
81 };
82
83 template<
84 typename U,
85 template <class> class Constness
86 >
87 class _ListIterator {
88 typedef _ListIterator<U, Constness> _Iter;
89 typedef typename Constness<U>::NodePtr _NodePtr;
90 typedef typename Constness<U>::Type _Type;
91
92 explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
93
94 public:
95 _ListIterator() {}
96 _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
97 ~_ListIterator() {}
98
99 // this will handle conversions from iterator to const_iterator
100 // (and also all convertible iterators)
101 // Here, in this implementation, the iterators can be converted
102 // if the nodes can be converted
103 template<typename V> explicit
104 _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
105
106
107 /*
108 * Dereference operator. Used to get at the juicy insides.
109 */
110 _Type& operator*() const { return mpNode->getRef(); }
111 _Type* operator->() const { return &(mpNode->getRef()); }
112
113 /*
114 * Iterator comparison.
115 */
116 inline bool operator==(const _Iter& right) const {
117 return mpNode == right.mpNode; }
118
119 inline bool operator!=(const _Iter& right) const {
120 return mpNode != right.mpNode; }
121
122 /*
123 * handle comparisons between iterator and const_iterator
124 */
125 template<typename OTHER>
126 inline bool operator==(const OTHER& right) const {
127 return mpNode == right.mpNode; }
128
129 template<typename OTHER>
130 inline bool operator!=(const OTHER& right) const {
131 return mpNode != right.mpNode; }
132
133 /*
134 * Incr/decr, used to move through the list.
135 */
136 inline _Iter& operator++() { // pre-increment
137 mpNode = mpNode->getNext();
138 return *this;
139 }
140 const _Iter operator++(int) { // post-increment
141 _Iter tmp(*this);
142 mpNode = mpNode->getNext();
143 return tmp;
144 }
145 inline _Iter& operator--() { // pre-increment
146 mpNode = mpNode->getPrev();
147 return *this;
148 }
149 const _Iter operator--(int) { // post-increment
150 _Iter tmp(*this);
151 mpNode = mpNode->getPrev();
152 return tmp;
153 }
154
155 inline _NodePtr getNode() const { return mpNode; }
156
157 _NodePtr mpNode; /* should be private, but older gcc fails */
158 private:
159 friend class List;
160 };
161
162 public:
163 List() {
164 prep();
165 }
166 List(const List<T>& src) { // copy-constructor
167 prep();
168 insert(begin(), src.begin(), src.end());
169 }
170 virtual ~List() {
171 clear();
172 delete[] (unsigned char*) mpMiddle;
173 }
174
175 typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
176 typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
177
178 List<T>& operator=(const List<T>& right);
179
180 /* returns true if the list is empty */
181 inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
182
183 /* return #of elements in list */
184 size_t size() const {
185 return size_t(distance(begin(), end()));
186 }
187
188 /*
189 * Return the first element or one past the last element. The
190 * _Node* we're returning is converted to an "iterator" by a
191 * constructor in _ListIterator.
192 */
193 inline iterator begin() {
194 return iterator(mpMiddle->getNext());
195 }
196 inline const_iterator begin() const {
197 return const_iterator(const_cast<_Node const*>(mpMiddle->getNext()));
198 }
199 inline iterator end() {
200 return iterator(mpMiddle);
201 }
202 inline const_iterator end() const {
203 return const_iterator(const_cast<_Node const*>(mpMiddle));
204 }
205
206 /* add the object to the head or tail of the list */
207 void push_front(const T& val) { insert(begin(), val); }
208 void push_back(const T& val) { insert(end(), val); }
209
210 /* insert before the current node; returns iterator at new node */
211 iterator insert(iterator posn, const T& val)
212 {
213 _Node* newNode = new _Node(val); // alloc & copy-construct
214 newNode->setNext(posn.getNode());
215 newNode->setPrev(posn.getNode()->getPrev());
216 posn.getNode()->getPrev()->setNext(newNode);
217 posn.getNode()->setPrev(newNode);
218 return iterator(newNode);
219 }
220
221 /* insert a range of elements before the current node */
222 void insert(iterator posn, const_iterator first, const_iterator last) {
223 for ( ; first != last; ++first)
224 insert(posn, *first);
225 }
226
227 /* remove one entry; returns iterator at next node */
228 iterator erase(iterator posn) {
229 _Node* pNext = posn.getNode()->getNext();
230 _Node* pPrev = posn.getNode()->getPrev();
231 pPrev->setNext(pNext);
232 pNext->setPrev(pPrev);
233 delete posn.getNode();
234 return iterator(pNext);
235 }
236
237 /* remove a range of elements */
238 iterator erase(iterator first, iterator last) {
239 while (first != last)
240 erase(first++); // don't erase than incr later!
241 return iterator(last);
242 }
243
244 /* remove all contents of the list */
245 void clear() {
246 _Node* pCurrent = mpMiddle->getNext();
247 _Node* pNext;
248
249 while (pCurrent != mpMiddle) {
250 pNext = pCurrent->getNext();
251 delete pCurrent;
252 pCurrent = pNext;
253 }
254 mpMiddle->setPrev(mpMiddle);
255 mpMiddle->setNext(mpMiddle);
256 }
257
258 /*
259 * Measure the distance between two iterators. On exist, "first"
260 * will be equal to "last". The iterators must refer to the same
261 * list.
262 *
263 * FIXME: This is actually a generic iterator function. It should be a
264 * template function at the top-level with specializations for things like
265 * vector<>, which can just do pointer math). Here we limit it to
266 * _ListIterator of the same type but different constness.
267 */
268 template<
269 typename U,
270 template <class> class CL,
271 template <class> class CR
272 >
273 ptrdiff_t distance(
274 _ListIterator<U, CL> first, _ListIterator<U, CR> last) const
275 {
276 ptrdiff_t count = 0;
277 while (first != last) {
278 ++first;
279 ++count;
280 }
281 return count;
282 }
283
284 private:
285 /*
286 * I want a _Node but don't need it to hold valid data. More
287 * to the point, I don't want T's constructor to fire, since it
288 * might have side-effects or require arguments. So, we do this
289 * slightly uncouth storage alloc.
290 */
291 void prep() {
292 mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
293 mpMiddle->setPrev(mpMiddle);
294 mpMiddle->setNext(mpMiddle);
295 }
296
297 /*
298 * This node plays the role of "pointer to head" and "pointer to tail".
299 * It sits in the middle of a circular list of nodes. The iterator
300 * runs around the circle until it encounters this one.
301 */
302 _Node* mpMiddle;
303 };
304
305 /*
306 * Assignment operator.
307 *
308 * The simplest way to do this would be to clear out the target list and
309 * fill it with the source. However, we can speed things along by
310 * re-using existing elements.
311 */
312 template<class T>
313 List<T>& List<T>::operator=(const List<T>& right)
314 {
315 if (this == &right)
316 return *this; // self-assignment
317 iterator firstDst = begin();
318 iterator lastDst = end();
319 const_iterator firstSrc = right.begin();
320 const_iterator lastSrc = right.end();
321 while (firstSrc != lastSrc && firstDst != lastDst)
322 *firstDst++ = *firstSrc++;
323 if (firstSrc == lastSrc) // ran out of elements in source?
324 erase(firstDst, lastDst); // yes, erase any extras
325 else
326 insert(lastDst, firstSrc, lastSrc); // copy remaining over
327 return *this;
328 }
329
330 }; // namespace android
331
332 #endif // _LIBS_UTILS_LIST_H

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial