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
startSkDeque::Block18 char* start() { return (char*)(this + 1); }
startSkDeque::Block19 const char* start() const { return (const char*)(this + 1); }
20
initSkDeque::Block21 void init(size_t size) {
22 fNext = fPrev = nullptr;
23 fBegin = fEnd = nullptr;
24 fStop = (char*)this + size;
25 }
26 };
27
SkDeque(size_t elemSize,int allocCount)28 SkDeque::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
SkDeque(size_t elemSize,void * storage,size_t storageSize,int allocCount)38 SkDeque::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
~SkDeque()56 SkDeque::~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
push_front()69 void* 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
push_back()109 void* 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
pop_front()150 void 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 first->fPrev = nullptr;
161 this->freeBlock(fFrontBlock);
162 fFrontBlock = first;
163 SkASSERT(first != nullptr); // else we popped too far
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
pop_back()184 void 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 last->fNext = nullptr;
195 this->freeBlock(fBackBlock);
196 fBackBlock = last;
197 SkASSERT(last != nullptr); // else we popped too far
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
numBlocksAllocated() const218 int 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
allocateBlock(int allocCount)228 SkDeque::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
freeBlock(Block * block)234 void SkDeque::freeBlock(Block* block) {
235 sk_free(block);
236 }
237
238 ///////////////////////////////////////////////////////////////////////////////
239
Iter()240 SkDeque::Iter::Iter() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {}
241
Iter(const SkDeque & d,IterStart startLoc)242 SkDeque::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.
next()248 void* 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.
prev()267 void* 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.
reset(const SkDeque & d,IterStart startLoc)289 void 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