1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkDeque.h" 9b549cc38c8404c58642ada75c0b24907702cc005Herb Derby#include "SkMalloc.h" 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 110a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comstruct SkDeque::Block { 120a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* fNext; 130a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* fPrev; 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fBegin; // start of used section in this chunk 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fEnd; // end of used section in this chunk 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fStop; // end of the allocated chunk 174c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* start() { return (char*)(this + 1); } 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const char* start() const { return (const char*)(this + 1); } 204c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void init(size_t size) { 2296fcdcc219d2a0d3579719b84b28bede76efba64halcanary fNext = fPrev = nullptr; 2396fcdcc219d2a0d3579719b84b28bede76efba64halcanary fBegin = fEnd = nullptr; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fStop = (char*)this + size; 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::SkDeque(size_t elemSize, int allocCount) 290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com : fElemSize(elemSize) 3096fcdcc219d2a0d3579719b84b28bede76efba64halcanary , fInitialStorage(nullptr) 310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fCount(0) 320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fAllocCount(allocCount) { 330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(allocCount >= 1); 3496fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFrontBlock = fBackBlock = nullptr; 3596fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFront = fBack = nullptr; 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 380a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) 390a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com : fElemSize(elemSize) 400a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fInitialStorage(storage) 410a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fCount(0) 420a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com , fAllocCount(allocCount) { 4396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(storageSize == 0 || storage != nullptr); 440a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(allocCount >= 1); 454c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 460a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (storageSize >= sizeof(Block) + elemSize) { 4763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = (Block*)storage; 4863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock->init(storageSize); 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 5096fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFrontBlock = nullptr; 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = fFrontBlock; 5396fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFront = fBack = nullptr; 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkDeque::~SkDeque() { 5763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* head = fFrontBlock; 580a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* initialHead = (Block*)fInitialStorage; 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (head) { 610a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* next = head->fNext; 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (head != initialHead) { 630a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com this->freeBlock(head); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com head = next; 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid* SkDeque::push_front() { 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount += 1; 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7296fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fFrontBlock) { 7363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = this->allocateBlock(fAllocCount); 7463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = fFrontBlock; // update our linklist 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 764c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 7763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* first = fFrontBlock; 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* begin; 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8096fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == first->fBegin) { 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com INIT_CHUNK: 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fEnd = first->fStop; 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com begin = first->fStop - fElemSize; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com begin = first->fBegin - fElemSize; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (begin < first->start()) { // no more room in this chunk 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // should we alloc more as we accumulate more elements? 880a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com first = this->allocateBlock(fAllocCount); 8963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com first->fNext = fFrontBlock; 9063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock->fPrev = first; 9163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = first; 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com goto INIT_CHUNK; 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fBegin = begin; 9763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 9896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fFront) { 9996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == fBack); 10063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = begin; 10163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 10249f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(fBack); 10363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = begin; 10463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 10563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return begin; 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid* SkDeque::push_back() { 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount += 1; 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11296fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fBackBlock) { 11363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = this->allocateBlock(fAllocCount); 11463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = fBackBlock; // update our linklist 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1164c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 11763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* last = fBackBlock; 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* end; 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12096fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == last->fBegin) { 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com INIT_CHUNK: 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fBegin = last->start(); 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com end = last->fBegin + fElemSize; 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com end = last->fEnd + fElemSize; 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (end > last->fStop) { // no more room in this chunk 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // should we alloc more as we accumulate more elements? 1280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com last = this->allocateBlock(fAllocCount); 12963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com last->fPrev = fBackBlock; 13063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock->fNext = last; 13163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = last; 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com goto INIT_CHUNK; 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fEnd = end; 13763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com end -= fElemSize; 13863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 13996fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fBack) { 14096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == fFront); 14163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = fBack = end; 14263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 14349f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(fFront); 14463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = end; 14563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 14663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 14763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com return end; 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkDeque::pop_front() { 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount > 0); 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount -= 1; 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* first = fFrontBlock; 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15696fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(first != nullptr); 1574c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 15896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (first->fBegin == nullptr) { // we were marked empty from before 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first = first->fNext; 16096fcdcc219d2a0d3579719b84b28bede76efba64halcanary first->fPrev = nullptr; 16163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com this->freeBlock(fFrontBlock); 16263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFrontBlock = first; 16396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(first != nullptr); // else we popped too far 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* begin = first->fBegin + fElemSize; 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(begin <= first->fEnd); 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 16963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com if (begin < fFrontBlock->fEnd) { 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com first->fBegin = begin; 17149f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(first->fBegin); 17263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = first->fBegin; 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 17496fcdcc219d2a0d3579719b84b28bede76efba64halcanary first->fBegin = first->fEnd = nullptr; // mark as empty 17596fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == first->fNext) { 17696fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFront = fBack = nullptr; 17763ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 17849f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(first->fNext->fBegin); 17963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fFront = first->fNext->fBegin; 18063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkDeque::pop_back() { 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount > 0); 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount -= 1; 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 18863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* last = fBackBlock; 1894c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 19096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(last != nullptr); 1914c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 19296fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (last->fEnd == nullptr) { // we were marked empty from before 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last = last->fPrev; 19496fcdcc219d2a0d3579719b84b28bede76efba64halcanary last->fNext = nullptr; 19563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com this->freeBlock(fBackBlock); 19663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBackBlock = last; 19796fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(last != nullptr); // else we popped too far 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1994c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* end = last->fEnd - fElemSize; 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(end >= last->fBegin); 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (end > last->fBegin) { 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com last->fEnd = end; 20549f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(last->fEnd); 20663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = last->fEnd - fElemSize; 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 20896fcdcc219d2a0d3579719b84b28bede76efba64halcanary last->fBegin = last->fEnd = nullptr; // mark as empty 20996fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == last->fPrev) { 21096fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFront = fBack = nullptr; 21163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } else { 21249f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(last->fPrev->fEnd); 21363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fBack = last->fPrev->fEnd - fElemSize; 21463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com } 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 218fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.comint SkDeque::numBlocksAllocated() const { 2190a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com int numBlocks = 0; 2200a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 22163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { 2220a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com ++numBlocks; 2230a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2240a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 225fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com return numBlocks; 2260a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2270a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::Block* SkDeque::allocateBlock(int allocCount) { 2290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); 2300a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com newBlock->init(sizeof(Block) + allocCount * fElemSize); 2310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com return newBlock; 2320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2340a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid SkDeque::freeBlock(Block* block) { 2350a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com sk_free(block); 2360a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2370a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 24096fcdcc219d2a0d3579719b84b28bede76efba64halcanarySkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {} 241d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 2420a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comSkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { 2430a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com this->reset(d, startLoc); 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2460a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// Due to how reset and next work, next actually returns the current element 2470a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// pointed to by fPos and then updates fPos to point to the next one. 2480a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid* SkDeque::Iter::next() { 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* pos = fPos; 2504c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pos) { // if we were valid, try to move to the next setting 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* next = pos + fElemSize; 2530a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(next <= fCurBlock->fEnd); 2540a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 2560a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fNext; 25796fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr); 25896fcdcc219d2a0d3579719b84b28bede76efba64halcanary next = fCurBlock ? fCurBlock->fBegin : nullptr; 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPos = next; 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return pos; 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2650a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// Like next, prev actually returns the current element pointed to by fPos and 2660a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// then makes fPos point to the previous element. 2670a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid* SkDeque::Iter::prev() { 2680a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com char* pos = fPos; 2690a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2700a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (pos) { // if we were valid, try to move to the prior setting 2710a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com char* prev = pos - fElemSize; 2720a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkASSERT(prev >= fCurBlock->fBegin - fElemSize); 2730a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior 2740a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com do { 2750a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fPrev; 27696fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr); 27796fcdcc219d2a0d3579719b84b28bede76efba64halcanary prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; 2780a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2790a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fPos = prev; 2800a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 2810a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com return pos; 2820a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com} 2830a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2840a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// reset works by skipping through the spare blocks at the start (or end) 2850a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// of the doubly linked list until a non-empty one is found. The fPos 2860a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// member is then set to the first (or last) element in the block. If 2870a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com// there are no elements in the deque both fCurBlock and fPos will come 28896fcdcc219d2a0d3579719b84b28bede76efba64halcanary// out of this routine nullptr. 2890a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.comvoid SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { 290d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com fElemSize = d.fElemSize; 2910a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 2920a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com if (kFront_IterStart == startLoc) { 2930a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // initialize the iterator to start at the front 29463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fCurBlock = d.fFrontBlock; 29596fcdcc219d2a0d3579719b84b28bede76efba64halcanary while (fCurBlock && nullptr == fCurBlock->fBegin) { 2960a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fNext; 2970a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 29896fcdcc219d2a0d3579719b84b28bede76efba64halcanary fPos = fCurBlock ? fCurBlock->fBegin : nullptr; 2990a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } else { 3000a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // initialize the iterator to start at the back 30163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com fCurBlock = d.fBackBlock; 30296fcdcc219d2a0d3579719b84b28bede76efba64halcanary while (fCurBlock && nullptr == fCurBlock->fEnd) { 3030a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com fCurBlock = fCurBlock->fPrev; 3040a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 30596fcdcc219d2a0d3579719b84b28bede76efba64halcanary fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr; 306d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com } 307d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com} 308