From 8b5f35d0aa39e39119dc1e3e2fc4d283995faa2a Mon Sep 17 00:00:00 2001 From: Nicolas Catania Date: Fri, 12 Jun 2009 10:41:09 -0700 Subject: Revert "Basic implementation of vector." This reverts commit fd56a38d5dcb569b146634bb22c5d9cb1e138e3f. --- include/vector | 320 --------------------------------------------------------- 1 file changed, 320 deletions(-) delete mode 100644 include/vector (limited to 'include/vector') diff --git a/include/vector b/include/vector deleted file mode 100644 index 1e65d54..0000000 --- a/include/vector +++ /dev/null @@ -1,320 +0,0 @@ -/* -*- 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 -#include -#include -#include -#include -#include - -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 -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(-1) / 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 kDefaultCapacity = 4; - 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 -vector<_T>::vector() - :mBegin(NULL), mCapacity(0), mLength(0) { } - -template -vector<_T>::vector(const size_type num, const value_type& init_value) -{ - if (num < max_size()) - { - mBegin = static_cast(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 -bool vector<_T>::reserve(size_type new_size) -{ - if (new_size == 0) - { - new_size = mLength ? mLength : kDefaultCapacity; - } - else if (new_size < mLength || new_size > max_size()) - { - return false; - } - - if (is_pod::value) - { - pointer oldBegin = mBegin; - mBegin = static_cast(realloc(mBegin, new_size * sizeof(value_type))); - if (!mBegin) - { - mBegin = oldBegin; - return false; - } - } - else - { - pointer newBegin = static_cast(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 -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 -void vector<_T>::pop_back() -{ - if (mLength > 0) - { - --mLength; - } -} - -template -void vector<_T>::clear() -{ - if(mBegin) - { - if (is_pod::value) - { - free(mBegin); - } - else - { - deallocate(); - } - } - mBegin = NULL; - mCapacity = 0; - mLength = 0; -} - -template -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 vector<_T>::size_type vector<_T>::grow() const -{ - if (mCapacity < kDefaultCapacity) - { - return kDefaultCapacity; - } - - size_type new_capacity; - if (mCapacity > kExponentialLimit) - { - new_capacity = mCapacity + kLinearIncrement; - } - else - { - new_capacity = mCapacity * kExponentialFactor; - } - if (mCapacity > new_capacity) - { // overflow - return 0; // overflow - } - else if (new_capacity > max_size()) - { // 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 -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__ -- cgit v1.2.3