1// Copyright 2014 The Android Open Source Project 2// 3// This software is licensed under the terms of the GNU General Public 4// License version 2, as published by the Free Software Foundation, and 5// may be copied, distributed, and modified under those terms. 6// 7// This program is distributed in the hope that it will be useful, 8// but WITHOUT ANY WARRANTY; without even the implied warranty of 9// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10// GNU General Public License for more details. 11 12#ifndef ANDROID_BASE_CONTAINERS_POD_VECTOR_H 13#define ANDROID_BASE_CONTAINERS_POD_VECTOR_H 14 15#include <android/base/Limits.h> 16#include <android/base/Log.h> 17 18#include <stddef.h> 19#include <stdint.h> 20 21namespace android { 22namespace base { 23 24// A PodVector is a templated vector-like type that is used to store 25// POD-struct compatible items only. This allows the implementation to 26// use ::memmove() to move items, and also malloc_usable_size() to 27// determine the best capacity. 28// 29// std::vector<> is capable of doing this in theory, using horrible 30// templating tricks that make error messages very difficult to 31// understand. 32// 33// Note that a PodVector can be used to store items that contain pointers, 34// as long as these do not point to items in the same container. 35// 36// The PodVector provides methods that also follow the std::vector<> 37// conventions, i.e. push_back() is an alias for append(). 38// 39 40// PodVectorBase is a base, non-templated, implementation class that all 41// PodVector instances derive from. This is used to reduce template 42// specialization. Do not use directly, i..e it's an implementation detail. 43class PodVectorBase { 44protected: 45 PodVectorBase() : mBegin(NULL), mEnd(NULL), mLimit(NULL) {} 46 explicit PodVectorBase(const PodVectorBase& other); 47 PodVectorBase& operator=(const PodVectorBase& other); 48 ~PodVectorBase(); 49 50 bool empty() const { return mEnd == mBegin; } 51 52 size_t byteSize() const { return mEnd - mBegin; } 53 54 size_t byteCapacity() const { return mLimit - mBegin; } 55 56 void* begin() { return mBegin; } 57 const void* begin() const { return mBegin; } 58 void* end() { return mEnd; } 59 const void* end() const { return mEnd; } 60 61 void* itemAt(size_t pos, size_t itemSize) { 62 const size_t kMaxCapacity = SIZE_MAX / itemSize; 63 DCHECK(pos <= kMaxCapacity); 64 return mBegin + pos * itemSize; 65 } 66 67 const void* itemAt(size_t pos, size_t itemSize) const { 68 const size_t kMaxCapacity = SIZE_MAX / itemSize; 69 DCHECK(pos <= kMaxCapacity); 70 return mBegin + pos * itemSize; 71 } 72 73 void assignFrom(const PodVectorBase& other); 74 75 inline size_t itemCount(size_t itemSize) const { 76 DCHECK(itemSize > 0) << "Item size cannot be 0!"; 77 return byteSize() / itemSize; 78 } 79 80 inline size_t itemCapacity(size_t itemSize) const { 81 DCHECK(itemSize > 0) << "Item size cannot be 0!"; 82 return byteCapacity() / itemSize; 83 } 84 85 inline size_t maxItemCapacity(size_t itemSize) const { 86 DCHECK(itemSize > 0) << "Item size cannot be 0!"; 87 return SIZE_MAX / itemSize; 88 } 89 90 void resize(size_t newSize, size_t itemSize); 91 void reserve(size_t newSize, size_t itemSize); 92 93 void removeAt(size_t index, size_t itemSize); 94 void* insertAt(size_t index, size_t itemSize); 95 void swapAll(PodVectorBase* other); 96 97 char* mBegin; 98 char* mEnd; 99 char* mLimit; 100 101private: 102 void initFrom(const void* from, size_t fromLen); 103}; 104 105 106// A PodVector<T> holds a vector (dynamically resizable array) or items 107// that must be POD-struct compatible (i.e. they cannot have constructors, 108// destructors, or virtual members). This allows the implementation to be 109// small, fast and efficient, memory-wise. 110// 111// If you want to implement a vector of C++ objects, consider using 112// std::vector<> instead, but keep in mind that this implies a non-trivial 113// cost when appending, inserting, removing items in the collection. 114// 115template <typename T> 116class PodVector : public PodVectorBase { 117public: 118 // Default constructor for an empty PodVector<T> 119 PodVector() : PodVectorBase() {} 120 121 // Copy constructor. This copies all items from |other| into 122 // the new instance with ::memmove(). 123 PodVector(const PodVector& other) : PodVectorBase(other) {} 124 125 // Assignment operator. 126 PodVector& operator=(const PodVector& other) { 127 this->assignFrom(other); 128 return *this; 129 } 130 131 // Destructor, this simply releases the internal storage block that 132 // holds all the items, but doesn't touch them otherwise. 133 ~PodVector() {} 134 135 // Return true iff the PodVector<T> instance is empty, i.e. does not 136 // have any items. 137 bool empty() const { return PodVectorBase::empty(); } 138 139 // Return the number of items in the current PodVector<T> instance. 140 size_t size() const { return PodVectorBase::itemCount(sizeof(T)); } 141 142 // Return the current capacity in the current PodVector<T> instance. 143 // Do not use directly, except if you know what you're doing. Try to 144 // use resize() or reserve() instead. 145 size_t capacity() const { 146 return PodVectorBase::itemCapacity(sizeof(T)); 147 } 148 149 // Return the maximum capacity of any PodVector<T> instance. 150 static inline size_t maxCapacity() { return SIZE_MAX / sizeof(T); } 151 152 // Resize the vector to ensure it can hold |newSize| 153 // items. This may or may not call reserve() under the hood. 154 // It's a fatal error to try to resize above maxCapacity(). 155 void resize(size_t newSize) { 156 PodVectorBase::resize(newSize, sizeof(T)); 157 } 158 159 // Resize the vector's storage array to ensure that it can hold at 160 // least |newSize| items. It's a fatal error to try to resize above 161 // maxCapacity(). 162 void reserve(size_t newSize) { 163 PodVectorBase::reserve(newSize, sizeof(T)); 164 } 165 166 // Return a pointer to the first item in the vector. This is only 167 // valid until the next call to any function that changes the size 168 // or capacity of the vector. Can be NULL if the vector is empty. 169 T* begin() { 170 return reinterpret_cast<T*>(PodVectorBase::begin()); 171 } 172 173 // Return a constant pointer to the first item in the vector. This is 174 // only valid until the next call to any function that changes the 175 // size of capacity of the vector. 176 const T* begin() const { 177 return reinterpret_cast<T*>(PodVectorBase::begin()); 178 } 179 180 // Return a pointer past the last item in the vector. I.e. if the 181 // result is not NULL, then |result - 1| points to the last item. 182 // Can be NULL if the vector is empty. 183 T* end() { 184 return reinterpret_cast<T*>(PodVectorBase::end()); 185 } 186 187 // Return a constant pointer past the last item in the vector. I.e. if 188 // the result is not NULL, then |result - 1| points to the last item. 189 // Can be NULL if the vector is empty. 190 const T* end() const { 191 return reinterpret_cast<T*>(PodVectorBase::end()); 192 } 193 194 // Returns a reference to the item a position |index| in the vector. 195 // It may be a fatal error to access an out-of-bounds position. 196 T& operator[](size_t index) { 197 return *reinterpret_cast<T*>( 198 PodVectorBase::itemAt(index, sizeof(T))); 199 } 200 201 const T& operator[](size_t index) const { 202 return *reinterpret_cast<const T*>( 203 PodVectorBase::itemAt(index, sizeof(T))); 204 } 205 206 // Increase the vector's size by 1, then move all items past a given 207 // position to the right. Return the position of the insertion point 208 // to let the caller copy the content it desires there. It's preferrable 209 // to use insert() directly, which will do the item copy for you. 210 T* emplace(size_t index) { 211 return reinterpret_cast<T*>( 212 PodVectorBase::insertAt(index, sizeof(T))); 213 } 214 215 // Insert an item at a given position. |index| is the insertion position 216 // which must be between 0 and size() included, or a fatal error may 217 // occur. |item| is a reference to an item to copy into the array, 218 // byte-by-byte. 219 void insert(size_t index, const T& item) { 220 *(this->emplace(index)) = item; 221 } 222 223 // Prepend an item at the start of a vector. This moves all vector items 224 // to the right, and is thus costly. |item| is a reference to an item 225 // to copy to the start of the vector. 226 void prepend(const T& item) { 227 *(this->emplace(0U)) = item; 228 } 229 230 // Append an item at the end of a vector. Specialized version of insert() 231 // which always uses size() as the insertion position. 232 void append(const T& item) { 233 *(this->emplace(this->size())) = item; 234 } 235 236 // Remove the item at a given position. |index| is the position of the 237 // item to delete. It must be between 0 and size(), included, or 238 // a fatal error may occur. Deleting the item at position size() 239 // doesn't do anything. 240 void remove(size_t index) { 241 PodVectorBase::removeAt(index, sizeof(T)); 242 } 243 244 void swap(PodVector* other) { 245 PodVectorBase::swapAll(other); 246 } 247 248 // Compatibility methods for std::vector<> 249 void push_back(const T& item) { append(item); } 250 void pop() { remove(0U); } 251 252 typedef T* iterator; 253 typedef const T* const_iterator; 254}; 255 256} // namespace base 257} // namespace android 258 259 260#endif // ANDROID_BASE_VECTOR_H 261