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