1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkDeque.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,308 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkDeque.h"
1.14 +
1.15 +struct SkDeque::Block {
1.16 + Block* fNext;
1.17 + Block* fPrev;
1.18 + char* fBegin; // start of used section in this chunk
1.19 + char* fEnd; // end of used section in this chunk
1.20 + char* fStop; // end of the allocated chunk
1.21 +
1.22 + char* start() { return (char*)(this + 1); }
1.23 + const char* start() const { return (const char*)(this + 1); }
1.24 +
1.25 + void init(size_t size) {
1.26 + fNext = fPrev = NULL;
1.27 + fBegin = fEnd = NULL;
1.28 + fStop = (char*)this + size;
1.29 + }
1.30 +};
1.31 +
1.32 +SkDeque::SkDeque(size_t elemSize, int allocCount)
1.33 + : fElemSize(elemSize)
1.34 + , fInitialStorage(NULL)
1.35 + , fCount(0)
1.36 + , fAllocCount(allocCount) {
1.37 + SkASSERT(allocCount >= 1);
1.38 + fFrontBlock = fBackBlock = NULL;
1.39 + fFront = fBack = NULL;
1.40 +}
1.41 +
1.42 +SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
1.43 + : fElemSize(elemSize)
1.44 + , fInitialStorage(storage)
1.45 + , fCount(0)
1.46 + , fAllocCount(allocCount) {
1.47 + SkASSERT(storageSize == 0 || storage != NULL);
1.48 + SkASSERT(allocCount >= 1);
1.49 +
1.50 + if (storageSize >= sizeof(Block) + elemSize) {
1.51 + fFrontBlock = (Block*)storage;
1.52 + fFrontBlock->init(storageSize);
1.53 + } else {
1.54 + fFrontBlock = NULL;
1.55 + }
1.56 + fBackBlock = fFrontBlock;
1.57 + fFront = fBack = NULL;
1.58 +}
1.59 +
1.60 +SkDeque::~SkDeque() {
1.61 + Block* head = fFrontBlock;
1.62 + Block* initialHead = (Block*)fInitialStorage;
1.63 +
1.64 + while (head) {
1.65 + Block* next = head->fNext;
1.66 + if (head != initialHead) {
1.67 + this->freeBlock(head);
1.68 + }
1.69 + head = next;
1.70 + }
1.71 +}
1.72 +
1.73 +void* SkDeque::push_front() {
1.74 + fCount += 1;
1.75 +
1.76 + if (NULL == fFrontBlock) {
1.77 + fFrontBlock = this->allocateBlock(fAllocCount);
1.78 + fBackBlock = fFrontBlock; // update our linklist
1.79 + }
1.80 +
1.81 + Block* first = fFrontBlock;
1.82 + char* begin;
1.83 +
1.84 + if (NULL == first->fBegin) {
1.85 + INIT_CHUNK:
1.86 + first->fEnd = first->fStop;
1.87 + begin = first->fStop - fElemSize;
1.88 + } else {
1.89 + begin = first->fBegin - fElemSize;
1.90 + if (begin < first->start()) { // no more room in this chunk
1.91 + // should we alloc more as we accumulate more elements?
1.92 + first = this->allocateBlock(fAllocCount);
1.93 + first->fNext = fFrontBlock;
1.94 + fFrontBlock->fPrev = first;
1.95 + fFrontBlock = first;
1.96 + goto INIT_CHUNK;
1.97 + }
1.98 + }
1.99 +
1.100 + first->fBegin = begin;
1.101 +
1.102 + if (NULL == fFront) {
1.103 + SkASSERT(NULL == fBack);
1.104 + fFront = fBack = begin;
1.105 + } else {
1.106 + SkASSERT(NULL != fBack);
1.107 + fFront = begin;
1.108 + }
1.109 +
1.110 + return begin;
1.111 +}
1.112 +
1.113 +void* SkDeque::push_back() {
1.114 + fCount += 1;
1.115 +
1.116 + if (NULL == fBackBlock) {
1.117 + fBackBlock = this->allocateBlock(fAllocCount);
1.118 + fFrontBlock = fBackBlock; // update our linklist
1.119 + }
1.120 +
1.121 + Block* last = fBackBlock;
1.122 + char* end;
1.123 +
1.124 + if (NULL == last->fBegin) {
1.125 + INIT_CHUNK:
1.126 + last->fBegin = last->start();
1.127 + end = last->fBegin + fElemSize;
1.128 + } else {
1.129 + end = last->fEnd + fElemSize;
1.130 + if (end > last->fStop) { // no more room in this chunk
1.131 + // should we alloc more as we accumulate more elements?
1.132 + last = this->allocateBlock(fAllocCount);
1.133 + last->fPrev = fBackBlock;
1.134 + fBackBlock->fNext = last;
1.135 + fBackBlock = last;
1.136 + goto INIT_CHUNK;
1.137 + }
1.138 + }
1.139 +
1.140 + last->fEnd = end;
1.141 + end -= fElemSize;
1.142 +
1.143 + if (NULL == fBack) {
1.144 + SkASSERT(NULL == fFront);
1.145 + fFront = fBack = end;
1.146 + } else {
1.147 + SkASSERT(NULL != fFront);
1.148 + fBack = end;
1.149 + }
1.150 +
1.151 + return end;
1.152 +}
1.153 +
1.154 +void SkDeque::pop_front() {
1.155 + SkASSERT(fCount > 0);
1.156 + fCount -= 1;
1.157 +
1.158 + Block* first = fFrontBlock;
1.159 +
1.160 + SkASSERT(first != NULL);
1.161 +
1.162 + if (first->fBegin == NULL) { // we were marked empty from before
1.163 + first = first->fNext;
1.164 + first->fPrev = NULL;
1.165 + this->freeBlock(fFrontBlock);
1.166 + fFrontBlock = first;
1.167 + SkASSERT(first != NULL); // else we popped too far
1.168 + }
1.169 +
1.170 + char* begin = first->fBegin + fElemSize;
1.171 + SkASSERT(begin <= first->fEnd);
1.172 +
1.173 + if (begin < fFrontBlock->fEnd) {
1.174 + first->fBegin = begin;
1.175 + SkASSERT(NULL != first->fBegin);
1.176 + fFront = first->fBegin;
1.177 + } else {
1.178 + first->fBegin = first->fEnd = NULL; // mark as empty
1.179 + if (NULL == first->fNext) {
1.180 + fFront = fBack = NULL;
1.181 + } else {
1.182 + SkASSERT(NULL != first->fNext->fBegin);
1.183 + fFront = first->fNext->fBegin;
1.184 + }
1.185 + }
1.186 +}
1.187 +
1.188 +void SkDeque::pop_back() {
1.189 + SkASSERT(fCount > 0);
1.190 + fCount -= 1;
1.191 +
1.192 + Block* last = fBackBlock;
1.193 +
1.194 + SkASSERT(last != NULL);
1.195 +
1.196 + if (last->fEnd == NULL) { // we were marked empty from before
1.197 + last = last->fPrev;
1.198 + last->fNext = NULL;
1.199 + this->freeBlock(fBackBlock);
1.200 + fBackBlock = last;
1.201 + SkASSERT(last != NULL); // else we popped too far
1.202 + }
1.203 +
1.204 + char* end = last->fEnd - fElemSize;
1.205 + SkASSERT(end >= last->fBegin);
1.206 +
1.207 + if (end > last->fBegin) {
1.208 + last->fEnd = end;
1.209 + SkASSERT(NULL != last->fEnd);
1.210 + fBack = last->fEnd - fElemSize;
1.211 + } else {
1.212 + last->fBegin = last->fEnd = NULL; // mark as empty
1.213 + if (NULL == last->fPrev) {
1.214 + fFront = fBack = NULL;
1.215 + } else {
1.216 + SkASSERT(NULL != last->fPrev->fEnd);
1.217 + fBack = last->fPrev->fEnd - fElemSize;
1.218 + }
1.219 + }
1.220 +}
1.221 +
1.222 +int SkDeque::numBlocksAllocated() const {
1.223 + int numBlocks = 0;
1.224 +
1.225 + for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
1.226 + ++numBlocks;
1.227 + }
1.228 +
1.229 + return numBlocks;
1.230 +}
1.231 +
1.232 +SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
1.233 + Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
1.234 + newBlock->init(sizeof(Block) + allocCount * fElemSize);
1.235 + return newBlock;
1.236 +}
1.237 +
1.238 +void SkDeque::freeBlock(Block* block) {
1.239 + sk_free(block);
1.240 +}
1.241 +
1.242 +///////////////////////////////////////////////////////////////////////////////
1.243 +
1.244 +SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {}
1.245 +
1.246 +SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
1.247 + this->reset(d, startLoc);
1.248 +}
1.249 +
1.250 +// Due to how reset and next work, next actually returns the current element
1.251 +// pointed to by fPos and then updates fPos to point to the next one.
1.252 +void* SkDeque::Iter::next() {
1.253 + char* pos = fPos;
1.254 +
1.255 + if (pos) { // if we were valid, try to move to the next setting
1.256 + char* next = pos + fElemSize;
1.257 + SkASSERT(next <= fCurBlock->fEnd);
1.258 + if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
1.259 + do {
1.260 + fCurBlock = fCurBlock->fNext;
1.261 + } while (fCurBlock != NULL && fCurBlock->fBegin == NULL);
1.262 + next = fCurBlock ? fCurBlock->fBegin : NULL;
1.263 + }
1.264 + fPos = next;
1.265 + }
1.266 + return pos;
1.267 +}
1.268 +
1.269 +// Like next, prev actually returns the current element pointed to by fPos and
1.270 +// then makes fPos point to the previous element.
1.271 +void* SkDeque::Iter::prev() {
1.272 + char* pos = fPos;
1.273 +
1.274 + if (pos) { // if we were valid, try to move to the prior setting
1.275 + char* prev = pos - fElemSize;
1.276 + SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
1.277 + if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
1.278 + do {
1.279 + fCurBlock = fCurBlock->fPrev;
1.280 + } while (fCurBlock != NULL && fCurBlock->fEnd == NULL);
1.281 + prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
1.282 + }
1.283 + fPos = prev;
1.284 + }
1.285 + return pos;
1.286 +}
1.287 +
1.288 +// reset works by skipping through the spare blocks at the start (or end)
1.289 +// of the doubly linked list until a non-empty one is found. The fPos
1.290 +// member is then set to the first (or last) element in the block. If
1.291 +// there are no elements in the deque both fCurBlock and fPos will come
1.292 +// out of this routine NULL.
1.293 +void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
1.294 + fElemSize = d.fElemSize;
1.295 +
1.296 + if (kFront_IterStart == startLoc) {
1.297 + // initialize the iterator to start at the front
1.298 + fCurBlock = d.fFrontBlock;
1.299 + while (NULL != fCurBlock && NULL == fCurBlock->fBegin) {
1.300 + fCurBlock = fCurBlock->fNext;
1.301 + }
1.302 + fPos = fCurBlock ? fCurBlock->fBegin : NULL;
1.303 + } else {
1.304 + // initialize the iterator to start at the back
1.305 + fCurBlock = d.fBackBlock;
1.306 + while (NULL != fCurBlock && NULL == fCurBlock->fEnd) {
1.307 + fCurBlock = fCurBlock->fPrev;
1.308 + }
1.309 + fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
1.310 + }
1.311 +}
