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. |
Steven Moreland | b8f152d | 2017-12-18 16:14:13 -0800 | [diff] [blame] | 40 | * |
| 41 | * DO NOT USE: please use std::list<T> |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 42 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 43 | template<typename T> |
| 44 | class List |
| 45 | { |
| 46 | protected: |
| 47 | /* |
| 48 | * One element in the list. |
| 49 | */ |
| 50 | class _Node { |
| 51 | public: |
| 52 | explicit _Node(const T& val) : mVal(val) {} |
| 53 | ~_Node() {} |
| 54 | inline T& getRef() { return mVal; } |
| 55 | inline const T& getRef() const { return mVal; } |
| 56 | inline _Node* getPrev() const { return mpPrev; } |
| 57 | inline _Node* getNext() const { return mpNext; } |
| 58 | inline void setVal(const T& val) { mVal = val; } |
| 59 | inline void setPrev(_Node* ptr) { mpPrev = ptr; } |
| 60 | inline void setNext(_Node* ptr) { mpNext = ptr; } |
| 61 | private: |
| 62 | friend class List; |
| 63 | friend class _ListIterator; |
| 64 | T mVal; |
| 65 | _Node* mpPrev; |
| 66 | _Node* mpNext; |
| 67 | }; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 68 | |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 69 | /* |
| 70 | * Iterator for walking through the list. |
| 71 | */ |
| 72 | |
| 73 | template <typename TYPE> |
| 74 | struct CONST_ITERATOR { |
| 75 | typedef _Node const * NodePtr; |
| 76 | typedef const TYPE Type; |
| 77 | }; |
| 78 | |
| 79 | template <typename TYPE> |
| 80 | struct NON_CONST_ITERATOR { |
| 81 | typedef _Node* NodePtr; |
| 82 | typedef TYPE Type; |
| 83 | }; |
| 84 | |
| 85 | template< |
| 86 | typename U, |
| 87 | template <class> class Constness |
| 88 | > |
| 89 | class _ListIterator { |
| 90 | typedef _ListIterator<U, Constness> _Iter; |
| 91 | typedef typename Constness<U>::NodePtr _NodePtr; |
| 92 | typedef typename Constness<U>::Type _Type; |
| 93 | |
| 94 | explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {} |
| 95 | |
| 96 | public: |
| 97 | _ListIterator() {} |
| 98 | _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {} |
| 99 | ~_ListIterator() {} |
| 100 | |
| 101 | // this will handle conversions from iterator to const_iterator |
| 102 | // (and also all convertible iterators) |
| 103 | // Here, in this implementation, the iterators can be converted |
| 104 | // if the nodes can be converted |
| 105 | template<typename V> explicit |
| 106 | _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {} |
| 107 | |
| 108 | |
| 109 | /* |
| 110 | * Dereference operator. Used to get at the juicy insides. |
| 111 | */ |
| 112 | _Type& operator*() const { return mpNode->getRef(); } |
| 113 | _Type* operator->() const { return &(mpNode->getRef()); } |
| 114 | |
| 115 | /* |
| 116 | * Iterator comparison. |
| 117 | */ |
| 118 | inline bool operator==(const _Iter& right) const { |
| 119 | return mpNode == right.mpNode; } |
| 120 | |
| 121 | inline bool operator!=(const _Iter& right) const { |
| 122 | return mpNode != right.mpNode; } |
| 123 | |
| 124 | /* |
| 125 | * handle comparisons between iterator and const_iterator |
| 126 | */ |
| 127 | template<typename OTHER> |
| 128 | inline bool operator==(const OTHER& right) const { |
| 129 | return mpNode == right.mpNode; } |
| 130 | |
| 131 | template<typename OTHER> |
| 132 | inline bool operator!=(const OTHER& right) const { |
| 133 | return mpNode != right.mpNode; } |
| 134 | |
| 135 | /* |
| 136 | * Incr/decr, used to move through the list. |
| 137 | */ |
| 138 | inline _Iter& operator++() { // pre-increment |
| 139 | mpNode = mpNode->getNext(); |
| 140 | return *this; |
| 141 | } |
| 142 | const _Iter operator++(int) { // post-increment |
| 143 | _Iter tmp(*this); |
| 144 | mpNode = mpNode->getNext(); |
| 145 | return tmp; |
| 146 | } |
| 147 | inline _Iter& operator--() { // pre-increment |
| 148 | mpNode = mpNode->getPrev(); |
| 149 | return *this; |
| 150 | } |
| 151 | const _Iter operator--(int) { // post-increment |
| 152 | _Iter tmp(*this); |
| 153 | mpNode = mpNode->getPrev(); |
| 154 | return tmp; |
| 155 | } |
| 156 | |
| 157 | inline _NodePtr getNode() const { return mpNode; } |
| 158 | |
Andy McFadden | 34ed827 | 2009-07-07 10:01:12 -0700 | [diff] [blame] | 159 | _NodePtr mpNode; /* should be private, but older gcc fails */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 160 | private: |
| 161 | friend class List; |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 162 | }; |
| 163 | |
| 164 | public: |
| 165 | List() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 166 | prep(); |
| 167 | } |
| 168 | List(const List<T>& src) { // copy-constructor |
| 169 | prep(); |
| 170 | insert(begin(), src.begin(), src.end()); |
| 171 | } |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 172 | virtual ~List() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 173 | clear(); |
| 174 | delete[] (unsigned char*) mpMiddle; |
| 175 | } |
| 176 | |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 177 | typedef _ListIterator<T, NON_CONST_ITERATOR> iterator; |
| 178 | typedef _ListIterator<T, CONST_ITERATOR> const_iterator; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 179 | |
| 180 | List<T>& operator=(const List<T>& right); |
| 181 | |
| 182 | /* returns true if the list is empty */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 183 | inline bool empty() const { return mpMiddle->getNext() == mpMiddle; } |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 184 | |
| 185 | /* return #of elements in list */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 186 | size_t size() const { |
| 187 | return size_t(distance(begin(), end())); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 188 | } |
| 189 | |
| 190 | /* |
| 191 | * Return the first element or one past the last element. The |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 192 | * _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] | 193 | * constructor in _ListIterator. |
| 194 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 195 | inline iterator begin() { |
| 196 | return iterator(mpMiddle->getNext()); |
| 197 | } |
| 198 | inline const_iterator begin() const { |
| 199 | return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); |
| 200 | } |
| 201 | inline iterator end() { |
| 202 | return iterator(mpMiddle); |
| 203 | } |
| 204 | inline const_iterator end() const { |
| 205 | return const_iterator(const_cast<_Node const*>(mpMiddle)); |
| 206 | } |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 207 | |
| 208 | /* add the object to the head or tail of the list */ |
| 209 | void push_front(const T& val) { insert(begin(), val); } |
| 210 | void push_back(const T& val) { insert(end(), val); } |
| 211 | |
| 212 | /* insert before the current node; returns iterator at new node */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 213 | iterator insert(iterator posn, const T& val) |
| 214 | { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 215 | _Node* newNode = new _Node(val); // alloc & copy-construct |
| 216 | newNode->setNext(posn.getNode()); |
| 217 | newNode->setPrev(posn.getNode()->getPrev()); |
| 218 | posn.getNode()->getPrev()->setNext(newNode); |
| 219 | posn.getNode()->setPrev(newNode); |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 220 | return iterator(newNode); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 221 | } |
| 222 | |
| 223 | /* insert a range of elements before the current node */ |
| 224 | void insert(iterator posn, const_iterator first, const_iterator last) { |
| 225 | for ( ; first != last; ++first) |
| 226 | insert(posn, *first); |
| 227 | } |
| 228 | |
| 229 | /* remove one entry; returns iterator at next node */ |
| 230 | iterator erase(iterator posn) { |
| 231 | _Node* pNext = posn.getNode()->getNext(); |
| 232 | _Node* pPrev = posn.getNode()->getPrev(); |
| 233 | pPrev->setNext(pNext); |
| 234 | pNext->setPrev(pPrev); |
| 235 | delete posn.getNode(); |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 236 | return iterator(pNext); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 237 | } |
| 238 | |
| 239 | /* remove a range of elements */ |
| 240 | iterator erase(iterator first, iterator last) { |
| 241 | while (first != last) |
| 242 | erase(first++); // don't erase than incr later! |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 243 | return iterator(last); |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 244 | } |
| 245 | |
| 246 | /* remove all contents of the list */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 247 | void clear() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 248 | _Node* pCurrent = mpMiddle->getNext(); |
| 249 | _Node* pNext; |
| 250 | |
| 251 | while (pCurrent != mpMiddle) { |
| 252 | pNext = pCurrent->getNext(); |
| 253 | delete pCurrent; |
| 254 | pCurrent = pNext; |
| 255 | } |
| 256 | mpMiddle->setPrev(mpMiddle); |
| 257 | mpMiddle->setNext(mpMiddle); |
| 258 | } |
| 259 | |
| 260 | /* |
| 261 | * Measure the distance between two iterators. On exist, "first" |
| 262 | * will be equal to "last". The iterators must refer to the same |
| 263 | * list. |
| 264 | * |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 265 | * FIXME: This is actually a generic iterator function. It should be a |
| 266 | * template function at the top-level with specializations for things like |
| 267 | * vector<>, which can just do pointer math). Here we limit it to |
| 268 | * _ListIterator of the same type but different constness. |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 269 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 270 | template< |
| 271 | typename U, |
| 272 | template <class> class CL, |
| 273 | template <class> class CR |
| 274 | > |
| 275 | ptrdiff_t distance( |
| 276 | _ListIterator<U, CL> first, _ListIterator<U, CR> last) const |
| 277 | { |
| 278 | ptrdiff_t count = 0; |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 279 | while (first != last) { |
| 280 | ++first; |
| 281 | ++count; |
| 282 | } |
| 283 | return count; |
| 284 | } |
| 285 | |
| 286 | private: |
| 287 | /* |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 288 | * 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] | 289 | * to the point, I don't want T's constructor to fire, since it |
| 290 | * might have side-effects or require arguments. So, we do this |
| 291 | * slightly uncouth storage alloc. |
| 292 | */ |
Mathias Agopian | 0077a0d | 2009-04-27 22:09:49 -0700 | [diff] [blame] | 293 | void prep() { |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 294 | mpMiddle = (_Node*) new unsigned char[sizeof(_Node)]; |
| 295 | mpMiddle->setPrev(mpMiddle); |
| 296 | mpMiddle->setNext(mpMiddle); |
| 297 | } |
| 298 | |
| 299 | /* |
| 300 | * This node plays the role of "pointer to head" and "pointer to tail". |
| 301 | * It sits in the middle of a circular list of nodes. The iterator |
| 302 | * runs around the circle until it encounters this one. |
| 303 | */ |
| 304 | _Node* mpMiddle; |
| 305 | }; |
| 306 | |
| 307 | /* |
| 308 | * Assignment operator. |
| 309 | * |
| 310 | * The simplest way to do this would be to clear out the target list and |
| 311 | * fill it with the source. However, we can speed things along by |
| 312 | * re-using existing elements. |
| 313 | */ |
| 314 | template<class T> |
| 315 | List<T>& List<T>::operator=(const List<T>& right) |
| 316 | { |
| 317 | if (this == &right) |
| 318 | return *this; // self-assignment |
| 319 | iterator firstDst = begin(); |
| 320 | iterator lastDst = end(); |
| 321 | const_iterator firstSrc = right.begin(); |
| 322 | const_iterator lastSrc = right.end(); |
| 323 | while (firstSrc != lastSrc && firstDst != lastDst) |
| 324 | *firstDst++ = *firstSrc++; |
| 325 | if (firstSrc == lastSrc) // ran out of elements in source? |
| 326 | erase(firstDst, lastDst); // yes, erase any extras |
| 327 | else |
| 328 | insert(lastDst, firstSrc, lastSrc); // copy remaining over |
| 329 | return *this; |
| 330 | } |
| 331 | |
Pirama Arumuga Nainar | 90affce | 2018-04-11 23:10:28 -0700 | [diff] [blame^] | 332 | } // namespace android |
The Android Open Source Project | cbb1011 | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 333 | |
| 334 | #endif // _LIBS_UTILS_LIST_H |