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