1/* -*- c++ -*- */
2/*
3 * Copyright (C) 2010 The Android Open Source Project
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *  * Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 *  * Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in
13 *    the documentation and/or other materials provided with the
14 *    distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30#ifndef ANDROID_ASTL_LIST__
31#define ANDROID_ASTL_LIST__
32
33#include <cstddef>
34#include <iterator>
35#include <limits>
36#include <algorithm>
37
38// Double linked list. In the android NS we declare the nodes and
39// iterators. The list declaration in the std NS follows that.
40
41namespace android {
42
43struct ListNodeBase {
44    ListNodeBase *mNext;
45    ListNodeBase *mPrev;
46
47    // Swap 2 nodes.
48    static void swap(ListNodeBase& a, ListNodeBase& b);
49
50    // Insert this node BEFORE pos.
51    void hook(ListNodeBase * const pos);
52
53    // Remove this node and link prev and next together.
54    void unhook();
55};
56
57template <typename _T>
58struct ListNode: public ListNodeBase {
59    _T mData;
60};
61
62// iterators: ListIterator and ListConstIterator are bidirectional ones.
63template<typename _T>
64struct ListIterator
65{
66    typedef ListIterator<_T>      iterator_type;
67    typedef android::ListNode<_T> node_type;
68  public:
69    typedef ptrdiff_t                       difference_type;
70    typedef std::bidirectional_iterator_tag iterator_category;
71    typedef _T                              value_type;
72    typedef _T*                             pointer;
73    typedef _T&                             reference;
74
75    ListIterator():
76        mNode() { }
77
78    explicit ListIterator(android::ListNodeBase* node):
79        mNode(node) { }
80
81    reference operator*() const { return static_cast<node_type*>(mNode)->mData; }
82    pointer operator->() const { return &operator*(); }
83
84    iterator_type& operator++() { mNode = mNode->mNext; return *this; }
85    iterator_type& operator++(int) {
86        iterator_type tmp = *this;
87        mNode = mNode->mNext;
88        return *tmp;
89    }
90
91    iterator_type& operator--() { mNode = mNode->mPrev; return *this; }
92    iterator_type& operator--(int) {
93        iterator_type tmp = *this;
94        mNode = mNode->mPrev;
95        return *tmp;
96    }
97
98    bool operator==(const iterator_type& o) const { return mNode == o.mNode; }
99    bool operator!=(const iterator_type& o) const { return mNode != o.mNode; }
100
101    ListNodeBase *mNode;
102};
103
104template<typename _T>
105struct ListConstIterator
106{
107    typedef ListConstIterator<_T> iterator_type;
108    typedef android::ListNode<_T> node_type;
109  public:
110    typedef ptrdiff_t                       difference_type;
111    typedef std::bidirectional_iterator_tag iterator_category;
112    typedef _T                              value_type;
113    typedef _T*                             pointer;
114    typedef _T&                             reference;
115
116    ListConstIterator():
117        mNode() { }
118
119    explicit ListConstIterator(ListNodeBase* node):
120        mNode(node) { }
121
122    ListConstIterator(const ListIterator<_T>& it): mNode(it.mNode) { }
123
124    reference operator*() const { return static_cast<node_type*>(mNode)->mData; }
125    pointer operator->() const { return &operator*(); }
126
127    iterator_type& operator++() { mNode = mNode->mNext; return *this; }
128    iterator_type& operator++(int) {
129        iterator_type tmp = *this;
130        mNode = mNode->mNext;
131        return *tmp;
132    }
133
134    iterator_type& operator--() { mNode = mNode->mPrev; return *this; }
135    iterator_type& operator--(int) {
136        iterator_type tmp = *this;
137        mNode = mNode->mPrev;
138        return *tmp;
139    }
140
141    bool operator==(const iterator_type& o) const { return mNode == o.mNode; }
142    bool operator!=(const iterator_type& o) const { return mNode != o.mNode; }
143
144    ListNodeBase *mNode;
145};
146
147}  // namespace android
148
149namespace std {
150
151// std::list
152
153template<typename _T>
154class list {
155  public:
156    typedef _T                              value_type;
157    typedef _T*                             pointer;
158    typedef const _T*                       const_pointer;
159    typedef _T&                             reference;
160    typedef const _T&                       const_reference;
161    typedef android::ListIterator<_T>       iterator;
162    typedef android::ListConstIterator<_T>  const_iterator;
163    typedef size_t                          size_type;
164    typedef ptrdiff_t                       difference_type;
165
166    // Default constructor, no element.
167    list() { init(); }
168    ~list() { clear(); }
169
170    // Empty the list.
171    void clear();
172
173    // Element access.
174    reference front() { return *iterator(mHead.mNext); }
175    const_reference front() const { return *iterator(mHead.mNext); }
176    reference back() { return *iterator(mHead.mPrev); }
177    const_reference back() const { return *iterator(mHead.mPrev); }
178
179    // Iterators.
180    iterator begin() { return iterator(mHead.mNext); }
181    const_iterator begin() const { return const_iterator(mHead.mNext); }
182    iterator end() { return iterator(&mHead); }
183    const_iterator end() const { return const_iterator(&mHead); }
184
185    // Add data at the begin of the list.
186    // @param elt To be added.
187    void push_front(const value_type& elt) { insert(begin(), elt); }
188    void push_back(const value_type& elt) { insert(end(), elt); }
189
190    // Removes first element. Invalidated the iterators/references to begin.
191    void pop_front() { eraseAtPos(iterator(mHead.mNext)); }
192
193    // Removes last element. Invalidated the iterators/references to
194    // the last element.
195    void pop_back() { eraseAtPos(iterator(mHead.mPrev)); }
196
197    bool empty() const { return mLength == 0; }
198
199    // @eturn the number of elements in the list.
200    size_type size() const { return mLength; }
201
202    // @return the maximum size for a list
203    size_type max_size() const { return numeric_limits<size_type>::max(); }
204
205    // Insert the element BEFORE the 'pos' iterator.
206    // @param pos Iterator in the list.
207    // @param elt Element to be inserted.
208    // @return an iterator that points to the inserted element.
209    iterator insert(iterator pos, const value_type& elt);
210
211    // Remove the element pointed by the iterator. Constant in time,
212    // calls once to _T's destructor.
213    // @param pos Iterator pointing to the elt to be removed.
214    // @return An iterator pointing to the next elt or end().
215    iterator erase(iterator position);
216
217    // Remove a range of elements [first, last)
218    // @param first Iterator pointing to the first element to be removed.
219    // @param last Iterator pointing to one past the last element to be removed.
220    // @return An iterator pointing to the elt next to 'last' or end().
221    iterator erase(iterator first, iterator last);
222
223  private:
224    void init() {
225        mHead.mNext = &mHead;
226        mHead.mPrev = &mHead;
227        mLength = 0;
228    }
229
230    // Erase, don't return anything.
231    void eraseAtPos(iterator pos);
232
233    size_type mLength;
234    // mHead does not contain any data, it represents end().
235    android::ListNodeBase mHead;
236};
237
238
239template<typename _T>
240void list<_T>::clear() {
241    while (mHead.mNext != &mHead) {
242        // Upcast so delete will reclaim all the memory.
243        android::ListNode<_T> *node =
244                static_cast<android::ListNode<_T> *>(mHead.mNext);
245        mHead.mNext = node->mNext;
246        delete node;
247    }
248    init();
249}
250
251template<typename _T>
252typename list<_T>::iterator list<_T>::insert(iterator pos, const value_type& elt) {
253    if (mLength + 1 > mLength) {
254        android::ListNode<_T> *node = new android::ListNode<_T>();
255        node->mData = elt;
256        node->hook(pos.mNode);
257        ++mLength;
258        return iterator(node);
259    } else {
260        return end();
261    }
262}
263
264template<typename _T>
265typename list<_T>::iterator list<_T>::erase(iterator pos) {
266    iterator res = iterator(pos.mNode->mNext);
267    eraseAtPos(pos);
268    return res;
269}
270
271template<typename _T>
272typename list<_T>::iterator list<_T>::erase(iterator first, iterator last) {
273    while (first != last) {
274        first = erase(first);  // erase returns an iterator to the next elt.
275    }
276    return last;
277}
278
279template<typename _T>
280void list<_T>::eraseAtPos(iterator pos) {
281    if (pos.mNode != &mHead) {
282        pos.mNode->unhook();
283        android::ListNode<_T>* node =
284                static_cast<android::ListNode<_T>*>(pos.mNode);
285        delete node;
286        --mLength;
287    }
288}
289
290}  // namespace std
291
292#endif  // ANDROID_ASTL_LIST__
293