Basic implementation of the std::list.
Moved the class used in vector test to common.h to track memory leaks.
diff --git a/include/list b/include/list
new file mode 100644
index 0000000..d6583d2
--- /dev/null
+++ b/include/list
@@ -0,0 +1,243 @@
+/* -*- c++ -*- */
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef ANDROID_ASTL_LIST__
+#define ANDROID_ASTL_LIST__
+
+#include <cstddef>
+#include <iterator>
+#include <limits>
+#include <algorithm>
+
+// Double linked list. In the android NS we declare the nodes and
+// iterators. The list declaration in the std NS follows that.
+
+namespace android {
+
+struct ListNodeBase {
+ ListNodeBase *mNext;
+ ListNodeBase *mPrev;
+
+ // Swap 2 nodes.
+ static void swap(ListNodeBase& a, ListNodeBase& b);
+
+ // Insert this node BEFORE pos.
+ void hook(ListNodeBase * const pos);
+
+ // Remove this node and link prev and next together.
+ void unhook();
+};
+
+template <typename _T>
+struct ListNode: public ListNodeBase {
+ _T mData;
+};
+
+// iterators: ListIterator and ListConstIterator are bidirectional ones.
+template<typename _T>
+struct ListIterator
+{
+ typedef ListIterator<_T> iterator_type;
+ typedef android::ListNode<_T> node_type;
+ public:
+ typedef ptrdiff_t difference_type;
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef _T value_type;
+ typedef _T* pointer;
+ typedef _T& reference;
+
+ ListIterator():
+ mNode() { }
+
+ explicit ListIterator(android::ListNodeBase* node):
+ mNode(node) { }
+
+ reference operator*() const { return static_cast<node_type*>(mNode)->mData; }
+ pointer operator->() const { return &operator*(); }
+
+ iterator_type& operator++() { mNode = mNode->mNext; return *this; }
+ iterator_type& operator++(int) {
+ iterator_type tmp = *this;
+ mNode = mNode->mNext;
+ return *tmp;
+ }
+
+ iterator_type& operator--() { mNode = mNode->mPrev; return *this; }
+ iterator_type& operator--(int) {
+ iterator_type tmp = *this;
+ mNode = mNode->mPrev;
+ return *tmp;
+ }
+
+ bool operator==(const iterator_type& o) const { return mNode == o.mNode; }
+ bool operator!=(const iterator_type& o) const { return mNode != o.mNode; }
+
+ ListNodeBase *mNode;
+};
+
+template<typename _T>
+struct ListConstIterator
+{
+ typedef ListConstIterator<_T> iterator_type;
+ typedef android::ListNode<_T> node_type;
+ public:
+ typedef ptrdiff_t difference_type;
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef _T value_type;
+ typedef _T* pointer;
+ typedef _T& reference;
+
+ ListConstIterator():
+ mNode() { }
+
+ explicit ListConstIterator(ListNodeBase* node):
+ mNode(node) { }
+
+ ListConstIterator(const ListIterator<_T>& it): mNode(it.mNode) { }
+
+ reference operator*() const { return static_cast<node_type*>(mNode)->mData; }
+ pointer operator->() const { return &operator*(); }
+
+ iterator_type& operator++() { mNode = mNode->mNext; return *this; }
+ iterator_type& operator++(int) {
+ iterator_type tmp = *this;
+ mNode = mNode->mNext;
+ return *tmp;
+ }
+
+ iterator_type& operator--() { mNode = mNode->mPrev; return *this; }
+ iterator_type& operator--(int) {
+ iterator_type tmp = *this;
+ mNode = mNode->mPrev;
+ return *tmp;
+ }
+
+ bool operator==(const iterator_type& o) const { return mNode == o.mNode; }
+ bool operator!=(const iterator_type& o) const { return mNode != o.mNode; }
+
+ ListNodeBase *mNode;
+};
+
+} // namespace android
+
+namespace std {
+
+// std::list
+
+template<typename _T>
+class list {
+ public:
+ typedef _T value_type;
+ typedef _T* pointer;
+ typedef const _T* const_pointer;
+ typedef _T& reference;
+ typedef const _T& const_reference;
+ typedef android::ListIterator<_T> iterator;
+ typedef android::ListConstIterator<_T> const_iterator;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+
+ // Default constructor, no element.
+ list() { init(); }
+ ~list() { clear(); }
+
+ // Empty the list.
+ void clear();
+
+ // Element access.
+ reference front() { return *begin(); }
+ const_reference front() const { return *begin(); }
+ reference back() { return *(end()--); }
+ const_reference back() const { return *(end()--); }
+
+ // Iterators.
+ iterator begin() { return iterator(mHead.mNext); }
+ const_iterator begin() const { return const_iterator(mHead.mNext); }
+ iterator end() { return iterator(&mHead); }
+ const_iterator end() const { return const_iterator(&mHead); }
+
+ // Add data at the begin of the list.
+ // @param elt To be added.
+ void push_front(const value_type& elt) { insert(begin(), elt); }
+ void push_back(const value_type& elt) { insert(end(), elt); }
+
+ bool empty() const { return mLength == 0; }
+
+ // @eturn the number of elements in the list.
+ size_type size() const { return mLength; }
+
+ // @return the maximum size for a list
+ size_type max_size() const { return numeric_limits<size_type>::max(); }
+
+ // Insert the element BEFORE the 'pos' iterator.
+ // @param pos Iterator in the list.
+ // @param elt Element to be inserted.
+ // @return an iterator that points to the inserted element.
+ iterator insert(iterator pos, const value_type& elt);
+
+ private:
+ void init() {
+ mHead.mNext = &mHead;
+ mHead.mPrev = &mHead;
+ mLength = 0;
+ }
+ size_type mLength;
+ // mHead does not contain any data, it represents end().
+ android::ListNodeBase mHead;
+};
+
+
+template<typename _T>
+void list<_T>::clear() {
+ while (mHead.mNext != &mHead) {
+ // Upcast so delete will reclaim all the memory.
+ android::ListNode<_T> *node =
+ static_cast<android::ListNode<_T> *>(mHead.mNext);
+ mHead.mNext = node->mNext;
+ delete node;
+ }
+ init();
+}
+
+template<typename _T>
+typename list<_T>::iterator list<_T>::insert(iterator pos, const value_type& elt) {
+ if (mLength + 1 > mLength) {
+ android::ListNode<_T> *node = new android::ListNode<_T>();
+ node->mData = elt;
+ node->hook(pos.mNode);
+ ++mLength;
+ return iterator(node);
+ } else {
+ return end();
+ }
+}
+
+} // namespace std
+
+#endif // ANDROID_ASTL_LIST__
diff --git a/src/Android.mk b/src/Android.mk
index 49c6d68..0dcf05d 100644
--- a/src/Android.mk
+++ b/src/Android.mk
@@ -21,6 +21,7 @@
ios_base.cpp \
ios_globals.cpp \
ios_pos_types.cpp \
+ list.cpp \
ostream.cpp \
stdio_filebuf.cpp \
streambuf.cpp \
diff --git a/src/list.cpp b/src/list.cpp
new file mode 100644
index 0000000..90e8e21
--- /dev/null
+++ b/src/list.cpp
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <list>
+
+namespace android {
+
+void ListNodeBase::swap(ListNodeBase& a, ListNodeBase& b) {
+ if (a.mNext != &a) {
+ if (b.mNext != &b) {
+ // a and b are not empty.
+ std::swap(a.mNext, b.mNext);
+ std::swap(a.mPrev, b.mPrev);
+ a.mNext->mPrev = a.mPrev->mNext = &a;
+ b.mNext->mPrev = b.mPrev->mNext = &b;
+ } else {
+ // a not empty but b is.
+ b.mNext = a.mNext;
+ b.mPrev = a.mPrev;
+ b.mNext->mPrev = b.mPrev->mNext = &b;
+ a.mNext = a.mPrev = &a; // empty a
+ }
+ } else if (b.mNext != &b) {
+ // a is empty but b is not.
+ a.mNext = b.mNext;
+ a.mPrev = b.mPrev;
+ a.mNext->mPrev = a.mPrev->mNext = &a;
+ b.mNext = b.mPrev = &b; // empty b
+ }
+}
+
+void ListNodeBase::hook(ListNodeBase *const pos) {
+ mNext = pos;
+ mPrev = pos->mPrev;
+ pos->mPrev->mNext = this;
+ pos->mPrev = this;
+}
+
+void ListNodeBase::unhook() {
+ ListNodeBase *const next = mNext;
+ ListNodeBase *const prev = mPrev;
+ prev->mNext = next;
+ next->mPrev = prev;
+}
+
+} // namespace android
diff --git a/tests/Android.mk b/tests/Android.mk
index 1418c3f..ddf3974 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -70,6 +70,7 @@
test_iostream.cpp \
test_iterator.cpp \
test_limits.cpp \
+ test_list.cpp \
test_memory.cpp \
test_set.cpp \
test_streambuf.cpp \
diff --git a/tests/common.h b/tests/common.h
index d59e3f8..16a1642 100644
--- a/tests/common.h
+++ b/tests/common.h
@@ -92,6 +92,25 @@
size_t CtorDtorCounter::mAssignCount;
size_t CtorDtorCounter::mDtorCount;
+// These class allocate chunks to detect memory leaks.
+template<typename T> struct A {
+ public:
+ A() {mChunk = new T[2046];}
+ A(const A<T>& a) {mChunk = new T[2046];}
+ virtual ~A() {delete [] mChunk;}
+ A& operator=(const A& o) { return *this;}
+ T *mChunk;
+};
+
+struct B {
+ public:
+ B() {mChunk = new char[2046];}
+ B(const B& b) {mChunk = new char[2046];}
+ virtual ~B() {delete [] mChunk;}
+ B& operator=(const B& o) { return *this;}
+ char *mChunk;
+};
+
} // anonymous namespace
diff --git a/tests/test_list.cpp b/tests/test_list.cpp
new file mode 100644
index 0000000..6cb9634
--- /dev/null
+++ b/tests/test_list.cpp
@@ -0,0 +1,127 @@
+/* -*- c++ -*- */
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "../include/list"
+#ifndef ANDROID_ASTL_LIST__
+#error "Wrong header included!!"
+#endif
+#include <string>
+#include "common.h"
+
+namespace android {
+using std::list;
+using std::string;
+
+bool testConstructor()
+{
+ list<int> list1;
+ list<int*> list2;
+ list<string> list3;
+ list<B> list4;
+ return true;
+}
+
+bool testClear()
+{
+ {
+ list<int> l;
+ for (int i = 0; i < 100; ++i) {
+ l.push_front(i);
+ l.push_back(i);
+ }
+ l.clear();
+ EXPECT_TRUE(l.size() == 0);
+ EXPECT_TRUE(l.empty());
+ }
+ {
+ list<B> l;
+ for (int i = 0; i < 10; ++i) {
+ l.push_front(B());
+ l.push_back(B());
+ }
+ l.clear();
+ EXPECT_TRUE(l.size() == 0);
+ EXPECT_TRUE(l.empty());
+ }
+ return true;
+}
+bool testSize()
+{
+ list<int> list;
+
+ EXPECT_TRUE(list.size() == 0);
+ EXPECT_TRUE(list.empty());
+
+ list.push_front(1);
+ EXPECT_TRUE(list.size() == 1);
+ EXPECT_FALSE(list.empty());
+
+ for (int i = 0; i < 10; ++i) {
+ list.push_front(1);
+ list.push_back(1);
+ }
+ EXPECT_TRUE(list.size() == 21);
+ return true;
+}
+
+bool testIterator()
+{
+ list<int> l;
+ for (int i = 0; i < 100; ++i) {
+ l.push_back(i);
+ }
+
+ list<int>::const_iterator it = l.begin();
+ for (int i = 0; it != l.end(); ++it, ++i) {
+ EXPECT_TRUE(*it == i);
+ }
+
+ l.clear();
+ for (int i = 0; i < 100; ++i) {
+ l.push_front(i);
+ }
+
+ it = l.begin();
+ for (int i = 99; it != l.end(); ++it, --i) {
+ EXPECT_TRUE(*it == i);
+ }
+
+ return true;
+}
+
+} // namespace android
+
+int main(int argc, char **argv)
+{
+ FAIL_UNLESS(testConstructor);
+ FAIL_UNLESS(testSize);
+ FAIL_UNLESS(testClear);
+ FAIL_UNLESS(testIterator);
+ return kPassed;
+}
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index 6279e97..8b85b97 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -82,24 +82,6 @@
}
typedef enum { ONE = 10, TWO} TestEnum;
-// These class allocate chunks to detect memory leaks.
-template<typename T> struct A {
- public:
- A() {mChunk = new T[2046];}
- A(const A<T>& a) {mChunk = new T[2046];}
- virtual ~A() {delete [] mChunk;}
- A& operator=(const A& o) { return *this;}
- T *mChunk;
-};
-
-struct B {
- public:
- B() {mChunk = new char[2046];}
- B(const B& b) {mChunk = new char[2046];}
- virtual ~B() {delete [] mChunk;}
- B& operator=(const B& o) { return *this;}
- char *mChunk;
-};
bool testConstructorClass()
{
