SkDeque.cpp revision 0a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5a
1 2/* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10#include "SkDeque.h" 11 12struct SkDeque::Block { 13 Block* fNext; 14 Block* fPrev; 15 char* fBegin; // start of used section in this chunk 16 char* fEnd; // end of used section in this chunk 17 char* fStop; // end of the allocated chunk 18 19 char* start() { return (char*)(this + 1); } 20 const char* start() const { return (const char*)(this + 1); } 21 22 void init(size_t size) { 23 fNext = fPrev = NULL; 24 fBegin = fEnd = NULL; 25 fStop = (char*)this + size; 26 } 27}; 28 29SkDeque::SkDeque(size_t elemSize, int allocCount) 30 : fElemSize(elemSize) 31 , fInitialStorage(NULL) 32 , fCount(0) 33 , fAllocCount(allocCount) { 34 SkASSERT(allocCount >= 1); 35 fFront = fBack = NULL; 36} 37 38SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount) 39 : fElemSize(elemSize) 40 , fInitialStorage(storage) 41 , fCount(0) 42 , fAllocCount(allocCount) { 43 SkASSERT(storageSize == 0 || storage != NULL); 44 SkASSERT(allocCount >= 1); 45 46 if (storageSize >= sizeof(Block) + elemSize) { 47 fFront = (Block*)storage; 48 fFront->init(storageSize); 49 } else { 50 fFront = NULL; 51 } 52 fBack = fFront; 53} 54 55SkDeque::~SkDeque() { 56 Block* head = fFront; 57 Block* initialHead = (Block*)fInitialStorage; 58 59 while (head) { 60 Block* next = head->fNext; 61 if (head != initialHead) { 62 this->freeBlock(head); 63 } 64 head = next; 65 } 66} 67 68const void* SkDeque::front() const { 69 Block* front = fFront; 70 71 if (NULL == front) { 72 return NULL; 73 } 74 if (NULL == front->fBegin) { 75 front = front->fNext; 76 if (NULL == front) { 77 return NULL; 78 } 79 } 80 SkASSERT(front->fBegin); 81 return front->fBegin; 82} 83 84const void* SkDeque::back() const { 85 Block* back = fBack; 86 87 if (NULL == back) { 88 return NULL; 89 } 90 if (NULL == back->fEnd) { // marked as deleted 91 back = back->fPrev; 92 if (NULL == back) { 93 return NULL; 94 } 95 } 96 SkASSERT(back->fEnd); 97 return back->fEnd - fElemSize; 98} 99 100void* SkDeque::push_front() { 101 fCount += 1; 102 103 if (NULL == fFront) { 104 fFront = this->allocateBlock(fAllocCount); 105 fBack = fFront; // update our linklist 106 } 107 108 Block* first = fFront; 109 char* begin; 110 111 if (NULL == first->fBegin) { 112 INIT_CHUNK: 113 first->fEnd = first->fStop; 114 begin = first->fStop - fElemSize; 115 } else { 116 begin = first->fBegin - fElemSize; 117 if (begin < first->start()) { // no more room in this chunk 118 // should we alloc more as we accumulate more elements? 119 first = this->allocateBlock(fAllocCount); 120 first->fNext = fFront; 121 fFront->fPrev = first; 122 fFront = first; 123 goto INIT_CHUNK; 124 } 125 } 126 127 first->fBegin = begin; 128 return begin; 129} 130 131void* SkDeque::push_back() { 132 fCount += 1; 133 134 if (NULL == fBack) { 135 fBack = this->allocateBlock(fAllocCount); 136 fFront = fBack; // update our linklist 137 } 138 139 Block* last = fBack; 140 char* end; 141 142 if (NULL == last->fBegin) { 143 INIT_CHUNK: 144 last->fBegin = last->start(); 145 end = last->fBegin + fElemSize; 146 } else { 147 end = last->fEnd + fElemSize; 148 if (end > last->fStop) { // no more room in this chunk 149 // should we alloc more as we accumulate more elements? 150 last = this->allocateBlock(fAllocCount); 151 last->fPrev = fBack; 152 fBack->fNext = last; 153 fBack = last; 154 goto INIT_CHUNK; 155 } 156 } 157 158 last->fEnd = end; 159 return end - fElemSize; 160} 161 162void SkDeque::pop_front() { 163 SkASSERT(fCount > 0); 164 fCount -= 1; 165 166 Block* first = fFront; 167 168 SkASSERT(first != NULL); 169 170 if (first->fBegin == NULL) { // we were marked empty from before 171 first = first->fNext; 172 first->fPrev = NULL; 173 this->freeBlock(fFront); 174 fFront = first; 175 SkASSERT(first != NULL); // else we popped too far 176 } 177 178 char* begin = first->fBegin + fElemSize; 179 SkASSERT(begin <= first->fEnd); 180 181 if (begin < fFront->fEnd) { 182 first->fBegin = begin; 183 } else { 184 first->fBegin = first->fEnd = NULL; // mark as empty 185 } 186} 187 188void SkDeque::pop_back() { 189 SkASSERT(fCount > 0); 190 fCount -= 1; 191 192 Block* last = fBack; 193 194 SkASSERT(last != NULL); 195 196 if (last->fEnd == NULL) { // we were marked empty from before 197 last = last->fPrev; 198 last->fNext = NULL; 199 this->freeBlock(fBack); 200 fBack = last; 201 SkASSERT(last != NULL); // else we popped too far 202 } 203 204 char* end = last->fEnd - fElemSize; 205 SkASSERT(end >= last->fBegin); 206 207 if (end > last->fBegin) { 208 last->fEnd = end; 209 } else { 210 last->fBegin = last->fEnd = NULL; // mark as empty 211 } 212} 213 214int SkDeque::numBlocksAllocated() const { 215 int numBlocks = 0; 216 217 for (const Block* temp = fFront; temp; temp = temp->fNext) { 218 ++numBlocks; 219 } 220 221 return numBlocks; 222} 223 224SkDeque::Block* SkDeque::allocateBlock(int allocCount) { 225 Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize); 226 newBlock->init(sizeof(Block) + allocCount * fElemSize); 227 return newBlock; 228} 229 230void SkDeque::freeBlock(Block* block) { 231 sk_free(block); 232} 233 234/////////////////////////////////////////////////////////////////////////////// 235 236SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {} 237 238SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) { 239 this->reset(d, startLoc); 240} 241 242// Due to how reset and next work, next actually returns the current element 243// pointed to by fPos and then updates fPos to point to the next one. 244void* SkDeque::Iter::next() { 245 char* pos = fPos; 246 247 if (pos) { // if we were valid, try to move to the next setting 248 char* next = pos + fElemSize; 249 SkASSERT(next <= fCurBlock->fEnd); 250 if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next 251 do { 252 fCurBlock = fCurBlock->fNext; 253 } while (fCurBlock != NULL && fCurBlock->fBegin == NULL); 254 next = fCurBlock ? fCurBlock->fBegin : NULL; 255 } 256 fPos = next; 257 } 258 return pos; 259} 260 261// Like next, prev actually returns the current element pointed to by fPos and 262// then makes fPos point to the previous element. 263void* SkDeque::Iter::prev() { 264 char* pos = fPos; 265 266 if (pos) { // if we were valid, try to move to the prior setting 267 char* prev = pos - fElemSize; 268 SkASSERT(prev >= fCurBlock->fBegin - fElemSize); 269 if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior 270 do { 271 fCurBlock = fCurBlock->fPrev; 272 } while (fCurBlock != NULL && fCurBlock->fEnd == NULL); 273 prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 274 } 275 fPos = prev; 276 } 277 return pos; 278} 279 280// reset works by skipping through the spare blocks at the start (or end) 281// of the doubly linked list until a non-empty one is found. The fPos 282// member is then set to the first (or last) element in the block. If 283// there are no elements in the deque both fCurBlock and fPos will come 284// out of this routine NULL. 285void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { 286 fElemSize = d.fElemSize; 287 288 if (kFront_IterStart == startLoc) { 289 // initialize the iterator to start at the front 290 fCurBlock = d.fFront; 291 while (NULL != fCurBlock && NULL == fCurBlock->fBegin) { 292 fCurBlock = fCurBlock->fNext; 293 } 294 fPos = fCurBlock ? fCurBlock->fBegin : NULL; 295 } else { 296 // initialize the iterator to start at the back 297 fCurBlock = d.fBack; 298 while (NULL != fCurBlock && NULL == fCurBlock->fEnd) { 299 fCurBlock = fCurBlock->fPrev; 300 } 301 fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; 302 } 303} 304