/* -*- c++ -*- */
/*
 * Copyright (C) 2009 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_MEMORY__
#define ANDROID_ASTL_MEMORY__

#include "type_traits.h"
#include <new>  // for placement new
#include <cstring>
#include <algorithm>

#if defined(_InputIterator) || defined(_ForwardIterator)
#error "_InputIterator or _ForwardIterator are already defined."
#endif

namespace std {

// uninitialized_copy is used when memory allocation and object
// 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
// degrades to a memmove call.

template<bool> 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);
        }
        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)
{
    const bool both_pod =
            is_pod<_InputIterator>::value && is_pod<_ForwardIterator>::value;
    return __uninitialized_copy<both_pod>::uninitialized_copy(begin, end, dest);
}

// 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,
// using the object's class copy constructor.

template<bool> struct __uninitialized_fill
{
    template<typename _ForwardIterator, typename _T>
    static void uninitialized_fill(_ForwardIterator *begin,
                                   _ForwardIterator *end,
                                   const _T& val)
    {
        for (; begin < end; ++begin)
            new (static_cast<void*>(begin)) _ForwardIterator(val);
    }
};

template<> struct __uninitialized_fill<true>
{
    template<typename _ForwardIterator, typename _T>
    static void uninitialized_fill(_ForwardIterator *begin,
                                   _ForwardIterator *end,
                                   const _T& val)
    {
        std::fill(begin, end, val);
    }
};

// The real STL takes iterators, we take pointers for now.
template<typename _ForwardIterator, typename _T>
inline void uninitialized_fill(_ForwardIterator *begin,
                               _ForwardIterator *end,
                               const _T& val)
{
    const bool pod = is_pod<_ForwardIterator>::value;
    return __uninitialized_fill<pod>::uninitialized_fill(begin, end, val);
}

}  // namespace std

#endif  // ANDROID_ASTL_MEMORY__