dynamic_vector.h revision 90c04ef3564eb228eebb5da5b21bb80e5e46e299
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 * Destructs the objects and releases the memory owned by the vector. 35 */ 36 ~DynamicVector(); 37 38 /** 39 * Returns a pointer to the underlying buffer. Note that this should not be 40 * considered to be persistent as the vector will be moved and resized 41 * automatically. 42 * 43 * @return the pointer to the underlying buffer. 44 */ 45 ElementType *data(); 46 47 /** 48 * Returns a const pointer to the underlying buffer. Note that this should not 49 * be considered to be persistent as the vector will be moved and resized 50 * automatically. 51 * 52 * @return the const pointer to the underlying buffer. 53 */ 54 const ElementType *data() const; 55 56 /** 57 * Returns the current number of elements in the vector. 58 * 59 * @return the number of elements in the vector. 60 */ 61 size_t size() const; 62 63 /** 64 * Returns the maximum number of elements that can be stored in this vector 65 * without a resize operation. 66 * 67 * @return the capacity of the vector. 68 */ 69 size_t capacity() const; 70 71 /** 72 * Determines whether the vector is empty or not. 73 * 74 * @return Returns true if the vector is empty. 75 */ 76 bool empty() const; 77 78 /** 79 * Pushes an element onto the back of the vector. If the vector requires a 80 * resize and that allocation fails this function will return false. 81 * 82 * @param The element to push onto the vector. 83 * @return Returns true if the element was pushed successfully. 84 */ 85 bool push_back(const ElementType& element); 86 87 /** 88 * Moves an element onto the back of the vector. If the vector requires a 89 * resize and that allocation fails this function will return false. 90 * 91 * @param The element to move onto the vector. 92 * @return Returns true if the element was moved successfully. 93 */ 94 bool push_back(ElementType&& element); 95 96 /** 97 * Constructs an element onto the back of the vector. It is illegal to 98 * construct an item onto a full vector. The user of the API must check the 99 * return of the full() function prior to constructing another element. 100 * 101 * @param The arguments to the constructor 102 */ 103 template<typename... Args> 104 bool emplace_back(Args&&... args); 105 106 /** 107 * Obtains an element of the vector given an index. It is illegal to index 108 * this vector out of bounds and the user of the API must check the size() 109 * function prior to indexing this vector to ensure that they will not read 110 * out of bounds. 111 * 112 * @param The index of the element. 113 * @return The element. 114 */ 115 ElementType& operator[](size_t index); 116 117 /** 118 * Obtains a const element of the vector given an index. It is illegal to 119 * index this vector out of bounds and the user of the API must check the 120 * size() function prior to indexing this vector to ensure that they will not 121 * read out of bounds. 122 * 123 * @param The index of the element. 124 * @return The element. 125 */ 126 const ElementType& operator[](size_t index) const; 127 128 /** 129 * Resizes the vector to a new capacity returning true if allocation was 130 * successful. If the new capacity is smaller than the current capacity, 131 * the operation is a no-op and true is returned. If a memory allocation 132 * fails, the contents of the vector are not modified and false is returned. 133 * This is intended to be similar to the reserve function of the std::vector. 134 * 135 * @param The new capacity of the vector. 136 * @return True if the resize operation was successful. 137 */ 138 bool reserve(size_t newCapacity); 139 140 /** 141 * Inserts an element into the vector at a given index. If a resize of the 142 * vector is required and the allocation fails, false will be returned. This 143 * will shift all vector elements after the given index one position backward 144 * in the list. The supplied index must be <= the size of the vector. It is 145 * not possible to have a sparse list of items. If the index is > the current 146 * size of the vector, false will be returned. 147 * 148 * @param index The index to insert an element at. 149 * @param element The element to insert. 150 * @return Whether or not the insert operation was successful. 151 */ 152 bool insert(size_t index, const ElementType& element); 153 154 /** 155 * Removes an element from the vector given an index. All elements after the 156 * indexed one are moved forward one position. The destructor is invoked on 157 * on the invalid item left at the end of the vector. The index passed in 158 * must be less than the size() of the vector. If the index is greater than or 159 * equal to the size no operation is performed. 160 * 161 * @param index The index to remove an element at. 162 */ 163 void erase(size_t index); 164 165 /** 166 * Searches the vector for an element. 167 * 168 * @param element The element to comare against. 169 * @return The index of the element found. If the return is equal to size() 170 * then the element was not found. 171 */ 172 size_t find(const ElementType& element) const; 173 174 /** 175 * Swaps the location of two elements stored in the vector. The indices 176 * passed in must be less than the size() of the vector. If the index is 177 * greater than or equal to the size, no operation is performed. 178 * 179 * @param index0 The index of the first element 180 * @param index1 The index of the second element 181 */ 182 void swap(size_t index0, size_t index1); 183 184 /** 185 * Returns a reference to the last element in the vector. It is illegal to 186 * call this on an empty vector. 187 * 188 * @return The last element in the vector. 189 */ 190 ElementType& back(); 191 192 /** 193 * Returns a const reference to the last element in the vector. It is illegal 194 * to call this on an empty vector. 195 * 196 * @return The last element in the vector. 197 */ 198 const ElementType& back() const; 199 200 /** 201 * Random-access iterator that points to some element in the container. 202 */ 203 typedef ElementType* iterator; 204 typedef const ElementType* const_iterator; 205 206 /** 207 * @return A random-access iterator to the beginning. 208 */ 209 typename DynamicVector<ElementType>::iterator begin(); 210 typename DynamicVector<ElementType>::const_iterator begin() const; 211 212 /** 213 * @return A random-access iterator to the end. 214 */ 215 typename DynamicVector<ElementType>::iterator end(); 216 typename DynamicVector<ElementType>::const_iterator end() const; 217 218 private: 219 //! A pointer to the underlying data buffer. 220 ElementType *mData = nullptr; 221 222 //! The current size of the vector, as in the number of elements stored. 223 size_t mSize = 0; 224 225 //! The current capacity of the vector, as in the maximum number of elements 226 //! that can be stored. 227 size_t mCapacity = 0; 228 229 /** 230 * Prepares a vector to push one element onto the back. The vector may be 231 * resized if required. 232 * 233 * @return Whether or not the resize was successful. 234 */ 235 bool prepareForPush(); 236}; 237 238} // namespace chre 239 240#include "chre/util/dynamic_vector_impl.h" 241 242#endif // CHRE_UTIL_DYNAMIC_VECTOR_H_ 243