vector revision 48d768f7d32790ee7f6691367dc543fda1f1181c
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 <iterator> 38#include <memory> 39#include <type_traits.h> 40 41namespace std { 42 43#ifdef _T 44#error "_T is a macro." 45#endif 46 47// Simple vector implementation. Its purpose is to be able to compile code that 48// uses the STL and requires std::vector. 49// 50// IMPORTANT: 51// . This class it is not fully STL compliant. Some constructors/methods maybe 52// missing, they will be added on demand. 53// . A standard container which offers fixed time access to individual 54// elements in any order. 55// 56// TODO: Use the stack for the default constructor. When the capacity 57// grows beyond that move the data to the heap. 58 59template<typename _T> 60class vector 61{ 62 typedef vector<_T> vector_type; 63 64 public: 65 typedef _T value_type; 66 typedef _T* pointer; 67 typedef const _T* const_pointer; 68 typedef _T& reference; 69 typedef const _T& const_reference; 70 71 typedef __wrapper_iterator<pointer,vector_type> iterator; 72 typedef __wrapper_iterator<const_pointer,vector_type> const_iterator; 73 74 typedef size_t size_type; 75 typedef ptrdiff_t difference_type; 76 77 vector(); 78 79 // Create a vector with bitwise copies of an exemplar element. 80 // @param num The number of elements to create. 81 // @param init_value The element to copy. 82 explicit vector(const size_type num, const value_type& init_value = value_type()); 83 84 ~vector() { clear(); } 85 86 // @return true if the vector is empty, false otherwise. 87 bool empty() const { return mLength == 0; } 88 size_type size() const { return mLength; } 89 90 // @return the maximum size for a vector. 91 size_type max_size() const { return (~size_type(0)) / sizeof(value_type); } 92 93 // Change the capacity to new_size. 0 means shrink to fit. 94 // @param new_size number of element to be allocated. 95 // @return true if successful. The STL version returns nothing. 96 bool reserve(size_type new_size = 0); 97 98 // @return The total number of elements that the vector can hold 99 // before more memory gets allocated. 100 size_type capacity() const { return mCapacity; } 101 102 reference front() { return *mBegin; } 103 const_reference front() const { return *mBegin; } 104 105 reference back() { return mLength ? *(mBegin + mLength - 1) : front(); } 106 const_reference back() const { return mLength ? *(mBegin + mLength - 1) : front(); } 107 108 // Subscript access to the vector's elements. Don't do boundary 109 // check. Use at() for checked access. 110 // @param index Of the element (0-based). 111 // @return A const reference to the element. 112 const_reference operator[](size_type index) const { return *(mBegin + index); } 113 114 // @param index Of the element (0-based). 115 // @return A reference to the element. 116 reference operator[](size_type index) { return *(mBegin + index); } 117 118 iterator begin() { return iterator(mBegin); } 119 iterator end() { return iterator(mBegin + mLength); } 120 121 const_iterator begin() const { return const_iterator(mBegin); } 122 const_iterator end() const { return const_iterator(mBegin + mLength); } 123 124 // Add data at the end of the vector. Constant in time if the 125 // memory has been preallocated (e.g using reserve). 126 // @param elt To be added. 127 void push_back(const value_type& elt); 128 129 // Remove the last element. However, no memory is reclaimed from 130 // the internal buffer: you need to call reserve() to recover it. 131 void pop_back(); 132 133 // Empty the vector on return. Release the internal buffer. Length 134 // and capacity are both 0 on return. If you want to keep the 135 // internal buffer around for reuse, call 'resize'/'erase' instead. 136 void clear(); 137 138 void swap(vector& other); 139 private: 140 // @return New internal buffer size when it is adjusted automatically. 141 size_type grow() const; 142 143 // Calls the class' deallocator explicitely on each instance in 144 // the vector. 145 void deallocate(); 146 147 pointer mBegin; 148 size_type mCapacity; 149 size_type mLength; 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 (0 == new_size) 192 { 193 if (0 == mLength) // Free whatever has been reserved. 194 { 195 clear(); 196 return true; 197 } 198 new_size = mLength; // Shrink to fit. 199 } 200 else if (new_size < mLength || new_size > max_size()) 201 { 202 return false; 203 } 204 205 if (is_pod<value_type>::value) 206 { 207 pointer oldBegin = mBegin; 208 mBegin = static_cast<pointer>(realloc(mBegin, new_size * sizeof(value_type))); 209 if (!mBegin) 210 { 211 mBegin = oldBegin; 212 return false; 213 } 214 } 215 else 216 { 217 pointer newBegin = static_cast<pointer>(malloc(new_size * sizeof(value_type))); 218 if (!newBegin) return false; 219 220 std::uninitialized_copy(mBegin, mBegin + mLength, newBegin); 221 if (mBegin) deallocate(); 222 mBegin = newBegin; 223 } 224 mCapacity = new_size; 225 return true; 226} 227 228template<typename _T> 229void vector<_T>::push_back(const value_type& elt) 230{ 231 if (max_size() == mLength) return; 232 if (mCapacity == mLength) 233 { 234 const size_type new_capacity = grow(); 235 if (0 == new_capacity || !reserve(new_capacity)) return; 236 } 237 // mLength < mCapacity 238 *(mBegin + mLength) = elt; 239 ++mLength; 240} 241 242template<typename _T> 243void vector<_T>::pop_back() 244{ 245 if (mLength > 0) 246 { 247 --mLength; 248 if (!is_pod<value_type>::value) 249 { 250 (mBegin + mLength)->~_T(); 251 } 252 } 253} 254 255template<typename _T> 256void vector<_T>::clear() 257{ 258 if(mBegin) 259 { 260 if (is_pod<value_type>::value) 261 { 262 free(mBegin); 263 } 264 else 265 { 266 deallocate(); 267 } 268 } 269 mBegin = NULL; 270 mCapacity = 0; 271 mLength = 0; 272} 273 274template<typename _T> 275void vector<_T>::swap(vector& other) 276{ 277 std::swap(mBegin, other.mBegin); 278 std::swap(mCapacity, other.mCapacity); 279 std::swap(mLength, other.mLength); 280} 281 282// Grow the capacity. Use exponential until kExponentialLimit then 283// linear until it reaches max_size(). 284template<typename _T> 285typename vector<_T>::size_type vector<_T>::grow() const 286{ 287 size_type new_capacity; 288 if (mCapacity > kExponentialLimit) 289 { 290 new_capacity = mCapacity + kLinearIncrement; 291 } 292 else 293 { 294 new_capacity = mCapacity == 0 ? kExponentialFactor : mCapacity * kExponentialFactor; 295 } 296 if (mCapacity > new_capacity || new_capacity > max_size()) 297 { // Overflow: 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