1
2 /*
3 * Copyright 2006 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10 #include "SkDeque.h"
11
12 #define INIT_ELEM_COUNT 1 // should we let the caller set this?
13
14 struct SkDeque::Head {
15 Head* fNext;
16 Head* 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::Head21 char* start() { return (char*)(this + 1); }
startSkDeque::Head22 const char* start() const { return (const char*)(this + 1); }
23
initSkDeque::Head24 void init(size_t size) {
25 fNext = fPrev = NULL;
26 fBegin = fEnd = NULL;
27 fStop = (char*)this + size;
28 }
29 };
30
SkDeque(size_t elemSize)31 SkDeque::SkDeque(size_t elemSize)
32 : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) {
33 fFront = fBack = NULL;
34 }
35
SkDeque(size_t elemSize,void * storage,size_t storageSize)36 SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize)
37 : fElemSize(elemSize), fInitialStorage(storage), fCount(0) {
38 SkASSERT(storageSize == 0 || storage != NULL);
39
40 if (storageSize >= sizeof(Head) + elemSize) {
41 fFront = (Head*)storage;
42 fFront->init(storageSize);
43 } else {
44 fFront = NULL;
45 }
46 fBack = fFront;
47 }
48
~SkDeque()49 SkDeque::~SkDeque() {
50 Head* head = fFront;
51 Head* initialHead = (Head*)fInitialStorage;
52
53 while (head) {
54 Head* next = head->fNext;
55 if (head != initialHead) {
56 sk_free(head);
57 }
58 head = next;
59 }
60 }
61
front() const62 const void* SkDeque::front() const {
63 Head* front = fFront;
64
65 if (NULL == front) {
66 return NULL;
67 }
68 if (NULL == front->fBegin) {
69 front = front->fNext;
70 if (NULL == front) {
71 return NULL;
72 }
73 }
74 SkASSERT(front->fBegin);
75 return front->fBegin;
76 }
77
back() const78 const void* SkDeque::back() const {
79 Head* back = fBack;
80
81 if (NULL == back) {
82 return NULL;
83 }
84 if (NULL == back->fEnd) { // marked as deleted
85 back = back->fPrev;
86 if (NULL == back) {
87 return NULL;
88 }
89 }
90 SkASSERT(back->fEnd);
91 return back->fEnd - fElemSize;
92 }
93
push_front()94 void* SkDeque::push_front() {
95 fCount += 1;
96
97 if (NULL == fFront) {
98 fFront = (Head*)sk_malloc_throw(sizeof(Head) +
99 INIT_ELEM_COUNT * fElemSize);
100 fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
101 fBack = fFront; // update our linklist
102 }
103
104 Head* first = fFront;
105 char* begin;
106
107 if (NULL == first->fBegin) {
108 INIT_CHUNK:
109 first->fEnd = first->fStop;
110 begin = first->fStop - fElemSize;
111 } else {
112 begin = first->fBegin - fElemSize;
113 if (begin < first->start()) { // no more room in this chunk
114 // should we alloc more as we accumulate more elements?
115 size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
116
117 first = (Head*)sk_malloc_throw(size);
118 first->init(size);
119 first->fNext = fFront;
120 fFront->fPrev = first;
121 fFront = first;
122 goto INIT_CHUNK;
123 }
124 }
125
126 first->fBegin = begin;
127 return begin;
128 }
129
push_back()130 void* SkDeque::push_back() {
131 fCount += 1;
132
133 if (NULL == fBack) {
134 fBack = (Head*)sk_malloc_throw(sizeof(Head) +
135 INIT_ELEM_COUNT * fElemSize);
136 fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
137 fFront = fBack; // update our linklist
138 }
139
140 Head* last = fBack;
141 char* end;
142
143 if (NULL == last->fBegin) {
144 INIT_CHUNK:
145 last->fBegin = last->start();
146 end = last->fBegin + fElemSize;
147 } else {
148 end = last->fEnd + fElemSize;
149 if (end > last->fStop) { // no more room in this chunk
150 // should we alloc more as we accumulate more elements?
151 size_t size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
152
153 last = (Head*)sk_malloc_throw(size);
154 last->init(size);
155 last->fPrev = fBack;
156 fBack->fNext = last;
157 fBack = last;
158 goto INIT_CHUNK;
159 }
160 }
161
162 last->fEnd = end;
163 return end - fElemSize;
164 }
165
pop_front()166 void SkDeque::pop_front() {
167 SkASSERT(fCount > 0);
168 fCount -= 1;
169
170 Head* first = fFront;
171
172 SkASSERT(first != NULL);
173
174 if (first->fBegin == NULL) { // we were marked empty from before
175 first = first->fNext;
176 first->fPrev = NULL;
177 sk_free(fFront);
178 fFront = first;
179 SkASSERT(first != NULL); // else we popped too far
180 }
181
182 char* begin = first->fBegin + fElemSize;
183 SkASSERT(begin <= first->fEnd);
184
185 if (begin < fFront->fEnd) {
186 first->fBegin = begin;
187 } else {
188 first->fBegin = first->fEnd = NULL; // mark as empty
189 }
190 }
191
pop_back()192 void SkDeque::pop_back() {
193 SkASSERT(fCount > 0);
194 fCount -= 1;
195
196 Head* last = fBack;
197
198 SkASSERT(last != NULL);
199
200 if (last->fEnd == NULL) { // we were marked empty from before
201 last = last->fPrev;
202 last->fNext = NULL;
203 sk_free(fBack);
204 fBack = last;
205 SkASSERT(last != NULL); // else we popped too far
206 }
207
208 char* end = last->fEnd - fElemSize;
209 SkASSERT(end >= last->fBegin);
210
211 if (end > last->fBegin) {
212 last->fEnd = end;
213 } else {
214 last->fBegin = last->fEnd = NULL; // mark as empty
215 }
216 }
217
218 ///////////////////////////////////////////////////////////////////////////////
219
F2BIter()220 SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {}
221
F2BIter(const SkDeque & d)222 SkDeque::F2BIter::F2BIter(const SkDeque& d) {
223 this->reset(d);
224 }
225
next()226 void* SkDeque::F2BIter::next() {
227 char* pos = fPos;
228
229 if (pos) { // if we were valid, try to move to the next setting
230 char* next = pos + fElemSize;
231 SkASSERT(next <= fHead->fEnd);
232 if (next == fHead->fEnd) { // exhausted this chunk, move to next
233 do {
234 fHead = fHead->fNext;
235 } while (fHead != NULL && fHead->fBegin == NULL);
236 next = fHead ? fHead->fBegin : NULL;
237 }
238 fPos = next;
239 }
240 return pos;
241 }
242
reset(const SkDeque & d)243 void SkDeque::F2BIter::reset(const SkDeque& d) {
244 fElemSize = d.fElemSize;
245 fHead = d.fFront;
246 while (fHead != NULL && fHead->fBegin == NULL) {
247 fHead = fHead->fNext;
248 }
249 fPos = fHead ? fHead->fBegin : NULL;
250 }
251