epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame^] | 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 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 9 | |
| 10 | #include "SkDeque.h" |
| 11 | |
| 12 | #define INIT_ELEM_COUNT 1 // should we let the caller set this? |
| 13 | |
| 14 | struct 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 |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 20 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 21 | char* start() { return (char*)(this + 1); } |
| 22 | const char* start() const { return (const char*)(this + 1); } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 23 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 24 | void init(size_t size) { |
| 25 | fNext = fPrev = NULL; |
| 26 | fBegin = fEnd = NULL; |
| 27 | fStop = (char*)this + size; |
| 28 | } |
| 29 | }; |
| 30 | |
| 31 | SkDeque::SkDeque(size_t elemSize) |
| 32 | : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) { |
| 33 | fFront = fBack = NULL; |
| 34 | } |
| 35 | |
| 36 | SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize) |
| 37 | : fElemSize(elemSize), fInitialStorage(storage), fCount(0) { |
| 38 | SkASSERT(storageSize == 0 || storage != NULL); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 39 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
| 49 | SkDeque::~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 | |
| 62 | const void* SkDeque::front() const { |
| 63 | Head* front = fFront; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 64 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
| 78 | const 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 | |
| 94 | void* 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 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 103 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
| 130 | void* 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 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 139 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
| 166 | void SkDeque::pop_front() { |
| 167 | SkASSERT(fCount > 0); |
| 168 | fCount -= 1; |
| 169 | |
| 170 | Head* first = fFront; |
| 171 | |
| 172 | SkASSERT(first != NULL); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 173 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
| 192 | void SkDeque::pop_back() { |
| 193 | SkASSERT(fCount > 0); |
| 194 | fCount -= 1; |
| 195 | |
| 196 | Head* last = fBack; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 197 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 198 | SkASSERT(last != NULL); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 199 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 207 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
vandebo@chromium.org | e1bc274 | 2011-06-21 22:26:39 +0000 | [diff] [blame] | 220 | SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {} |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame] | 221 | |
| 222 | SkDeque::F2BIter::F2BIter(const SkDeque& d) { |
| 223 | this->reset(d); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 224 | } |
| 225 | |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 226 | void* SkDeque::F2BIter::next() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 227 | char* pos = fPos; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 228 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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 | |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame] | 243 | void 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 | } |