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