Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
third_party
skia
src
base
SkDeque.cpp
Go to the documentation of this file.
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
21
char
*
start
() {
return
(
char
*)(
this
+ 1); }
22
const
char
*
start
()
const
{
return
(
const
char
*)(
this
+ 1); }
23
24
void
init
(
size_t
size) {
25
fNext
=
fPrev
=
nullptr
;
26
fBegin
=
fEnd
=
nullptr
;
27
fStop
= (
char
*)
this
+ size;
28
}
29
};
30
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
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
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
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
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
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
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
221
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
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
237
void
SkDeque::freeBlock(
Block
* block) {
238
sk_free
(block);
239
}
240
241
///////////////////////////////////////////////////////////////////////////////
242
243
SkDeque::Iter::Iter
() : fCurBlock(nullptr), fPos(nullptr), fElemSize(0) {}
244
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.
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.
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.
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
}
reset
m reset()
pos
SkPoint pos
Definition
ImageShaderTest.cpp:27
next
static float next(float f)
Definition
PathOpsAngleTest.cpp:32
prev
static float prev(float f)
Definition
PathOpsAngleTest.cpp:40
SkAssert.h
SkASSERT
#define SkASSERT(cond)
Definition
SkAssert.h:116
SkDeque.h
SkMalloc.h
sk_free
SK_API void sk_free(void *)
Definition
SkMemory_malloc.cpp:83
sk_malloc_throw
static void * sk_malloc_throw(size_t size)
Definition
SkMalloc.h:67
SkBlockAllocator::Block
Definition
SkBlockAllocator.h:71
SkDeque::Iter::next
void * next()
Definition
SkDeque.cpp:251
SkDeque::Iter::prev
void * prev()
Definition
SkDeque.cpp:270
SkDeque::Iter::Iter
Iter()
Definition
SkDeque.cpp:243
SkDeque::Iter::IterStart
IterStart
Definition
SkDeque.h:64
SkDeque::Iter::reset
void reset(const SkDeque &d, IterStart startLoc)
Definition
SkDeque.cpp:292
SkDeque
Definition
SkDeque.h:28
SkDeque::push_back
void * push_back()
Definition
SkDeque.cpp:112
SkDeque::~SkDeque
~SkDeque()
Definition
SkDeque.cpp:59
SkDeque::pop_front
void pop_front()
Definition
SkDeque.cpp:153
SkDeque::pop_back
void pop_back()
Definition
SkDeque.cpp:187
SkDeque::push_front
void * push_front()
Definition
SkDeque.cpp:72
SkDeque::SkDeque
SkDeque(size_t elemSize, int allocCount=1)
Definition
SkDeque.cpp:31
SkDeque::elemSize
size_t elemSize() const
Definition
SkDeque.h:40
begin
static const char * begin(const StringSlice &s)
Definition
editor.cpp:252
d
VULKAN_HPP_DEFAULT_DISPATCH_LOADER_DYNAMIC_STORAGE auto & d
Definition
main.cc:19
start
glong start
Definition
fl_accessible_text_field.cc:39
end
glong glong end
Definition
fl_accessible_text_field.cc:40
SkDeque::Block
Definition
SkDeque.cpp:14
SkDeque::Block::start
const char * start() const
Definition
SkDeque.cpp:22
SkDeque::Block::start
char * start()
Definition
SkDeque.cpp:21
SkDeque::Block::fEnd
char * fEnd
Definition
SkDeque.cpp:18
SkDeque::Block::init
void init(size_t size)
Definition
SkDeque.cpp:24
SkDeque::Block::fPrev
Block * fPrev
Definition
SkDeque.cpp:16
SkDeque::Block::fNext
Block * fNext
Definition
SkDeque.cpp:15
SkDeque::Block::fBegin
char * fBegin
Definition
SkDeque.cpp:17
SkDeque::Block::fStop
char * fStop
Definition
SkDeque.cpp:19
Generated on Fri Apr 26 2024 06:16:32 for Flutter Engine by
1.9.8