1 /* -*- c++ -*- */ 2 /* 3 * Copyright (C) 2009 The Android Open Source Project 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 #ifndef ANDROID_ASTL_MEMORY__ 31 #define ANDROID_ASTL_MEMORY__ 32 33 #include "type_traits.h" 34 #include <new> // for placement new 35 #include <cstring> 36 #include <algorithm> 37 #include <iterator> 38 #include <limits> 39 40 #if defined(_InputIterator) || defined(_ForwardIterator) 41 #error "_InputIterator or _ForwardIterator are already defined." 42 #endif 43 44 namespace std { 45 46 // uninitialized_copy is used when memory allocation and object 47 // construction need to happen in separate steps. For each instance in 48 // the input range a copy is created and placed in the corresponding 49 // memory pointed by dest. 50 // If the input range is made of pod instances AND both input and 51 // destination iterators are random access ones, uninitialized_copy 52 // degrades to a memmove call. 53 // Returns an iterator pass the end of the destination range. 54 55 // Default implementation used when iterators are not random access 56 // and the value type are not both POD. 57 template<bool, typename _InputIteratorTag, typename _ForwardIteratorTag> 58 struct __uninitialized_copy 59 { 60 template<typename _InputIterator, typename _ForwardIterator> 61 static _ForwardIterator uninitialized_copy(_InputIterator begin, 62 _InputIterator end, 63 _ForwardIterator dest) { 64 typedef typename iterator_traits<_ForwardIterator>:: 65 value_type value_type; 66 for (; begin != end; ++begin, ++dest) { 67 new (static_cast<void*>(&*dest)) value_type(*begin); 68 } 69 return dest; 70 } 71 }; 72 73 // Full specialization when the src and dest types are pod && both 74 // iterators are random access. 75 template<> 76 struct __uninitialized_copy<true, 77 random_access_iterator_tag, 78 random_access_iterator_tag> 79 { 80 template<typename _InputIterator, typename _ForwardIterator> 81 static _ForwardIterator uninitialized_copy(_InputIterator begin, 82 _InputIterator end, 83 _ForwardIterator dest) 84 { 85 typedef typename iterator_traits<_InputIterator>:: 86 difference_type difference_type; 87 const difference_type len = std::distance(begin, end); 88 const difference_type kMaxSize = 89 std::numeric_limits<difference_type>::max(); 90 91 typedef typename iterator_traits<_ForwardIterator>:: 92 value_type value_type; 93 const size_t kSize = sizeof(value_type); 94 95 if (len > 0 && 96 static_cast<size_t>(kMaxSize) / kSize > static_cast<size_t>(len)) { 97 std::memmove(static_cast<void*>(&*dest), 98 static_cast<const void*>(&*begin), kSize * len); 99 return dest + len; 100 } else { 101 return dest; 102 } 103 } 104 }; 105 106 // TODO: If placement new degrades to assignement for POD, we can get 107 // rid of this one. 108 // Bothe pod but not both random access 109 template<> struct __uninitialized_copy<true, 110 input_iterator_tag, 111 forward_iterator_tag> 112 { 113 template<typename _InputIterator, typename _ForwardIterator> 114 static _ForwardIterator uninitialized_copy(_InputIterator begin, 115 _InputIterator end, 116 _ForwardIterator dest) { 117 for (; begin != end; ++begin, ++dest) { 118 *dest = *begin; 119 } 120 return dest; 121 } 122 }; 123 124 125 template<typename _InputIterator, typename _ForwardIterator> 126 inline _ForwardIterator uninitialized_copy(_InputIterator begin, 127 _InputIterator end, 128 _ForwardIterator dest) 129 { 130 typedef typename iterator_traits<_InputIterator>::value_type _ValueType1; 131 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; 132 133 const bool both_pod = 134 is_pod<_ValueType1>::value && is_pod<_ValueType2>::value; 135 136 return __uninitialized_copy<both_pod, 137 typename iterator_traits<_InputIterator>::iterator_category, 138 typename iterator_traits<_ForwardIterator>::iterator_category>:: 139 uninitialized_copy(begin, end, dest); 140 } 141 142 // TODO: replace pointers with iterator below. 143 144 // uninitialized_fill is used when memory allocation and object 145 // construction need to happen in separate steps. uninitialized_fill 146 // creates a copy of 'obj' in the location pointed by the interator, 147 // using the object's class copy constructor. 148 149 template<bool> struct __uninitialized_fill 150 { 151 template<typename _ForwardIterator, typename _T> 152 static void uninitialized_fill(_ForwardIterator *begin, 153 _ForwardIterator *end, 154 const _T& val) 155 { 156 for (; begin < end; ++begin) 157 new (static_cast<void*>(&*begin)) _ForwardIterator(val); 158 } 159 }; 160 161 template<> struct __uninitialized_fill<true> 162 { 163 template<typename _ForwardIterator, typename _T> 164 static void uninitialized_fill(_ForwardIterator *begin, 165 _ForwardIterator *end, 166 const _T& val) 167 { 168 std::fill(begin, end, val); 169 } 170 }; 171 172 // The real STL takes iterators, we take pointers for now. 173 template<typename _ForwardIterator, typename _T> 174 inline void uninitialized_fill(_ForwardIterator *begin, 175 _ForwardIterator *end, 176 const _T& val) 177 { 178 const bool pod = is_pod<_ForwardIterator>::value; 179 return __uninitialized_fill<pod>::uninitialized_fill(begin, end, val); 180 } 181 182 } // namespace std 183 184 #endif // ANDROID_ASTL_MEMORY__ 185
