SkDeque.cpp 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  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. #include "include/core/SkDeque.h"
  8. #include "include/private/SkMalloc.h"
  9. struct SkDeque::Block {
  10. Block* fNext;
  11. Block* fPrev;
  12. char* fBegin; // start of used section in this chunk
  13. char* fEnd; // end of used section in this chunk
  14. char* fStop; // end of the allocated chunk
  15. char* start() { return (char*)(this + 1); }
  16. const char* start() const { return (const char*)(this + 1); }
  17. void init(size_t size) {
  18. fNext = fPrev = nullptr;
  19. fBegin = fEnd = nullptr;
  20. fStop = (char*)this + size;
  21. }
  22. };
  23. SkDeque::SkDeque(size_t elemSize, int allocCount)
  24. : fElemSize(elemSize)
  25. , fInitialStorage(nullptr)
  26. , fCount(0)
  27. , fAllocCount(allocCount) {
  28. SkASSERT(allocCount >= 1);
  29. fFrontBlock = fBackBlock = nullptr;
  30. fFront = fBack = nullptr;
  31. }
  32. SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
  33. : fElemSize(elemSize)
  34. , fInitialStorage(storage)
  35. , fCount(0)
  36. , fAllocCount(allocCount) {
  37. SkASSERT(storageSize == 0 || storage != nullptr);
  38. SkASSERT(allocCount >= 1);
  39. if (storageSize >= sizeof(Block) + elemSize) {
  40. fFrontBlock = (Block*)storage;
  41. fFrontBlock->init(storageSize);
  42. } else {
  43. fFrontBlock = nullptr;
  44. }
  45. fBackBlock = fFrontBlock;
  46. fFront = fBack = nullptr;
  47. }
  48. SkDeque::~SkDeque() {
  49. Block* head = fFrontBlock;
  50. Block* initialHead = (Block*)fInitialStorage;
  51. while (head) {
  52. Block* next = head->fNext;
  53. if (head != initialHead) {
  54. this->freeBlock(head);
  55. }
  56. head = next;
  57. }
  58. }
  59. void* SkDeque::push_front() {
  60. fCount += 1;
  61. if (nullptr == fFrontBlock) {
  62. fFrontBlock = this->allocateBlock(fAllocCount);
  63. fBackBlock = fFrontBlock; // update our linklist
  64. }
  65. Block* first = fFrontBlock;
  66. char* begin;
  67. if (nullptr == first->fBegin) {
  68. INIT_CHUNK:
  69. first->fEnd = first->fStop;
  70. begin = first->fStop - fElemSize;
  71. } else {
  72. begin = first->fBegin - fElemSize;
  73. if (begin < first->start()) { // no more room in this chunk
  74. // should we alloc more as we accumulate more elements?
  75. first = this->allocateBlock(fAllocCount);
  76. first->fNext = fFrontBlock;
  77. fFrontBlock->fPrev = first;
  78. fFrontBlock = first;
  79. goto INIT_CHUNK;
  80. }
  81. }
  82. first->fBegin = begin;
  83. if (nullptr == fFront) {
  84. SkASSERT(nullptr == fBack);
  85. fFront = fBack = begin;
  86. } else {
  87. SkASSERT(fBack);
  88. fFront = begin;
  89. }
  90. return begin;
  91. }
  92. void* SkDeque::push_back() {
  93. fCount += 1;
  94. if (nullptr == fBackBlock) {
  95. fBackBlock = this->allocateBlock(fAllocCount);
  96. fFrontBlock = fBackBlock; // update our linklist
  97. }
  98. Block* last = fBackBlock;
  99. char* end;
  100. if (nullptr == last->fBegin) {
  101. INIT_CHUNK:
  102. last->fBegin = last->start();
  103. end = last->fBegin + fElemSize;
  104. } else {
  105. end = last->fEnd + fElemSize;
  106. if (end > last->fStop) { // no more room in this chunk
  107. // should we alloc more as we accumulate more elements?
  108. last = this->allocateBlock(fAllocCount);
  109. last->fPrev = fBackBlock;
  110. fBackBlock->fNext = last;
  111. fBackBlock = last;
  112. goto INIT_CHUNK;
  113. }
  114. }
  115. last->fEnd = end;
  116. end -= fElemSize;
  117. if (nullptr == fBack) {
  118. SkASSERT(nullptr == fFront);
  119. fFront = fBack = end;
  120. } else {
  121. SkASSERT(fFront);
  122. fBack = end;
  123. }
  124. return end;
  125. }
  126. void SkDeque::pop_front() {
  127. SkASSERT(fCount > 0);
  128. fCount -= 1;
  129. Block* first = fFrontBlock;
  130. SkASSERT(first != nullptr);
  131. if (first->fBegin == nullptr) { // we were marked empty from before
  132. first = first->fNext;
  133. SkASSERT(first != nullptr); // else we popped too far
  134. first->fPrev = nullptr;
  135. this->freeBlock(fFrontBlock);
  136. fFrontBlock = first;
  137. }
  138. char* begin = first->fBegin + fElemSize;
  139. SkASSERT(begin <= first->fEnd);
  140. if (begin < fFrontBlock->fEnd) {
  141. first->fBegin = begin;
  142. SkASSERT(first->fBegin);
  143. fFront = first->fBegin;
  144. } else {
  145. first->fBegin = first->fEnd = nullptr; // mark as empty
  146. if (nullptr == first->fNext) {
  147. fFront = fBack = nullptr;
  148. } else {
  149. SkASSERT(first->fNext->fBegin);
  150. fFront = first->fNext->fBegin;
  151. }
  152. }
  153. }
  154. void SkDeque::pop_back() {
  155. SkASSERT(fCount > 0);
  156. fCount -= 1;
  157. Block* last = fBackBlock;
  158. SkASSERT(last != nullptr);
  159. if (last->fEnd == nullptr) { // we were marked empty from before
  160. last = last->fPrev;
  161. SkASSERT(last != nullptr); // else we popped too far
  162. last->fNext = nullptr;
  163. this->freeBlock(fBackBlock);
  164. fBackBlock = last;
  165. }
  166. char* end = last->fEnd - fElemSize;
  167. SkASSERT(end >= last->fBegin);
  168. if (end > last->fBegin) {
  169. last->fEnd = end;
  170. SkASSERT(last->fEnd);
  171. fBack = last->fEnd - fElemSize;
  172. } else {
  173. last->fBegin = last->fEnd = nullptr; // mark as empty
  174. if (nullptr == last->fPrev) {
  175. fFront = fBack = nullptr;
  176. } else {
  177. SkASSERT(last->fPrev->fEnd);
  178. fBack = last->fPrev->fEnd - fElemSize;
  179. }
  180. }
  181. }
  182. int SkDeque::numBlocksAllocated() const {
  183. int numBlocks = 0;
  184. for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
  185. ++numBlocks;
  186. }
  187. return numBlocks;
  188. }
  189. SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
  190. Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
  191. newBlock->init(sizeof(Block) + allocCount * fElemSize);
  192. return newBlock;
  193. }
  194. void SkDeque::freeBlock(Block* block) {
  195. sk_free(block);
  196. }
  197. ///////////////////////////////////////////////////////////////////////////////
  198. SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {}
  199. SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
  200. this->reset(d, startLoc);
  201. }
  202. // Due to how reset and next work, next actually returns the current element
  203. // pointed to by fPos and then updates fPos to point to the next one.
  204. void* SkDeque::Iter::next() {
  205. char* pos = fPos;
  206. if (pos) { // if we were valid, try to move to the next setting
  207. char* next = pos + fElemSize;
  208. SkASSERT(next <= fCurBlock->fEnd);
  209. if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
  210. do {
  211. fCurBlock = fCurBlock->fNext;
  212. } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr);
  213. next = fCurBlock ? fCurBlock->fBegin : nullptr;
  214. }
  215. fPos = next;
  216. }
  217. return pos;
  218. }
  219. // Like next, prev actually returns the current element pointed to by fPos and
  220. // then makes fPos point to the previous element.
  221. void* SkDeque::Iter::prev() {
  222. char* pos = fPos;
  223. if (pos) { // if we were valid, try to move to the prior setting
  224. char* prev = pos - fElemSize;
  225. SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
  226. if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
  227. do {
  228. fCurBlock = fCurBlock->fPrev;
  229. } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr);
  230. prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
  231. }
  232. fPos = prev;
  233. }
  234. return pos;
  235. }
  236. // reset works by skipping through the spare blocks at the start (or end)
  237. // of the doubly linked list until a non-empty one is found. The fPos
  238. // member is then set to the first (or last) element in the block. If
  239. // there are no elements in the deque both fCurBlock and fPos will come
  240. // out of this routine nullptr.
  241. void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
  242. fElemSize = d.fElemSize;
  243. if (kFront_IterStart == startLoc) {
  244. // initialize the iterator to start at the front
  245. fCurBlock = d.fFrontBlock;
  246. while (fCurBlock && nullptr == fCurBlock->fBegin) {
  247. fCurBlock = fCurBlock->fNext;
  248. }
  249. fPos = fCurBlock ? fCurBlock->fBegin : nullptr;
  250. } else {
  251. // initialize the iterator to start at the back
  252. fCurBlock = d.fBackBlock;
  253. while (fCurBlock && nullptr == fCurBlock->fEnd) {
  254. fCurBlock = fCurBlock->fPrev;
  255. }
  256. fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
  257. }
  258. }