epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
| 2 | /* |
| 3 | * Copyright 2006 The Android Open Source Project |
| 4 | * |
| 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
| 7 | */ |
| 8 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 9 | |
| 10 | #include "SkDeque.h" |
| 11 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 12 | struct SkDeque::Block { |
| 13 | Block* fNext; |
| 14 | Block* fPrev; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 15 | char* fBegin; // start of used section in this chunk |
| 16 | char* fEnd; // end of used section in this chunk |
| 17 | char* fStop; // end of the allocated chunk |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 18 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 19 | char* start() { return (char*)(this + 1); } |
| 20 | const char* start() const { return (const char*)(this + 1); } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 21 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 22 | void init(size_t size) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 23 | fNext = fPrev = nullptr; |
| 24 | fBegin = fEnd = nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 25 | fStop = (char*)this + size; |
| 26 | } |
| 27 | }; |
| 28 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 29 | SkDeque::SkDeque(size_t elemSize, int allocCount) |
| 30 | : fElemSize(elemSize) |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 31 | , fInitialStorage(nullptr) |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 32 | , fCount(0) |
| 33 | , fAllocCount(allocCount) { |
| 34 | SkASSERT(allocCount >= 1); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 35 | fFrontBlock = fBackBlock = nullptr; |
| 36 | fFront = fBack = nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 37 | } |
| 38 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 39 | SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) |
| 40 | : fElemSize(elemSize) |
| 41 | , fInitialStorage(storage) |
| 42 | , fCount(0) |
| 43 | , fAllocCount(allocCount) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 44 | SkASSERT(storageSize == 0 || storage != nullptr); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 45 | SkASSERT(allocCount >= 1); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 46 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 47 | if (storageSize >= sizeof(Block) + elemSize) { |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 48 | fFrontBlock = (Block*)storage; |
| 49 | fFrontBlock->init(storageSize); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 50 | } else { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 51 | fFrontBlock = nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 52 | } |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 53 | fBackBlock = fFrontBlock; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 54 | fFront = fBack = nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 55 | } |
| 56 | |
| 57 | SkDeque::~SkDeque() { |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 58 | Block* head = fFrontBlock; |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 59 | Block* initialHead = (Block*)fInitialStorage; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 60 | |
| 61 | while (head) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 62 | Block* next = head->fNext; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 63 | if (head != initialHead) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 64 | this->freeBlock(head); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 65 | } |
| 66 | head = next; |
| 67 | } |
| 68 | } |
| 69 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 70 | void* SkDeque::push_front() { |
| 71 | fCount += 1; |
| 72 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 73 | if (nullptr == fFrontBlock) { |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 74 | fFrontBlock = this->allocateBlock(fAllocCount); |
| 75 | fBackBlock = fFrontBlock; // update our linklist |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 76 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 77 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 78 | Block* first = fFrontBlock; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 79 | char* begin; |
| 80 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 81 | if (nullptr == first->fBegin) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 82 | INIT_CHUNK: |
| 83 | first->fEnd = first->fStop; |
| 84 | begin = first->fStop - fElemSize; |
| 85 | } else { |
| 86 | begin = first->fBegin - fElemSize; |
| 87 | if (begin < first->start()) { // no more room in this chunk |
| 88 | // should we alloc more as we accumulate more elements? |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 89 | first = this->allocateBlock(fAllocCount); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 90 | first->fNext = fFrontBlock; |
| 91 | fFrontBlock->fPrev = first; |
| 92 | fFrontBlock = first; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 93 | goto INIT_CHUNK; |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | first->fBegin = begin; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 98 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 99 | if (nullptr == fFront) { |
| 100 | SkASSERT(nullptr == fBack); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 101 | fFront = fBack = begin; |
| 102 | } else { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 103 | SkASSERT(fBack); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 104 | fFront = begin; |
| 105 | } |
| 106 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 107 | return begin; |
| 108 | } |
| 109 | |
| 110 | void* SkDeque::push_back() { |
| 111 | fCount += 1; |
| 112 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 113 | if (nullptr == fBackBlock) { |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 114 | fBackBlock = this->allocateBlock(fAllocCount); |
| 115 | fFrontBlock = fBackBlock; // update our linklist |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 116 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 117 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 118 | Block* last = fBackBlock; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 119 | char* end; |
| 120 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 121 | if (nullptr == last->fBegin) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 122 | INIT_CHUNK: |
| 123 | last->fBegin = last->start(); |
| 124 | end = last->fBegin + fElemSize; |
| 125 | } else { |
| 126 | end = last->fEnd + fElemSize; |
| 127 | if (end > last->fStop) { // no more room in this chunk |
| 128 | // should we alloc more as we accumulate more elements? |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 129 | last = this->allocateBlock(fAllocCount); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 130 | last->fPrev = fBackBlock; |
| 131 | fBackBlock->fNext = last; |
| 132 | fBackBlock = last; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 133 | goto INIT_CHUNK; |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | last->fEnd = end; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 138 | end -= fElemSize; |
| 139 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 140 | if (nullptr == fBack) { |
| 141 | SkASSERT(nullptr == fFront); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 142 | fFront = fBack = end; |
| 143 | } else { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 144 | SkASSERT(fFront); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 145 | fBack = end; |
| 146 | } |
| 147 | |
| 148 | return end; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 149 | } |
| 150 | |
| 151 | void SkDeque::pop_front() { |
| 152 | SkASSERT(fCount > 0); |
| 153 | fCount -= 1; |
| 154 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 155 | Block* first = fFrontBlock; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 156 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 157 | SkASSERT(first != nullptr); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 158 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 159 | if (first->fBegin == nullptr) { // we were marked empty from before |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 160 | first = first->fNext; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 161 | first->fPrev = nullptr; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 162 | this->freeBlock(fFrontBlock); |
| 163 | fFrontBlock = first; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 164 | SkASSERT(first != nullptr); // else we popped too far |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 165 | } |
| 166 | |
| 167 | char* begin = first->fBegin + fElemSize; |
| 168 | SkASSERT(begin <= first->fEnd); |
| 169 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 170 | if (begin < fFrontBlock->fEnd) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 171 | first->fBegin = begin; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 172 | SkASSERT(first->fBegin); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 173 | fFront = first->fBegin; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 174 | } else { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 175 | first->fBegin = first->fEnd = nullptr; // mark as empty |
| 176 | if (nullptr == first->fNext) { |
| 177 | fFront = fBack = nullptr; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 178 | } else { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 179 | SkASSERT(first->fNext->fBegin); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 180 | fFront = first->fNext->fBegin; |
| 181 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 182 | } |
| 183 | } |
| 184 | |
| 185 | void SkDeque::pop_back() { |
| 186 | SkASSERT(fCount > 0); |
| 187 | fCount -= 1; |
| 188 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 189 | Block* last = fBackBlock; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 190 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 191 | SkASSERT(last != nullptr); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 192 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 193 | if (last->fEnd == nullptr) { // we were marked empty from before |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 194 | last = last->fPrev; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 195 | last->fNext = nullptr; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 196 | this->freeBlock(fBackBlock); |
| 197 | fBackBlock = last; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 198 | SkASSERT(last != nullptr); // else we popped too far |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 199 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 200 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 201 | char* end = last->fEnd - fElemSize; |
| 202 | SkASSERT(end >= last->fBegin); |
| 203 | |
| 204 | if (end > last->fBegin) { |
| 205 | last->fEnd = end; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 206 | SkASSERT(last->fEnd); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 207 | fBack = last->fEnd - fElemSize; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 208 | } else { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 209 | last->fBegin = last->fEnd = nullptr; // mark as empty |
| 210 | if (nullptr == last->fPrev) { |
| 211 | fFront = fBack = nullptr; |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 212 | } else { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 213 | SkASSERT(last->fPrev->fEnd); |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 214 | fBack = last->fPrev->fEnd - fElemSize; |
| 215 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 216 | } |
| 217 | } |
| 218 | |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 219 | int SkDeque::numBlocksAllocated() const { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 220 | int numBlocks = 0; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 221 | |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 222 | for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 223 | ++numBlocks; |
| 224 | } |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame] | 225 | |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 226 | return numBlocks; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 227 | } |
| 228 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 229 | SkDeque::Block* SkDeque::allocateBlock(int allocCount) { |
| 230 | Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); |
| 231 | newBlock->init(sizeof(Block) + allocCount * fElemSize); |
| 232 | return newBlock; |
| 233 | } |
| 234 | |
| 235 | void SkDeque::freeBlock(Block* block) { |
| 236 | sk_free(block); |
| 237 | } |
| 238 | |
| 239 | /////////////////////////////////////////////////////////////////////////////// |
| 240 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 241 | SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {} |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 242 | |
| 243 | SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { |
| 244 | this->reset(d, startLoc); |
| 245 | } |
| 246 | |
| 247 | // Due to how reset and next work, next actually returns the current element |
| 248 | // pointed to by fPos and then updates fPos to point to the next one. |
| 249 | void* SkDeque::Iter::next() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 250 | char* pos = fPos; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 251 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 252 | if (pos) { // if we were valid, try to move to the next setting |
| 253 | char* next = pos + fElemSize; |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 254 | SkASSERT(next <= fCurBlock->fEnd); |
| 255 | if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 256 | do { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 257 | fCurBlock = fCurBlock->fNext; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 258 | } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr); |
| 259 | next = fCurBlock ? fCurBlock->fBegin : nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 260 | } |
| 261 | fPos = next; |
| 262 | } |
| 263 | return pos; |
| 264 | } |
| 265 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 266 | // Like next, prev actually returns the current element pointed to by fPos and |
| 267 | // then makes fPos point to the previous element. |
| 268 | void* SkDeque::Iter::prev() { |
| 269 | char* pos = fPos; |
| 270 | |
| 271 | if (pos) { // if we were valid, try to move to the prior setting |
| 272 | char* prev = pos - fElemSize; |
| 273 | SkASSERT(prev >= fCurBlock->fBegin - fElemSize); |
| 274 | if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior |
| 275 | do { |
| 276 | fCurBlock = fCurBlock->fPrev; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 277 | } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr); |
| 278 | prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 279 | } |
| 280 | fPos = prev; |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame] | 281 | } |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 282 | return pos; |
| 283 | } |
| 284 | |
| 285 | // reset works by skipping through the spare blocks at the start (or end) |
| 286 | // of the doubly linked list until a non-empty one is found. The fPos |
| 287 | // member is then set to the first (or last) element in the block. If |
| 288 | // there are no elements in the deque both fCurBlock and fPos will come |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 289 | // out of this routine nullptr. |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 290 | void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { |
| 291 | fElemSize = d.fElemSize; |
| 292 | |
| 293 | if (kFront_IterStart == startLoc) { |
| 294 | // initialize the iterator to start at the front |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 295 | fCurBlock = d.fFrontBlock; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 296 | while (fCurBlock && nullptr == fCurBlock->fBegin) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 297 | fCurBlock = fCurBlock->fNext; |
| 298 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 299 | fPos = fCurBlock ? fCurBlock->fBegin : nullptr; |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 300 | } else { |
| 301 | // initialize the iterator to start at the back |
robertphillips@google.com | 63ae1cf | 2012-08-17 13:53:05 +0000 | [diff] [blame] | 302 | fCurBlock = d.fBackBlock; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 303 | while (fCurBlock && nullptr == fCurBlock->fEnd) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 304 | fCurBlock = fCurBlock->fPrev; |
| 305 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame^] | 306 | fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 307 | } |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame] | 308 | } |