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.
diff --git a/include/limits b/include/limits
index f097c23..6f6d9f3 100644
--- a/include/limits
+++ b/include/limits
@@ -134,6 +134,38 @@
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 @@
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 @@
// 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;
- }
-};
-
-template<> struct __uninitialized_copy<true>
-{
- template<typename _InputIterator, typename _ForwardIterator>
- static _ForwardIterator *uninitialized_copy(const _InputIterator *begin,
- const _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);
+ 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;
}
};
-// 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)
+// 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(_InputIterator begin,
+ _InputIterator end,
+ _ForwardIterator dest)
+ {
+ 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;
+ }
+};
+
+
+template<typename _InputIterator, typename _ForwardIterator>
+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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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);
