summaryrefslogtreecommitdiffstats
path: root/include/utils/List.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/utils/List.h')
-rw-r--r--include/utils/List.h280
1 files changed, 0 insertions, 280 deletions
diff --git a/include/utils/List.h b/include/utils/List.h
deleted file mode 100644
index 1a6be9a..0000000
--- a/include/utils/List.h
+++ /dev/null
@@ -1,280 +0,0 @@
-/*
- * 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
generated by cgit v1.1 at 2024-05-23 08:02:38 +0000