1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkDeque.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 120a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comstruct SkDeque::Block { 130a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* fNext; 140a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* fPrev; 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fBegin; // start of used section in this chunk 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fEnd; // end of used section in this chunk 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fStop; // end of the allocated chunk 184c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* start() { return (char*)(this + 1); } 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const char* start() const { return (const char*)(this + 1); } 214c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void init(size_t size) { 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fNext = fPrev = NULL; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fBegin = fEnd = NULL; 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fStop = (char*)this + size; 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::SkDeque(size_t elemSize, int allocCount) 300a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com : fElemSize(elemSize) 310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fInitialStorage(NULL) 320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fCount(0) 330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fAllocCount(allocCount) { 340a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(allocCount >= 1); 3563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = fBackBlock = NULL; 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFront = fBack = NULL; 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 390a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) 400a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com : fElemSize(elemSize) 410a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fInitialStorage(storage) 420a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fCount(0) 430a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fAllocCount(allocCount) { 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(storageSize == 0 || storage != NULL); 450a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(allocCount >= 1); 464c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 470a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (storageSize >= sizeof(Block) + elemSize) { 4863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = (Block*)storage; 4963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock->init(storageSize); 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 5163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = NULL; 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = fFrontBlock; 5463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = NULL; 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkDeque::~SkDeque() { 5863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* head = fFrontBlock; 590a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* initialHead = (Block*)fInitialStorage; 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (head) { 620a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* next = head->fNext; 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (head != initialHead) { 640a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com this->freeBlock(head); 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com head = next; 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid* SkDeque::push_front() { 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount += 1; 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == fFrontBlock) { 7463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = this->allocateBlock(fAllocCount); 7563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = fFrontBlock; // update our linklist 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 774c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 7863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* first = fFrontBlock; 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* begin; 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (NULL == first->fBegin) { 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com INIT_CHUNK: 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fEnd = first->fStop; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com begin = first->fStop - fElemSize; 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com begin = first->fBegin - fElemSize; 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (begin < first->start()) { // no more room in this chunk 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // should we alloc more as we accumulate more elements? 890a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com first = this->allocateBlock(fAllocCount); 9063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com first->fNext = fFrontBlock; 9163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock->fPrev = first; 9263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = first; 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com goto INIT_CHUNK; 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fBegin = begin; 9863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 9963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == fFront) { 10063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com SkASSERT(NULL == fBack); 10163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = begin; 10263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 10349f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(fBack); 10463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = begin; 10563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 10663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return begin; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid* SkDeque::push_back() { 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount += 1; 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == fBackBlock) { 11463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = this->allocateBlock(fAllocCount); 11563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = fBackBlock; // update our linklist 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1174c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 11863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* last = fBackBlock; 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* end; 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (NULL == last->fBegin) { 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com INIT_CHUNK: 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fBegin = last->start(); 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com end = last->fBegin + fElemSize; 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com end = last->fEnd + fElemSize; 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (end > last->fStop) { // no more room in this chunk 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // should we alloc more as we accumulate more elements? 1290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com last = this->allocateBlock(fAllocCount); 13063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com last->fPrev = fBackBlock; 13163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock->fNext = last; 13263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = last; 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com goto INIT_CHUNK; 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fEnd = end; 13863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com end -= fElemSize; 13963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 14063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == fBack) { 14163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com SkASSERT(NULL == fFront); 14263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = end; 14363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 14449f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(fFront); 14563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = end; 14663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 14763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 14863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com return end; 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkDeque::pop_front() { 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount > 0); 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount -= 1; 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* first = fFrontBlock; 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(first != NULL); 1584c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (first->fBegin == NULL) { // we were marked empty from before 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first = first->fNext; 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fPrev = NULL; 16263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com this->freeBlock(fFrontBlock); 16363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = first; 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(first != NULL); // else we popped too far 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* begin = first->fBegin + fElemSize; 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(begin <= first->fEnd); 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 17063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (begin < fFrontBlock->fEnd) { 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fBegin = begin; 17249f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(first->fBegin); 17363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = first->fBegin; 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fBegin = first->fEnd = NULL; // mark as empty 17663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == first->fNext) { 17763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = NULL; 17863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 17949f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(first->fNext->fBegin); 18063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = first->fNext->fBegin; 18163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkDeque::pop_back() { 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount > 0); 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount -= 1; 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 18963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* last = fBackBlock; 1904c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(last != NULL); 1924c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (last->fEnd == NULL) { // we were marked empty from before 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last = last->fPrev; 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fNext = NULL; 19663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com this->freeBlock(fBackBlock); 19763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = last; 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(last != NULL); // else we popped too far 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2004c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* end = last->fEnd - fElemSize; 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(end >= last->fBegin); 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (end > last->fBegin) { 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fEnd = end; 20649f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(last->fEnd); 20763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = last->fEnd - fElemSize; 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fBegin = last->fEnd = NULL; // mark as empty 21063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (NULL == last->fPrev) { 21163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = NULL; 21263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 21349f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(last->fPrev->fEnd); 21463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = last->fPrev->fEnd - fElemSize; 21563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 219fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.comint SkDeque::numBlocksAllocated() const { 2200a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com int numBlocks = 0; 2210a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 22263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { 2230a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com ++numBlocks; 2240a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2250a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 226fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com return numBlocks; 2270a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::Block* SkDeque::allocateBlock(int allocCount) { 2300a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); 2310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com newBlock->init(sizeof(Block) + allocCount * fElemSize); 2320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com return newBlock; 2330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2340a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2350a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid SkDeque::freeBlock(Block* block) { 2360a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com sk_free(block); 2370a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2380a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2410a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {} 242d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 2430a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { 2440a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com this->reset(d, startLoc); 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2470a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// Due to how reset and next work, next actually returns the current element 2480a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// pointed to by fPos and then updates fPos to point to the next one. 2490a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid* SkDeque::Iter::next() { 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* pos = fPos; 2514c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pos) { // if we were valid, try to move to the next setting 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* next = pos + fElemSize; 2540a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(next <= fCurBlock->fEnd); 2550a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 2570a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fNext; 2580a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } while (fCurBlock != NULL && fCurBlock->fBegin == NULL); 2590a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com next = fCurBlock ? fCurBlock->fBegin : NULL; 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPos = next; 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return pos; 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2660a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// Like next, prev actually returns the current element pointed to by fPos and 2670a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// then makes fPos point to the previous element. 2680a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid* SkDeque::Iter::prev() { 2690a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com char* pos = fPos; 2700a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2710a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (pos) { // if we were valid, try to move to the prior setting 2720a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com char* prev = pos - fElemSize; 2730a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(prev >= fCurBlock->fBegin - fElemSize); 2740a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior 2750a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com do { 2760a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fPrev; 2770a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } while (fCurBlock != NULL && fCurBlock->fEnd == NULL); 2780a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 2790a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2800a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fPos = prev; 2810a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2820a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com return pos; 2830a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2840a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2850a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// reset works by skipping through the spare blocks at the start (or end) 2860a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// of the doubly linked list until a non-empty one is found. The fPos 2870a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// member is then set to the first (or last) element in the block. If 2880a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// there are no elements in the deque both fCurBlock and fPos will come 2890a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// out of this routine NULL. 2900a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { 291d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com fElemSize = d.fElemSize; 2920a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2930a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (kFront_IterStart == startLoc) { 2940a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // initialize the iterator to start at the front 29563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fCurBlock = d.fFrontBlock; 29649f085dddff10473b6ebf832a974288300224e60bsalomon while (fCurBlock && NULL == fCurBlock->fBegin) { 2970a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fNext; 2980a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2990a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fPos = fCurBlock ? fCurBlock->fBegin : NULL; 3000a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } else { 3010a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // initialize the iterator to start at the back 30263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fCurBlock = d.fBackBlock; 30349f085dddff10473b6ebf832a974288300224e60bsalomon while (fCurBlock && NULL == fCurBlock->fEnd) { 3040a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fPrev; 3050a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 3060a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 307d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com } 308d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com} 309