1/*
2 * Copyright 2010 Google Inc.
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#ifndef GrAllocator_DEFINED
9#define GrAllocator_DEFINED
10
11#include "GrConfig.h"
12#include "GrTypes.h"
13#include "SkTArray.h"
14#include "SkTypes.h"
15
16class GrAllocator : SkNoncopyable {
17public:
18    ~GrAllocator() { this->reset(); }
19
20    /**
21     * Create an allocator
22     *
23     * @param   itemSize        the size of each item to allocate
24     * @param   itemsPerBlock   the number of items to allocate at once
25     * @param   initialBlock    optional memory to use for the first block.
26     *                          Must be at least itemSize*itemsPerBlock sized.
27     *                          Caller is responsible for freeing this memory.
28     */
29    GrAllocator(size_t itemSize, int itemsPerBlock, void* initialBlock)
30        : fItemSize(itemSize)
31        , fItemsPerBlock(itemsPerBlock)
32        , fOwnFirstBlock(NULL == initialBlock)
33        , fCount(0)
34        , fInsertionIndexInBlock(0) {
35        SkASSERT(itemsPerBlock > 0);
36        fBlockSize = fItemSize * fItemsPerBlock;
37        if (fOwnFirstBlock) {
38            // This force us to allocate a new block on push_back().
39            fInsertionIndexInBlock = fItemsPerBlock;
40        } else {
41            fBlocks.push_back() = initialBlock;
42            fInsertionIndexInBlock = 0;
43        }
44    }
45
46    /**
47     * Adds an item and returns pointer to it.
48     *
49     * @return pointer to the added item.
50     */
51    void* push_back() {
52        // we always have at least one block
53        if (fItemsPerBlock == fInsertionIndexInBlock) {
54            fBlocks.push_back() = sk_malloc_throw(fBlockSize);
55            fInsertionIndexInBlock = 0;
56        }
57        void* ret = (char*)fBlocks.back() + fItemSize * fInsertionIndexInBlock;
58        ++fCount;
59        ++fInsertionIndexInBlock;
60        return ret;
61    }
62
63    /**
64     * Remove the last item, only call if count() != 0
65     */
66    void pop_back() {
67        SkASSERT(fCount);
68        SkASSERT(fInsertionIndexInBlock > 0);
69        --fInsertionIndexInBlock;
70        --fCount;
71        if (0 == fInsertionIndexInBlock) {
72            // Never delete the first block
73            if (fBlocks.count() > 1) {
74                sk_free(fBlocks.back());
75                fBlocks.pop_back();
76                fInsertionIndexInBlock = fItemsPerBlock;
77            }
78        }
79    }
80
81    /**
82     * Removes all added items.
83     */
84    void reset() {
85        int firstBlockToFree = fOwnFirstBlock ? 0 : 1;
86        for (int i = firstBlockToFree; i < fBlocks.count(); ++i) {
87            sk_free(fBlocks[i]);
88        }
89        if (fOwnFirstBlock) {
90            fBlocks.reset();
91            // This force us to allocate a new block on push_back().
92            fInsertionIndexInBlock = fItemsPerBlock;
93        } else {
94            fBlocks.pop_back_n(fBlocks.count() - 1);
95            fInsertionIndexInBlock = 0;
96        }
97        fCount = 0;
98    }
99
100    /**
101     * Returns the item count.
102     */
103    int count() const {
104        return fCount;
105    }
106
107    /**
108     * Is the count 0?
109     */
110    bool empty() const { return 0 == fCount; }
111
112    /**
113     * Access last item, only call if count() != 0
114     */
115    void* back() {
116        SkASSERT(fCount);
117        SkASSERT(fInsertionIndexInBlock > 0);
118        return (char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize;
119    }
120
121    /**
122     * Access last item, only call if count() != 0
123     */
124    const void* back() const {
125        SkASSERT(fCount);
126        SkASSERT(fInsertionIndexInBlock > 0);
127        return (const char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize;
128    }
129
130    /**
131     * Iterates through the allocator. This is faster than using operator[] when walking linearly
132     * through the allocator.
133     */
134    class Iter {
135    public:
136        /**
137         * Initializes the iterator. next() must be called before get().
138         */
139        Iter(const GrAllocator* allocator)
140            : fAllocator(allocator)
141            , fBlockIndex(-1)
142            , fIndexInBlock(allocator->fItemsPerBlock - 1)
143            , fItemIndex(-1) {}
144
145        /**
146         * Advances the iterator. Iteration is finished when next() returns false.
147         */
148        bool next() {
149            ++fIndexInBlock;
150            ++fItemIndex;
151            if (fIndexInBlock == fAllocator->fItemsPerBlock) {
152                ++fBlockIndex;
153                fIndexInBlock = 0;
154            }
155            return fItemIndex < fAllocator->fCount;
156        }
157
158        /**
159         * Gets the current iterator value. Call next() at least once before calling. Don't call
160         * after next() returns false.
161         */
162        void* get() const {
163            SkASSERT(fItemIndex >= 0 && fItemIndex < fAllocator->fCount);
164            return (char*) fAllocator->fBlocks[fBlockIndex] + fIndexInBlock * fAllocator->fItemSize;
165        }
166
167    private:
168        const GrAllocator* fAllocator;
169        int                fBlockIndex;
170        int                fIndexInBlock;
171        int                fItemIndex;
172    };
173
174    /**
175     * Access item by index.
176     */
177    void* operator[] (int i) {
178        SkASSERT(i >= 0 && i < fCount);
179        return (char*)fBlocks[i / fItemsPerBlock] +
180               fItemSize * (i % fItemsPerBlock);
181    }
182
183    /**
184     * Access item by index.
185     */
186    const void* operator[] (int i) const {
187        SkASSERT(i >= 0 && i < fCount);
188        return (const char*)fBlocks[i / fItemsPerBlock] +
189               fItemSize * (i % fItemsPerBlock);
190    }
191
192protected:
193    /**
194     * Set first block of memory to write into.  Must be called before any other methods.
195     * This requires that you have passed NULL in the constructor.
196     *
197     * @param   initialBlock    optional memory to use for the first block.
198     *                          Must be at least itemSize*itemsPerBlock sized.
199     *                          Caller is responsible for freeing this memory.
200     */
201    void setInitialBlock(void* initialBlock) {
202        SkASSERT(0 == fCount);
203        SkASSERT(0 == fBlocks.count());
204        SkASSERT(fItemsPerBlock == fInsertionIndexInBlock);
205        fOwnFirstBlock = false;
206        fBlocks.push_back() = initialBlock;
207        fInsertionIndexInBlock = 0;
208    }
209
210    // For access to above function.
211    template <typename T> friend class GrTAllocator;
212
213private:
214    static const int NUM_INIT_BLOCK_PTRS = 8;
215
216    SkSTArray<NUM_INIT_BLOCK_PTRS, void*, true>   fBlocks;
217    size_t                                        fBlockSize;
218    size_t                                        fItemSize;
219    int                                           fItemsPerBlock;
220    bool                                          fOwnFirstBlock;
221    int                                           fCount;
222    int                                           fInsertionIndexInBlock;
223
224    typedef SkNoncopyable INHERITED;
225};
226
227template <typename T> class GrTAllocator;
228template <typename T> void* operator new(size_t, GrTAllocator<T>*);
229
230template <typename T> class GrTAllocator : SkNoncopyable {
231public:
232    virtual ~GrTAllocator() { this->reset(); };
233
234    /**
235     * Create an allocator
236     *
237     * @param   itemsPerBlock   the number of items to allocate at once
238     */
239    explicit GrTAllocator(int itemsPerBlock)
240        : fAllocator(sizeof(T), itemsPerBlock, NULL) {}
241
242    /**
243     * Adds an item and returns it.
244     *
245     * @return the added item.
246     */
247    T& push_back() {
248        void* item = fAllocator.push_back();
249        SkASSERT(item);
250        SkNEW_PLACEMENT(item, T);
251        return *(T*)item;
252    }
253
254    T& push_back(const T& t) {
255        void* item = fAllocator.push_back();
256        SkASSERT(item);
257        SkNEW_PLACEMENT_ARGS(item, T, (t));
258        return *(T*)item;
259    }
260
261    /**
262     * Remove the last item, only call if count() != 0
263     */
264    void pop_back() {
265        this->back().~T();
266        fAllocator.pop_back();
267    }
268
269    /**
270     * Removes all added items.
271     */
272    void reset() {
273        int c = fAllocator.count();
274        for (int i = 0; i < c; ++i) {
275            ((T*)fAllocator[i])->~T();
276        }
277        fAllocator.reset();
278    }
279
280    /**
281     * Returns the item count.
282     */
283    int count() const {
284        return fAllocator.count();
285    }
286
287    /**
288     * Is the count 0?
289     */
290    bool empty() const { return fAllocator.empty(); }
291
292    /**
293     * Access last item, only call if count() != 0
294     */
295    T& back() {
296        return *(T*)fAllocator.back();
297    }
298
299    /**
300     * Access last item, only call if count() != 0
301     */
302    const T& back() const {
303        return *(const T*)fAllocator.back();
304    }
305
306    /**
307     * Iterates through the allocator. This is faster than using operator[] when walking linearly
308     * through the allocator.
309     */
310    class Iter {
311    public:
312        /**
313         * Initializes the iterator. next() must be called before get() or ops * and ->.
314         */
315        Iter(const GrTAllocator* allocator) : fImpl(&allocator->fAllocator) {}
316
317        /**
318         * Advances the iterator. Iteration is finished when next() returns false.
319         */
320        bool next() { return fImpl.next(); }
321
322        /**
323         * Gets the current iterator value. Call next() at least once before calling. Don't call
324         * after next() returns false.
325         */
326        T* get() const { return (T*) fImpl.get(); }
327
328        /**
329         * Convenience operators. Same rules for calling apply as get().
330         */
331        T& operator*() const { return *this->get(); }
332        T* operator->() const { return this->get(); }
333
334    private:
335        GrAllocator::Iter fImpl;
336    };
337
338    /**
339     * Access item by index.
340     */
341    T& operator[] (int i) {
342        return *(T*)(fAllocator[i]);
343    }
344
345    /**
346     * Access item by index.
347     */
348    const T& operator[] (int i) const {
349        return *(const T*)(fAllocator[i]);
350    }
351
352protected:
353    /*
354     * Set first block of memory to write into.  Must be called before any other methods.
355     *
356     * @param   initialBlock    optional memory to use for the first block.
357     *                          Must be at least size(T)*itemsPerBlock sized.
358     *                          Caller is responsible for freeing this memory.
359     */
360    void setInitialBlock(void* initialBlock) {
361        fAllocator.setInitialBlock(initialBlock);
362    }
363
364private:
365    friend void* operator new<T>(size_t, GrTAllocator*);
366
367    GrAllocator fAllocator;
368    typedef SkNoncopyable INHERITED;
369};
370
371template <int N, typename T> class GrSTAllocator : public GrTAllocator<T> {
372private:
373    typedef GrTAllocator<T> INHERITED;
374
375public:
376    GrSTAllocator() : INHERITED(N) {
377        this->setInitialBlock(fStorage.get());
378    }
379
380private:
381    SkAlignedSTStorage<N, T> fStorage;
382};
383
384template <typename T> void* operator new(size_t size, GrTAllocator<T>* allocator) {
385    return allocator->fAllocator.push_back();
386}
387
388// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
389// to match the op new silences warnings about missing op delete when a constructor throws an
390// exception.
391template <typename T> void operator delete(void*, GrTAllocator<T>*) {
392    SK_CRASH();
393}
394
395#define GrNEW_APPEND_TO_ALLOCATOR(allocator_ptr, type_name, args) \
396    new (allocator_ptr) type_name args
397
398#endif
399