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 _NETD_LIST_H 28 #define _NETD_LIST_H 29 30 #include <stddef.h> 31 #include <stdint.h> 32 33 namespace android { 34 namespace netd { 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 netd 332 }; // namespace android 333 334 #endif // _NETD_LIST_H 335
