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