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