The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/core/SkDeque.cpp
gfx/skia/trunk/src/core/SkDeque.cpp
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d92fa0e74674 |
|---|---|
| 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 | |
| 9 | |
| 10 #include "SkDeque.h" | |
| 11 | |
| 12 struct SkDeque::Block { | |
| 13 Block* fNext; | |
| 14 Block* fPrev; | |
| 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 | |
| 18 | |
| 19 char* start() { return (char*)(this + 1); } | |
| 20 const char* start() const { return (const char*)(this + 1); } | |
| 21 | |
| 22 void init(size_t size) { | |
| 23 fNext = fPrev = NULL; | |
| 24 fBegin = fEnd = NULL; | |
| 25 fStop = (char*)this + size; | |
| 26 } | |
| 27 }; | |
| 28 | |
| 29 SkDeque::SkDeque(size_t elemSize, int allocCount) | |
| 30 : fElemSize(elemSize) | |
| 31 , fInitialStorage(NULL) | |
| 32 , fCount(0) | |
| 33 , fAllocCount(allocCount) { | |
| 34 SkASSERT(allocCount >= 1); | |
| 35 fFrontBlock = fBackBlock = NULL; | |
| 36 fFront = fBack = NULL; | |
| 37 } | |
| 38 | |
| 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) { | |
| 44 SkASSERT(storageSize == 0 || storage != NULL); | |
| 45 SkASSERT(allocCount >= 1); | |
| 46 | |
| 47 if (storageSize >= sizeof(Block) + elemSize) { | |
| 48 fFrontBlock = (Block*)storage; | |
| 49 fFrontBlock->init(storageSize); | |
| 50 } else { | |
| 51 fFrontBlock = NULL; | |
| 52 } | |
| 53 fBackBlock = fFrontBlock; | |
| 54 fFront = fBack = NULL; | |
| 55 } | |
| 56 | |
| 57 SkDeque::~SkDeque() { | |
| 58 Block* head = fFrontBlock; | |
| 59 Block* initialHead = (Block*)fInitialStorage; | |
| 60 | |
| 61 while (head) { | |
| 62 Block* next = head->fNext; | |
| 63 if (head != initialHead) { | |
| 64 this->freeBlock(head); | |
| 65 } | |
| 66 head = next; | |
| 67 } | |
| 68 } | |
| 69 | |
| 70 void* SkDeque::push_front() { | |
| 71 fCount += 1; | |
| 72 | |
| 73 if (NULL == fFrontBlock) { | |
| 74 fFrontBlock = this->allocateBlock(fAllocCount); | |
| 75 fBackBlock = fFrontBlock; // update our linklist | |
| 76 } | |
| 77 | |
| 78 Block* first = fFrontBlock; | |
| 79 char* begin; | |
| 80 | |
| 81 if (NULL == first->fBegin) { | |
| 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? | |
| 89 first = this->allocateBlock(fAllocCount); | |
| 90 first->fNext = fFrontBlock; | |
| 91 fFrontBlock->fPrev = first; | |
| 92 fFrontBlock = first; | |
| 93 goto INIT_CHUNK; | |
| 94 } | |
| 95 } | |
| 96 | |
| 97 first->fBegin = begin; | |
| 98 | |
| 99 if (NULL == fFront) { | |
| 100 SkASSERT(NULL == fBack); | |
| 101 fFront = fBack = begin; | |
| 102 } else { | |
| 103 SkASSERT(NULL != fBack); | |
| 104 fFront = begin; | |
| 105 } | |
| 106 | |
| 107 return begin; | |
| 108 } | |
| 109 | |
| 110 void* SkDeque::push_back() { | |
| 111 fCount += 1; | |
| 112 | |
| 113 if (NULL == fBackBlock) { | |
| 114 fBackBlock = this->allocateBlock(fAllocCount); | |
| 115 fFrontBlock = fBackBlock; // update our linklist | |
| 116 } | |
| 117 | |
| 118 Block* last = fBackBlock; | |
| 119 char* end; | |
| 120 | |
| 121 if (NULL == last->fBegin) { | |
| 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? | |
| 129 last = this->allocateBlock(fAllocCount); | |
| 130 last->fPrev = fBackBlock; | |
| 131 fBackBlock->fNext = last; | |
| 132 fBackBlock = last; | |
| 133 goto INIT_CHUNK; | |
| 134 } | |
| 135 } | |
| 136 | |
| 137 last->fEnd = end; | |
| 138 end -= fElemSize; | |
| 139 | |
| 140 if (NULL == fBack) { | |
| 141 SkASSERT(NULL == fFront); | |
| 142 fFront = fBack = end; | |
| 143 } else { | |
| 144 SkASSERT(NULL != fFront); | |
| 145 fBack = end; | |
| 146 } | |
| 147 | |
| 148 return end; | |
| 149 } | |
| 150 | |
| 151 void SkDeque::pop_front() { | |
| 152 SkASSERT(fCount > 0); | |
| 153 fCount -= 1; | |
| 154 | |
| 155 Block* first = fFrontBlock; | |
| 156 | |
| 157 SkASSERT(first != NULL); | |
| 158 | |
| 159 if (first->fBegin == NULL) { // we were marked empty from before | |
| 160 first = first->fNext; | |
| 161 first->fPrev = NULL; | |
| 162 this->freeBlock(fFrontBlock); | |
| 163 fFrontBlock = first; | |
| 164 SkASSERT(first != NULL); // else we popped too far | |
| 165 } | |
| 166 | |
| 167 char* begin = first->fBegin + fElemSize; | |
| 168 SkASSERT(begin <= first->fEnd); | |
| 169 | |
| 170 if (begin < fFrontBlock->fEnd) { | |
| 171 first->fBegin = begin; | |
| 172 SkASSERT(NULL != first->fBegin); | |
| 173 fFront = first->fBegin; | |
| 174 } else { | |
| 175 first->fBegin = first->fEnd = NULL; // mark as empty | |
| 176 if (NULL == first->fNext) { | |
| 177 fFront = fBack = NULL; | |
| 178 } else { | |
| 179 SkASSERT(NULL != first->fNext->fBegin); | |
| 180 fFront = first->fNext->fBegin; | |
| 181 } | |
| 182 } | |
| 183 } | |
| 184 | |
| 185 void SkDeque::pop_back() { | |
| 186 SkASSERT(fCount > 0); | |
| 187 fCount -= 1; | |
| 188 | |
| 189 Block* last = fBackBlock; | |
| 190 | |
| 191 SkASSERT(last != NULL); | |
| 192 | |
| 193 if (last->fEnd == NULL) { // we were marked empty from before | |
| 194 last = last->fPrev; | |
| 195 last->fNext = NULL; | |
| 196 this->freeBlock(fBackBlock); | |
| 197 fBackBlock = last; | |
| 198 SkASSERT(last != NULL); // else we popped too far | |
| 199 } | |
| 200 | |
| 201 char* end = last->fEnd - fElemSize; | |
| 202 SkASSERT(end >= last->fBegin); | |
| 203 | |
| 204 if (end > last->fBegin) { | |
| 205 last->fEnd = end; | |
| 206 SkASSERT(NULL != last->fEnd); | |
| 207 fBack = last->fEnd - fElemSize; | |
| 208 } else { | |
| 209 last->fBegin = last->fEnd = NULL; // mark as empty | |
| 210 if (NULL == last->fPrev) { | |
| 211 fFront = fBack = NULL; | |
| 212 } else { | |
| 213 SkASSERT(NULL != last->fPrev->fEnd); | |
| 214 fBack = last->fPrev->fEnd - fElemSize; | |
| 215 } | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 int SkDeque::numBlocksAllocated() const { | |
| 220 int numBlocks = 0; | |
| 221 | |
| 222 for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { | |
| 223 ++numBlocks; | |
| 224 } | |
| 225 | |
| 226 return numBlocks; | |
| 227 } | |
| 228 | |
| 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 | |
| 241 SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {} | |
| 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() { | |
| 250 char* pos = fPos; | |
| 251 | |
| 252 if (pos) { // if we were valid, try to move to the next setting | |
| 253 char* next = pos + fElemSize; | |
| 254 SkASSERT(next <= fCurBlock->fEnd); | |
| 255 if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next | |
| 256 do { | |
| 257 fCurBlock = fCurBlock->fNext; | |
| 258 } while (fCurBlock != NULL && fCurBlock->fBegin == NULL); | |
| 259 next = fCurBlock ? fCurBlock->fBegin : NULL; | |
| 260 } | |
| 261 fPos = next; | |
| 262 } | |
| 263 return pos; | |
| 264 } | |
| 265 | |
| 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; | |
| 277 } while (fCurBlock != NULL && fCurBlock->fEnd == NULL); | |
| 278 prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; | |
| 279 } | |
| 280 fPos = prev; | |
| 281 } | |
| 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 | |
| 289 // out of this routine NULL. | |
| 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 | |
| 295 fCurBlock = d.fFrontBlock; | |
| 296 while (NULL != fCurBlock && NULL == fCurBlock->fBegin) { | |
| 297 fCurBlock = fCurBlock->fNext; | |
| 298 } | |
| 299 fPos = fCurBlock ? fCurBlock->fBegin : NULL; | |
| 300 } else { | |
| 301 // initialize the iterator to start at the back | |
| 302 fCurBlock = d.fBackBlock; | |
| 303 while (NULL != fCurBlock && NULL == fCurBlock->fEnd) { | |
| 304 fCurBlock = fCurBlock->fPrev; | |
| 305 } | |
| 306 fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; | |
| 307 } | |
| 308 } |
