reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1 | /* libs/graphics/sgl/SkDeque.cpp |
| 2 | ** |
| 3 | ** Copyright 2006, The Android Open Source Project |
| 4 | ** |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 5 | ** Licensed under the Apache License, Version 2.0 (the "License"); |
| 6 | ** you may not use this file except in compliance with the License. |
| 7 | ** You may obtain a copy of the License at |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 8 | ** |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 9 | ** http://www.apache.org/licenses/LICENSE-2.0 |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 10 | ** |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 11 | ** Unless required by applicable law or agreed to in writing, software |
| 12 | ** distributed under the License is distributed on an "AS IS" BASIS, |
| 13 | ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 14 | ** See the License for the specific language governing permissions and |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 15 | ** limitations under the License. |
| 16 | */ |
| 17 | |
| 18 | #include "SkDeque.h" |
| 19 | |
| 20 | #define INIT_ELEM_COUNT 1 // should we let the caller set this? |
| 21 | |
| 22 | struct SkDeque::Head { |
| 23 | Head* fNext; |
| 24 | Head* fPrev; |
| 25 | char* fBegin; // start of used section in this chunk |
| 26 | char* fEnd; // end of used section in this chunk |
| 27 | char* fStop; // end of the allocated chunk |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 28 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 29 | char* start() { return (char*)(this + 1); } |
| 30 | const char* start() const { return (const char*)(this + 1); } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 31 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 32 | void init(size_t size) { |
| 33 | fNext = fPrev = NULL; |
| 34 | fBegin = fEnd = NULL; |
| 35 | fStop = (char*)this + size; |
| 36 | } |
| 37 | }; |
| 38 | |
| 39 | SkDeque::SkDeque(size_t elemSize) |
| 40 | : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) { |
| 41 | fFront = fBack = NULL; |
| 42 | } |
| 43 | |
| 44 | SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize) |
| 45 | : fElemSize(elemSize), fInitialStorage(storage), fCount(0) { |
| 46 | SkASSERT(storageSize == 0 || storage != NULL); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 47 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 48 | if (storageSize >= sizeof(Head) + elemSize) { |
| 49 | fFront = (Head*)storage; |
| 50 | fFront->init(storageSize); |
| 51 | } else { |
| 52 | fFront = NULL; |
| 53 | } |
| 54 | fBack = fFront; |
| 55 | } |
| 56 | |
| 57 | SkDeque::~SkDeque() { |
| 58 | Head* head = fFront; |
| 59 | Head* initialHead = (Head*)fInitialStorage; |
| 60 | |
| 61 | while (head) { |
| 62 | Head* next = head->fNext; |
| 63 | if (head != initialHead) { |
| 64 | sk_free(head); |
| 65 | } |
| 66 | head = next; |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | const void* SkDeque::front() const { |
| 71 | Head* front = fFront; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 72 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 73 | if (NULL == front) { |
| 74 | return NULL; |
| 75 | } |
| 76 | if (NULL == front->fBegin) { |
| 77 | front = front->fNext; |
| 78 | if (NULL == front) { |
| 79 | return NULL; |
| 80 | } |
| 81 | } |
| 82 | SkASSERT(front->fBegin); |
| 83 | return front->fBegin; |
| 84 | } |
| 85 | |
| 86 | const void* SkDeque::back() const { |
| 87 | Head* back = fBack; |
| 88 | |
| 89 | if (NULL == back) { |
| 90 | return NULL; |
| 91 | } |
| 92 | if (NULL == back->fEnd) { // marked as deleted |
| 93 | back = back->fPrev; |
| 94 | if (NULL == back) { |
| 95 | return NULL; |
| 96 | } |
| 97 | } |
| 98 | SkASSERT(back->fEnd); |
| 99 | return back->fEnd - fElemSize; |
| 100 | } |
| 101 | |
| 102 | void* SkDeque::push_front() { |
| 103 | fCount += 1; |
| 104 | |
| 105 | if (NULL == fFront) { |
| 106 | fFront = (Head*)sk_malloc_throw(sizeof(Head) + |
| 107 | INIT_ELEM_COUNT * fElemSize); |
| 108 | fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); |
| 109 | fBack = fFront; // update our linklist |
| 110 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 111 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 112 | Head* first = fFront; |
| 113 | char* begin; |
| 114 | |
| 115 | if (NULL == first->fBegin) { |
| 116 | INIT_CHUNK: |
| 117 | first->fEnd = first->fStop; |
| 118 | begin = first->fStop - fElemSize; |
| 119 | } else { |
| 120 | begin = first->fBegin - fElemSize; |
| 121 | if (begin < first->start()) { // no more room in this chunk |
| 122 | // should we alloc more as we accumulate more elements? |
| 123 | size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; |
| 124 | |
| 125 | first = (Head*)sk_malloc_throw(size); |
| 126 | first->init(size); |
| 127 | first->fNext = fFront; |
| 128 | fFront->fPrev = first; |
| 129 | fFront = first; |
| 130 | goto INIT_CHUNK; |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | first->fBegin = begin; |
| 135 | return begin; |
| 136 | } |
| 137 | |
| 138 | void* SkDeque::push_back() { |
| 139 | fCount += 1; |
| 140 | |
| 141 | if (NULL == fBack) { |
| 142 | fBack = (Head*)sk_malloc_throw(sizeof(Head) + |
| 143 | INIT_ELEM_COUNT * fElemSize); |
| 144 | fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize); |
| 145 | fFront = fBack; // update our linklist |
| 146 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 147 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 148 | Head* last = fBack; |
| 149 | char* end; |
| 150 | |
| 151 | if (NULL == last->fBegin) { |
| 152 | INIT_CHUNK: |
| 153 | last->fBegin = last->start(); |
| 154 | end = last->fBegin + fElemSize; |
| 155 | } else { |
| 156 | end = last->fEnd + fElemSize; |
| 157 | if (end > last->fStop) { // no more room in this chunk |
| 158 | // should we alloc more as we accumulate more elements? |
| 159 | size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize; |
| 160 | |
| 161 | last = (Head*)sk_malloc_throw(size); |
| 162 | last->init(size); |
| 163 | last->fPrev = fBack; |
| 164 | fBack->fNext = last; |
| 165 | fBack = last; |
| 166 | goto INIT_CHUNK; |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | last->fEnd = end; |
| 171 | return end - fElemSize; |
| 172 | } |
| 173 | |
| 174 | void SkDeque::pop_front() { |
| 175 | SkASSERT(fCount > 0); |
| 176 | fCount -= 1; |
| 177 | |
| 178 | Head* first = fFront; |
| 179 | |
| 180 | SkASSERT(first != NULL); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 181 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 182 | if (first->fBegin == NULL) { // we were marked empty from before |
| 183 | first = first->fNext; |
| 184 | first->fPrev = NULL; |
| 185 | sk_free(fFront); |
| 186 | fFront = first; |
| 187 | SkASSERT(first != NULL); // else we popped too far |
| 188 | } |
| 189 | |
| 190 | char* begin = first->fBegin + fElemSize; |
| 191 | SkASSERT(begin <= first->fEnd); |
| 192 | |
| 193 | if (begin < fFront->fEnd) { |
| 194 | first->fBegin = begin; |
| 195 | } else { |
| 196 | first->fBegin = first->fEnd = NULL; // mark as empty |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | void SkDeque::pop_back() { |
| 201 | SkASSERT(fCount > 0); |
| 202 | fCount -= 1; |
| 203 | |
| 204 | Head* last = fBack; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 205 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 206 | SkASSERT(last != NULL); |
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 | if (last->fEnd == NULL) { // we were marked empty from before |
| 209 | last = last->fPrev; |
| 210 | last->fNext = NULL; |
| 211 | sk_free(fBack); |
| 212 | fBack = last; |
| 213 | SkASSERT(last != NULL); // else we popped too far |
| 214 | } |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 215 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 216 | char* end = last->fEnd - fElemSize; |
| 217 | SkASSERT(end >= last->fBegin); |
| 218 | |
| 219 | if (end > last->fBegin) { |
| 220 | last->fEnd = end; |
| 221 | } else { |
| 222 | last->fBegin = last->fEnd = NULL; // mark as empty |
| 223 | } |
| 224 | } |
| 225 | |
| 226 | /////////////////////////////////////////////////////////////////////////////// |
| 227 | |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame^] | 228 | SkDeque::F2BIter::F2BIter() { |
| 229 | fPos = NULL; |
| 230 | } |
| 231 | |
| 232 | SkDeque::F2BIter::F2BIter(const SkDeque& d) { |
| 233 | this->reset(d); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 234 | } |
| 235 | |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 236 | void* SkDeque::F2BIter::next() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 237 | char* pos = fPos; |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 238 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 239 | if (pos) { // if we were valid, try to move to the next setting |
| 240 | char* next = pos + fElemSize; |
| 241 | SkASSERT(next <= fHead->fEnd); |
| 242 | if (next == fHead->fEnd) { // exhausted this chunk, move to next |
| 243 | do { |
| 244 | fHead = fHead->fNext; |
| 245 | } while (fHead != NULL && fHead->fBegin == NULL); |
| 246 | next = fHead ? fHead->fBegin : NULL; |
| 247 | } |
| 248 | fPos = next; |
| 249 | } |
| 250 | return pos; |
| 251 | } |
| 252 | |
bsalomon@google.com | d302f14 | 2011-03-03 13:54:13 +0000 | [diff] [blame^] | 253 | void SkDeque::F2BIter::reset(const SkDeque& d) { |
| 254 | fElemSize = d.fElemSize; |
| 255 | fHead = d.fFront; |
| 256 | while (fHead != NULL && fHead->fBegin == NULL) { |
| 257 | fHead = fHead->fNext; |
| 258 | } |
| 259 | fPos = fHead ? fHead->fBegin : NULL; |
| 260 | } |