| /* |
| * 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. |
| * |
| * DO NOT USE: please use std::list<T> |
| */ |
| 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 |