• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  * DO NOT USE: please use std::list<T>
42  */
43 template<typename T>
44 class List
45 {
46 protected:
47     /*
48      * One element in the list.
49      */
50     class _Node {
51     public:
_Node(const T & val)52         explicit _Node(const T& val) : mVal(val) {}
~_Node()53         ~_Node() {}
getRef()54         inline T& getRef() { return mVal; }
getRef()55         inline const T& getRef() const { return mVal; }
getPrev()56         inline _Node* getPrev() const { return mpPrev; }
getNext()57         inline _Node* getNext() const { return mpNext; }
setVal(const T & val)58         inline void setVal(const T& val) { mVal = val; }
setPrev(_Node * ptr)59         inline void setPrev(_Node* ptr) { mpPrev = ptr; }
setNext(_Node * ptr)60         inline void setNext(_Node* ptr) { mpNext = ptr; }
61     private:
62         friend class List;
63         friend class _ListIterator;
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 
_ListIterator(_NodePtr ptr)94         explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
95 
96     public:
_ListIterator()97         _ListIterator() {}
_ListIterator(const _Iter & rhs)98         _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
~_ListIterator()99         ~_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
_ListIterator(const V & rhs)106         _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
107 
108 
109         /*
110          * Dereference operator.  Used to get at the juicy insides.
111          */
112         _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         inline bool operator!=(const _Iter& right) const {
122             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         inline _Iter& operator++() {     // pre-increment
139             mpNode = mpNode->getNext();
140             return *this;
141         }
142         const _Iter operator++(int) {    // post-increment
143             _Iter tmp(*this);
144             mpNode = mpNode->getNext();
145             return tmp;
146         }
147         inline _Iter& operator--() {     // pre-increment
148             mpNode = mpNode->getPrev();
149             return *this;
150         }
151         const _Iter operator--(int) {   // post-increment
152             _Iter tmp(*this);
153             mpNode = mpNode->getPrev();
154             return tmp;
155         }
156 
getNode()157         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:
List()165     List() {
166         prep();
167     }
List(const List<T> & src)168     List(const List<T>& src) {      // copy-constructor
169         prep();
170         insert(begin(), src.begin(), src.end());
171     }
~List()172     virtual ~List() {
173         clear();
174         delete[] (unsigned char*) mpMiddle;
175     }
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 */
empty()183     inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
184 
185     /* return #of elements in list */
size()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      */
begin()195     inline iterator begin() {
196         return iterator(mpMiddle->getNext());
197     }
begin()198     inline const_iterator begin() const {
199         return const_iterator(const_cast<_Node const*>(mpMiddle->getNext()));
200     }
end()201     inline iterator end() {
202         return iterator(mpMiddle);
203     }
end()204     inline const_iterator end() const {
205         return const_iterator(const_cast<_Node const*>(mpMiddle));
206     }
207 
208     /* add the object to the head or tail of the list */
push_front(const T & val)209     void push_front(const T& val) { insert(begin(), val); }
push_back(const T & val)210     void push_back(const T& val) { insert(end(), val); }
211 
212     /* insert before the current node; returns iterator at new node */
insert(iterator posn,const T & val)213     iterator insert(iterator posn, const T& val)
214     {
215         _Node* newNode = new _Node(val);        // alloc & copy-construct
216         newNode->setNext(posn.getNode());
217         newNode->setPrev(posn.getNode()->getPrev());
218         posn.getNode()->getPrev()->setNext(newNode);
219         posn.getNode()->setPrev(newNode);
220         return iterator(newNode);
221     }
222 
223     /* insert a range of elements before the current node */
insert(iterator posn,const_iterator first,const_iterator last)224     void insert(iterator posn, const_iterator first, const_iterator last) {
225         for ( ; first != last; ++first)
226             insert(posn, *first);
227     }
228 
229     /* remove one entry; returns iterator at next node */
erase(iterator posn)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 */
erase(iterator first,iterator last)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 */
clear()247     void clear() {
248         _Node* pCurrent = mpMiddle->getNext();
249         _Node* pNext;
250 
251         while (pCurrent != mpMiddle) {
252             pNext = pCurrent->getNext();
253             delete pCurrent;
254             pCurrent = pNext;
255         }
256         mpMiddle->setPrev(mpMiddle);
257         mpMiddle->setNext(mpMiddle);
258     }
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     >
distance(_ListIterator<U,CL> first,_ListIterator<U,CR> last)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      */
prep()293     void prep() {
294         mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
295         mpMiddle->setPrev(mpMiddle);
296         mpMiddle->setNext(mpMiddle);
297     }
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 android
333 
334 #endif // _LIBS_UTILS_LIST_H
335