server/List.h

   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