180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkDeque.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct SkDeque::Block { 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* fNext; 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* fPrev; 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fBegin; // start of used section in this chunk 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fEnd; // end of used section in this chunk 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fStop; // end of the allocated chunk 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* start() { return (char*)(this + 1); } 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const char* start() const { return (const char*)(this + 1); } 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void init(size_t size) { 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fNext = fPrev = NULL; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBegin = fEnd = NULL; 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fStop = (char*)this + size; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::SkDeque(size_t elemSize, int allocCount) 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru : fElemSize(elemSize) 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fInitialStorage(NULL) 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fCount(0) 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fAllocCount(allocCount) { 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(allocCount >= 1); 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = fBackBlock = NULL; 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = NULL; 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru : fElemSize(elemSize) 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fInitialStorage(storage) 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fCount(0) 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru , fAllocCount(allocCount) { 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(storageSize == 0 || storage != NULL); 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(allocCount >= 1); 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (storageSize >= sizeof(Block) + elemSize) { 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = (Block*)storage; 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock->init(storageSize); 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = NULL; 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock = fFrontBlock; 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = NULL; 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::~SkDeque() { 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* head = fFrontBlock; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* initialHead = (Block*)fInitialStorage; 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (head) { 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* next = head->fNext; 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (head != initialHead) { 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->freeBlock(head); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru head = next; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* SkDeque::push_front() { 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount += 1; 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == fFrontBlock) { 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = this->allocateBlock(fAllocCount); 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock = fFrontBlock; // update our linklist 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* first = fFrontBlock; 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* begin; 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == first->fBegin) { 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru INIT_CHUNK: 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fEnd = first->fStop; 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru begin = first->fStop - fElemSize; 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru begin = first->fBegin - fElemSize; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (begin < first->start()) { // no more room in this chunk 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // should we alloc more as we accumulate more elements? 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first = this->allocateBlock(fAllocCount); 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fNext = fFrontBlock; 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock->fPrev = first; 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = first; 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru goto INIT_CHUNK; 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fBegin = begin; 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == fFront) { 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL == fBack); 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = begin; 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != fBack); 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = begin; 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return begin; 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* SkDeque::push_back() { 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount += 1; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == fBackBlock) { 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock = this->allocateBlock(fAllocCount); 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = fBackBlock; // update our linklist 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* last = fBackBlock; 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* end; 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == last->fBegin) { 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru INIT_CHUNK: 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fBegin = last->start(); 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru end = last->fBegin + fElemSize; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru end = last->fEnd + fElemSize; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (end > last->fStop) { // no more room in this chunk 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // should we alloc more as we accumulate more elements? 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last = this->allocateBlock(fAllocCount); 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fPrev = fBackBlock; 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock->fNext = last; 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock = last; 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru goto INIT_CHUNK; 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fEnd = end; 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru end -= fElemSize; 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == fBack) { 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL == fFront); 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = end; 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != fFront); 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBack = end; 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return end; 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkDeque::pop_front() { 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCount > 0); 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount -= 1; 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* first = fFrontBlock; 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(first != NULL); 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (first->fBegin == NULL) { // we were marked empty from before 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first = first->fNext; 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fPrev = NULL; 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->freeBlock(fFrontBlock); 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFrontBlock = first; 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(first != NULL); // else we popped too far 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* begin = first->fBegin + fElemSize; 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(begin <= first->fEnd); 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (begin < fFrontBlock->fEnd) { 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fBegin = begin; 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != first->fBegin); 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = first->fBegin; 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru first->fBegin = first->fEnd = NULL; // mark as empty 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == first->fNext) { 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = NULL; 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != first->fNext->fBegin); 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = first->fNext->fBegin; 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkDeque::pop_back() { 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCount > 0); 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount -= 1; 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* last = fBackBlock; 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(last != NULL); 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (last->fEnd == NULL) { // we were marked empty from before 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last = last->fPrev; 19580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fNext = NULL; 19680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->freeBlock(fBackBlock); 19780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBackBlock = last; 19880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(last != NULL); // else we popped too far 19980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 20080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* end = last->fEnd - fElemSize; 20280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(end >= last->fBegin); 20380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (end > last->fBegin) { 20580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fEnd = end; 20680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != last->fEnd); 20780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBack = last->fEnd - fElemSize; 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru last->fBegin = last->fEnd = NULL; // mark as empty 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == last->fPrev) { 21180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFront = fBack = NULL; 21280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 21380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL != last->fPrev->fEnd); 21480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBack = last->fPrev->fEnd - fElemSize; 21580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 21880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkDeque::numBlocksAllocated() const { 22080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int numBlocks = 0; 22180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { 22380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ++numBlocks; 22480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 22580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return numBlocks; 22780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 22880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::Block* SkDeque::allocateBlock(int allocCount) { 23080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); 23180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru newBlock->init(sizeof(Block) + allocCount * fElemSize); 23280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return newBlock; 23380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 23480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkDeque::freeBlock(Block* block) { 23680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(block); 23780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 23880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 24080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {} 24280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { 24480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->reset(d, startLoc); 24580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 24680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Due to how reset and next work, next actually returns the current element 24880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// pointed to by fPos and then updates fPos to point to the next one. 24980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* SkDeque::Iter::next() { 25080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* pos = fPos; 25180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 25280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pos) { // if we were valid, try to move to the next setting 25380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* next = pos + fElemSize; 25480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(next <= fCurBlock->fEnd); 25580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next 25680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 25780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = fCurBlock->fNext; 25880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (fCurBlock != NULL && fCurBlock->fBegin == NULL); 25980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru next = fCurBlock ? fCurBlock->fBegin : NULL; 26080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPos = next; 26280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return pos; 26480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 26580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 26680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Like next, prev actually returns the current element pointed to by fPos and 26780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// then makes fPos point to the previous element. 26880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* SkDeque::Iter::prev() { 26980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* pos = fPos; 27080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pos) { // if we were valid, try to move to the prior setting 27280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* prev = pos - fElemSize; 27380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(prev >= fCurBlock->fBegin - fElemSize); 27480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior 27580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 27680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = fCurBlock->fPrev; 27780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (fCurBlock != NULL && fCurBlock->fEnd == NULL); 27880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 27980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 28080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPos = prev; 28180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 28280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return pos; 28380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 28480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// reset works by skipping through the spare blocks at the start (or end) 28680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// of the doubly linked list until a non-empty one is found. The fPos 28780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// member is then set to the first (or last) element in the block. If 28880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// there are no elements in the deque both fCurBlock and fPos will come 28980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// out of this routine NULL. 29080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { 29180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fElemSize = d.fElemSize; 29280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (kFront_IterStart == startLoc) { 29480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // initialize the iterator to start at the front 29580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = d.fFrontBlock; 29680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (NULL != fCurBlock && NULL == fCurBlock->fBegin) { 29780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = fCurBlock->fNext; 29880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 29980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPos = fCurBlock ? fCurBlock->fBegin : NULL; 30080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 30180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // initialize the iterator to start at the back 30280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = d.fBackBlock; 30380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (NULL != fCurBlock && NULL == fCurBlock->fEnd) { 30480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurBlock = fCurBlock->fPrev; 30580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 30780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 309