memory revision fe47cee745a2b91cd9a2b98f7a82c9ad9fec726f 
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
44namespace 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.
57template<bool, typename _InputIteratorTag, typename _ForwardIteratorTag>
58struct __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.
75template<>
76struct __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
109template<> 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
125template<typename _InputIterator, typename _ForwardIterator>
126inline _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
149template<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
161template<> 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.
173template<typename _ForwardIterator, typename _T>
174inline 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