10910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* libs/graphics/sgl/SkDeque.cpp 20910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** 30910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** Copyright 2006, The Android Open Source Project 40910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** 50910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** Licensed under the Apache License, Version 2.0 (the "License"); 60910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** you may not use this file except in compliance with the License. 70910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** You may obtain a copy of the License at 80910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** 90910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** http://www.apache.org/licenses/LICENSE-2.0 100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** 110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** Unless required by applicable law or agreed to in writing, software 120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** distributed under the License is distributed on an "AS IS" BASIS, 130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** See the License for the specific language governing permissions and 150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project** limitations under the License. 160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/ 170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkDeque.h" 190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define INIT_ELEM_COUNT 1 // should we let the caller set this? 210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstruct SkDeque::Head { 230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* fNext; 240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* fPrev; 250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* fBegin; // start of used section in this chunk 260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* fEnd; // end of used section in this chunk 270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* fStop; // end of the allocated chunk 280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* start() { return (char*)(this + 1); } 300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const char* start() const { return (const char*)(this + 1); } 310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void init(size_t size) { 330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fNext = fPrev = NULL; 340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBegin = fEnd = NULL; 350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fStop = (char*)this + size; 360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}; 380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkDeque::SkDeque(size_t elemSize) 400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) { 410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = fBack = NULL; 420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize) 450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project : fElemSize(elemSize), fInitialStorage(storage), fCount(0) { 460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(storageSize == 0 || storage != NULL); 470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (storageSize >= sizeof(Head) + elemSize) { 490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = (Head*)storage; 500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront->init(storageSize); 510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = NULL; 530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack = fFront; 550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkDeque::~SkDeque() { 580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* head = fFront; 590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* initialHead = (Head*)fInitialStorage; 600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (head) { 620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* next = head->fNext; 630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (head != initialHead) { 640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(head); 650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project head = next; 670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectconst void* SkDeque::front() const { 710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* front = fFront; 720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == front) { 740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return NULL; 750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == front->fBegin) { 770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project front = front->fNext; 780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == front) { 790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return NULL; 800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(front->fBegin); 830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return front->fBegin; 840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectconst void* SkDeque::back() const { 870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* back = fBack; 880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == back) { 900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return NULL; 910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == back->fEnd) { // marked as deleted 930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project back = back->fPrev; 940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == back) { 950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return NULL; 960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(back->fEnd); 990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return back->fEnd - fElemSize; 1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid* SkDeque::push_front() { 1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount += 1; 1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == fFront) { 1060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = (Head*)sk_malloc_throw(sizeof(Head) + 1070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project INIT_ELEM_COUNT * fElemSize); 1080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); 1090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack = fFront; // update our linklist 1100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* first = fFront; 1130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* begin; 1140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == first->fBegin) { 1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project INIT_CHUNK: 1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fEnd = first->fStop; 1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project begin = first->fStop - fElemSize; 1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project begin = first->fBegin - fElemSize; 1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (begin < first->start()) { // no more room in this chunk 1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // should we alloc more as we accumulate more elements? 1230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; 1240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first = (Head*)sk_malloc_throw(size); 1260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->init(size); 1270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fNext = fFront; 1280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront->fPrev = first; 1290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = first; 1300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project goto INIT_CHUNK; 1310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fBegin = begin; 1350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return begin; 1360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid* SkDeque::push_back() { 1390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount += 1; 1400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == fBack) { 1420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack = (Head*)sk_malloc_throw(sizeof(Head) + 1430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project INIT_ELEM_COUNT * fElemSize); 1440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); 1450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = fBack; // update our linklist 1460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* last = fBack; 1490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* end; 1500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (NULL == last->fBegin) { 1520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project INIT_CHUNK: 1530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fBegin = last->start(); 1540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project end = last->fBegin + fElemSize; 1550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 1560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project end = last->fEnd + fElemSize; 1570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (end > last->fStop) { // no more room in this chunk 1580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // should we alloc more as we accumulate more elements? 1590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; 1600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last = (Head*)sk_malloc_throw(size); 1620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->init(size); 1630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fPrev = fBack; 1640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack->fNext = last; 1650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack = last; 1660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project goto INIT_CHUNK; 1670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fEnd = end; 1710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return end - fElemSize; 1720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkDeque::pop_front() { 1750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fCount > 0); 1760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount -= 1; 1770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* first = fFront; 1790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(first != NULL); 1810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (first->fBegin == NULL) { // we were marked empty from before 1830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first = first->fNext; 1840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fPrev = NULL; 1850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(fFront); 1860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fFront = first; 1870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(first != NULL); // else we popped too far 1880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* begin = first->fBegin + fElemSize; 1910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(begin <= first->fEnd); 1920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (begin < fFront->fEnd) { 1940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fBegin = begin; 1950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 1960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project first->fBegin = first->fEnd = NULL; // mark as empty 1970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkDeque::pop_back() { 2010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fCount > 0); 2020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount -= 1; 2030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Head* last = fBack; 2050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(last != NULL); 2070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (last->fEnd == NULL) { // we were marked empty from before 2090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last = last->fPrev; 2100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fNext = NULL; 2110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(fBack); 2120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fBack = last; 2130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(last != NULL); // else we popped too far 2140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* end = last->fEnd - fElemSize; 2170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(end >= last->fBegin); 2180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (end > last->fBegin) { 2200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fEnd = end; 2210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 2220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project last->fBegin = last->fEnd = NULL; // mark as empty 2230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 2250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/////////////////////////////////////////////////////////////////////////////// 2270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkDeque::Iter::Iter(const SkDeque& d) : fElemSize(d.fElemSize) { 2290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fHead = d.fFront; 2300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (fHead != NULL && fHead->fBegin == NULL) { 2310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fHead = fHead->fNext; 2320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPos = fHead ? fHead->fBegin : NULL; 2340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 2350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid* SkDeque::Iter::next() { 2370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* pos = fPos; 2380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (pos) { // if we were valid, try to move to the next setting 2400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* next = pos + fElemSize; 2410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(next <= fHead->fEnd); 2420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (next == fHead->fEnd) { // exhausted this chunk, move to next 2430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project do { 2440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fHead = fHead->fNext; 2450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } while (fHead != NULL && fHead->fBegin == NULL); 2460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project next = fHead ? fHead->fBegin : NULL; 2470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fPos = next; 2490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return pos; 2510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 2520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 253