The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | // |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 25 | // The only class you want to use from here is "List". |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 26 | // |
| 27 | #ifndef _LIBS_UTILS_LIST_H |
| 28 | #define _LIBS_UTILS_LIST_H |
| 29 | |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 30 | #include <stddef.h> |
| 31 | #include <stdint.h> |
| 32 | |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 33 | namespace android { |
| 34 | |
| 35 | /* |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 41 | template<typename T> |
| 42 | class List |
| 43 | { |
| 44 | protected: |
| 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 | }; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 66 | |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 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 | |
Andy McFadden | 34ed827 | 2009-07-07 10:01:12 -0700 | [diff] [blame] | 157 | _NodePtr mpNode; /* should be private, but older gcc fails */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 158 | private: |
| 159 | friend class List; |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 160 | }; |
| 161 | |
| 162 | public: |
| 163 | List() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 164 | prep(); |
| 165 | } |
| 166 | List(const List<T>& src) { // copy-constructor |
| 167 | prep(); |
| 168 | insert(begin(), src.begin(), src.end()); |
| 169 | } |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 170 | virtual ~List() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 171 | clear(); |
| 172 | delete[] (unsigned char*) mpMiddle; |
| 173 | } |
| 174 | |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 175 | typedef _ListIterator<T, NON_CONST_ITERATOR> iterator; |
| 176 | typedef _ListIterator<T, CONST_ITERATOR> const_iterator; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 177 | |
| 178 | List<T>& operator=(const List<T>& right); |
| 179 | |
| 180 | /* returns true if the list is empty */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 181 | inline bool empty() const { return mpMiddle->getNext() == mpMiddle; } |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 182 | |
| 183 | /* return #of elements in list */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 184 | size_t size() const { |
| 185 | return size_t(distance(begin(), end())); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 186 | } |
| 187 | |
| 188 | /* |
| 189 | * Return the first element or one past the last element. The |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 190 | * _Node* we're returning is converted to an "iterator" by a |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 191 | * constructor in _ListIterator. |
| 192 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 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 | } |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 211 | iterator insert(iterator posn, const T& val) |
| 212 | { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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); |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 218 | return iterator(newNode); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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(); |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 234 | return iterator(pNext); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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! |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 241 | return iterator(last); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 242 | } |
| 243 | |
| 244 | /* remove all contents of the list */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 245 | void clear() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | * |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 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. |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 267 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 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; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 277 | while (first != last) { |
| 278 | ++first; |
| 279 | ++count; |
| 280 | } |
| 281 | return count; |
| 282 | } |
| 283 | |
| 284 | private: |
| 285 | /* |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 286 | * I want a _Node but don't need it to hold valid data. More |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 291 | void prep() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | */ |
| 312 | template<class T> |
| 313 | List<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 |