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