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#define INIT_ELEM_COUNT 1 // should we let the caller set this? 13 14struct SkDeque::Head { 15 Head* fNext; 16 Head* fPrev; 17 char* fBegin; // start of used section in this chunk 18 char* fEnd; // end of used section in this chunk 19 char* fStop; // end of the allocated chunk 20 21 char* start() { return (char*)(this + 1); } 22 const char* start() const { return (const char*)(this + 1); } 23 24 void init(size_t size) { 25 fNext = fPrev = NULL; 26 fBegin = fEnd = NULL; 27 fStop = (char*)this + size; 28 } 29}; 30 31SkDeque::SkDeque(size_t elemSize) 32 : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) { 33 fFront = fBack = NULL; 34} 35 36SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize) 37 : fElemSize(elemSize), fInitialStorage(storage), fCount(0) { 38 SkASSERT(storageSize == 0 || storage != NULL); 39 40 if (storageSize >= sizeof(Head) + elemSize) { 41 fFront = (Head*)storage; 42 fFront->init(storageSize); 43 } else { 44 fFront = NULL; 45 } 46 fBack = fFront; 47} 48 49SkDeque::~SkDeque() { 50 Head* head = fFront; 51 Head* initialHead = (Head*)fInitialStorage; 52 53 while (head) { 54 Head* next = head->fNext; 55 if (head != initialHead) { 56 sk_free(head); 57 } 58 head = next; 59 } 60} 61 62const void* SkDeque::front() const { 63 Head* front = fFront; 64 65 if (NULL == front) { 66 return NULL; 67 } 68 if (NULL == front->fBegin) { 69 front = front->fNext; 70 if (NULL == front) { 71 return NULL; 72 } 73 } 74 SkASSERT(front->fBegin); 75 return front->fBegin; 76} 77 78const void* SkDeque::back() const { 79 Head* back = fBack; 80 81 if (NULL == back) { 82 return NULL; 83 } 84 if (NULL == back->fEnd) { // marked as deleted 85 back = back->fPrev; 86 if (NULL == back) { 87 return NULL; 88 } 89 } 90 SkASSERT(back->fEnd); 91 return back->fEnd - fElemSize; 92} 93 94void* SkDeque::push_front() { 95 fCount += 1; 96 97 if (NULL == fFront) { 98 fFront = (Head*)sk_malloc_throw(sizeof(Head) + 99 INIT_ELEM_COUNT * fElemSize); 100 fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); 101 fBack = fFront; // update our linklist 102 } 103 104 Head* first = fFront; 105 char* begin; 106 107 if (NULL == first->fBegin) { 108 INIT_CHUNK: 109 first->fEnd = first->fStop; 110 begin = first->fStop - fElemSize; 111 } else { 112 begin = first->fBegin - fElemSize; 113 if (begin < first->start()) { // no more room in this chunk 114 // should we alloc more as we accumulate more elements? 115 size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; 116 117 first = (Head*)sk_malloc_throw(size); 118 first->init(size); 119 first->fNext = fFront; 120 fFront->fPrev = first; 121 fFront = first; 122 goto INIT_CHUNK; 123 } 124 } 125 126 first->fBegin = begin; 127 return begin; 128} 129 130void* SkDeque::push_back() { 131 fCount += 1; 132 133 if (NULL == fBack) { 134 fBack = (Head*)sk_malloc_throw(sizeof(Head) + 135 INIT_ELEM_COUNT * fElemSize); 136 fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); 137 fFront = fBack; // update our linklist 138 } 139 140 Head* last = fBack; 141 char* end; 142 143 if (NULL == last->fBegin) { 144 INIT_CHUNK: 145 last->fBegin = last->start(); 146 end = last->fBegin + fElemSize; 147 } else { 148 end = last->fEnd + fElemSize; 149 if (end > last->fStop) { // no more room in this chunk 150 // should we alloc more as we accumulate more elements? 151 size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; 152 153 last = (Head*)sk_malloc_throw(size); 154 last->init(size); 155 last->fPrev = fBack; 156 fBack->fNext = last; 157 fBack = last; 158 goto INIT_CHUNK; 159 } 160 } 161 162 last->fEnd = end; 163 return end - fElemSize; 164} 165 166void SkDeque::pop_front() { 167 SkASSERT(fCount > 0); 168 fCount -= 1; 169 170 Head* first = fFront; 171 172 SkASSERT(first != NULL); 173 174 if (first->fBegin == NULL) { // we were marked empty from before 175 first = first->fNext; 176 first->fPrev = NULL; 177 sk_free(fFront); 178 fFront = first; 179 SkASSERT(first != NULL); // else we popped too far 180 } 181 182 char* begin = first->fBegin + fElemSize; 183 SkASSERT(begin <= first->fEnd); 184 185 if (begin < fFront->fEnd) { 186 first->fBegin = begin; 187 } else { 188 first->fBegin = first->fEnd = NULL; // mark as empty 189 } 190} 191 192void SkDeque::pop_back() { 193 SkASSERT(fCount > 0); 194 fCount -= 1; 195 196 Head* last = fBack; 197 198 SkASSERT(last != NULL); 199 200 if (last->fEnd == NULL) { // we were marked empty from before 201 last = last->fPrev; 202 last->fNext = NULL; 203 sk_free(fBack); 204 fBack = last; 205 SkASSERT(last != NULL); // else we popped too far 206 } 207 208 char* end = last->fEnd - fElemSize; 209 SkASSERT(end >= last->fBegin); 210 211 if (end > last->fBegin) { 212 last->fEnd = end; 213 } else { 214 last->fBegin = last->fEnd = NULL; // mark as empty 215 } 216} 217 218/////////////////////////////////////////////////////////////////////////////// 219 220SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {} 221 222SkDeque::F2BIter::F2BIter(const SkDeque& d) { 223 this->reset(d); 224} 225 226void* SkDeque::F2BIter::next() { 227 char* pos = fPos; 228 229 if (pos) { // if we were valid, try to move to the next setting 230 char* next = pos + fElemSize; 231 SkASSERT(next <= fHead->fEnd); 232 if (next == fHead->fEnd) { // exhausted this chunk, move to next 233 do { 234 fHead = fHead->fNext; 235 } while (fHead != NULL && fHead->fBegin == NULL); 236 next = fHead ? fHead->fBegin : NULL; 237 } 238 fPos = next; 239 } 240 return pos; 241} 242 243void SkDeque::F2BIter::reset(const SkDeque& d) { 244 fElemSize = d.fElemSize; 245 fHead = d.fFront; 246 while (fHead != NULL && fHead->fBegin == NULL) { 247 fHead = fHead->fNext; 248 } 249 fPos = fHead ? fHead->fBegin : NULL; 250} 251