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 <type_traits> 21 22 #include "chre/util/dynamic_vector_base.h" 23 24 namespace chre { 25 26 /** 27 * A container for storing a sequential array of elements. This container 28 * resizes dynamically using heap allocations. 29 */ 30 template <typename ElementType> 31 class DynamicVector : private DynamicVectorBase { 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 * Move-constructs a dynamic vector from another. The other dynamic vector is 56 * left in an empty state. 57 */ 58 DynamicVector &operator=(DynamicVector<ElementType> &&other); 59 60 /** 61 * Destructs the objects and releases the memory owned by the vector. 62 */ 63 ~DynamicVector(); 64 65 /** 66 * Removes all elements from the vector, but does not change the capacity. 67 * All iterators and references are invalidated. 68 */ 69 void clear(); 70 71 /** 72 * Returns a pointer to the underlying buffer. Note that this should not be 73 * considered to be persistent as the vector will be moved and resized 74 * automatically. 75 * 76 * @return The pointer to the underlying buffer. 77 */ 78 ElementType *data(); 79 80 /** 81 * Returns a const pointer to the underlying buffer. Note that this should not 82 * be considered to be persistent as the vector will be moved and resized 83 * automatically. 84 * 85 * @return The const pointer to the underlying buffer. 86 */ 87 const ElementType *data() const; 88 89 /** 90 * Returns the current number of elements in the vector. 91 * 92 * @return The number of elements in the vector. 93 */ 94 size_type size() const; 95 96 /** 97 * Returns the maximum number of elements that can be stored in this vector 98 * without a resize operation. 99 * 100 * @return The capacity of the vector. 101 */ 102 size_type capacity() const; 103 104 /** 105 * Determines whether the vector is empty or not. 106 * 107 * @return true if the vector is empty. 108 */ 109 bool empty() const; 110 111 /** 112 * Erases the last element in the vector. Invalid to call on an empty vector. 113 * 114 * Invalidates any references to back() and end()/cend(). 115 */ 116 void pop_back(); 117 118 /** 119 * Copy- or move-constructs an element onto the back of the vector. If the 120 * vector requires a resize and that allocation fails this function will 121 * return false. All iterators and references are invalidated if the container 122 * has been resized. Otherwise, only the past-the-end iterator is invalidated. 123 * 124 * @param The element to push onto the vector. 125 * @return true if the element was pushed successfully. 126 */ 127 bool push_back(const ElementType &element); 128 bool push_back(ElementType &&element); 129 130 /** 131 * Constructs an element onto the back of the vector. All iterators and 132 * references are invalidated if the container has been resized. Otherwise, 133 * only the past-the-end iterator is invalidated. 134 * 135 * @param The arguments to the constructor 136 * @return true if the element is constructed successfully. 137 */ 138 template <typename... Args> 139 bool emplace_back(Args &&... args); 140 141 /** 142 * Obtains an element of the vector given an index. It is illegal to index 143 * this vector out of bounds and the user of the API must check the size() 144 * function prior to indexing this vector to ensure that they will not read 145 * out of bounds. 146 * 147 * @param The index of the element. 148 * @return The element. 149 */ 150 ElementType &operator[](size_type index); 151 152 /** 153 * Obtains a const element of the vector given an index. It is illegal to 154 * index this vector out of bounds and the user of the API must check the 155 * size() function prior to indexing this vector to ensure that they will not 156 * read out of bounds. 157 * 158 * @param The index of the element. 159 * @return The element. 160 */ 161 const ElementType &operator[](size_type index) const; 162 163 /** 164 * Compares two vectors for equality. It will compare the vector sizes and 165 * return false if those are different; if not, it will compare the contents 166 * of the vectors element-by-element. The operator == should be defined and 167 * meaningful for the vector's element type. 168 * 169 * @param Right-hand side vector to compared with. 170 * @return true if two vectors are equal, false otherwise. 171 */ 172 bool operator==(const DynamicVector<ElementType> &other) const; 173 174 /** 175 * Resizes the vector to a new capacity returning true if allocation was 176 * successful. If the new capacity is smaller than the current capacity, 177 * the operation is a no-op and true is returned. If a memory allocation 178 * fails, the contents of the vector are not modified and false is returned. 179 * This is intended to be similar to the reserve function of the std::vector. 180 * All iterators and references are invalidated unless the container did not 181 * resize. 182 * 183 * @param newCapacity The new capacity of the vector. 184 * @return true if the resize operation was successful. 185 */ 186 bool reserve(size_type newCapacity); 187 188 /** 189 * Resizes the vector to a new size. If the new capacity is smaller than the 190 * current size, the extraneous objects at the end are destructed. If the new 191 * capacity is larger than the current size, the new objects are 192 * default-constructed. 193 * 194 * @param newSize The new size of the vector. 195 * @return true if the resize operation was successful. 196 */ 197 bool resize(size_type newSize); 198 199 /** 200 * Inserts an element into the vector at a given index. If a resize of the 201 * vector is required and the allocation fails, false will be returned. This 202 * will shift all vector elements after the given index one position backward 203 * in the list. The supplied index must be <= the size of the vector. It is 204 * not possible to have a sparse list of items. If the index is > the current 205 * size of the vector, false will be returned. All iterators and references 206 * to and after the indexed element are invalidated. Iterators and references 207 * to before the indexed elements are unaffected if the container did not 208 * resize. 209 * 210 * @param index The index to insert an element at. 211 * @param element The element to insert. 212 * @return Whether or not the insert operation was successful. 213 */ 214 bool insert(size_type index, const ElementType &element); 215 bool insert(size_type index, ElementType &&element); 216 217 /** 218 * Removes an element from the vector given an index. All elements after the 219 * indexed one are moved forward one position. The destructor is invoked on 220 * on the invalid item left at the end of the vector. The index passed in 221 * must be less than the size() of the vector. If the index is greater than or 222 * equal to the size no operation is performed. All iterators and references 223 * to and after the indexed element are invalidated. 224 * 225 * @param index The index to remove an element at. 226 */ 227 void erase(size_type index); 228 229 /** 230 * Searches the vector for an element. 231 * 232 * @param element The element to comare against. 233 * @return The index of the element found. If the return is equal to size() 234 * then the element was not found. 235 */ 236 size_type find(const ElementType &element) const; 237 238 /** 239 * Swaps the location of two elements stored in the vector. The indices 240 * passed in must be less than the size() of the vector. If the index is 241 * greater than or equal to the size, no operation is performed. All 242 * iterators and references to these two indexed elements are invalidated. 243 * 244 * @param index0 The index of the first element 245 * @param index1 The index of the second element 246 */ 247 void swap(size_type index0, size_type index1); 248 249 /** 250 * Returns a reference to the first element in the vector. It is illegal to 251 * call this on an empty vector. 252 * 253 * @return The first element in the vector. 254 */ 255 ElementType &front(); 256 257 /** 258 * Returns a const reference to the first element in the vector. It is illegal 259 * to call this on an empty vector. 260 * 261 * @return The first element in the vector. 262 */ 263 const ElementType &front() const; 264 265 /** 266 * Returns a reference to the last element in the vector. It is illegal to 267 * call this on an empty vector. 268 * 269 * @return The last element in the vector. 270 */ 271 ElementType &back(); 272 273 /** 274 * Returns a const reference to the last element in the vector. It is illegal 275 * to call this on an empty vector. 276 * 277 * @return The last element in the vector. 278 */ 279 const ElementType &back() const; 280 281 /** 282 * Prepares a vector to push a minimum of one element onto the back. The 283 * vector may be resized if required. The capacity of the vector increases 284 * with the growth policy of this vector (doubles for each resize for now). 285 * 286 * @return Whether or not the resize was successful. 287 */ 288 bool prepareForPush(); 289 290 /** 291 * @return A random-access iterator to the beginning. 292 */ 293 typename DynamicVector<ElementType>::iterator begin(); 294 typename DynamicVector<ElementType>::const_iterator begin() const; 295 typename DynamicVector<ElementType>::const_iterator cbegin() const; 296 297 /** 298 * @return A random-access iterator to the end. 299 */ 300 typename DynamicVector<ElementType>::iterator end(); 301 typename DynamicVector<ElementType>::const_iterator end() const; 302 typename DynamicVector<ElementType>::const_iterator cend() const; 303 304 private: 305 /** 306 * Prepares the vector for insertion - upon successful return, the memory at 307 * the given index will be allocated but uninitialized 308 * 309 * @param index 310 * @return true 311 */ 312 bool prepareInsert(size_t index); 313 314 /** 315 * Performs the reserve operation for DynamicVector when ElementType is a 316 * trivial type. See {@link DynamicVector::reserve} for the rest of the 317 * details. 318 */ 319 bool doReserve(size_type newCapacity, std::true_type); 320 321 /** 322 * Performs the reserve operation for DynamicVector when ElementType is a 323 * non-trivial type. See {@link DynamicVector::reserve} for the rest of the 324 * details. 325 */ 326 bool doReserve(size_type newCapacity, std::false_type); 327 328 /** 329 * Performs the prepare for push operation for DynamicVector when ElementType 330 * is a trivial type. See {@link DynamicVector::prepareForPush} for the rest 331 * of the details. 332 */ 333 bool doPrepareForPush(std::true_type); 334 335 /** 336 * Performs the prepare for push operation for DynamicVector when ElementType 337 * is a non-trivial type. See {@link DynamicVector::prepareForPush} for the 338 * rest of the details. 339 */ 340 bool doPrepareForPush(std::false_type); 341 342 /** 343 * Performs the erase operation for DynamicVector when ElementType is a 344 * trivial type. See {@link DynamicVector::erase} for the rest of the details. 345 */ 346 void doErase(size_type index, std::true_type); 347 348 /** 349 * Performs the erase operation for DynamicVector when ElementType is a 350 * non-trivial type. See {@link DynamicVector::erase} for the rest of the 351 * details. 352 */ 353 void doErase(size_type index, std::false_type); 354 355 /** 356 * Performs the push back operation for DynamicVector when ElementType is a 357 * trivial type. See {@link DynamicVector::push_back} for the rest of the 358 * details. 359 */ 360 bool doPushBack(const ElementType &element, std::true_type); 361 362 /** 363 * Performs the push back operation for DynamicVector when ElementType is a 364 * non-trivial type. See {@link DynamicVector::push_back} for the rest of the 365 * details. 366 */ 367 bool doPushBack(const ElementType &element, std::false_type); 368 }; 369 370 } // namespace chre 371 372 #include "chre/util/dynamic_vector_impl.h" 373 374 #endif // CHRE_UTIL_DYNAMIC_VECTOR_H_ 375