summaryrefslogtreecommitdiffstats
path: root/include/utils/List.h
blob: 403cd7f1e540213b22b4f289eff14edafcf7fa27 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
/*
 * Copyright (C) 2005 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Templated list class.  Normally we'd use STL, but we don't have that.
// This class mimics STL's interfaces.
//
// Objects are copied into the list with the '=' operator or with copy-
// construction, so if the compiler's auto-generated versions won't work for
// you, define your own.
//
// The only class you want to use from here is "List".
//
#ifndef _LIBS_UTILS_LIST_H
#define _LIBS_UTILS_LIST_H

#include <stddef.h>
#include <stdint.h>

namespace android {

/*
 * Doubly-linked list.  Instantiate with "List<MyClass> myList".
 *
 * Objects added to the list are copied using the assignment operator,
 * so this must be defined.
 */
template<typename T> 
class List 
{
protected:
    /*
     * One element in the list.
     */
    class _Node {
    public:
        explicit _Node(const T& val) : mVal(val) {}
        ~_Node() {}
        inline T& getRef() { return mVal; }
        inline const T& getRef() const { return mVal; }
        inline _Node* getPrev() const { return mpPrev; }
        inline _Node* getNext() const { return mpNext; }
        inline void setVal(const T& val) { mVal = val; }
        inline void setPrev(_Node* ptr) { mpPrev = ptr; }
        inline void setNext(_Node* ptr) { mpNext = ptr; }
    private:
        friend class List;
        friend class _ListIterator;
        T           mVal;
        _Node*      mpPrev;
        _Node*      mpNext;
    };

    /*
     * Iterator for walking through the list.
     */
    
    template <typename TYPE>
    struct CONST_ITERATOR {
        typedef _Node const * NodePtr;
        typedef const TYPE Type;
    };
    
    template <typename TYPE>
    struct NON_CONST_ITERATOR {
        typedef _Node* NodePtr;
        typedef TYPE Type;
    };
    
    template<
        typename U,
        template <class> class Constness
    > 
    class _ListIterator {
        typedef _ListIterator<U, Constness>     _Iter;
        typedef typename Constness<U>::NodePtr  _NodePtr;
        typedef typename Constness<U>::Type     _Type;

        explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}

    public:
        _ListIterator() {}
        _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
        ~_ListIterator() {}
        
        // this will handle conversions from iterator to const_iterator
        // (and also all convertible iterators)
        // Here, in this implementation, the iterators can be converted
        // if the nodes can be converted
        template<typename V> explicit 
        _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
        

        /*
         * Dereference operator.  Used to get at the juicy insides.
         */
        _Type& operator*() const { return mpNode->getRef(); }
        _Type* operator->() const { return &(mpNode->getRef()); }

        /*
         * Iterator comparison.
         */
        inline bool operator==(const _Iter& right) const { 
            return mpNode == right.mpNode; }
        
        inline bool operator!=(const _Iter& right) const { 
            return mpNode != right.mpNode; }

        /*
         * handle comparisons between iterator and const_iterator
         */
        template<typename OTHER>
        inline bool operator==(const OTHER& right) const { 
            return mpNode == right.mpNode; }
        
        template<typename OTHER>
        inline bool operator!=(const OTHER& right) const { 
            return mpNode != right.mpNode; }

        /*
         * Incr/decr, used to move through the list.
         */
        inline _Iter& operator++() {     // pre-increment
            mpNode = mpNode->getNext();
            return *this;
        }
        const _Iter operator++(int) {    // post-increment
            _Iter tmp(*this);
            mpNode = mpNode->getNext();
            return tmp;
        }
        inline _Iter& operator--() {     // pre-increment
            mpNode = mpNode->getPrev();
            return *this;
        }
        const _Iter operator--(int) {   // post-increment
            _Iter tmp(*this);
            mpNode = mpNode->getPrev();
            return tmp;
        }

        inline _NodePtr getNode() const { return mpNode; }

        _NodePtr mpNode;    /* should be private, but older gcc fails */
    private:
        friend class List;
    };

public:
    List() {
        prep();
    }
    List(const List<T>& src) {      // copy-constructor
        prep();
        insert(begin(), src.begin(), src.end());
    }
    virtual ~List() {
        clear();
        delete[] (unsigned char*) mpMiddle;
    }

    typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
    typedef _ListIterator<T, CONST_ITERATOR> const_iterator;

    List<T>& operator=(const List<T>& right);

    /* returns true if the list is empty */
    inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }

    /* return #of elements in list */
    size_t size() const {
        return size_t(distance(begin(), end()));
    }

    /*
     * Return the first element or one past the last element.  The
     * _Node* we're returning is converted to an "iterator" by a
     * constructor in _ListIterator.
     */
    inline iterator begin() { 
        return iterator(mpMiddle->getNext()); 
    }
    inline const_iterator begin() const { 
        return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 
    }
    inline iterator end() { 
        return iterator(mpMiddle); 
    }
    inline const_iterator end() const { 
        return const_iterator(const_cast<_Node const*>(mpMiddle)); 
    }

    /* add the object to the head or tail of the list */
    void push_front(const T& val) { insert(begin(), val); }
    void push_back(const T& val) { insert(end(), val); }

    /* insert before the current node; returns iterator at new node */
    iterator insert(iterator posn, const T& val) 
    {
        _Node* newNode = new _Node(val);        // alloc & copy-construct
        newNode->setNext(posn.getNode());
        newNode->setPrev(posn.getNode()->getPrev());
        posn.getNode()->getPrev()->setNext(newNode);
        posn.getNode()->setPrev(newNode);
        return iterator(newNode);
    }

    /* insert a range of elements before the current node */
    void insert(iterator posn, const_iterator first, const_iterator last) {
        for ( ; first != last; ++first)
            insert(posn, *first);
    }

    /* remove one entry; returns iterator at next node */
    iterator erase(iterator posn) {
        _Node* pNext = posn.getNode()->getNext();
        _Node* pPrev = posn.getNode()->getPrev();
        pPrev->setNext(pNext);
        pNext->setPrev(pPrev);
        delete posn.getNode();
        return iterator(pNext);
    }

    /* remove a range of elements */
    iterator erase(iterator first, iterator last) {
        while (first != last)
            erase(first++);     // don't erase than incr later!
        return iterator(last);
    }

    /* remove all contents of the list */
    void clear() {
        _Node* pCurrent = mpMiddle->getNext();
        _Node* pNext;

        while (pCurrent != mpMiddle) {
            pNext = pCurrent->getNext();
            delete pCurrent;
            pCurrent = pNext;
        }
        mpMiddle->setPrev(mpMiddle);
        mpMiddle->setNext(mpMiddle);
    }

    /*
     * Measure the distance between two iterators.  On exist, "first"
     * will be equal to "last".  The iterators must refer to the same
     * list.
     *
     * FIXME: This is actually a generic iterator function. It should be a 
     * template function at the top-level with specializations for things like
     * vector<>, which can just do pointer math). Here we limit it to
     * _ListIterator of the same type but different constness.
     */
    template<
        typename U,
        template <class> class CL,
        template <class> class CR
    > 
    ptrdiff_t distance(
            _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 
    {
        ptrdiff_t count = 0;
        while (first != last) {
            ++first;
            ++count;
        }
        return count;
    }

private:
    /*
     * I want a _Node but don't need it to hold valid data.  More
     * to the point, I don't want T's constructor to fire, since it
     * might have side-effects or require arguments.  So, we do this
     * slightly uncouth storage alloc.
     */
    void prep() {
        mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
        mpMiddle->setPrev(mpMiddle);
        mpMiddle->setNext(mpMiddle);
    }

    /*
     * This node plays the role of "pointer to head" and "pointer to tail".
     * It sits in the middle of a circular list of nodes.  The iterator
     * runs around the circle until it encounters this one.
     */
    _Node*      mpMiddle;
};

/*
 * Assignment operator.
 *
 * The simplest way to do this would be to clear out the target list and
 * fill it with the source.  However, we can speed things along by
 * re-using existing elements.
 */
template<class T>
List<T>& List<T>::operator=(const List<T>& right)
{
    if (this == &right)
        return *this;       // self-assignment
    iterator firstDst = begin();
    iterator lastDst = end();
    const_iterator firstSrc = right.begin();
    const_iterator lastSrc = right.end();
    while (firstSrc != lastSrc && firstDst != lastDst)
        *firstDst++ = *firstSrc++;
    if (firstSrc == lastSrc)        // ran out of elements in source?
        erase(firstDst, lastDst);   // yes, erase any extras
    else
        insert(lastDst, firstSrc, lastSrc);     // copy remaining over
    return *this;
}

}; // namespace android

#endif // _LIBS_UTILS_LIST_H