Line data Source code
1 : /*
2 : * Copyright 2006 The Android Open Source Project
3 : *
4 : * Use of this source code is governed by a BSD-style license that can be
5 : * found in the LICENSE file.
6 : */
7 :
8 : #include "SkDeque.h"
9 : #include "SkMalloc.h"
10 :
11 : struct SkDeque::Block {
12 : Block* fNext;
13 : Block* fPrev;
14 : char* fBegin; // start of used section in this chunk
15 : char* fEnd; // end of used section in this chunk
16 : char* fStop; // end of the allocated chunk
17 :
18 148 : char* start() { return (char*)(this + 1); }
19 : const char* start() const { return (const char*)(this + 1); }
20 :
21 148 : void init(size_t size) {
22 148 : fNext = fPrev = nullptr;
23 148 : fBegin = fEnd = nullptr;
24 148 : fStop = (char*)this + size;
25 148 : }
26 : };
27 :
28 0 : SkDeque::SkDeque(size_t elemSize, int allocCount)
29 : : fElemSize(elemSize)
30 : , fInitialStorage(nullptr)
31 : , fCount(0)
32 0 : , fAllocCount(allocCount) {
33 0 : SkASSERT(allocCount >= 1);
34 0 : fFrontBlock = fBackBlock = nullptr;
35 0 : fFront = fBack = nullptr;
36 0 : }
37 :
38 148 : SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
39 : : fElemSize(elemSize)
40 : , fInitialStorage(storage)
41 : , fCount(0)
42 148 : , fAllocCount(allocCount) {
43 148 : SkASSERT(storageSize == 0 || storage != nullptr);
44 148 : SkASSERT(allocCount >= 1);
45 :
46 148 : if (storageSize >= sizeof(Block) + elemSize) {
47 148 : fFrontBlock = (Block*)storage;
48 148 : fFrontBlock->init(storageSize);
49 : } else {
50 0 : fFrontBlock = nullptr;
51 : }
52 148 : fBackBlock = fFrontBlock;
53 148 : fFront = fBack = nullptr;
54 148 : }
55 :
56 192 : SkDeque::~SkDeque() {
57 96 : Block* head = fFrontBlock;
58 96 : Block* initialHead = (Block*)fInitialStorage;
59 :
60 288 : while (head) {
61 96 : Block* next = head->fNext;
62 96 : if (head != initialHead) {
63 0 : this->freeBlock(head);
64 : }
65 96 : head = next;
66 : }
67 96 : }
68 :
69 0 : void* SkDeque::push_front() {
70 0 : fCount += 1;
71 :
72 0 : if (nullptr == fFrontBlock) {
73 0 : fFrontBlock = this->allocateBlock(fAllocCount);
74 0 : fBackBlock = fFrontBlock; // update our linklist
75 : }
76 :
77 0 : Block* first = fFrontBlock;
78 : char* begin;
79 :
80 0 : if (nullptr == first->fBegin) {
81 : INIT_CHUNK:
82 0 : first->fEnd = first->fStop;
83 0 : begin = first->fStop - fElemSize;
84 : } else {
85 0 : begin = first->fBegin - fElemSize;
86 0 : if (begin < first->start()) { // no more room in this chunk
87 : // should we alloc more as we accumulate more elements?
88 0 : first = this->allocateBlock(fAllocCount);
89 0 : first->fNext = fFrontBlock;
90 0 : fFrontBlock->fPrev = first;
91 0 : fFrontBlock = first;
92 0 : goto INIT_CHUNK;
93 : }
94 : }
95 :
96 0 : first->fBegin = begin;
97 :
98 0 : if (nullptr == fFront) {
99 0 : SkASSERT(nullptr == fBack);
100 0 : fFront = fBack = begin;
101 : } else {
102 0 : SkASSERT(fBack);
103 0 : fFront = begin;
104 : }
105 :
106 0 : return begin;
107 : }
108 :
109 1360 : void* SkDeque::push_back() {
110 1360 : fCount += 1;
111 :
112 1360 : if (nullptr == fBackBlock) {
113 0 : fBackBlock = this->allocateBlock(fAllocCount);
114 0 : fFrontBlock = fBackBlock; // update our linklist
115 : }
116 :
117 1360 : Block* last = fBackBlock;
118 : char* end;
119 :
120 1360 : if (nullptr == last->fBegin) {
121 : INIT_CHUNK:
122 148 : last->fBegin = last->start();
123 148 : end = last->fBegin + fElemSize;
124 : } else {
125 1212 : end = last->fEnd + fElemSize;
126 1212 : if (end > last->fStop) { // no more room in this chunk
127 : // should we alloc more as we accumulate more elements?
128 0 : last = this->allocateBlock(fAllocCount);
129 0 : last->fPrev = fBackBlock;
130 0 : fBackBlock->fNext = last;
131 0 : fBackBlock = last;
132 0 : goto INIT_CHUNK;
133 : }
134 : }
135 :
136 1360 : last->fEnd = end;
137 1360 : end -= fElemSize;
138 :
139 1360 : if (nullptr == fBack) {
140 148 : SkASSERT(nullptr == fFront);
141 148 : fFront = fBack = end;
142 : } else {
143 1212 : SkASSERT(fFront);
144 1212 : fBack = end;
145 : }
146 :
147 1360 : return end;
148 : }
149 :
150 0 : void SkDeque::pop_front() {
151 0 : SkASSERT(fCount > 0);
152 0 : fCount -= 1;
153 :
154 0 : Block* first = fFrontBlock;
155 :
156 0 : SkASSERT(first != nullptr);
157 :
158 0 : if (first->fBegin == nullptr) { // we were marked empty from before
159 0 : first = first->fNext;
160 0 : first->fPrev = nullptr;
161 0 : this->freeBlock(fFrontBlock);
162 0 : fFrontBlock = first;
163 0 : SkASSERT(first != nullptr); // else we popped too far
164 : }
165 :
166 0 : char* begin = first->fBegin + fElemSize;
167 0 : SkASSERT(begin <= first->fEnd);
168 :
169 0 : if (begin < fFrontBlock->fEnd) {
170 0 : first->fBegin = begin;
171 0 : SkASSERT(first->fBegin);
172 0 : fFront = first->fBegin;
173 : } else {
174 0 : first->fBegin = first->fEnd = nullptr; // mark as empty
175 0 : if (nullptr == first->fNext) {
176 0 : fFront = fBack = nullptr;
177 : } else {
178 0 : SkASSERT(first->fNext->fBegin);
179 0 : fFront = first->fNext->fBegin;
180 : }
181 : }
182 0 : }
183 :
184 1308 : void SkDeque::pop_back() {
185 1308 : SkASSERT(fCount > 0);
186 1308 : fCount -= 1;
187 :
188 1308 : Block* last = fBackBlock;
189 :
190 1308 : SkASSERT(last != nullptr);
191 :
192 1308 : if (last->fEnd == nullptr) { // we were marked empty from before
193 0 : last = last->fPrev;
194 0 : last->fNext = nullptr;
195 0 : this->freeBlock(fBackBlock);
196 0 : fBackBlock = last;
197 0 : SkASSERT(last != nullptr); // else we popped too far
198 : }
199 :
200 1308 : char* end = last->fEnd - fElemSize;
201 1308 : SkASSERT(end >= last->fBegin);
202 :
203 1308 : if (end > last->fBegin) {
204 1212 : last->fEnd = end;
205 1212 : SkASSERT(last->fEnd);
206 1212 : fBack = last->fEnd - fElemSize;
207 : } else {
208 96 : last->fBegin = last->fEnd = nullptr; // mark as empty
209 96 : if (nullptr == last->fPrev) {
210 96 : fFront = fBack = nullptr;
211 : } else {
212 0 : SkASSERT(last->fPrev->fEnd);
213 0 : fBack = last->fPrev->fEnd - fElemSize;
214 : }
215 : }
216 1308 : }
217 :
218 0 : int SkDeque::numBlocksAllocated() const {
219 0 : int numBlocks = 0;
220 :
221 0 : for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
222 0 : ++numBlocks;
223 : }
224 :
225 0 : return numBlocks;
226 : }
227 :
228 0 : SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
229 0 : Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
230 0 : newBlock->init(sizeof(Block) + allocCount * fElemSize);
231 0 : return newBlock;
232 : }
233 :
234 0 : void SkDeque::freeBlock(Block* block) {
235 0 : sk_free(block);
236 0 : }
237 :
238 : ///////////////////////////////////////////////////////////////////////////////
239 :
240 0 : SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {}
241 :
242 1210 : SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
243 1210 : this->reset(d, startLoc);
244 1210 : }
245 :
246 : // Due to how reset and next work, next actually returns the current element
247 : // pointed to by fPos and then updates fPos to point to the next one.
248 4674 : void* SkDeque::Iter::next() {
249 4674 : char* pos = fPos;
250 :
251 4674 : if (pos) { // if we were valid, try to move to the next setting
252 3464 : char* next = pos + fElemSize;
253 3464 : SkASSERT(next <= fCurBlock->fEnd);
254 3464 : if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
255 0 : do {
256 1210 : fCurBlock = fCurBlock->fNext;
257 1210 : } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr);
258 1210 : next = fCurBlock ? fCurBlock->fBegin : nullptr;
259 : }
260 3464 : fPos = next;
261 : }
262 4674 : return pos;
263 : }
264 :
265 : // Like next, prev actually returns the current element pointed to by fPos and
266 : // then makes fPos point to the previous element.
267 0 : void* SkDeque::Iter::prev() {
268 0 : char* pos = fPos;
269 :
270 0 : if (pos) { // if we were valid, try to move to the prior setting
271 0 : char* prev = pos - fElemSize;
272 0 : SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
273 0 : if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
274 0 : do {
275 0 : fCurBlock = fCurBlock->fPrev;
276 0 : } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr);
277 0 : prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
278 : }
279 0 : fPos = prev;
280 : }
281 0 : return pos;
282 : }
283 :
284 : // reset works by skipping through the spare blocks at the start (or end)
285 : // of the doubly linked list until a non-empty one is found. The fPos
286 : // member is then set to the first (or last) element in the block. If
287 : // there are no elements in the deque both fCurBlock and fPos will come
288 : // out of this routine nullptr.
289 1210 : void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
290 1210 : fElemSize = d.fElemSize;
291 :
292 1210 : if (kFront_IterStart == startLoc) {
293 : // initialize the iterator to start at the front
294 1210 : fCurBlock = d.fFrontBlock;
295 1210 : while (fCurBlock && nullptr == fCurBlock->fBegin) {
296 0 : fCurBlock = fCurBlock->fNext;
297 : }
298 1210 : fPos = fCurBlock ? fCurBlock->fBegin : nullptr;
299 : } else {
300 : // initialize the iterator to start at the back
301 0 : fCurBlock = d.fBackBlock;
302 0 : while (fCurBlock && nullptr == fCurBlock->fEnd) {
303 0 : fCurBlock = fCurBlock->fPrev;
304 : }
305 0 : fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
306 : }
307 1210 : }
|
