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". Do not use classes 26// starting with "_" directly. 27// 28#ifndef _LIBS_UTILS_LIST_H 29#define _LIBS_UTILS_LIST_H 30 31namespace android { 32 33/* 34 * One element in the list. 35 */ 36template<class T> class _ListNode { 37public: 38 typedef _ListNode<T> _Node; 39 40 _ListNode(const T& val) : mVal(val) {} 41 ~_ListNode(void) {} 42 43 T& getRef(void) { return mVal; } 44 void setVal(const T& val) { mVal = val; } 45 46 _Node* getPrev(void) const { return mpPrev; } 47 void setPrev(_Node* ptr) { mpPrev = ptr; } 48 _Node* getNext(void) const { return mpNext; } 49 void setNext(_Node* ptr) { mpNext = ptr; } 50 51private: 52 T mVal; 53 _Node* mpPrev; 54 _Node* mpNext; 55}; 56 57/* 58 * Iterator for walking through the list. 59 */ 60template<class T, class Tref> class _ListIterator { 61public: 62 typedef _ListIterator<T,Tref> _Iter; 63 typedef _ListNode<T> _Node; 64 65 _ListIterator(void) {} 66 _ListIterator(_Node* ptr) : mpNode(ptr) {} 67 ~_ListIterator(void) {} 68 69 /* 70 * Dereference operator. Used to get at the juicy insides. 71 */ 72 Tref operator*() const { return mpNode->getRef(); } 73 74 /* 75 * Iterator comparison. 76 */ 77 bool operator==(const _Iter& right) const { return mpNode == right.mpNode; } 78 bool operator!=(const _Iter& right) const { return mpNode != right.mpNode; } 79 80 /* 81 * Incr/decr, used to move through the list. 82 */ 83 _Iter& operator++(void) { // pre-increment 84 mpNode = mpNode->getNext(); 85 return *this; 86 } 87 _Iter operator++(int) { // post-increment 88 _Iter tmp = *this; 89 ++*this; 90 return tmp; 91 } 92 _Iter& operator--(void) { // pre-increment 93 mpNode = mpNode->getPrev(); 94 return *this; 95 } 96 _Iter operator--(int) { // post-increment 97 _Iter tmp = *this; 98 --*this; 99 return tmp; 100 } 101 102 _Node* getNode(void) const { return mpNode; } 103 104private: 105 _Node* mpNode; 106}; 107 108 109/* 110 * Doubly-linked list. Instantiate with "List<MyClass> myList". 111 * 112 * Objects added to the list are copied using the assignment operator, 113 * so this must be defined. 114 */ 115template<class T> class List { 116public: 117 typedef _ListNode<T> _Node; 118 119 List(void) { 120 prep(); 121 } 122 List(const List<T>& src) { // copy-constructor 123 prep(); 124 insert(begin(), src.begin(), src.end()); 125 } 126 virtual ~List(void) { 127 clear(); 128 delete[] (unsigned char*) mpMiddle; 129 } 130 131 typedef _ListIterator<T,T&> iterator; 132 typedef _ListIterator<T, const T&> const_iterator; 133 134 List<T>& operator=(const List<T>& right); 135 136 /* returns true if the list is empty */ 137 bool empty(void) const { return mpMiddle->getNext() == mpMiddle; } 138 139 /* return #of elements in list */ 140 unsigned int size(void) const { 141 return distance(begin(), end()); 142 } 143 144 /* 145 * Return the first element or one past the last element. The 146 * _ListNode* we're returning is converted to an "iterator" by a 147 * constructor in _ListIterator. 148 */ 149 iterator begin() { return mpMiddle->getNext(); } 150 const_iterator begin() const { return mpMiddle->getNext(); } 151 iterator end() { return mpMiddle; } 152 const_iterator end() const { return mpMiddle; } 153 154 /* add the object to the head or tail of the list */ 155 void push_front(const T& val) { insert(begin(), val); } 156 void push_back(const T& val) { insert(end(), val); } 157 158 /* insert before the current node; returns iterator at new node */ 159 iterator insert(iterator posn, const T& val) { 160 _Node* newNode = new _Node(val); // alloc & copy-construct 161 newNode->setNext(posn.getNode()); 162 newNode->setPrev(posn.getNode()->getPrev()); 163 posn.getNode()->getPrev()->setNext(newNode); 164 posn.getNode()->setPrev(newNode); 165 return newNode; 166 } 167 168 /* insert a range of elements before the current node */ 169 void insert(iterator posn, const_iterator first, const_iterator last) { 170 for ( ; first != last; ++first) 171 insert(posn, *first); 172 } 173 174 /* remove one entry; returns iterator at next node */ 175 iterator erase(iterator posn) { 176 _Node* pNext = posn.getNode()->getNext(); 177 _Node* pPrev = posn.getNode()->getPrev(); 178 pPrev->setNext(pNext); 179 pNext->setPrev(pPrev); 180 delete posn.getNode(); 181 return pNext; 182 } 183 184 /* remove a range of elements */ 185 iterator erase(iterator first, iterator last) { 186 while (first != last) 187 erase(first++); // don't erase than incr later! 188 return last; 189 } 190 191 /* remove all contents of the list */ 192 void clear(void) { 193 _Node* pCurrent = mpMiddle->getNext(); 194 _Node* pNext; 195 196 while (pCurrent != mpMiddle) { 197 pNext = pCurrent->getNext(); 198 delete pCurrent; 199 pCurrent = pNext; 200 } 201 mpMiddle->setPrev(mpMiddle); 202 mpMiddle->setNext(mpMiddle); 203 } 204 205 /* 206 * Measure the distance between two iterators. On exist, "first" 207 * will be equal to "last". The iterators must refer to the same 208 * list. 209 * 210 * (This is actually a generic iterator function. It should be part 211 * of some other class, possibly an iterator base class. It needs to 212 * know the difference between a list, which has to march through, 213 * and a vector, which can just do pointer math.) 214 */ 215 unsigned int distance(iterator first, iterator last) { 216 unsigned int count = 0; 217 while (first != last) { 218 ++first; 219 ++count; 220 } 221 return count; 222 } 223 unsigned int distance(const_iterator first, const_iterator last) const { 224 unsigned int count = 0; 225 while (first != last) { 226 ++first; 227 ++count; 228 } 229 return count; 230 } 231 232private: 233 /* 234 * I want a _ListNode but don't need it to hold valid data. More 235 * to the point, I don't want T's constructor to fire, since it 236 * might have side-effects or require arguments. So, we do this 237 * slightly uncouth storage alloc. 238 */ 239 void prep(void) { 240 mpMiddle = (_Node*) new unsigned char[sizeof(_Node)]; 241 mpMiddle->setPrev(mpMiddle); 242 mpMiddle->setNext(mpMiddle); 243 } 244 245 /* 246 * This node plays the role of "pointer to head" and "pointer to tail". 247 * It sits in the middle of a circular list of nodes. The iterator 248 * runs around the circle until it encounters this one. 249 */ 250 _Node* mpMiddle; 251}; 252 253/* 254 * Assignment operator. 255 * 256 * The simplest way to do this would be to clear out the target list and 257 * fill it with the source. However, we can speed things along by 258 * re-using existing elements. 259 */ 260template<class T> 261List<T>& List<T>::operator=(const List<T>& right) 262{ 263 if (this == &right) 264 return *this; // self-assignment 265 iterator firstDst = begin(); 266 iterator lastDst = end(); 267 const_iterator firstSrc = right.begin(); 268 const_iterator lastSrc = right.end(); 269 while (firstSrc != lastSrc && firstDst != lastDst) 270 *firstDst++ = *firstSrc++; 271 if (firstSrc == lastSrc) // ran out of elements in source? 272 erase(firstDst, lastDst); // yes, erase any extras 273 else 274 insert(lastDst, firstSrc, lastSrc); // copy remaining over 275 return *this; 276} 277 278}; // namespace android 279 280#endif // _LIBS_UTILS_LIST_H 281