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".  Do not use classes
26// starting with "_" directly.
27//
28#ifndef _LIBS_UTILS_LIST_H
29#define _LIBS_UTILS_LIST_H
30
31namespace android {
32
33/*
34 * One element in the list.
35 */
36template<class T> class _ListNode {
37public:
38    typedef _ListNode<T> _Node;
39
40    _ListNode(const T& val) : mVal(val) {}
41    ~_ListNode(void) {}
42
43    T& getRef(void) { return mVal; }
44    void setVal(const T& val) { mVal = val; }
45
46    _Node* getPrev(void) const { return mpPrev; }
47    void setPrev(_Node* ptr) { mpPrev = ptr; }
48    _Node* getNext(void) const { return mpNext; }
49    void setNext(_Node* ptr) { mpNext = ptr; }
50
51private:
52    T           mVal;
53    _Node*      mpPrev;
54    _Node*      mpNext;
55};
56
57/*
58 * Iterator for walking through the list.
59 */
60template<class T, class Tref> class _ListIterator {
61public:
62    typedef _ListIterator<T,Tref> _Iter;
63    typedef _ListNode<T> _Node;
64
65    _ListIterator(void) {}
66    _ListIterator(_Node* ptr) : mpNode(ptr) {}
67    ~_ListIterator(void) {}
68
69    /*
70     * Dereference operator.  Used to get at the juicy insides.
71     */
72    Tref operator*() const { return mpNode->getRef(); }
73
74    /*
75     * Iterator comparison.
76     */
77    bool operator==(const _Iter& right) const { return mpNode == right.mpNode; }
78    bool operator!=(const _Iter& right) const { return mpNode != right.mpNode; }
79
80    /*
81     * Incr/decr, used to move through the list.
82     */
83    _Iter& operator++(void) {        // pre-increment
84        mpNode = mpNode->getNext();
85        return *this;
86    }
87    _Iter operator++(int) {          // post-increment
88        _Iter tmp = *this;
89        ++*this;
90        return tmp;
91    }
92    _Iter& operator--(void) {        // pre-increment
93        mpNode = mpNode->getPrev();
94        return *this;
95    }
96    _Iter operator--(int) {          // post-increment
97        _Iter tmp = *this;
98        --*this;
99        return tmp;
100    }
101
102    _Node* getNode(void) const { return mpNode; }
103
104private:
105    _Node*      mpNode;
106};
107
108
109/*
110 * Doubly-linked list.  Instantiate with "List<MyClass> myList".
111 *
112 * Objects added to the list are copied using the assignment operator,
113 * so this must be defined.
114 */
115template<class T> class List {
116public:
117    typedef _ListNode<T> _Node;
118
119    List(void) {
120        prep();
121    }
122    List(const List<T>& src) {      // copy-constructor
123        prep();
124        insert(begin(), src.begin(), src.end());
125    }
126    virtual ~List(void) {
127        clear();
128        delete[] (unsigned char*) mpMiddle;
129    }
130
131    typedef _ListIterator<T,T&> iterator;
132    typedef _ListIterator<T, const T&> const_iterator;
133
134    List<T>& operator=(const List<T>& right);
135
136    /* returns true if the list is empty */
137    bool empty(void) const { return mpMiddle->getNext() == mpMiddle; }
138
139    /* return #of elements in list */
140    unsigned int size(void) const {
141        return distance(begin(), end());
142    }
143
144    /*
145     * Return the first element or one past the last element.  The
146     * _ListNode* we're returning is converted to an "iterator" by a
147     * constructor in _ListIterator.
148     */
149    iterator begin()                { return mpMiddle->getNext(); }
150    const_iterator begin() const    { return mpMiddle->getNext(); }
151    iterator end()                  { return mpMiddle; }
152    const_iterator end() const      { return mpMiddle; }
153
154    /* add the object to the head or tail of the list */
155    void push_front(const T& val) { insert(begin(), val); }
156    void push_back(const T& val) { insert(end(), val); }
157
158    /* insert before the current node; returns iterator at new node */
159    iterator insert(iterator posn, const T& val) {
160        _Node* newNode = new _Node(val);        // alloc & copy-construct
161        newNode->setNext(posn.getNode());
162        newNode->setPrev(posn.getNode()->getPrev());
163        posn.getNode()->getPrev()->setNext(newNode);
164        posn.getNode()->setPrev(newNode);
165        return newNode;
166    }
167
168    /* insert a range of elements before the current node */
169    void insert(iterator posn, const_iterator first, const_iterator last) {
170        for ( ; first != last; ++first)
171            insert(posn, *first);
172    }
173
174    /* remove one entry; returns iterator at next node */
175    iterator erase(iterator posn) {
176        _Node* pNext = posn.getNode()->getNext();
177        _Node* pPrev = posn.getNode()->getPrev();
178        pPrev->setNext(pNext);
179        pNext->setPrev(pPrev);
180        delete posn.getNode();
181        return pNext;
182    }
183
184    /* remove a range of elements */
185    iterator erase(iterator first, iterator last) {
186        while (first != last)
187            erase(first++);     // don't erase than incr later!
188        return last;
189    }
190
191    /* remove all contents of the list */
192    void clear(void) {
193        _Node* pCurrent = mpMiddle->getNext();
194        _Node* pNext;
195
196        while (pCurrent != mpMiddle) {
197            pNext = pCurrent->getNext();
198            delete pCurrent;
199            pCurrent = pNext;
200        }
201        mpMiddle->setPrev(mpMiddle);
202        mpMiddle->setNext(mpMiddle);
203    }
204
205    /*
206     * Measure the distance between two iterators.  On exist, "first"
207     * will be equal to "last".  The iterators must refer to the same
208     * list.
209     *
210     * (This is actually a generic iterator function.  It should be part
211     * of some other class, possibly an iterator base class.  It needs to
212     * know the difference between a list, which has to march through,
213     * and a vector, which can just do pointer math.)
214     */
215    unsigned int distance(iterator first, iterator last) {
216        unsigned int count = 0;
217        while (first != last) {
218            ++first;
219            ++count;
220        }
221        return count;
222    }
223    unsigned int distance(const_iterator first, const_iterator last) const {
224        unsigned int count = 0;
225        while (first != last) {
226            ++first;
227            ++count;
228        }
229        return count;
230    }
231
232private:
233    /*
234     * I want a _ListNode but don't need it to hold valid data.  More
235     * to the point, I don't want T's constructor to fire, since it
236     * might have side-effects or require arguments.  So, we do this
237     * slightly uncouth storage alloc.
238     */
239    void prep(void) {
240        mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
241        mpMiddle->setPrev(mpMiddle);
242        mpMiddle->setNext(mpMiddle);
243    }
244
245    /*
246     * This node plays the role of "pointer to head" and "pointer to tail".
247     * It sits in the middle of a circular list of nodes.  The iterator
248     * runs around the circle until it encounters this one.
249     */
250    _Node*      mpMiddle;
251};
252
253/*
254 * Assignment operator.
255 *
256 * The simplest way to do this would be to clear out the target list and
257 * fill it with the source.  However, we can speed things along by
258 * re-using existing elements.
259 */
260template<class T>
261List<T>& List<T>::operator=(const List<T>& right)
262{
263    if (this == &right)
264        return *this;       // self-assignment
265    iterator firstDst = begin();
266    iterator lastDst = end();
267    const_iterator firstSrc = right.begin();
268    const_iterator lastSrc = right.end();
269    while (firstSrc != lastSrc && firstDst != lastDst)
270        *firstDst++ = *firstSrc++;
271    if (firstSrc == lastSrc)        // ran out of elements in source?
272        erase(firstDst, lastDst);   // yes, erase any extras
273    else
274        insert(lastDst, firstSrc, lastSrc);     // copy remaining over
275    return *this;
276}
277
278}; // namespace android
279
280#endif // _LIBS_UTILS_LIST_H
281