Use iterators in unitialized_copy.

Previously, unitialized_copy assumed the args were pointers.
Replace the const * with iterators.

Fixed a bug, uninitialized_copy must return an iterator pass
the last element inserted in dest. Previously we were returning
the start of dest.

Fixed a bug, we can use memmove only when the types pointed are POD
but also when both source AND dest iterators are random access ones
(i.e both source and dest use a contiguous array to store the values)
The prev code would call memmove if the input was a vector<int> and
output a linked list<int> which is wrong since the list element are
stored in nodes, non contiguous area.

Added a specialization when the 2 types are pod but the iterator
are not random access ones (think linked list of ints). I was not
sure if placement new degrades to assignement in that case so I
provided a specialization that explicitly uses '='.

In limits,
added support for int and unsigned int.
replaced C style casts with static_cast.

6 files changed, 238 insertions, 52 deletions

diff --git a/include/limits b/include/limits
index f097c23..6f6d9f3 100644
--- a/include/limits
+++ b/include/limits
@@ -134,6 +134,38 @@ struct numeric_limits<double>
     static const int digits10 = __DBL_DIG__;
 };
 
+// numeric_limits<int>
+template<>
+struct numeric_limits<int>
+{
+    static const bool is_specialized = true;
+
+    static int min() { return INT_MIN; }
+    static int max() { return INT_MAX; }
+
+    static const bool is_signed = true;
+    static const bool is_integer = true;
+
+    static const int digits = static_cast<int>(sizeof(int) * CHAR_BIT);
+    static const int digits10 = digits10<int, digits, is_signed>::value;
+};
+
+// numeric_limits<unsigned int>
+template<>
+struct numeric_limits<unsigned int>
+{
+    static const bool is_specialized = true;
+
+    static unsigned int min() { return 0; }
+    static unsigned int max() { return UINT_MAX; }
+
+    static const bool is_signed = false;
+    static const bool is_integer = true;
+
+    static const int digits = static_cast<int>(sizeof(unsigned int) * CHAR_BIT);
+    static const int digits10 = digits10<int, digits, is_signed>::value;
+};
+
 // numeric_limits<long>
 template<>
 struct numeric_limits<long>
@@ -162,7 +194,7 @@ struct numeric_limits<long long>
     static const bool is_signed = true;
     static const bool is_integer = true;
 
-    static const int digits = ((int)(sizeof(long long) * CHAR_BIT));
+    static const int digits = static_cast<int>(sizeof(long long) * CHAR_BIT);
     static const int digits10 = digits10<int, digits, is_signed>::value;
 };
 
diff --git a/include/memory b/include/memory
index d83851f..d73606f 100644
--- a/include/memory
+++ b/include/memory
@@ -34,6 +34,8 @@
 #include <new>  // for placement new
 #include <cstring>
 #include <algorithm>
+#include <iterator>
+#include <limits>
 
 #if defined(_InputIterator) || defined(_ForwardIterator)
 #error "_InputIterator or _ForwardIterator are already defined."
@@ -45,54 +47,100 @@ namespace std {
 // construction need to happen in separate steps. For each instance in
 // the input range a copy is created and placed in the corresponding
 // memory pointed by dest.
-// If the input range is made of pod instances, uninitialized_copy
+// If the input range is made of pod instances AND both input and
+// destination iterators are random access ones, uninitialized_copy
 // degrades to a memmove call.
+// Returns an iterator pass the end of the destination range.
 
-template<bool> struct __uninitialized_copy
+// Default implementation used when iterators are not random access
+// and the value type are not both POD.
+template<bool, typename _InputIteratorTag, typename _ForwardIteratorTag>
+struct __uninitialized_copy
 {
     template<typename _InputIterator, typename _ForwardIterator>
-    static _ForwardIterator *uninitialized_copy(const _InputIterator *begin,
-                                                const _InputIterator *end,
-                                                _ForwardIterator *dest)
-    {
-        _ForwardIterator *result = dest;
-        for (; begin < end; ++begin, ++dest)
-            new (static_cast<void*>(dest)) _ForwardIterator(*begin);
-        return result;
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest) {
+        typedef typename iterator_traits<_ForwardIterator>::
+                value_type value_type;
+        for (; begin != end; ++begin, ++dest) {
+            new (static_cast<void*>(&*dest)) value_type(*begin);
+        }
+        return dest;
     }
 };
 
-template<> struct __uninitialized_copy<true>
+// Full specialization when the src and dest types are pod && both
+// iterators are random access.
+template<>
+struct __uninitialized_copy<true,
+                            random_access_iterator_tag,
+                            random_access_iterator_tag>
 {
     template<typename _InputIterator, typename _ForwardIterator>
-    static _ForwardIterator *uninitialized_copy(const _InputIterator *begin,
-                                                const _InputIterator *end,
-                                                _ForwardIterator *dest)
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest)
     {
-        const ptrdiff_t len = end - begin;
-        const size_t kMaxSizeT = ~((size_t)0);
-        const size_t kSize = sizeof(_InputIterator);
-
-        if (len > 0 && kMaxSizeT / kSize > static_cast<size_t>(len))
-        {
-            std::memmove(static_cast<void*>(dest),
-                         static_cast<const void*>(begin), kSize * len);
+        typedef typename iterator_traits<_InputIterator>::
+                difference_type difference_type;
+        const difference_type len = std::distance(begin, end);
+        const difference_type kMaxSize =
+                std::numeric_limits<difference_type>::max();
+
+        typedef typename iterator_traits<_ForwardIterator>::
+                value_type value_type;
+        const size_t kSize = sizeof(value_type);
+
+        if (len > 0 &&
+            static_cast<size_t>(kMaxSize) / kSize > static_cast<size_t>(len)) {
+            std::memmove(static_cast<void*>(&*dest),
+                         static_cast<const void*>(&*begin), kSize * len);
+            return dest + len;
+        } else {
+            return dest;
+        }
+    }
+};
+
+// TODO: If placement new degrades to assignement for POD, we can get
+// rid of this one.
+// Bothe pod but not both random access
+template<> struct __uninitialized_copy<true,
+                                       input_iterator_tag,
+                                       forward_iterator_tag>
+{
+    template<typename _InputIterator, typename _ForwardIterator>
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest) {
+        for (; begin != end; ++begin, ++dest) {
+            *dest = *begin;
         }
         return dest;
     }
 };
 
-// The real STL takes iterators, we take pointers for now.
+
 template<typename _InputIterator, typename _ForwardIterator>
-inline _ForwardIterator* uninitialized_copy(const _InputIterator *begin,
-                                            const _InputIterator *end,
-                                            _ForwardIterator *dest)
+inline _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                           _InputIterator end,
+                                           _ForwardIterator dest)
 {
+    typedef typename iterator_traits<_InputIterator>::value_type _ValueType1;
+    typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2;
+
     const bool both_pod =
-            is_pod<_InputIterator>::value && is_pod<_ForwardIterator>::value;
-    return __uninitialized_copy<both_pod>::uninitialized_copy(begin, end, dest);
+            is_pod<_ValueType1>::value && is_pod<_ValueType2>::value;
+
+    return __uninitialized_copy<both_pod,
+            typename iterator_traits<_InputIterator>::iterator_category,
+            typename iterator_traits<_ForwardIterator>::iterator_category>::
+            uninitialized_copy(begin, end, dest);
 }
 
+// TODO: replace pointers with iterator below.
+
 // uninitialized_fill is used when memory allocation and object
 // construction need to happen in separate steps. uninitialized_fill
 // creates a copy of 'obj' in the location pointed by the interator,
diff --git a/tests/Android.mk b/tests/Android.mk
index 3d90faa..e27bafa 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -61,17 +61,18 @@ define host-test
 endef
 
 sources := \
-    test_algorithm.cpp \
-    test_functional.cpp \
-    test_ios_base.cpp \
-    test_ios_pos_types.cpp \
-    test_iterator.cpp \
-    test_limits.cpp \
-    test_set.cpp \
-    test_string.cpp \
-    test_type_traits.cpp \
-    test_uninitialized.cpp \
-    test_vector.cpp
+   test_algorithm.cpp \
+   test_functional.cpp \
+   test_ios_base.cpp \
+   test_ios_pos_types.cpp \
+   test_iterator.cpp \
+   test_limits.cpp \
+   test_memory.cpp \
+   test_set.cpp \
+   test_string.cpp \
+   test_type_traits.cpp \
+   test_uninitialized.cpp \
+   test_vector.cpp
 
 # Disable all optimization for the host target to help test tools (valgrind...)
 EXTRA_CFLAGS := -I bionic/libstdc++/include -I external/astl/include -g -O0
diff --git a/tests/common.h b/tests/common.h
index 514783c..d59e3f8 100644
--- a/tests/common.h
+++ b/tests/common.h
@@ -79,6 +79,10 @@ class CtorDtorCounter {
     CtorDtorCounter& operator=(const CtorDtorCounter& nc) {++mAssignCount; return *this;}
     ~CtorDtorCounter() {++mDtorCount;}
     static void reset() {mCtorCount = 0; mCopyCtorCount = 0; mAssignCount = 0; mDtorCount = 0;}
+    static void printf() {
+        std::fprintf(stderr, "CtorDtorCounter: %d %d %d %d\n",
+                     mCtorCount, mCopyCtorCount, mAssignCount, mDtorCount);
+    }
   private:
 };
 
diff --git a/tests/test_memory.cpp b/tests/test_memory.cpp
new file mode 100644
index 0000000..cfadf21
--- /dev/null
+++ b/tests/test_memory.cpp
@@ -0,0 +1,82 @@
+/*
+ * 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/memory"
+#ifndef ANDROID_ASTL_MEMORY__
+#error "Wrong header included!!"
+#endif
+#include "common.h"
+#include <iterator>
+
+namespace android {
+
+bool testUnitializedCopyPODRandomIterators() {
+    const char *const kSrc = "a string";
+    const char *begin = kSrc;
+    const int kLen = strlen(kSrc);
+    const char *end = begin + kLen;
+    char dest[kLen];
+    char *const kDest = dest;
+    char *res;
+
+    res = std::uninitialized_copy(begin, end, dest);
+    EXPECT_TRUE(res == kDest + kLen);
+
+    for (int i = 0; i < kLen; ++i) {
+        EXPECT_TRUE(kDest[i] == kSrc[i]);
+    }
+    return true;
+}
+
+bool testUnitializedCopyClassRandomIterators() {
+    const int kLen = 10;
+    const CtorDtorCounter kSrc[10];
+    const CtorDtorCounter *begin = kSrc;
+    const CtorDtorCounter *end = begin + kLen;
+    CtorDtorCounter *dest = new CtorDtorCounter[kLen];
+    CtorDtorCounter *const kDest = dest;
+    CtorDtorCounter *res;
+
+    CtorDtorCounter::reset();
+    res = std::uninitialized_copy(begin, end, dest);
+    EXPECT_TRUE(res == kDest + kLen);
+    EXPECT_TRUE(kLen == CtorDtorCounter::mCopyCtorCount);
+    EXPECT_TRUE(0 == CtorDtorCounter::mCtorCount);
+
+    delete [] dest;
+    return true;
+}
+
+}  // namespace android
+
+int main(int argc, char **argv)
+{
+    FAIL_UNLESS(testUnitializedCopyPODRandomIterators);
+    FAIL_UNLESS(testUnitializedCopyClassRandomIterators);
+    return kPassed;
+}
diff --git a/tests/test_uninitialized.cpp b/tests/test_uninitialized.cpp
index 808e836..8a88787 100644
--- a/tests/test_uninitialized.cpp
+++ b/tests/test_uninitialized.cpp
@@ -42,13 +42,21 @@ using std::uninitialized_fill;
 
 bool testCopyPod()
 {
-    int src[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
-    const int size = ARRAYSIZE(src);
-    int dest[size] = {0, };
+    {
+        int src[0];
+        const int size = ARRAYSIZE(src);
+        int dest[10] = {0, };
+        EXPECT_TRUE(uninitialized_copy(src, src + size, dest) == dest);
+    }
+    {
+        int src[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+        const int size = ARRAYSIZE(src);
+        int dest[size] = {0, };
 
-    EXPECT_TRUE(uninitialized_copy(src, src + size, dest) == dest);
+        EXPECT_TRUE(uninitialized_copy(src, src + size, dest) == dest + size);
 
-    EXPECT_TRUE(std::equal(src, src + size, dest));
+        EXPECT_TRUE(std::equal(src, src + size, dest));
+    }
     return true;
 }
 
@@ -58,7 +66,9 @@ bool testCopyPodOverflow()
     int src, dest;
 
     // Should not crash
-    EXPECT_TRUE(uninitialized_copy(&src, &src + kMaxSizeT / sizeof(src) + 1, &dest) == &dest);
+    EXPECT_TRUE(
+        uninitialized_copy(&src, &src + kMaxSizeT / sizeof(src) + 1, &dest) ==
+        &dest);
     return true;
 }
 
@@ -68,7 +78,8 @@ bool testCopyClass()
     CtorDtorCounter::reset();
 
     CtorDtorCounter src[kSize];
-    CtorDtorCounter *dest = static_cast<CtorDtorCounter*>(malloc(kSize * sizeof(CtorDtorCounter)));
+    CtorDtorCounter *dest = static_cast<CtorDtorCounter*>(
+        malloc(kSize * sizeof(CtorDtorCounter)));
 
     EXPECT_TRUE(CtorDtorCounter::mCtorCount == kSize);
     EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 0);
@@ -76,7 +87,7 @@ bool testCopyClass()
 
     CtorDtorCounter::reset();
 
-    EXPECT_TRUE(uninitialized_copy(src, src + kSize, dest) == dest);
+    EXPECT_TRUE(uninitialized_copy(src, src + kSize, dest) == dest + kSize);
 
     EXPECT_TRUE(CtorDtorCounter::mCtorCount == 0);
     EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == kSize);
@@ -89,24 +100,31 @@ struct A {};
 bool testCopyArray()
 {
     {
+        A src[0];
+        A one;
+        A *dest = &one;
+        // Empty, dest should not have moved.
+        EXPECT_TRUE(uninitialized_copy(src, src, dest) == dest);
+    }
+    {
         const A src[] = {A()};
         A one;
         A *dest = &one;
 
-        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest);
+        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest + 1);
     }
     {
         A src[] = {A()};
         A one;
         A *dest = &one;
 
-        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest);
+        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest + 1);
     }
     {
         const A src[] = {A()};
         A dest[1];
 
-        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest);
+        EXPECT_TRUE(uninitialized_copy(src, src + 1, dest) == dest + 1);
     }
     return true;
 }
@@ -141,7 +159,8 @@ bool testFillClass()
     CtorDtorCounter::reset();
 
     CtorDtorCounter src;
-    CtorDtorCounter *dest = static_cast<CtorDtorCounter*>(malloc(kSize * sizeof(CtorDtorCounter)));
+    CtorDtorCounter *dest = static_cast<CtorDtorCounter*>(
+        malloc(kSize * sizeof(CtorDtorCounter)));
 
     EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);
     EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 0);