SkDeque.cpp revision e1bc274295ec57cb3d3f01aaa8abff3b49c76c73 
1/* libs/graphics/sgl/SkDeque.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include "SkDeque.h"
19
20#define INIT_ELEM_COUNT 1  // should we let the caller set this?
21
22struct SkDeque::Head {
23    Head*   fNext;
24    Head*   fPrev;
25    char*   fBegin; // start of used section in this chunk
26    char*   fEnd;   // end of used section in this chunk
27    char*   fStop;  // end of the allocated chunk
28
29    char*       start() { return (char*)(this + 1); }
30    const char* start() const { return (const char*)(this + 1); }
31
32    void init(size_t size) {
33        fNext   = fPrev = NULL;
34        fBegin  = fEnd = NULL;
35        fStop   = (char*)this + size;
36    }
37};
38
39SkDeque::SkDeque(size_t elemSize)
40        : fElemSize(elemSize), fInitialStorage(NULL), fCount(0) {
41    fFront = fBack = NULL;
42}
43
44SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize)
45        : fElemSize(elemSize), fInitialStorage(storage), fCount(0) {
46    SkASSERT(storageSize == 0 || storage != NULL);
47
48    if (storageSize >= sizeof(Head) + elemSize) {
49        fFront = (Head*)storage;
50        fFront->init(storageSize);
51    } else {
52        fFront = NULL;
53    }
54    fBack = fFront;
55}
56
57SkDeque::~SkDeque() {
58    Head* head = fFront;
59    Head* initialHead = (Head*)fInitialStorage;
60
61    while (head) {
62        Head* next = head->fNext;
63        if (head != initialHead) {
64            sk_free(head);
65        }
66        head = next;
67    }
68}
69
70const void* SkDeque::front() const {
71    Head* front = fFront;
72
73    if (NULL == front) {
74        return NULL;
75    }
76    if (NULL == front->fBegin) {
77        front = front->fNext;
78        if (NULL == front) {
79            return NULL;
80        }
81    }
82    SkASSERT(front->fBegin);
83    return front->fBegin;
84}
85
86const void* SkDeque::back() const {
87    Head* back = fBack;
88
89    if (NULL == back) {
90        return NULL;
91    }
92    if (NULL == back->fEnd) {  // marked as deleted
93        back = back->fPrev;
94        if (NULL == back) {
95            return NULL;
96        }
97    }
98    SkASSERT(back->fEnd);
99    return back->fEnd - fElemSize;
100}
101
102void* SkDeque::push_front() {
103    fCount += 1;
104
105    if (NULL == fFront) {
106        fFront = (Head*)sk_malloc_throw(sizeof(Head) +
107                                        INIT_ELEM_COUNT * fElemSize);
108        fFront->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
109        fBack = fFront;     // update our linklist
110    }
111
112    Head*   first = fFront;
113    char*   begin;
114
115    if (NULL == first->fBegin) {
116    INIT_CHUNK:
117        first->fEnd = first->fStop;
118        begin = first->fStop - fElemSize;
119    } else {
120        begin = first->fBegin - fElemSize;
121        if (begin < first->start()) {    // no more room in this chunk
122            // should we alloc more as we accumulate more elements?
123            size_t  size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
124
125            first = (Head*)sk_malloc_throw(size);
126            first->init(size);
127            first->fNext = fFront;
128            fFront->fPrev = first;
129            fFront = first;
130            goto INIT_CHUNK;
131        }
132    }
133
134    first->fBegin = begin;
135    return begin;
136}
137
138void* SkDeque::push_back() {
139    fCount += 1;
140
141    if (NULL == fBack) {
142        fBack = (Head*)sk_malloc_throw(sizeof(Head) +
143                                       INIT_ELEM_COUNT * fElemSize);
144        fBack->init(sizeof(Head) + INIT_ELEM_COUNT * fElemSize);
145        fFront = fBack; // update our linklist
146    }
147
148    Head*   last = fBack;
149    char*   end;
150
151    if (NULL == last->fBegin) {
152    INIT_CHUNK:
153        last->fBegin = last->start();
154        end = last->fBegin + fElemSize;
155    } else {
156        end = last->fEnd + fElemSize;
157        if (end > last->fStop) {  // no more room in this chunk
158            // should we alloc more as we accumulate more elements?
159            size_t  size = sizeof(Head) + INIT_ELEM_COUNT * fElemSize;
160
161            last = (Head*)sk_malloc_throw(size);
162            last->init(size);
163            last->fPrev = fBack;
164            fBack->fNext = last;
165            fBack = last;
166            goto INIT_CHUNK;
167        }
168    }
169
170    last->fEnd = end;
171    return end - fElemSize;
172}
173
174void SkDeque::pop_front() {
175    SkASSERT(fCount > 0);
176    fCount -= 1;
177
178    Head*   first = fFront;
179
180    SkASSERT(first != NULL);
181
182    if (first->fBegin == NULL) {  // we were marked empty from before
183        first = first->fNext;
184        first->fPrev = NULL;
185        sk_free(fFront);
186        fFront = first;
187        SkASSERT(first != NULL);    // else we popped too far
188    }
189
190    char* begin = first->fBegin + fElemSize;
191    SkASSERT(begin <= first->fEnd);
192
193    if (begin < fFront->fEnd) {
194        first->fBegin = begin;
195    } else {
196        first->fBegin = first->fEnd = NULL;  // mark as empty
197    }
198}
199
200void SkDeque::pop_back() {
201    SkASSERT(fCount > 0);
202    fCount -= 1;
203
204    Head* last = fBack;
205
206    SkASSERT(last != NULL);
207
208    if (last->fEnd == NULL) {  // we were marked empty from before
209        last = last->fPrev;
210        last->fNext = NULL;
211        sk_free(fBack);
212        fBack = last;
213        SkASSERT(last != NULL);  // else we popped too far
214    }
215
216    char* end = last->fEnd - fElemSize;
217    SkASSERT(end >= last->fBegin);
218
219    if (end > last->fBegin) {
220        last->fEnd = end;
221    } else {
222        last->fBegin = last->fEnd = NULL;    // mark as empty
223    }
224}
225
226///////////////////////////////////////////////////////////////////////////////
227
228SkDeque::F2BIter::F2BIter() : fHead(NULL), fPos(NULL), fElemSize(0) {}
229
230SkDeque::F2BIter::F2BIter(const SkDeque& d) {
231    this->reset(d);
232}
233
234void* SkDeque::F2BIter::next() {
235    char* pos = fPos;
236
237    if (pos) {   // if we were valid, try to move to the next setting
238        char* next = pos + fElemSize;
239        SkASSERT(next <= fHead->fEnd);
240        if (next == fHead->fEnd) { // exhausted this chunk, move to next
241            do {
242                fHead = fHead->fNext;
243            } while (fHead != NULL && fHead->fBegin == NULL);
244            next = fHead ? fHead->fBegin : NULL;
245        }
246        fPos = next;
247    }
248    return pos;
249}
250
251void SkDeque::F2BIter::reset(const SkDeque& d) {
252    fElemSize = d.fElemSize;
253    fHead = d.fFront;
254    while (fHead != NULL && fHead->fBegin == NULL) {
255        fHead = fHead->fNext;
256    }
257    fPos = fHead ? fHead->fBegin : NULL;
258}
259