vector revision fd56a38d5dcb569b146634bb22c5d9cb1e138e3f
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(-1) / 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 kDefaultCapacity = 4; 150 static const size_type kExponentialFactor = 2; 151 static const size_type kExponentialLimit = 256; 152 static const size_type kLinearIncrement = 256; 153}; 154 155 156// The implementation uses malloc instead of new because Posix states that: 157// The pointer returned if the allocation succeeds shall be suitably 158// aligned so that it may be assigned to a pointer to any type of 159// object and then used to access such an object in the space 160// allocated 161// So as long as we malloc() more than 4 bytes, the returned block 162// must be able to contain a pointer, and thus will be 32-bit 163// aligned. I believe the bionic implementation uses a minimum of 8 or 16. 164// 165// Invariant: mLength <= mCapacity <= max_size() 166 167template<typename _T> 168vector<_T>::vector() 169 :mBegin(NULL), mCapacity(0), mLength(0) { } 170 171template<typename _T> 172vector<_T>::vector(const size_type num, const value_type& init_value) 173{ 174 if (num < max_size()) 175 { 176 mBegin = static_cast<pointer>(malloc(num * sizeof(value_type))); 177 if (mBegin) 178 { 179 mLength = mCapacity = num; 180 std::uninitialized_fill(mBegin, mBegin + mLength, init_value); 181 return; 182 } 183 } 184 mBegin = NULL; 185 mLength = mCapacity = 0; 186} 187 188template<typename _T> 189bool vector<_T>::reserve(size_type new_size) 190{ 191 if (new_size == 0) 192 { 193 new_size = mLength ? mLength : kDefaultCapacity; 194 } 195 else if (new_size < mLength || new_size > max_size()) 196 { 197 return false; 198 } 199 200 if (is_pod<value_type>::value) 201 { 202 pointer oldBegin = mBegin; 203 mBegin = static_cast<pointer>(realloc(mBegin, new_size * sizeof(value_type))); 204 if (!mBegin) 205 { 206 mBegin = oldBegin; 207 return false; 208 } 209 } 210 else 211 { 212 pointer newBegin = static_cast<pointer>(malloc(new_size * sizeof(value_type))); 213 if (!newBegin) return false; 214 215 std::uninitialized_copy(mBegin, mBegin + mLength, newBegin); 216 if (mBegin) deallocate(); 217 mBegin = newBegin; 218 } 219 mCapacity = new_size; 220 return true; 221} 222 223template<typename _T> 224void vector<_T>::push_back(const value_type& elt) 225{ 226 if (max_size() == mLength) return; 227 if (mCapacity == mLength) 228 { 229 const size_type new_capacity = grow(); 230 if (0 == new_capacity || !reserve(new_capacity)) return; 231 } 232 // mLength < mCapacity 233 *(mBegin + mLength) = elt; 234 ++mLength; 235} 236 237template<typename _T> 238void vector<_T>::pop_back() 239{ 240 if (mLength > 0) 241 { 242 --mLength; 243 } 244} 245 246template<typename _T> 247void vector<_T>::clear() 248{ 249 if(mBegin) 250 { 251 if (is_pod<value_type>::value) 252 { 253 free(mBegin); 254 } 255 else 256 { 257 deallocate(); 258 } 259 } 260 mBegin = NULL; 261 mCapacity = 0; 262 mLength = 0; 263} 264 265template<typename _T> 266void vector<_T>::swap(vector& other) 267{ 268 std::swap(mBegin, other.mBegin); 269 std::swap(mCapacity, other.mCapacity); 270 std::swap(mLength, other.mLength); 271} 272 273// Grow the capacity. Use exponential until kExponentialLimit then 274// linear until it reaches max_size(). 275template<typename _T> 276typename vector<_T>::size_type vector<_T>::grow() const 277{ 278 if (mCapacity < kDefaultCapacity) 279 { 280 return kDefaultCapacity; 281 } 282 283 size_type new_capacity; 284 if (mCapacity > kExponentialLimit) 285 { 286 new_capacity = mCapacity + kLinearIncrement; 287 } 288 else 289 { 290 new_capacity = mCapacity * kExponentialFactor; 291 } 292 if (mCapacity > new_capacity) 293 { // overflow 294 return 0; // overflow 295 } 296 else if (new_capacity > max_size()) 297 { // cap at max_size() if not there already. 298 new_capacity = mCapacity == max_size() ? 0 : max_size(); 299 } 300 return new_capacity; 301} 302 303 304// mBegin should not be NULL. 305template<typename _T> 306void vector<_T>::deallocate() 307{ 308 pointer begin = mBegin; 309 pointer end = mBegin + mLength; 310 311 for (; begin != end; ++begin) 312 { 313 begin->~_T(); 314 } 315 free(mBegin); 316} 317 318} // namespace std 319 320#endif // ANDROID_ASTL_VECTOR__ 321