GrAllocator.h 12 KB

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