auto import from //depot/cupcake/@135843
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