1/* 2 * Copyright 2010 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#ifndef GrAllocator_DEFINED 9#define GrAllocator_DEFINED 10 11#include "GrConfig.h" 12#include "GrTypes.h" 13#include "SkTArray.h" 14#include "SkTypes.h" 15 16class GrAllocator : SkNoncopyable { 17public: 18 ~GrAllocator() { this->reset(); } 19 20 /** 21 * Create an allocator 22 * 23 * @param itemSize the size of each item to allocate 24 * @param itemsPerBlock the number of items to allocate at once 25 * @param initialBlock optional memory to use for the first block. 26 * Must be at least itemSize*itemsPerBlock sized. 27 * Caller is responsible for freeing this memory. 28 */ 29 GrAllocator(size_t itemSize, int itemsPerBlock, void* initialBlock) 30 : fItemSize(itemSize) 31 , fItemsPerBlock(itemsPerBlock) 32 , fOwnFirstBlock(nullptr == initialBlock) 33 , fCount(0) 34 , fInsertionIndexInBlock(0) { 35 SkASSERT(itemsPerBlock > 0); 36 fBlockSize = fItemSize * fItemsPerBlock; 37 if (fOwnFirstBlock) { 38 // This force us to allocate a new block on push_back(). 39 fInsertionIndexInBlock = fItemsPerBlock; 40 } else { 41 fBlocks.push_back() = initialBlock; 42 fInsertionIndexInBlock = 0; 43 } 44 } 45 46 /** 47 * Adds an item and returns pointer to it. 48 * 49 * @return pointer to the added item. 50 */ 51 void* push_back() { 52 // we always have at least one block 53 if (fItemsPerBlock == fInsertionIndexInBlock) { 54 fBlocks.push_back() = sk_malloc_throw(fBlockSize); 55 fInsertionIndexInBlock = 0; 56 } 57 void* ret = (char*)fBlocks.back() + fItemSize * fInsertionIndexInBlock; 58 ++fCount; 59 ++fInsertionIndexInBlock; 60 return ret; 61 } 62 63 /** 64 * Remove the last item, only call if count() != 0 65 */ 66 void pop_back() { 67 SkASSERT(fCount); 68 SkASSERT(fInsertionIndexInBlock > 0); 69 --fInsertionIndexInBlock; 70 --fCount; 71 if (0 == fInsertionIndexInBlock) { 72 // Never delete the first block 73 if (fBlocks.count() > 1) { 74 sk_free(fBlocks.back()); 75 fBlocks.pop_back(); 76 fInsertionIndexInBlock = fItemsPerBlock; 77 } 78 } 79 } 80 81 /** 82 * Removes all added items. 83 */ 84 void reset() { 85 int firstBlockToFree = fOwnFirstBlock ? 0 : 1; 86 for (int i = firstBlockToFree; i < fBlocks.count(); ++i) { 87 sk_free(fBlocks[i]); 88 } 89 if (fOwnFirstBlock) { 90 fBlocks.reset(); 91 // This force us to allocate a new block on push_back(). 92 fInsertionIndexInBlock = fItemsPerBlock; 93 } else { 94 fBlocks.pop_back_n(fBlocks.count() - 1); 95 fInsertionIndexInBlock = 0; 96 } 97 fCount = 0; 98 } 99 100 /** 101 * Returns the item count. 102 */ 103 int count() const { 104 return fCount; 105 } 106 107 /** 108 * Is the count 0? 109 */ 110 bool empty() const { return 0 == fCount; } 111 112 /** 113 * Access last item, only call if count() != 0 114 */ 115 void* back() { 116 SkASSERT(fCount); 117 SkASSERT(fInsertionIndexInBlock > 0); 118 return (char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize; 119 } 120 121 /** 122 * Access last item, only call if count() != 0 123 */ 124 const void* back() const { 125 SkASSERT(fCount); 126 SkASSERT(fInsertionIndexInBlock > 0); 127 return (const char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize; 128 } 129 130 /** 131 * Iterates through the allocator. This is faster than using operator[] when walking linearly 132 * through the allocator. 133 */ 134 class Iter { 135 public: 136 /** 137 * Initializes the iterator. next() must be called before get(). 138 */ 139 Iter(const GrAllocator* allocator) 140 : fAllocator(allocator) 141 , fBlockIndex(-1) 142 , fIndexInBlock(allocator->fItemsPerBlock - 1) 143 , fItemIndex(-1) {} 144 145 /** 146 * Advances the iterator. Iteration is finished when next() returns false. 147 */ 148 bool next() { 149 ++fIndexInBlock; 150 ++fItemIndex; 151 if (fIndexInBlock == fAllocator->fItemsPerBlock) { 152 ++fBlockIndex; 153 fIndexInBlock = 0; 154 } 155 return fItemIndex < fAllocator->fCount; 156 } 157 158 /** 159 * Gets the current iterator value. Call next() at least once before calling. Don't call 160 * after next() returns false. 161 */ 162 void* get() const { 163 SkASSERT(fItemIndex >= 0 && fItemIndex < fAllocator->fCount); 164 return (char*) fAllocator->fBlocks[fBlockIndex] + fIndexInBlock * fAllocator->fItemSize; 165 } 166 167 private: 168 const GrAllocator* fAllocator; 169 int fBlockIndex; 170 int fIndexInBlock; 171 int fItemIndex; 172 }; 173 174 /** 175 * Access item by index. 176 */ 177 void* operator[] (int i) { 178 SkASSERT(i >= 0 && i < fCount); 179 return (char*)fBlocks[i / fItemsPerBlock] + 180 fItemSize * (i % fItemsPerBlock); 181 } 182 183 /** 184 * Access item by index. 185 */ 186 const void* operator[] (int i) const { 187 SkASSERT(i >= 0 && i < fCount); 188 return (const char*)fBlocks[i / fItemsPerBlock] + 189 fItemSize * (i % fItemsPerBlock); 190 } 191 192protected: 193 /** 194 * Set first block of memory to write into. Must be called before any other methods. 195 * This requires that you have passed nullptr in the constructor. 196 * 197 * @param initialBlock optional memory to use for the first block. 198 * Must be at least itemSize*itemsPerBlock sized. 199 * Caller is responsible for freeing this memory. 200 */ 201 void setInitialBlock(void* initialBlock) { 202 SkASSERT(0 == fCount); 203 SkASSERT(0 == fBlocks.count()); 204 SkASSERT(fItemsPerBlock == fInsertionIndexInBlock); 205 fOwnFirstBlock = false; 206 fBlocks.push_back() = initialBlock; 207 fInsertionIndexInBlock = 0; 208 } 209 210 // For access to above function. 211 template <typename T> friend class GrTAllocator; 212 213private: 214 static const int NUM_INIT_BLOCK_PTRS = 8; 215 216 SkSTArray<NUM_INIT_BLOCK_PTRS, void*, true> fBlocks; 217 size_t fBlockSize; 218 size_t fItemSize; 219 int fItemsPerBlock; 220 bool fOwnFirstBlock; 221 int fCount; 222 int fInsertionIndexInBlock; 223 224 typedef SkNoncopyable INHERITED; 225}; 226 227template <typename T> class GrTAllocator; 228template <typename T> void* operator new(size_t, GrTAllocator<T>*); 229 230template <typename T> class GrTAllocator : SkNoncopyable { 231public: 232 virtual ~GrTAllocator() { this->reset(); } 233 234 /** 235 * Create an allocator 236 * 237 * @param itemsPerBlock the number of items to allocate at once 238 */ 239 explicit GrTAllocator(int itemsPerBlock) 240 : fAllocator(sizeof(T), itemsPerBlock, nullptr) {} 241 242 /** 243 * Adds an item and returns it. 244 * 245 * @return the added item. 246 */ 247 T& push_back() { 248 void* item = fAllocator.push_back(); 249 SkASSERT(item); 250 new (item) T; 251 return *(T*)item; 252 } 253 254 T& push_back(const T& t) { 255 void* item = fAllocator.push_back(); 256 SkASSERT(item); 257 new (item) T(t); 258 return *(T*)item; 259 } 260 261 template <typename... Args> T& emplace_back(Args&&... args) { 262 void* item = fAllocator.push_back(); 263 SkASSERT(item); 264 new (item) T(std::forward<Args>(args)...); 265 return *(T*)item; 266 } 267 268 /** 269 * Remove the last item, only call if count() != 0 270 */ 271 void pop_back() { 272 this->back().~T(); 273 fAllocator.pop_back(); 274 } 275 276 /** 277 * Removes all added items. 278 */ 279 void reset() { 280 int c = fAllocator.count(); 281 for (int i = 0; i < c; ++i) { 282 ((T*)fAllocator[i])->~T(); 283 } 284 fAllocator.reset(); 285 } 286 287 /** 288 * Returns the item count. 289 */ 290 int count() const { 291 return fAllocator.count(); 292 } 293 294 /** 295 * Is the count 0? 296 */ 297 bool empty() const { return fAllocator.empty(); } 298 299 /** 300 * Access last item, only call if count() != 0 301 */ 302 T& back() { 303 return *(T*)fAllocator.back(); 304 } 305 306 /** 307 * Access last item, only call if count() != 0 308 */ 309 const T& back() const { 310 return *(const T*)fAllocator.back(); 311 } 312 313 /** 314 * Iterates through the allocator. This is faster than using operator[] when walking linearly 315 * through the allocator. 316 */ 317 class Iter { 318 public: 319 /** 320 * Initializes the iterator. next() must be called before get() or ops * and ->. 321 */ 322 Iter(const GrTAllocator* allocator) : fImpl(&allocator->fAllocator) {} 323 324 /** 325 * Advances the iterator. Iteration is finished when next() returns false. 326 */ 327 bool next() { return fImpl.next(); } 328 329 /** 330 * Gets the current iterator value. Call next() at least once before calling. Don't call 331 * after next() returns false. 332 */ 333 T* get() const { return (T*) fImpl.get(); } 334 335 /** 336 * Convenience operators. Same rules for calling apply as get(). 337 */ 338 T& operator*() const { return *this->get(); } 339 T* operator->() const { return this->get(); } 340 341 private: 342 GrAllocator::Iter fImpl; 343 }; 344 345 /** 346 * Access item by index. 347 */ 348 T& operator[] (int i) { 349 return *(T*)(fAllocator[i]); 350 } 351 352 /** 353 * Access item by index. 354 */ 355 const T& operator[] (int i) const { 356 return *(const T*)(fAllocator[i]); 357 } 358 359protected: 360 /* 361 * Set first block of memory to write into. Must be called before any other methods. 362 * 363 * @param initialBlock optional memory to use for the first block. 364 * Must be at least size(T)*itemsPerBlock sized. 365 * Caller is responsible for freeing this memory. 366 */ 367 void setInitialBlock(void* initialBlock) { 368 fAllocator.setInitialBlock(initialBlock); 369 } 370 371private: 372 friend void* operator new<T>(size_t, GrTAllocator*); 373 374 GrAllocator fAllocator; 375 typedef SkNoncopyable INHERITED; 376}; 377 378template <int N, typename T> class GrSTAllocator : public GrTAllocator<T> { 379private: 380 typedef GrTAllocator<T> INHERITED; 381 382public: 383 GrSTAllocator() : INHERITED(N) { 384 this->setInitialBlock(fStorage.get()); 385 } 386 387private: 388 SkAlignedSTStorage<N, T> fStorage; 389}; 390 391template <typename T> void* operator new(size_t size, GrTAllocator<T>* allocator) { 392 return allocator->fAllocator.push_back(); 393} 394 395// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete 396// to match the op new silences warnings about missing op delete when a constructor throws an 397// exception. 398template <typename T> void operator delete(void*, GrTAllocator<T>*) { 399 SK_ABORT("Invalid Operation"); 400} 401 402#define GrNEW_APPEND_TO_ALLOCATOR(allocator_ptr, type_name, args) \ 403 new (allocator_ptr) type_name args 404 405#endif 406