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