dynamic_vector.h revision f3ea231ca3ca6a526316c75e9a3df033dcf1ee07
1/* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef CHRE_UTIL_DYNAMIC_VECTOR_H_ 18#define CHRE_UTIL_DYNAMIC_VECTOR_H_ 19 20#include <cstddef> 21 22#include "chre/util/non_copyable.h" 23 24namespace chre { 25 26/** 27 * A container for storing a sequential array of elements. This container 28 * resizes dynamically using heap allocations. 29 */ 30template<typename ElementType> 31class DynamicVector : public NonCopyable { 32 public: 33 /** 34 * Random-access iterator that points to some element in the container. 35 */ 36 typedef ElementType* iterator; 37 typedef const ElementType* const_iterator; 38 39 typedef size_t size_type; 40 41 /** 42 * Default-constructs a dynamic vector. 43 */ 44 DynamicVector(); 45 46 /** 47 * Move-constructs a dynamic vector from another. The other dynamic vector is 48 * left in an empty state. 49 * 50 * @param other The other vector to move from. 51 */ 52 DynamicVector(DynamicVector<ElementType>&& other); 53 54 /** 55 * Destructs the objects and releases the memory owned by the vector. 56 */ 57 ~DynamicVector(); 58 59 /** 60 * Removes all elements from the vector, but does not change the capacity. 61 * All iterators and references are invalidated. 62 */ 63 void clear(); 64 65 /** 66 * Returns a pointer to the underlying buffer. Note that this should not be 67 * considered to be persistent as the vector will be moved and resized 68 * automatically. 69 * 70 * @return The pointer to the underlying buffer. 71 */ 72 ElementType *data(); 73 74 /** 75 * Returns a const pointer to the underlying buffer. Note that this should not 76 * be considered to be persistent as the vector will be moved and resized 77 * automatically. 78 * 79 * @return The const pointer to the underlying buffer. 80 */ 81 const ElementType *data() const; 82 83 /** 84 * Returns the current number of elements in the vector. 85 * 86 * @return The number of elements in the vector. 87 */ 88 size_type size() const; 89 90 /** 91 * Returns the maximum number of elements that can be stored in this vector 92 * without a resize operation. 93 * 94 * @return The capacity of the vector. 95 */ 96 size_type capacity() const; 97 98 /** 99 * Determines whether the vector is empty or not. 100 * 101 * @return true if the vector is empty. 102 */ 103 bool empty() const; 104 105 /** 106 * Erases the last element in the vector. Invalid to call on an empty vector. 107 * 108 * Invalidates any references to back() and end()/cend(). 109 */ 110 void pop_back(); 111 112 /** 113 * Copy- or move-constructs an element onto the back of the vector. If the 114 * vector requires a resize and that allocation fails this function will 115 * return false. All iterators and references are invalidated if the container 116 * has been resized. Otherwise, only the past-the-end iterator is invalidated. 117 * 118 * @param The element to push onto the vector. 119 * @return true if the element was pushed successfully. 120 */ 121 bool push_back(const ElementType& element); 122 bool push_back(ElementType&& element); 123 124 /** 125 * Constructs an element onto the back of the vector. All iterators and 126 * references are invalidated if the container has been resized. Otherwise, 127 * only the past-the-end iterator is invalidated. 128 * 129 * @param The arguments to the constructor 130 * @return true if the element is constructed successfully. 131 */ 132 template<typename... Args> 133 bool emplace_back(Args&&... args); 134 135 /** 136 * Obtains an element of the vector given an index. It is illegal to index 137 * this vector out of bounds and the user of the API must check the size() 138 * function prior to indexing this vector to ensure that they will not read 139 * out of bounds. 140 * 141 * @param The index of the element. 142 * @return The element. 143 */ 144 ElementType& operator[](size_type index); 145 146 /** 147 * Obtains a const element of the vector given an index. It is illegal to 148 * index this vector out of bounds and the user of the API must check the 149 * size() function prior to indexing this vector to ensure that they will not 150 * read out of bounds. 151 * 152 * @param The index of the element. 153 * @return The element. 154 */ 155 const ElementType& operator[](size_type index) const; 156 157 /** 158 * Compares two vectors for equality. It will compare the vector sizes and 159 * return false if those are different; if not, it will compare the contents 160 * of the vectors element-by-element. The operator == should be defined and 161 * meaningful for the vector's element type. 162 * 163 * @param Right-hand side vector to compared with. 164 * @return true if two vectors are equal, false otherwise. 165 */ 166 bool operator==(const DynamicVector<ElementType>& other) const; 167 168 /** 169 * Resizes the vector to a new capacity returning true if allocation was 170 * successful. If the new capacity is smaller than the current capacity, 171 * the operation is a no-op and true is returned. If a memory allocation 172 * fails, the contents of the vector are not modified and false is returned. 173 * This is intended to be similar to the reserve function of the std::vector. 174 * All iterators and references are invalidated unless the container did not 175 * resize. 176 * 177 * @param The new capacity of the vector. 178 * @return true if the resize operation was successful. 179 */ 180 bool reserve(size_type newCapacity); 181 182 /** 183 * Inserts an element into the vector at a given index. If a resize of the 184 * vector is required and the allocation fails, false will be returned. This 185 * will shift all vector elements after the given index one position backward 186 * in the list. The supplied index must be <= the size of the vector. It is 187 * not possible to have a sparse list of items. If the index is > the current 188 * size of the vector, false will be returned. All iterators and references 189 * to and after the indexed element are invalidated. Iterators and references 190 * to before the indexed elements are unaffected if the container did not resize. 191 * 192 * @param index The index to insert an element at. 193 * @param element The element to insert. 194 * @return Whether or not the insert operation was successful. 195 */ 196 bool insert(size_type index, const ElementType& element); 197 bool insert(size_type index, ElementType&& element); 198 199 /** 200 * Similar to wrap(), except makes a copy of the supplied C-style array, 201 * maintaining ownership of the buffer within the DynamicVector container. The 202 * vector's capacity is increased if necessary to fit the given array, though 203 * note that this function will not cause the capacity to shrink. Upon 204 * successful reservation of necessary capacity, any pre-existing items in the 205 * vector are removed (via clear()), the supplied array is copied, and the 206 * vector's size is set to elementCount. All iterators and references are 207 * invalidated unless the container did not resize. 208 * 209 * This is essentially equivalent to calling these functions from std::vector: 210 * vector.clear(); 211 * vector.insert(vector.begin(), array, &array[elementCount]); 212 * 213 * This function is not valid to call on a vector where owns_data() is false. 214 * Use unwrap() first in that case. 215 * 216 * @param array Pointer to the start of an array 217 * @param elementCount Number of elements in the supplied array to copy 218 * 219 * @return true if capacity was reserved to fit the supplied array (or the 220 * vector already had sufficient capacity), and the supplied array was 221 * copied into the vector. If false, the vector is not modified. 222 */ 223 bool copy_array(const ElementType *array, size_type elementCount); 224 225 /** 226 * Removes an element from the vector given an index. All elements after the 227 * indexed one are moved forward one position. The destructor is invoked on 228 * on the invalid item left at the end of the vector. The index passed in 229 * must be less than the size() of the vector. If the index is greater than or 230 * equal to the size no operation is performed. All iterators and references 231 * to and after the indexed element are invalidated. 232 * 233 * @param index The index to remove an element at. 234 */ 235 void erase(size_type index); 236 237 /** 238 * Searches the vector for an element. 239 * 240 * @param element The element to comare against. 241 * @return The index of the element found. If the return is equal to size() 242 * then the element was not found. 243 */ 244 size_type find(const ElementType& element) const; 245 246 /** 247 * Swaps the location of two elements stored in the vector. The indices 248 * passed in must be less than the size() of the vector. If the index is 249 * greater than or equal to the size, no operation is performed. All 250 * iterators and references to these two indexed elements are invalidated. 251 * 252 * @param index0 The index of the first element 253 * @param index1 The index of the second element 254 */ 255 void swap(size_type index0, size_type index1); 256 257 /** 258 * Wraps an existing C-style array so it can be used as a DynamicVector. A 259 * reference to the supplied array is kept, as opposed to making a copy. The 260 * caller retains ownership of the memory. Calling code must therefore ensure 261 * that the lifetime of the supplied array is at least as long as that of this 262 * vector, and that the memory is released after this vector is destructed, as 263 * the vector will not attempt to free the memory itself. 264 * 265 * Once a vector wraps another buffer, it cannot be resized except through 266 * another call to wrap(). However, elements can be erased to make room for 267 * adding new elements. 268 * 269 * Destruction of elements within a wrapped array remains the responsibility 270 * of the calling code. While the vector may invoke the element destructor as 271 * a result of explicit calls to functions like erase() or clear(), it will 272 * not destruct elements remaining in the array when the vector is destructed. 273 * Therefore, special care must be taken when wrapping an array of elements 274 * that have a non-trivial destructor. 275 * 276 * @param array Pointer to a pre-allocated array 277 * @param elementCount Number of elements in the array (NOT the array's size 278 * in bytes); will become the vector's size() and capacity() 279 */ 280 void wrap(ElementType *array, size_type elementCount); 281 282 283 /** 284 * Returns a vector that is wrapping an array to the newly-constructed state, 285 * with capacity equal to 0, and owns_data() is true. 286 */ 287 void unwrap(); 288 289 /** 290 * @return false if this vector is wrapping an array passed in via wrap() 291 */ 292 bool owns_data() const; 293 294 /** 295 * Returns a reference to the first element in the vector. It is illegal to 296 * call this on an empty vector. 297 * 298 * @return The first element in the vector. 299 */ 300 ElementType& front(); 301 302 /** 303 * Returns a const reference to the first element in the vector. It is illegal 304 * to call this on an empty vector. 305 * 306 * @return The first element in the vector. 307 */ 308 const ElementType& front() const; 309 310 /** 311 * Returns a reference to the last element in the vector. It is illegal to 312 * call this on an empty vector. 313 * 314 * @return The last element in the vector. 315 */ 316 ElementType& back(); 317 318 /** 319 * Returns a const reference to the last element in the vector. It is illegal 320 * to call this on an empty vector. 321 * 322 * @return The last element in the vector. 323 */ 324 const ElementType& back() const; 325 326 /** 327 * Prepares a vector to push a minimum of one element onto the back. The 328 * vector may be resized if required. The capacity of the vector increases 329 * with the growth policy of this vector (doubles for each resize for now). 330 * 331 * @return Whether or not the resize was successful. 332 */ 333 bool prepareForPush(); 334 335 /** 336 * @return A random-access iterator to the beginning. 337 */ 338 typename DynamicVector<ElementType>::iterator begin(); 339 typename DynamicVector<ElementType>::const_iterator begin() const; 340 typename DynamicVector<ElementType>::const_iterator cbegin() const; 341 342 /** 343 * @return A random-access iterator to the end. 344 */ 345 typename DynamicVector<ElementType>::iterator end(); 346 typename DynamicVector<ElementType>::const_iterator end() const; 347 typename DynamicVector<ElementType>::const_iterator cend() const; 348 349 private: 350 //! A pointer to the underlying data buffer. 351 ElementType *mData = nullptr; 352 353 //! The current size of the vector, as in the number of elements stored. 354 size_t mSize = 0; 355 356 //! The current capacity of the vector, as in the maximum number of elements 357 //! that can be stored. 358 size_t mCapacity = 0; 359 360 //! Set to true when the buffer (mData) was supplied via wrap() 361 bool mDataIsWrapped = false; 362 363 /** 364 * Prepares the vector for insertion - upon successful return, the memory at 365 * the given index will be allocated but uninitialized 366 * 367 * @param index 368 * @return true 369 */ 370 bool prepareInsert(size_t index); 371}; 372 373} // namespace chre 374 375#include "chre/util/dynamic_vector_impl.h" 376 377#endif // CHRE_UTIL_DYNAMIC_VECTOR_H_ 378