vector revision 2a4077a9186d6f6dff104bbd1a73484aae6d5c01
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_VECTOR__ 31#define ANDROID_ASTL_VECTOR__ 32 33#include <cstddef> 34#include <cstdlib> 35#include <cstring> 36#include <algorithm> 37#include <memory> 38#include <type_traits.h> 39 40namespace std { 41 42#ifdef _T 43#error "_T is a macro." 44#endif 45 46// Simple vector implementation. Its purpose is to be able to compile code that 47// uses the STL and requires std::vector. 48// 49// IMPORTANT: 50// . This class it is not fully STL compliant. Some constructors/methods maybe 51// missing, they will be added on demand. 52// . A standard container which offers fixed time access to individual 53// elements in any order. 54// 55// TODO: Use the stack for the default constructor. When the capacity 56// grows beyond that move the data to the heap. 57 58template<typename _T> 59class vector 60{ 61 public: 62 typedef _T value_type; 63 typedef _T* pointer; 64 typedef const _T* const_pointer; 65 typedef _T& reference; 66 typedef const _T& const_reference; 67 68 typedef pointer iterator; 69 typedef const_pointer const_iterator; 70 71 typedef size_t size_type; 72 typedef ptrdiff_t difference_type; 73 74 vector(); 75 76 // Create a vector with bitwise copies of an exemplar element. 77 // @param num The number of elements to create. 78 // @param init_value The element to copy. 79 explicit vector(const size_type num, const value_type& init_value = value_type()); 80 81 ~vector() { clear(); } 82 83 // @return true if the vector is empty, false otherwise. 84 bool empty() const { return mLength == 0; } 85 size_type size() const { return mLength; } 86 87 // @return the maximum size for a vector. 88 size_type max_size() const { return (~size_type(0)) / sizeof(value_type); } 89 90 // Change the capacity to new_size. 0 means shrink to fit. 91 // @param new_size number of element to be allocated. 92 // @return true if successful. The STL version returns nothing. 93 bool reserve(size_type new_size = 0); 94 95 // @return The total number of elements that the vector can hold 96 // before more memory gets allocated. 97 size_type capacity() const { return mCapacity; } 98 99 reference front() { return *mBegin; } 100 const_reference front() const { return *mBegin; } 101 102 reference back() { return mLength ? *(mBegin + mLength - 1) : front(); } 103 const_reference back() const { return mLength ? *(mBegin + mLength - 1) : front(); } 104 105 // Subscript access to the vector's elements. Don't do boundary 106 // check. Use at() for checked access. 107 // @param index Of the element (0-based). 108 // @return A const reference to the element. 109 const_reference operator[](size_type index) const { return *(mBegin + index); } 110 111 // @param index Of the element (0-based). 112 // @return A reference to the element. 113 reference operator[](size_type index) { return *(mBegin + index); } 114 115 // We don't have iterator, use pointers for now. begin and end 116 // return NULL if the vector has been cleared or not initialized. 117 iterator begin() { return mBegin; } 118 iterator end() { return mBegin + mLength; } 119 120 const_iterator begin() const { return mBegin; } 121 const_iterator end() const { return mBegin + mLength; } 122 123 // Add data at the end of the vector. Constant in time if the 124 // memory has been preallocated (e.g using reserve). 125 // @param elt To be added. 126 void push_back(const value_type& elt); 127 128 // Remove the last element. However, no memory is reclaimed from 129 // the internal buffer: you need to call reserve() to recover it. 130 void pop_back(); 131 132 // Empty the vector on return. Release the internal buffer. Length 133 // and capacity are both 0 on return. If you want to keep the 134 // internal buffer around for reuse, call 'resize'/'erase' instead. 135 void clear(); 136 137 void swap(vector& other); 138 private: 139 // @return New internal buffer size when it is adjusted automatically. 140 size_type grow() const; 141 142 // Calls the class' deallocator explicitely on each instance in 143 // the vector. 144 void deallocate(); 145 146 pointer mBegin; 147 size_type mCapacity; 148 size_type mLength; 149 static const size_type kExponentialFactor = 2; 150 static const size_type kExponentialLimit = 256; 151 static const size_type kLinearIncrement = 256; 152}; 153 154 155// The implementation uses malloc instead of new because Posix states that: 156// The pointer returned if the allocation succeeds shall be suitably 157// aligned so that it may be assigned to a pointer to any type of 158// object and then used to access such an object in the space 159// allocated 160// So as long as we malloc() more than 4 bytes, the returned block 161// must be able to contain a pointer, and thus will be 32-bit 162// aligned. I believe the bionic implementation uses a minimum of 8 or 16. 163// 164// Invariant: mLength <= mCapacity <= max_size() 165 166template<typename _T> 167vector<_T>::vector() 168 :mBegin(NULL), mCapacity(0), mLength(0) { } 169 170template<typename _T> 171vector<_T>::vector(const size_type num, const value_type& init_value) 172{ 173 if (num < max_size()) 174 { 175 mBegin = static_cast<pointer>(malloc(num * sizeof(value_type))); 176 if (mBegin) 177 { 178 mLength = mCapacity = num; 179 std::uninitialized_fill(mBegin, mBegin + mLength, init_value); 180 return; 181 } 182 } 183 mBegin = NULL; 184 mLength = mCapacity = 0; 185} 186 187template<typename _T> 188bool vector<_T>::reserve(size_type new_size) 189{ 190 if (0 == new_size) 191 { 192 if (0 == mLength) // Free whatever has been reserved. 193 { 194 clear(); 195 return true; 196 } 197 new_size = mLength; // Shrink to fit. 198 } 199 else if (new_size < mLength || new_size > max_size()) 200 { 201 return false; 202 } 203 204 if (is_pod<value_type>::value) 205 { 206 pointer oldBegin = mBegin; 207 mBegin = static_cast<pointer>(realloc(mBegin, new_size * sizeof(value_type))); 208 if (!mBegin) 209 { 210 mBegin = oldBegin; 211 return false; 212 } 213 } 214 else 215 { 216 pointer newBegin = static_cast<pointer>(malloc(new_size * sizeof(value_type))); 217 if (!newBegin) return false; 218 219 std::uninitialized_copy(mBegin, mBegin + mLength, newBegin); 220 if (mBegin) deallocate(); 221 mBegin = newBegin; 222 } 223 mCapacity = new_size; 224 return true; 225} 226 227template<typename _T> 228void vector<_T>::push_back(const value_type& elt) 229{ 230 if (max_size() == mLength) return; 231 if (mCapacity == mLength) 232 { 233 const size_type new_capacity = grow(); 234 if (0 == new_capacity || !reserve(new_capacity)) return; 235 } 236 // mLength < mCapacity 237 *(mBegin + mLength) = elt; 238 ++mLength; 239} 240 241template<typename _T> 242void vector<_T>::pop_back() 243{ 244 if (mLength > 0) 245 { 246 --mLength; 247 if (!is_pod<value_type>::value) 248 { 249 (mBegin + mLength)->~_T(); 250 } 251 } 252} 253 254template<typename _T> 255void vector<_T>::clear() 256{ 257 if(mBegin) 258 { 259 if (is_pod<value_type>::value) 260 { 261 free(mBegin); 262 } 263 else 264 { 265 deallocate(); 266 } 267 } 268 mBegin = NULL; 269 mCapacity = 0; 270 mLength = 0; 271} 272 273template<typename _T> 274void vector<_T>::swap(vector& other) 275{ 276 std::swap(mBegin, other.mBegin); 277 std::swap(mCapacity, other.mCapacity); 278 std::swap(mLength, other.mLength); 279} 280 281// Grow the capacity. Use exponential until kExponentialLimit then 282// linear until it reaches max_size(). 283template<typename _T> 284typename vector<_T>::size_type vector<_T>::grow() const 285{ 286 size_type new_capacity; 287 if (mCapacity > kExponentialLimit) 288 { 289 new_capacity = mCapacity + kLinearIncrement; 290 } 291 else 292 { 293 new_capacity = mCapacity == 0 ? kExponentialFactor : mCapacity * kExponentialFactor; 294 } 295 if (mCapacity > new_capacity || new_capacity > max_size()) 296 { // Overflow: cap at max_size() if not there already. 297 new_capacity = mCapacity == max_size() ? 0 : max_size(); 298 } 299 return new_capacity; 300} 301 302 303// mBegin should not be NULL. 304template<typename _T> 305void vector<_T>::deallocate() 306{ 307 pointer begin = mBegin; 308 pointer end = mBegin + mLength; 309 310 for (; begin != end; ++begin) 311 { 312 begin->~_T(); 313 } 314 free(mBegin); 315} 316 317} // namespace std 318 319#endif // ANDROID_ASTL_VECTOR__ 320