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