diff options
Diffstat (limited to 'include/utils/List.h')
-rw-r--r-- | include/utils/List.h | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/include/utils/List.h b/include/utils/List.h new file mode 100644 index 0000000..1a6be9a --- /dev/null +++ b/include/utils/List.h @@ -0,0 +1,280 @@ +/* + * 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". Do not use classes +// starting with "_" directly. +// +#ifndef _LIBS_UTILS_LIST_H +#define _LIBS_UTILS_LIST_H + +namespace android { + +/* + * One element in the list. + */ +template<class T> class _ListNode { +public: + typedef _ListNode<T> _Node; + + _ListNode(const T& val) : mVal(val) {} + ~_ListNode(void) {} + + T& getRef(void) { return mVal; } + void setVal(const T& val) { mVal = val; } + + _Node* getPrev(void) const { return mpPrev; } + void setPrev(_Node* ptr) { mpPrev = ptr; } + _Node* getNext(void) const { return mpNext; } + void setNext(_Node* ptr) { mpNext = ptr; } + +private: + T mVal; + _Node* mpPrev; + _Node* mpNext; +}; + +/* + * Iterator for walking through the list. + */ +template<class T, class Tref> class _ListIterator { +public: + typedef _ListIterator<T,Tref> _Iter; + typedef _ListNode<T> _Node; + + _ListIterator(void) {} + _ListIterator(_Node* ptr) : mpNode(ptr) {} + ~_ListIterator(void) {} + + /* + * Dereference operator. Used to get at the juicy insides. + */ + Tref operator*() const { return mpNode->getRef(); } + + /* + * Iterator comparison. + */ + bool operator==(const _Iter& right) const { return mpNode == right.mpNode; } + bool operator!=(const _Iter& right) const { return mpNode != right.mpNode; } + + /* + * Incr/decr, used to move through the list. + */ + _Iter& operator++(void) { // pre-increment + mpNode = mpNode->getNext(); + return *this; + } + _Iter operator++(int) { // post-increment + _Iter tmp = *this; + ++*this; + return tmp; + } + _Iter& operator--(void) { // pre-increment + mpNode = mpNode->getPrev(); + return *this; + } + _Iter operator--(int) { // post-increment + _Iter tmp = *this; + --*this; + return tmp; + } + + _Node* getNode(void) const { return mpNode; } + +private: + _Node* mpNode; +}; + + +/* + * 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<class T> class List { +public: + typedef _ListNode<T> _Node; + + List(void) { + prep(); + } + List(const List<T>& src) { // copy-constructor + prep(); + insert(begin(), src.begin(), src.end()); + } + virtual ~List(void) { + clear(); + delete[] (unsigned char*) mpMiddle; + } + + typedef _ListIterator<T,T&> iterator; + typedef _ListIterator<T, const T&> const_iterator; + + List<T>& operator=(const List<T>& right); + + /* returns true if the list is empty */ + bool empty(void) const { return mpMiddle->getNext() == mpMiddle; } + + /* return #of elements in list */ + unsigned int size(void) const { + return distance(begin(), end()); + } + + /* + * Return the first element or one past the last element. The + * _ListNode* we're returning is converted to an "iterator" by a + * constructor in _ListIterator. + */ + iterator begin() { return mpMiddle->getNext(); } + const_iterator begin() const { return mpMiddle->getNext(); } + iterator end() { return mpMiddle; } + const_iterator end() const { return 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 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 pNext; + } + + /* remove a range of elements */ + iterator erase(iterator first, iterator last) { + while (first != last) + erase(first++); // don't erase than incr later! + return last; + } + + /* remove all contents of the list */ + void clear(void) { + _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. + * + * (This is actually a generic iterator function. It should be part + * of some other class, possibly an iterator base class. It needs to + * know the difference between a list, which has to march through, + * and a vector, which can just do pointer math.) + */ + unsigned int distance(iterator first, iterator last) { + unsigned int count = 0; + while (first != last) { + ++first; + ++count; + } + return count; + } + unsigned int distance(const_iterator first, const_iterator last) const { + unsigned int count = 0; + while (first != last) { + ++first; + ++count; + } + return count; + } + +private: + /* + * I want a _ListNode 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(void) { + 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 |