Basic implementation of the std::list.

Moved the class used in vector test to common.h to track memory leaks.

7 files changed, 462 insertions, 18 deletions

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 @@ astl_common_src_files := \
     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 @@ sources := \
    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::mCopyCtorCount;
 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 @@ bool testConstructorString()
 }
 
 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()
 {