| /* |
| * Copyright 2006 The Android Open Source Project |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "SkDeque.h" |
| #include "SkMalloc.h" |
| |
| struct SkDeque::Block { |
| Block* fNext; |
| Block* fPrev; |
| char* fBegin; // start of used section in this chunk |
| char* fEnd; // end of used section in this chunk |
| char* fStop; // end of the allocated chunk |
| |
| char* start() { return (char*)(this + 1); } |
| const char* start() const { return (const char*)(this + 1); } |
| |
| void init(size_t size) { |
| fNext = fPrev = nullptr; |
| fBegin = fEnd = nullptr; |
| fStop = (char*)this + size; |
| } |
| }; |
| |
| SkDeque::SkDeque(size_t elemSize, int allocCount) |
| : fElemSize(elemSize) |
| , fInitialStorage(nullptr) |
| , fCount(0) |
| , fAllocCount(allocCount) { |
| SkASSERT(allocCount >= 1); |
| fFrontBlock = fBackBlock = nullptr; |
| fFront = fBack = nullptr; |
| } |
| |
| SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) |
| : fElemSize(elemSize) |
| , fInitialStorage(storage) |
| , fCount(0) |
| , fAllocCount(allocCount) { |
| SkASSERT(storageSize == 0 || storage != nullptr); |
| SkASSERT(allocCount >= 1); |
| |
| if (storageSize >= sizeof(Block) + elemSize) { |
| fFrontBlock = (Block*)storage; |
| fFrontBlock->init(storageSize); |
| } else { |
| fFrontBlock = nullptr; |
| } |
| fBackBlock = fFrontBlock; |
| fFront = fBack = nullptr; |
| } |
| |
| SkDeque::~SkDeque() { |
| Block* head = fFrontBlock; |
| Block* initialHead = (Block*)fInitialStorage; |
| |
| while (head) { |
| Block* next = head->fNext; |
| if (head != initialHead) { |
| this->freeBlock(head); |
| } |
| head = next; |
| } |
| } |
| |
| void* SkDeque::push_front() { |
| fCount += 1; |
| |
| if (nullptr == fFrontBlock) { |
| fFrontBlock = this->allocateBlock(fAllocCount); |
| fBackBlock = fFrontBlock; // update our linklist |
| } |
| |
| Block* first = fFrontBlock; |
| char* begin; |
| |
| if (nullptr == first->fBegin) { |
| INIT_CHUNK: |
| first->fEnd = first->fStop; |
| begin = first->fStop - fElemSize; |
| } else { |
| begin = first->fBegin - fElemSize; |
| if (begin < first->start()) { // no more room in this chunk |
| // should we alloc more as we accumulate more elements? |
| first = this->allocateBlock(fAllocCount); |
| first->fNext = fFrontBlock; |
| fFrontBlock->fPrev = first; |
| fFrontBlock = first; |
| goto INIT_CHUNK; |
| } |
| } |
| |
| first->fBegin = begin; |
| |
| if (nullptr == fFront) { |
| SkASSERT(nullptr == fBack); |
| fFront = fBack = begin; |
| } else { |
| SkASSERT(fBack); |
| fFront = begin; |
| } |
| |
| return begin; |
| } |
| |
| void* SkDeque::push_back() { |
| fCount += 1; |
| |
| if (nullptr == fBackBlock) { |
| fBackBlock = this->allocateBlock(fAllocCount); |
| fFrontBlock = fBackBlock; // update our linklist |
| } |
| |
| Block* last = fBackBlock; |
| char* end; |
| |
| if (nullptr == last->fBegin) { |
| INIT_CHUNK: |
| last->fBegin = last->start(); |
| end = last->fBegin + fElemSize; |
| } else { |
| end = last->fEnd + fElemSize; |
| if (end > last->fStop) { // no more room in this chunk |
| // should we alloc more as we accumulate more elements? |
| last = this->allocateBlock(fAllocCount); |
| last->fPrev = fBackBlock; |
| fBackBlock->fNext = last; |
| fBackBlock = last; |
| goto INIT_CHUNK; |
| } |
| } |
| |
| last->fEnd = end; |
| end -= fElemSize; |
| |
| if (nullptr == fBack) { |
| SkASSERT(nullptr == fFront); |
| fFront = fBack = end; |
| } else { |
| SkASSERT(fFront); |
| fBack = end; |
| } |
| |
| return end; |
| } |
| |
| void SkDeque::pop_front() { |
| SkASSERT(fCount > 0); |
| fCount -= 1; |
| |
| Block* first = fFrontBlock; |
| |
| SkASSERT(first != nullptr); |
| |
| if (first->fBegin == nullptr) { // we were marked empty from before |
| first = first->fNext; |
| first->fPrev = nullptr; |
| this->freeBlock(fFrontBlock); |
| fFrontBlock = first; |
| SkASSERT(first != nullptr); // else we popped too far |
| } |
| |
| char* begin = first->fBegin + fElemSize; |
| SkASSERT(begin <= first->fEnd); |
| |
| if (begin < fFrontBlock->fEnd) { |
| first->fBegin = begin; |
| SkASSERT(first->fBegin); |
| fFront = first->fBegin; |
| } else { |
| first->fBegin = first->fEnd = nullptr; // mark as empty |
| if (nullptr == first->fNext) { |
| fFront = fBack = nullptr; |
| } else { |
| SkASSERT(first->fNext->fBegin); |
| fFront = first->fNext->fBegin; |
| } |
| } |
| } |
| |
| void SkDeque::pop_back() { |
| SkASSERT(fCount > 0); |
| fCount -= 1; |
| |
| Block* last = fBackBlock; |
| |
| SkASSERT(last != nullptr); |
| |
| if (last->fEnd == nullptr) { // we were marked empty from before |
| last = last->fPrev; |
| last->fNext = nullptr; |
| this->freeBlock(fBackBlock); |
| fBackBlock = last; |
| SkASSERT(last != nullptr); // else we popped too far |
| } |
| |
| char* end = last->fEnd - fElemSize; |
| SkASSERT(end >= last->fBegin); |
| |
| if (end > last->fBegin) { |
| last->fEnd = end; |
| SkASSERT(last->fEnd); |
| fBack = last->fEnd - fElemSize; |
| } else { |
| last->fBegin = last->fEnd = nullptr; // mark as empty |
| if (nullptr == last->fPrev) { |
| fFront = fBack = nullptr; |
| } else { |
| SkASSERT(last->fPrev->fEnd); |
| fBack = last->fPrev->fEnd - fElemSize; |
| } |
| } |
| } |
| |
| int SkDeque::numBlocksAllocated() const { |
| int numBlocks = 0; |
| |
| for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { |
| ++numBlocks; |
| } |
| |
| return numBlocks; |
| } |
| |
| SkDeque::Block* SkDeque::allocateBlock(int allocCount) { |
| Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); |
| newBlock->init(sizeof(Block) + allocCount * fElemSize); |
| return newBlock; |
| } |
| |
| void SkDeque::freeBlock(Block* block) { |
| sk_free(block); |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {} |
| |
| SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { |
| this->reset(d, startLoc); |
| } |
| |
| // Due to how reset and next work, next actually returns the current element |
| // pointed to by fPos and then updates fPos to point to the next one. |
| void* SkDeque::Iter::next() { |
| char* pos = fPos; |
| |
| if (pos) { // if we were valid, try to move to the next setting |
| char* next = pos + fElemSize; |
| SkASSERT(next <= fCurBlock->fEnd); |
| if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next |
| do { |
| fCurBlock = fCurBlock->fNext; |
| } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr); |
| next = fCurBlock ? fCurBlock->fBegin : nullptr; |
| } |
| fPos = next; |
| } |
| return pos; |
| } |
| |
| // Like next, prev actually returns the current element pointed to by fPos and |
| // then makes fPos point to the previous element. |
| void* SkDeque::Iter::prev() { |
| char* pos = fPos; |
| |
| if (pos) { // if we were valid, try to move to the prior setting |
| char* prev = pos - fElemSize; |
| SkASSERT(prev >= fCurBlock->fBegin - fElemSize); |
| if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior |
| do { |
| fCurBlock = fCurBlock->fPrev; |
| } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr); |
| prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; |
| } |
| fPos = prev; |
| } |
| return pos; |
| } |
| |
| // reset works by skipping through the spare blocks at the start (or end) |
| // of the doubly linked list until a non-empty one is found. The fPos |
| // member is then set to the first (or last) element in the block. If |
| // there are no elements in the deque both fCurBlock and fPos will come |
| // out of this routine nullptr. |
| void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { |
| fElemSize = d.fElemSize; |
| |
| if (kFront_IterStart == startLoc) { |
| // initialize the iterator to start at the front |
| fCurBlock = d.fFrontBlock; |
| while (fCurBlock && nullptr == fCurBlock->fBegin) { |
| fCurBlock = fCurBlock->fNext; |
| } |
| fPos = fCurBlock ? fCurBlock->fBegin : nullptr; |
| } else { |
| // initialize the iterator to start at the back |
| fCurBlock = d.fBackBlock; |
| while (fCurBlock && nullptr == fCurBlock->fEnd) { |
| fCurBlock = fCurBlock->fPrev; |
| } |
| fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; |
| } |
| } |