| OLD | NEW |
|---|
| (Empty) |
| 1 /* libs/graphics/sgl/SkDeque.cpp | |
| 2 ** | |
| 3 ** Copyright 2006, The Android Open Source Project | |
| 4 ** | |
| 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 | |
| 8 ** | |
| 9 ** http://www.apache.org/licenses/LICENSE-2.0 | |
| 10 ** | |
| 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 | |
| 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 | |
| 28 | |
| 29 char* start() { return (char*)(this + 1); } | |
| 30 const char* start() const { return (const char*)(this + 1); } | |
| 31 | |
| 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); | |
| 47 | |
| 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; | |
| 72 | |
| 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 } | |
| 111 | |
| 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 } | |
| 147 | |
| 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); | |
| 181 | |
| 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; | |
| 205 | |
| 206 SkASSERT(last != NULL); | |
| 207 | |
| 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 } | |
| 215 | |
| 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 | |
| 228 SkDeque::Iter::Iter(const SkDeque& d) : fElemSize(d.fElemSize) { | |
| 229 fHead = d.fFront; | |
| 230 while (fHead != NULL && fHead->fBegin == NULL) { | |
| 231 fHead = fHead->fNext; | |
| 232 } | |
| 233 fPos = fHead ? fHead->fBegin : NULL; | |
| 234 } | |
| 235 | |
| 236 void* SkDeque::Iter::next() { | |
| 237 char* pos = fPos; | |
| 238 | |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 113827:
Remove the remainder of the skia source code from the Chromium repo.... (Closed)
Base URL: svn://chrome-svn/chrome/trunk/src/