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