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
14struct 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
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 = NULL;
26        fBegin  = fEnd = NULL;
27        fStop   = (char*)this + size;
28    }
29};
30
31SkDeque::SkDeque(size_t elemSize)
32        : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) {
33    fFront = fBack = NULL;
34}
35
36SkDeque::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
49SkDeque::~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
62const 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
78const 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
94void* 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
130void* 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
166void 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
192void 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
220SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {}
221
222SkDeque::F2BIter::F2BIter(const SkDeque& d) {
223    this->reset(d);
224}
225
226void* 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
243void 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