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