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