/*
* 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