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
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        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
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        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
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