vector revision 6943930994c640cbb24773ddb8df99de8a5d7e16
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 // Create a vector by copying the elements from [first, last). 85 // 86 // If the iterators are random-access, the constructor will be 87 // able to reserve the memory in a single call before copying the 88 // elements. If the elements are POD, the constructor uses memmove. 89 template<typename _Iterator> 90 vector(_Iterator first, _Iterator last) { 91 // Because of template matching, vector<int>(int n, int val) 92 // will now match this constructor (int != size_type) instead 93 // of the repeat one above. In this case, the _Iterator 94 // template parameter is an integral type and not an iterator, 95 // we use that to call the correct initialize impl. 96 typedef typename is_integral<_Iterator>::type integral; 97 initialize(first, last, integral()); 98 } 99 100 ~vector() { clear(); } 101 102 // @return true if the vector is empty, false otherwise. 103 bool empty() const { return mLength == 0; } 104 size_type size() const { return mLength; } 105 106 // @return the maximum size for a vector. 107 size_type max_size() const { return (~size_type(0)) / sizeof(value_type); } 108 109 // Change the capacity to new_size. 0 means shrink to fit. The 110 // extra memory is not initialized when the capacity is grown. 111 // @param new_size number of element to be allocated. 112 // @return true if successful. The STL version returns nothing. 113 bool reserve(size_type new_size = 0); 114 115 // @return The total number of elements that the vector can hold 116 // before more memory gets allocated. 117 size_type capacity() const { return mCapacity; } 118 119 reference front() { return *mBegin; } 120 const_reference front() const { return *mBegin; } 121 122 reference back() { return mLength ? *(mBegin + mLength - 1) : front(); } 123 const_reference back() const { return mLength ? *(mBegin + mLength - 1) : front(); } 124 125 // Subscript access to the vector's elements. Don't do boundary 126 // check. Use at() for checked access. 127 // @param index Of the element (0-based). 128 // @return A const reference to the element. 129 const_reference operator[](size_type index) const { return *(mBegin + index); } 130 131 // @param index Of the element (0-based). 132 // @return A reference to the element. 133 reference operator[](size_type index) { return *(mBegin + index); } 134 135 iterator begin() { return iterator(mBegin); } 136 iterator end() { return iterator(mBegin + mLength); } 137 138 const_iterator begin() const { return const_iterator(mBegin); } 139 const_iterator end() const { return const_iterator(mBegin + mLength); } 140 141 // Add data at the end of the vector. Constant in time if the 142 // memory has been preallocated (e.g using reserve). 143 // @param elt To be added. 144 void push_back(const value_type& elt); 145 146 // Remove the last element. However, no memory is reclaimed from 147 // the internal buffer: you need to call reserve() to recover it. 148 void pop_back(); 149 150 // Remove the element pointed by the iterator. 151 // Expensive since the remaining elts must be shifted around. 152 // @param pos Iterator pointing to the elt to be removed. 153 // @return An iterator pointing to the next elt or end(). 154 iterator erase(iterator pos); 155 156 // Remove a range of elements [first, last) 157 // @param first Iterator pointing to the first element to be removed. 158 // @param last Iterator pointing to one past the last element to be removed. 159 // @return An iterator pointing to the elt next to 'last' or end(). 160 iterator erase(iterator first, iterator last); 161 162 // Empty the vector on return. Release the internal buffer. Length 163 // and capacity are both 0 on return. If you want to keep the 164 // internal buffer around for reuse, call 'resize'/'erase' instead. 165 void clear(); 166 167 // Resize the vector to contain 'size' element. If 'size' is 168 // smaller than the current size, the extra elements are dropped 169 // but the reserved memory is not changed (use 'swap' to recover 170 // memory.) If 'size' is greater, the vector is expanded by 171 // inserting at the end as many copy of 'init_value' (this may 172 // lead to some realloc) as necessary. See 'reserve'. 173 void resize(size_type size, value_type init_value = value_type()); 174 175 void swap(vector& other); 176 private: 177 // See the 2 'initialize' methods first. They desambiguate between 178 // repeat and range initialize. For range initialize, there is 179 // another desambiguation based on the nature of the iterators. 180 181 // Repeat constructor implementation. 182 void repeat_initialize(const size_type num, 183 const value_type& init_value); 184 185 // Initialize from a random access iterator. 186 template<typename _Iterator> 187 void range_initialize(_Iterator first, _Iterator last, 188 random_access_iterator_tag); 189 190 // Initialize from an input iterator. 191 template<typename _InputIterator> 192 void range_initialize(_InputIterator first, _InputIterator last, 193 input_iterator_tag); 194 195 // Repeat constructor that matched the templatized constructor for iterator. 196 // The last parameter true_type is used by the caller to target this method. 197 template<typename _Integral> 198 void initialize(_Integral num, _Integral init_value, true_type) { 199 repeat_initialize((size_type)num, init_value); 200 } 201 202 // Not a repeat constructor (last param type is false_type). first 203 // and last are really iterators. Dispatch the call depending on 204 // the iterators' category. 205 template<typename _InputIterator> 206 void initialize(_InputIterator first, _InputIterator last, false_type) { 207 range_initialize(first, last, android::iterator_category(first)); 208 } 209 210 // @return New internal buffer size when it is adjusted automatically. 211 size_type grow() const; 212 213 // Calls the class' deallocator explicitely on each instance in 214 // the vector. 215 void deallocate(); 216 217 pointer mBegin; 218 size_type mCapacity; 219 size_type mLength; 220 static const size_type kExponentialFactor = 2; 221 static const size_type kExponentialLimit = 256; 222 static const size_type kLinearIncrement = 256; 223}; 224 225 226// The implementation uses malloc instead of new because Posix states that: 227// The pointer returned if the allocation succeeds shall be suitably 228// aligned so that it may be assigned to a pointer to any type of 229// object and then used to access such an object in the space 230// allocated 231// So as long as we malloc() more than 4 bytes, the returned block 232// must be able to contain a pointer, and thus will be 32-bit 233// aligned. I believe the bionic implementation uses a minimum of 8 or 16. 234// 235// Invariant: mLength <= mCapacity <= max_size() 236 237template<typename _T> 238vector<_T>::vector() 239 :mBegin(NULL), mCapacity(0), mLength(0) { } 240 241template<typename _T> 242vector<_T>::vector(const size_type num, const value_type& init_value) 243{ 244 repeat_initialize(num, init_value); 245} 246 247template<typename _T> 248void vector<_T>::repeat_initialize(const size_type num, 249 const value_type& init_value) 250{ 251 if (num < max_size()) 252 { 253 mBegin = static_cast<pointer>(malloc(num * sizeof(value_type))); 254 if (mBegin) 255 { 256 mLength = mCapacity = num; 257 std::uninitialized_fill(mBegin, mBegin + mLength, init_value); 258 return; 259 } 260 } 261 mBegin = NULL; 262 mLength = mCapacity = 0; 263} 264 265template<typename _T> 266bool vector<_T>::reserve(size_type new_size) 267{ 268 if (0 == new_size) 269 { 270 if (0 == mLength) // Free whatever has been reserved. 271 { 272 clear(); 273 return true; 274 } 275 new_size = mLength; // Shrink to fit. 276 } 277 else if (new_size < mLength || new_size > max_size()) 278 { 279 return false; 280 } 281 282 if (is_pod<value_type>::value) 283 { 284 pointer oldBegin = mBegin; 285 mBegin = static_cast<pointer>( 286 realloc(mBegin, new_size * sizeof(value_type))); 287 if (!mBegin) 288 { 289 mBegin = oldBegin; 290 return false; 291 } 292 } 293 else 294 { 295 pointer newBegin = static_cast<pointer>( 296 malloc(new_size * sizeof(value_type))); 297 if (!newBegin) return false; 298 299 if (mBegin != NULL) { 300 std::uninitialized_copy(mBegin, mBegin + mLength, newBegin); 301 deallocate(); 302 } 303 mBegin = newBegin; 304 } 305 mCapacity = new_size; 306 return true; 307} 308 309template<typename _T> 310void vector<_T>::push_back(const value_type& elt) 311{ 312 if (max_size() == mLength) return; 313 if (mCapacity == mLength) 314 { 315 const size_type new_capacity = grow(); 316 if (0 == new_capacity || !reserve(new_capacity)) return; 317 } 318 // mLength < mCapacity 319 if (is_pod<value_type>::value) { 320 *(mBegin + mLength) = elt; 321 } else { 322 // The memory where the new element is added is uninitialized, 323 // we cannot use assigment (lhs is not valid). 324 new((void *)(mBegin + mLength)) _T(elt); 325 } 326 ++mLength; 327} 328 329template<typename _T> 330void vector<_T>::pop_back() 331{ 332 if (mLength > 0) 333 { 334 --mLength; 335 if (!is_pod<value_type>::value) 336 { 337 (mBegin + mLength)->~_T(); 338 } 339 } 340} 341 342template<typename _T> 343typename vector<_T>::iterator 344vector<_T>::erase(iterator pos) { 345 if (mLength) { 346 std::copy(pos + 1, end(), pos); 347 --mLength; 348 if (!is_pod<value_type>::value) { 349 end()->~_T(); 350 } 351 } 352 return pos; 353} 354 355template<typename _T> 356typename vector<_T>::iterator 357vector<_T>::erase(iterator first, iterator last) { 358 difference_type len = std::distance(first, last); 359 if (len > 0) { 360 last = std::copy(last, end(), first); 361 362 if (!is_pod<value_type>::value) { 363 while (last != end()) { 364 last->~_T(); 365 ++last; 366 } 367 } 368 mLength -= len; 369 } 370 return first; 371} 372 373template<typename _T> 374void vector<_T>::clear() 375{ 376 if(mBegin) 377 { 378 if (is_pod<value_type>::value) 379 { 380 free(mBegin); 381 } 382 else 383 { 384 deallocate(); 385 } 386 } 387 mBegin = NULL; 388 mCapacity = 0; 389 mLength = 0; 390} 391 392template<typename _T> 393void vector<_T>::resize(size_type new_size, value_type init_value) 394{ 395 if (mLength == new_size || new_size > max_size()) { 396 return; 397 } else if (new_size < mLength) { 398 if (!is_pod<value_type>::value) { 399 const pointer end = mBegin + mLength; 400 for (pointer begin = mBegin + new_size; 401 begin < end; ++begin) { 402 begin->~_T(); 403 } 404 } 405 mLength = new_size; 406 return; 407 } 408 409 if (new_size > mCapacity && !reserve(new_size)) { 410 return; 411 } 412 std::uninitialized_fill(mBegin + mLength, mBegin + new_size, init_value); 413 mLength = new_size; 414} 415 416template<typename _T> 417void vector<_T>::swap(vector& other) 418{ 419 std::swap(mBegin, other.mBegin); 420 std::swap(mCapacity, other.mCapacity); 421 std::swap(mLength, other.mLength); 422} 423 424template<typename _T> 425template<typename _InputIterator> 426void vector<_T>::range_initialize(_InputIterator first, _InputIterator last, 427 input_iterator_tag) { 428 // There is no way to know how many elements we are going to 429 // insert, call push_back which will alloc/realloc as needed. 430 mBegin = NULL; 431 mLength = mCapacity = 0; 432 for (; first != last; ++first) { 433 push_back(*first); 434 } 435} 436 437template<typename _T> 438template<typename _Iterator> 439void vector<_T>::range_initialize(_Iterator first, _Iterator last, 440 random_access_iterator_tag) { 441 typedef typename iterator_traits<_Iterator>::difference_type difference_type; 442 const difference_type num = std::distance(first, last); 443 444 if (0 <= num && static_cast<size_type>(num) < max_size()) { 445 mBegin = static_cast<pointer>(malloc(num * sizeof(value_type))); 446 if (mBegin) { 447 mLength = mCapacity = num; 448 std::uninitialized_copy(first, last, iterator(mBegin)); 449 return; 450 } 451 } 452 mBegin = NULL; 453 mLength = mCapacity = 0; 454} 455 456 457// Grow the capacity. Use exponential until kExponentialLimit then 458// linear until it reaches max_size(). 459template<typename _T> 460typename vector<_T>::size_type vector<_T>::grow() const 461{ 462 size_type new_capacity; 463 if (mCapacity > kExponentialLimit) 464 { 465 new_capacity = mCapacity + kLinearIncrement; 466 } 467 else 468 { 469 new_capacity = mCapacity == 0 ? kExponentialFactor : mCapacity * kExponentialFactor; 470 } 471 if (mCapacity > new_capacity || new_capacity > max_size()) 472 { // Overflow: cap at max_size() if not there already. 473 new_capacity = mCapacity == max_size() ? 0 : max_size(); 474 } 475 return new_capacity; 476} 477 478 479// mBegin should not be NULL. 480template<typename _T> 481void vector<_T>::deallocate() 482{ 483 pointer begin = mBegin; 484 pointer end = mBegin + mLength; 485 486 for (; begin != end; ++begin) 487 { 488 begin->~_T(); 489 } 490 free(mBegin); 491} 492 493} // namespace std 494 495#endif // ANDROID_ASTL_VECTOR__ 496