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
33namespace 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 */
41template<typename T>
42class List
43{
44protected:
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
162public:
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
284private:
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 */
312template<class T>
313List<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
333