The Tor Browser / file revision

 /*

  * Copyright (C) 2005 The Android Open Source Project

  *

  * Licensed under the Apache License, Version 2.0 (the "License");

  * you may not use this file except in compliance with the License.

  * You may obtain a copy of the License at

  *

  *      http://www.apache.org/licenses/LICENSE-2.0

  *

  * Unless required by applicable law or agreed to in writing, software

  * distributed under the License is distributed on an "AS IS" BASIS,

  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

  * See the License for the specific language governing permissions and

  * limitations under the License.

  */

 //

 // Templated list class.  Normally we'd use STL, but we don't have that.

 // This class mimics STL's interfaces.

 //

 // Objects are copied into the list with the '=' operator or with copy-

 // construction, so if the compiler's auto-generated versions won't work for

 // you, define your own.

 //

 // The only class you want to use from here is "List".

 //

 #ifndef _LIBS_UTILS_LIST_H

 #define _LIBS_UTILS_LIST_H

 #include <stddef.h>

 #include <stdint.h>

 namespace android {

 /*

  * Doubly-linked list.  Instantiate with "List<MyClass> myList".

  *

  * Objects added to the list are copied using the assignment operator,

  * so this must be defined.

  */

 template<typename T> 

 class List 

 {

 protected:

     /*

      * One element in the list.

      */

     class _Node {

     public:

         explicit _Node(const T& val) : mVal(val) {}

         ~_Node() {}

         inline T& getRef() { return mVal; }

         inline const T& getRef() const { return mVal; }

         inline _Node* getPrev() const { return mpPrev; }

         inline _Node* getNext() const { return mpNext; }

         inline void setVal(const T& val) { mVal = val; }

         inline void setPrev(_Node* ptr) { mpPrev = ptr; }

         inline void setNext(_Node* ptr) { mpNext = ptr; }

     private:

         friend class List;

         friend class _ListIterator;

         T           mVal;

         _Node*      mpPrev;

         _Node*      mpNext;

     };

     /*

      * Iterator for walking through the list.

      */

     template <typename TYPE>

     struct CONST_ITERATOR {

         typedef _Node const * NodePtr;

         typedef const TYPE Type;

     };

     template <typename TYPE>

     struct NON_CONST_ITERATOR {

         typedef _Node* NodePtr;

         typedef TYPE Type;

     };

     template<

         typename U,

         template <class> class Constness

     > 

     class _ListIterator {

         typedef _ListIterator<U, Constness>     _Iter;

         typedef typename Constness<U>::NodePtr  _NodePtr;

         typedef typename Constness<U>::Type     _Type;

         explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}

     public:

         _ListIterator() {}

         _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}

         ~_ListIterator() {}

         // this will handle conversions from iterator to const_iterator

         // (and also all convertible iterators)

         // Here, in this implementation, the iterators can be converted

         // if the nodes can be converted

         template<typename V> explicit 

         _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}

         /*

          * Dereference operator.  Used to get at the juicy insides.

          */

         _Type& operator*() const { return mpNode->getRef(); }

         _Type* operator->() const { return &(mpNode->getRef()); }

         /*

          * Iterator comparison.

          */

         inline bool operator==(const _Iter& right) const { 

             return mpNode == right.mpNode; }

         inline bool operator!=(const _Iter& right) const { 

             return mpNode != right.mpNode; }

         /*

          * handle comparisons between iterator and const_iterator

          */

         template<typename OTHER>

         inline bool operator==(const OTHER& right) const { 

             return mpNode == right.mpNode; }

         template<typename OTHER>

         inline bool operator!=(const OTHER& right) const { 

             return mpNode != right.mpNode; }

         /*

          * Incr/decr, used to move through the list.

          */

         inline _Iter& operator++() {     // pre-increment

             mpNode = mpNode->getNext();

             return *this;

         }

         const _Iter operator++(int) {    // post-increment

             _Iter tmp(*this);

             mpNode = mpNode->getNext();

             return tmp;

         }

         inline _Iter& operator--() {     // pre-increment

             mpNode = mpNode->getPrev();

             return *this;

         }

         const _Iter operator--(int) {   // post-increment

             _Iter tmp(*this);

             mpNode = mpNode->getPrev();

             return tmp;

         }

         inline _NodePtr getNode() const { return mpNode; }

         _NodePtr mpNode;    /* should be private, but older gcc fails */

     private:

         friend class List;

     };

 public:

     List() {

         prep();

     }

     List(const List<T>& src) {      // copy-constructor

         prep();

         insert(begin(), src.begin(), src.end());

     }

     virtual ~List() {

         clear();

         delete[] (unsigned char*) mpMiddle;

     }

     typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;

     typedef _ListIterator<T, CONST_ITERATOR> const_iterator;

     List<T>& operator=(const List<T>& right);

     /* returns true if the list is empty */

     inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }

     /* return #of elements in list */

     size_t size() const {

         return size_t(distance(begin(), end()));

     }

     /*

      * Return the first element or one past the last element.  The

      * _Node* we're returning is converted to an "iterator" by a

      * constructor in _ListIterator.

      */

     inline iterator begin() { 

         return iterator(mpMiddle->getNext()); 

     }

     inline const_iterator begin() const { 

         return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 

     }

     inline iterator end() { 

         return iterator(mpMiddle); 

     }

     inline const_iterator end() const { 

         return const_iterator(const_cast<_Node const*>(mpMiddle)); 

     }

     /* add the object to the head or tail of the list */

     void push_front(const T& val) { insert(begin(), val); }

     void push_back(const T& val) { insert(end(), val); }

     /* insert before the current node; returns iterator at new node */

     iterator insert(iterator posn, const T& val) 

     {

         _Node* newNode = new _Node(val);        // alloc & copy-construct

         newNode->setNext(posn.getNode());

         newNode->setPrev(posn.getNode()->getPrev());

         posn.getNode()->getPrev()->setNext(newNode);

         posn.getNode()->setPrev(newNode);

         return iterator(newNode);

     }

     /* insert a range of elements before the current node */

     void insert(iterator posn, const_iterator first, const_iterator last) {

         for ( ; first != last; ++first)

             insert(posn, *first);

     }

     /* remove one entry; returns iterator at next node */

     iterator erase(iterator posn) {

         _Node* pNext = posn.getNode()->getNext();

         _Node* pPrev = posn.getNode()->getPrev();

         pPrev->setNext(pNext);

         pNext->setPrev(pPrev);

         delete posn.getNode();

         return iterator(pNext);

     }

     /* remove a range of elements */

     iterator erase(iterator first, iterator last) {

         while (first != last)

             erase(first++);     // don't erase than incr later!

         return iterator(last);

     }

     /* remove all contents of the list */

     void clear() {

         _Node* pCurrent = mpMiddle->getNext();

         _Node* pNext;

         while (pCurrent != mpMiddle) {

             pNext = pCurrent->getNext();

             delete pCurrent;

             pCurrent = pNext;

         }

         mpMiddle->setPrev(mpMiddle);

         mpMiddle->setNext(mpMiddle);

     }

     /*

      * Measure the distance between two iterators.  On exist, "first"

      * will be equal to "last".  The iterators must refer to the same

      * list.

      *

      * FIXME: This is actually a generic iterator function. It should be a 

      * template function at the top-level with specializations for things like

      * vector<>, which can just do pointer math). Here we limit it to

      * _ListIterator of the same type but different constness.

      */

     template<

         typename U,

         template <class> class CL,

         template <class> class CR

     > 

     ptrdiff_t distance(

             _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 

     {

         ptrdiff_t count = 0;

         while (first != last) {

             ++first;

             ++count;

         }

         return count;

     }

 private:

     /*

      * I want a _Node but don't need it to hold valid data.  More

      * to the point, I don't want T's constructor to fire, since it

      * might have side-effects or require arguments.  So, we do this

      * slightly uncouth storage alloc.

      */

     void prep() {

         mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];

         mpMiddle->setPrev(mpMiddle);

         mpMiddle->setNext(mpMiddle);

     }

     /*

      * This node plays the role of "pointer to head" and "pointer to tail".

      * It sits in the middle of a circular list of nodes.  The iterator

      * runs around the circle until it encounters this one.

      */

     _Node*      mpMiddle;

 };

 /*

  * Assignment operator.

  *

  * The simplest way to do this would be to clear out the target list and

  * fill it with the source.  However, we can speed things along by

  * re-using existing elements.

  */

 template<class T>

 List<T>& List<T>::operator=(const List<T>& right)

 {

     if (this == &right)

         return *this;       // self-assignment

     iterator firstDst = begin();

     iterator lastDst = end();

     const_iterator firstSrc = right.begin();

     const_iterator lastSrc = right.end();

     while (firstSrc != lastSrc && firstDst != lastDst)

         *firstDst++ = *firstSrc++;

     if (firstSrc == lastSrc)        // ran out of elements in source?

         erase(firstDst, lastDst);   // yes, erase any extras

     else

         insert(lastDst, firstSrc, lastSrc);     // copy remaining over

     return *this;

 }

 }; // namespace android

 #endif // _LIBS_UTILS_LIST_H