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 "include/private/SkDeque.h"
9#include "include/private/SkMalloc.h"
10
11struct 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 char* start() { return (char*)(this + 1); }
19 const char* start() const { return (const char*)(this + 1); }
20
21 void init(size_t size) {
22 fNext = fPrev = nullptr;
23 fBegin = fEnd = nullptr;
24 fStop = (char*)this + size;
25 }
26};
27
28SkDeque::SkDeque(size_t elemSize, int allocCount)
29 : fElemSize(elemSize)
30 , fInitialStorage(nullptr)
31 , fCount(0)
32 , fAllocCount(allocCount) {
33 SkASSERT(allocCount >= 1);
34 fFrontBlock = fBackBlock = nullptr;
35 fFront = fBack = nullptr;
36}
37
38SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
39 : fElemSize(elemSize)
40 , fInitialStorage(storage)
41 , fCount(0)
42 , fAllocCount(allocCount) {
43 SkASSERT(storageSize == 0 || storage != nullptr);
44 SkASSERT(allocCount >= 1);
45
46 if (storageSize >= sizeof(Block) + elemSize) {
47 fFrontBlock = (Block*)storage;
48 fFrontBlock->init(storageSize);
49 } else {
50 fFrontBlock = nullptr;
51 }
52 fBackBlock = fFrontBlock;
53 fFront = fBack = nullptr;
54}
55
56SkDeque::~SkDeque() {
57 Block* head = fFrontBlock;
58 Block* initialHead = (Block*)fInitialStorage;
59
60 while (head) {
61 Block* next = head->fNext;
62 if (head != initialHead) {
63 this->freeBlock(head);
64 }
65 head = next;
66 }
67}
68
69void* SkDeque::push_front() {
70 fCount += 1;
71
72 if (nullptr == fFrontBlock) {
73 fFrontBlock = this->allocateBlock(fAllocCount);
74 fBackBlock = fFrontBlock; // update our linklist
75 }
76
77 Block* first = fFrontBlock;
78 char* begin;
79
80 if (nullptr == first->fBegin) {
81 INIT_CHUNK:
82 first->fEnd = first->fStop;
83 begin = first->fStop - fElemSize;
84 } else {
85 begin = first->fBegin - fElemSize;
86 if (begin < first->start()) { // no more room in this chunk
87 // should we alloc more as we accumulate more elements?
88 first = this->allocateBlock(fAllocCount);
89 first->fNext = fFrontBlock;
90 fFrontBlock->fPrev = first;
91 fFrontBlock = first;
92 goto INIT_CHUNK;
93 }
94 }
95
96 first->fBegin = begin;
97
98 if (nullptr == fFront) {
99 SkASSERT(nullptr == fBack);
100 fFront = fBack = begin;
101 } else {
102 SkASSERT(fBack);
103 fFront = begin;
104 }
105
106 return begin;
107}
108
109void* SkDeque::push_back() {
110 fCount += 1;
111
112 if (nullptr == fBackBlock) {
113 fBackBlock = this->allocateBlock(fAllocCount);
114 fFrontBlock = fBackBlock; // update our linklist
115 }
116
117 Block* last = fBackBlock;
118 char* end;
119
120 if (nullptr == last->fBegin) {
121 INIT_CHUNK:
122 last->fBegin = last->start();
123 end = last->fBegin + fElemSize;
124 } else {
125 end = last->fEnd + fElemSize;
126 if (end > last->fStop) { // no more room in this chunk
127 // should we alloc more as we accumulate more elements?
128 last = this->allocateBlock(fAllocCount);
129 last->fPrev = fBackBlock;
130 fBackBlock->fNext = last;
131 fBackBlock = last;
132 goto INIT_CHUNK;
133 }
134 }
135
136 last->fEnd = end;
137 end -= fElemSize;
138
139 if (nullptr == fBack) {
140 SkASSERT(nullptr == fFront);
141 fFront = fBack = end;
142 } else {
143 SkASSERT(fFront);
144 fBack = end;
145 }
146
147 return end;
148}
149
150void SkDeque::pop_front() {
151 SkASSERT(fCount > 0);
152 fCount -= 1;
153
154 Block* first = fFrontBlock;
155
156 SkASSERT(first != nullptr);
157
158 if (first->fBegin == nullptr) { // we were marked empty from before
159 first = first->fNext;
160 SkASSERT(first != nullptr); // else we popped too far
161 first->fPrev = nullptr;
162 this->freeBlock(fFrontBlock);
163 fFrontBlock = first;
164 }
165
166 char* begin = first->fBegin + fElemSize;
167 SkASSERT(begin <= first->fEnd);
168
169 if (begin < fFrontBlock->fEnd) {
170 first->fBegin = begin;
171 SkASSERT(first->fBegin);
172 fFront = first->fBegin;
173 } else {
174 first->fBegin = first->fEnd = nullptr; // mark as empty
175 if (nullptr == first->fNext) {
176 fFront = fBack = nullptr;
177 } else {
178 SkASSERT(first->fNext->fBegin);
179 fFront = first->fNext->fBegin;
180 }
181 }
182}
183
184void SkDeque::pop_back() {
185 SkASSERT(fCount > 0);
186 fCount -= 1;
187
188 Block* last = fBackBlock;
189
190 SkASSERT(last != nullptr);
191
192 if (last->fEnd == nullptr) { // we were marked empty from before
193 last = last->fPrev;
194 SkASSERT(last != nullptr); // else we popped too far
195 last->fNext = nullptr;
196 this->freeBlock(fBackBlock);
197 fBackBlock = last;
198 }
199
200 char* end = last->fEnd - fElemSize;
201 SkASSERT(end >= last->fBegin);
202
203 if (end > last->fBegin) {
204 last->fEnd = end;
205 SkASSERT(last->fEnd);
206 fBack = last->fEnd - fElemSize;
207 } else {
208 last->fBegin = last->fEnd = nullptr; // mark as empty
209 if (nullptr == last->fPrev) {
210 fFront = fBack = nullptr;
211 } else {
212 SkASSERT(last->fPrev->fEnd);
213 fBack = last->fPrev->fEnd - fElemSize;
214 }
215 }
216}
217
218int SkDeque::numBlocksAllocated() const {
219 int numBlocks = 0;
220
221 for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
222 ++numBlocks;
223 }
224
225 return numBlocks;
226}
227
228SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
229 Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
230 newBlock->init(sizeof(Block) + allocCount * fElemSize);
231 return newBlock;
232}
233
234void SkDeque::freeBlock(Block* block) {
235 sk_free(block);
236}
237
238///////////////////////////////////////////////////////////////////////////////
239
240SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {}
241
242SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
243 this->reset(d, startLoc);
244}
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.
248void* SkDeque::Iter::next() {
249 char* pos = fPos;
250
251 if (pos) { // if we were valid, try to move to the next setting
252 char* next = pos + fElemSize;
253 SkASSERT(next <= fCurBlock->fEnd);
254 if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
255 do {
256 fCurBlock = fCurBlock->fNext;
257 } while (fCurBlock != nullptr && fCurBlock->fBegin == nullptr);
258 next = fCurBlock ? fCurBlock->fBegin : nullptr;
259 }
260 fPos = next;
261 }
262 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.
267void* SkDeque::Iter::prev() {
268 char* pos = fPos;
269
270 if (pos) { // if we were valid, try to move to the prior setting
271 char* prev = pos - fElemSize;
272 SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
273 if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
274 do {
275 fCurBlock = fCurBlock->fPrev;
276 } while (fCurBlock != nullptr && fCurBlock->fEnd == nullptr);
277 prev = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
278 }
279 fPos = prev;
280 }
281 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.
289void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
290 fElemSize = d.fElemSize;
291
292 if (kFront_IterStart == startLoc) {
293 // initialize the iterator to start at the front
294 fCurBlock = d.fFrontBlock;
295 while (fCurBlock && nullptr == fCurBlock->fBegin) {
296 fCurBlock = fCurBlock->fNext;
297 }
298 fPos = fCurBlock ? fCurBlock->fBegin : nullptr;
299 } else {
300 // initialize the iterator to start at the back
301 fCurBlock = d.fBackBlock;
302 while (fCurBlock && nullptr == fCurBlock->fEnd) {
303 fCurBlock = fCurBlock->fPrev;
304 }
305 fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : nullptr;
306 }
307}
308