123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307 |
- /*
- * 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 "include/core/SkDeque.h"
- #include "include/private/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;
- SkASSERT(first != nullptr); // else we popped too far
- first->fPrev = nullptr;
- this->freeBlock(fFrontBlock);
- fFrontBlock = first;
- }
- 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;
- SkASSERT(last != nullptr); // else we popped too far
- last->fNext = nullptr;
- this->freeBlock(fBackBlock);
- fBackBlock = last;
- }
- 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;
- }
- }
|