| OLD | NEW |
| 1 | 1 |
| 2 /* | 2 /* |
| 3 * Copyright 2006 The Android Open Source Project | 3 * Copyright 2006 The Android Open Source Project |
| 4 * | 4 * |
| 5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
| 6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
| 7 */ | 7 */ |
| 8 | 8 |
| 9 | 9 |
| 10 #include "SkDeque.h" | 10 #include "SkDeque.h" |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 93 goto INIT_CHUNK; | 93 goto INIT_CHUNK; |
| 94 } | 94 } |
| 95 } | 95 } |
| 96 | 96 |
| 97 first->fBegin = begin; | 97 first->fBegin = begin; |
| 98 | 98 |
| 99 if (NULL == fFront) { | 99 if (NULL == fFront) { |
| 100 SkASSERT(NULL == fBack); | 100 SkASSERT(NULL == fBack); |
| 101 fFront = fBack = begin; | 101 fFront = fBack = begin; |
| 102 } else { | 102 } else { |
| 103 SkASSERT(NULL != fBack); | 103 SkASSERT(fBack); |
| 104 fFront = begin; | 104 fFront = begin; |
| 105 } | 105 } |
| 106 | 106 |
| 107 return begin; | 107 return begin; |
| 108 } | 108 } |
| 109 | 109 |
| 110 void* SkDeque::push_back() { | 110 void* SkDeque::push_back() { |
| 111 fCount += 1; | 111 fCount += 1; |
| 112 | 112 |
| 113 if (NULL == fBackBlock) { | 113 if (NULL == fBackBlock) { |
| (...skipping 20 matching lines...) Expand all Loading... |
| 134 } | 134 } |
| 135 } | 135 } |
| 136 | 136 |
| 137 last->fEnd = end; | 137 last->fEnd = end; |
| 138 end -= fElemSize; | 138 end -= fElemSize; |
| 139 | 139 |
| 140 if (NULL == fBack) { | 140 if (NULL == fBack) { |
| 141 SkASSERT(NULL == fFront); | 141 SkASSERT(NULL == fFront); |
| 142 fFront = fBack = end; | 142 fFront = fBack = end; |
| 143 } else { | 143 } else { |
| 144 SkASSERT(NULL != fFront); | 144 SkASSERT(fFront); |
| 145 fBack = end; | 145 fBack = end; |
| 146 } | 146 } |
| 147 | 147 |
| 148 return end; | 148 return end; |
| 149 } | 149 } |
| 150 | 150 |
| 151 void SkDeque::pop_front() { | 151 void SkDeque::pop_front() { |
| 152 SkASSERT(fCount > 0); | 152 SkASSERT(fCount > 0); |
| 153 fCount -= 1; | 153 fCount -= 1; |
| 154 | 154 |
| 155 Block* first = fFrontBlock; | 155 Block* first = fFrontBlock; |
| 156 | 156 |
| 157 SkASSERT(first != NULL); | 157 SkASSERT(first != NULL); |
| 158 | 158 |
| 159 if (first->fBegin == NULL) { // we were marked empty from before | 159 if (first->fBegin == NULL) { // we were marked empty from before |
| 160 first = first->fNext; | 160 first = first->fNext; |
| 161 first->fPrev = NULL; | 161 first->fPrev = NULL; |
| 162 this->freeBlock(fFrontBlock); | 162 this->freeBlock(fFrontBlock); |
| 163 fFrontBlock = first; | 163 fFrontBlock = first; |
| 164 SkASSERT(first != NULL); // else we popped too far | 164 SkASSERT(first != NULL); // else we popped too far |
| 165 } | 165 } |
| 166 | 166 |
| 167 char* begin = first->fBegin + fElemSize; | 167 char* begin = first->fBegin + fElemSize; |
| 168 SkASSERT(begin <= first->fEnd); | 168 SkASSERT(begin <= first->fEnd); |
| 169 | 169 |
| 170 if (begin < fFrontBlock->fEnd) { | 170 if (begin < fFrontBlock->fEnd) { |
| 171 first->fBegin = begin; | 171 first->fBegin = begin; |
| 172 SkASSERT(NULL != first->fBegin); | 172 SkASSERT(first->fBegin); |
| 173 fFront = first->fBegin; | 173 fFront = first->fBegin; |
| 174 } else { | 174 } else { |
| 175 first->fBegin = first->fEnd = NULL; // mark as empty | 175 first->fBegin = first->fEnd = NULL; // mark as empty |
| 176 if (NULL == first->fNext) { | 176 if (NULL == first->fNext) { |
| 177 fFront = fBack = NULL; | 177 fFront = fBack = NULL; |
| 178 } else { | 178 } else { |
| 179 SkASSERT(NULL != first->fNext->fBegin); | 179 SkASSERT(first->fNext->fBegin); |
| 180 fFront = first->fNext->fBegin; | 180 fFront = first->fNext->fBegin; |
| 181 } | 181 } |
| 182 } | 182 } |
| 183 } | 183 } |
| 184 | 184 |
| 185 void SkDeque::pop_back() { | 185 void SkDeque::pop_back() { |
| 186 SkASSERT(fCount > 0); | 186 SkASSERT(fCount > 0); |
| 187 fCount -= 1; | 187 fCount -= 1; |
| 188 | 188 |
| 189 Block* last = fBackBlock; | 189 Block* last = fBackBlock; |
| 190 | 190 |
| 191 SkASSERT(last != NULL); | 191 SkASSERT(last != NULL); |
| 192 | 192 |
| 193 if (last->fEnd == NULL) { // we were marked empty from before | 193 if (last->fEnd == NULL) { // we were marked empty from before |
| 194 last = last->fPrev; | 194 last = last->fPrev; |
| 195 last->fNext = NULL; | 195 last->fNext = NULL; |
| 196 this->freeBlock(fBackBlock); | 196 this->freeBlock(fBackBlock); |
| 197 fBackBlock = last; | 197 fBackBlock = last; |
| 198 SkASSERT(last != NULL); // else we popped too far | 198 SkASSERT(last != NULL); // else we popped too far |
| 199 } | 199 } |
| 200 | 200 |
| 201 char* end = last->fEnd - fElemSize; | 201 char* end = last->fEnd - fElemSize; |
| 202 SkASSERT(end >= last->fBegin); | 202 SkASSERT(end >= last->fBegin); |
| 203 | 203 |
| 204 if (end > last->fBegin) { | 204 if (end > last->fBegin) { |
| 205 last->fEnd = end; | 205 last->fEnd = end; |
| 206 SkASSERT(NULL != last->fEnd); | 206 SkASSERT(last->fEnd); |
| 207 fBack = last->fEnd - fElemSize; | 207 fBack = last->fEnd - fElemSize; |
| 208 } else { | 208 } else { |
| 209 last->fBegin = last->fEnd = NULL; // mark as empty | 209 last->fBegin = last->fEnd = NULL; // mark as empty |
| 210 if (NULL == last->fPrev) { | 210 if (NULL == last->fPrev) { |
| 211 fFront = fBack = NULL; | 211 fFront = fBack = NULL; |
| 212 } else { | 212 } else { |
| 213 SkASSERT(NULL != last->fPrev->fEnd); | 213 SkASSERT(last->fPrev->fEnd); |
| 214 fBack = last->fPrev->fEnd - fElemSize; | 214 fBack = last->fPrev->fEnd - fElemSize; |
| 215 } | 215 } |
| 216 } | 216 } |
| 217 } | 217 } |
| 218 | 218 |
| 219 int SkDeque::numBlocksAllocated() const { | 219 int SkDeque::numBlocksAllocated() const { |
| 220 int numBlocks = 0; | 220 int numBlocks = 0; |
| 221 | 221 |
| 222 for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { | 222 for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) { |
| 223 ++numBlocks; | 223 ++numBlocks; |
| (...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 286 // of the doubly linked list until a non-empty one is found. The fPos | 286 // of the doubly linked list until a non-empty one is found. The fPos |
| 287 // member is then set to the first (or last) element in the block. If | 287 // member is then set to the first (or last) element in the block. If |
| 288 // there are no elements in the deque both fCurBlock and fPos will come | 288 // there are no elements in the deque both fCurBlock and fPos will come |
| 289 // out of this routine NULL. | 289 // out of this routine NULL. |
| 290 void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { | 290 void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) { |
| 291 fElemSize = d.fElemSize; | 291 fElemSize = d.fElemSize; |
| 292 | 292 |
| 293 if (kFront_IterStart == startLoc) { | 293 if (kFront_IterStart == startLoc) { |
| 294 // initialize the iterator to start at the front | 294 // initialize the iterator to start at the front |
| 295 fCurBlock = d.fFrontBlock; | 295 fCurBlock = d.fFrontBlock; |
| 296 while (NULL != fCurBlock && NULL == fCurBlock->fBegin) { | 296 while (fCurBlock && NULL == fCurBlock->fBegin) { |
| 297 fCurBlock = fCurBlock->fNext; | 297 fCurBlock = fCurBlock->fNext; |
| 298 } | 298 } |
| 299 fPos = fCurBlock ? fCurBlock->fBegin : NULL; | 299 fPos = fCurBlock ? fCurBlock->fBegin : NULL; |
| 300 } else { | 300 } else { |
| 301 // initialize the iterator to start at the back | 301 // initialize the iterator to start at the back |
| 302 fCurBlock = d.fBackBlock; | 302 fCurBlock = d.fBackBlock; |
| 303 while (NULL != fCurBlock && NULL == fCurBlock->fEnd) { | 303 while (fCurBlock && NULL == fCurBlock->fEnd) { |
| 304 fCurBlock = fCurBlock->fPrev; | 304 fCurBlock = fCurBlock->fPrev; |
| 305 } | 305 } |
| 306 fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; | 306 fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL; |
| 307 } | 307 } |
| 308 } | 308 } |
| OLD | NEW |