include/vector

/* -*- 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_VECTOR__
#define ANDROID_ASTL_VECTOR__

#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <memory>
#include <type_traits.h>

namespace std {

#ifdef _T
#error "_T is a macro."
#endif

// Simple vector implementation. Its purpose is to be able to compile code that
// uses the STL and requires std::vector.
//
// IMPORTANT:
// . This class it is not fully STL compliant. Some constructors/methods maybe
// missing, they will be added on demand.
// . A standard container which offers fixed time access to individual
// elements in any order.
//
// TODO: Use the stack for the default constructor. When the capacity
// grows beyond that move the data to the heap.

template<typename _T>
class vector
{
  public:
    typedef _T         value_type;
    typedef _T*        pointer;
    typedef const _T*  const_pointer;
    typedef _T&        reference;
    typedef const _T&  const_reference;

    typedef pointer iterator;
    typedef const_pointer const_iterator;

    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;

    vector();

    // Create a vector with bitwise copies of an exemplar element.
    // @param num The number of elements to create.
    // @param init_value The element to copy.
    explicit vector(const size_type num, const value_type& init_value = value_type());

    ~vector() { clear(); }

    // @return true if the vector is empty, false otherwise.
    bool empty() const { return mLength == 0; }
    size_type size() const { return mLength; }

    // @return the maximum size for a vector.
    size_type max_size() const { return (~size_type(0)) / sizeof(value_type); }

    // Change the capacity to new_size. 0 means shrink to fit.
    // @param new_size number of element to be allocated.
    // @return true if successful. The STL version returns nothing.
    bool reserve(size_type new_size = 0);

    // @return The total number of elements that the vector can hold
    // before more memory gets allocated.
    size_type capacity() const { return mCapacity; }

    reference front() { return *mBegin; }
    const_reference front() const { return *mBegin; }

    reference back() { return mLength ? *(mBegin + mLength - 1) : front(); }
    const_reference back() const { return mLength ? *(mBegin + mLength - 1) : front(); }

    // Subscript access to the vector's elements. Don't do boundary
    // check. Use at() for checked access.
    // @param index Of the element (0-based).
    // @return A const reference to the element.
    const_reference operator[](size_type index) const { return *(mBegin + index); }

    // @param index Of the element (0-based).
    // @return A reference to the element.
    reference operator[](size_type index) { return *(mBegin + index); }

    // We don't have iterator, use pointers for now.  begin and end
    // return NULL if the vector has been cleared or not initialized.
    iterator begin() { return mBegin; }
    iterator end() { return mBegin + mLength; }

    const_iterator begin() const { return mBegin; }
    const_iterator end() const { return mBegin + mLength; }

    // Add data at the end of the vector. Constant in time if the
    // memory has been preallocated (e.g using reserve).
    // @param elt To be added.
    void push_back(const value_type& elt);

    // Remove the last element. However, no memory is reclaimed from
    // the internal buffer: you need to call reserve() to recover it.
    void pop_back();

    // Empty the vector on return. Release the internal buffer. Length
    // and capacity are both 0 on return. If you want to keep the
    // internal buffer around for reuse, call 'resize'/'erase' instead.
    void clear();

    void swap(vector& other);
  private:
    // @return New internal buffer size when it is adjusted automatically.
    size_type grow() const;

    // Calls the class' deallocator explicitely on each instance in
    // the vector.
    void deallocate();

    pointer mBegin;
    size_type mCapacity;
    size_type mLength;
    static const size_type kExponentialFactor = 2;
    static const size_type kExponentialLimit = 256;
    static const size_type kLinearIncrement = 256;
};


// The implementation uses malloc instead of new because Posix states that:
// The pointer returned if the allocation succeeds shall be suitably
// aligned so that it may be assigned to a pointer to any type of
// object and then used to access such an object in the space
// allocated
// So as long as we malloc() more than 4 bytes, the returned block
// must be able to contain a pointer, and thus will be 32-bit
// aligned. I believe the bionic implementation uses a minimum of 8 or 16.
//
// Invariant: mLength <= mCapacity <= max_size()

template<typename _T>
vector<_T>::vector()
        :mBegin(NULL), mCapacity(0), mLength(0) { }

template<typename _T>
vector<_T>::vector(const size_type num, const value_type& init_value)
{
    if (num < max_size())
    {
        mBegin = static_cast<pointer>(malloc(num * sizeof(value_type)));
        if (mBegin)
        {
            mLength = mCapacity =  num;
            std::uninitialized_fill(mBegin, mBegin + mLength, init_value);
            return;
        }
    }
    mBegin = NULL;
    mLength = mCapacity =  0;
}

template<typename _T>
bool vector<_T>::reserve(size_type new_size)
{
    if (0 == new_size)
    {
        if (0 == mLength)  // Free whatever has been reserved.
        {
            clear();
            return true;
        }
        new_size = mLength;  // Shrink to fit.
    }
    else if (new_size < mLength || new_size > max_size())
    {
        return false;
    }

    if (is_pod<value_type>::value)
    {
        pointer oldBegin = mBegin;
        mBegin = static_cast<pointer>(realloc(mBegin, new_size * sizeof(value_type)));
        if (!mBegin)
        {
            mBegin = oldBegin;
            return false;
        }
    }
    else
    {
        pointer newBegin =  static_cast<pointer>(malloc(new_size * sizeof(value_type)));
        if (!newBegin) return false;

        std::uninitialized_copy(mBegin, mBegin + mLength, newBegin);
        if (mBegin) deallocate();
        mBegin = newBegin;
    }
    mCapacity = new_size;
    return true;
}

template<typename _T>
void vector<_T>::push_back(const value_type& elt)
{
    if (max_size() == mLength) return;
    if (mCapacity == mLength)
    {
        const size_type new_capacity = grow();
        if (0 == new_capacity || !reserve(new_capacity)) return;
    }
    // mLength < mCapacity
    *(mBegin + mLength) = elt;
    ++mLength;
}

template<typename _T>
void vector<_T>::pop_back()
{
    if (mLength > 0)
    {
        --mLength;
        if (!is_pod<value_type>::value)
        {
            (mBegin + mLength)->~_T();
        }
    }
}

template<typename _T>
void vector<_T>::clear()
{
    if(mBegin)
    {
        if (is_pod<value_type>::value)
        {
            free(mBegin);
        }
        else
        {
            deallocate();
        }
    }
    mBegin = NULL;
    mCapacity = 0;
    mLength = 0;
}

template<typename _T>
void vector<_T>::swap(vector& other)
{
    std::swap(mBegin, other.mBegin);
    std::swap(mCapacity, other.mCapacity);
    std::swap(mLength, other.mLength);
}

// Grow the capacity. Use exponential until kExponentialLimit then
// linear until it reaches max_size().
template<typename _T>
typename vector<_T>::size_type vector<_T>::grow() const
{
    size_type new_capacity;
    if (mCapacity > kExponentialLimit)
    {
        new_capacity = mCapacity + kLinearIncrement;
    }
    else
    {
        new_capacity = mCapacity == 0 ? kExponentialFactor : mCapacity * kExponentialFactor;
    }
    if (mCapacity > new_capacity || new_capacity > max_size())
    { // Overflow: cap at max_size() if not there already.
        new_capacity = mCapacity == max_size() ? 0 : max_size();
    }
    return  new_capacity;
}


// mBegin should not be NULL.
template<typename _T>
void vector<_T>::deallocate()
{
    pointer begin = mBegin;
    pointer end = mBegin + mLength;

    for (; begin != end; ++begin)
    {
        begin->~_T();
    }
    free(mBegin);
}

}  // namespace std

#endif  // ANDROID_ASTL_VECTOR__