Home | History | Annotate | Download | only in server
      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