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 |