1/*
2 * Copyright 2014 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 SkFreeList_DEFINED
9#define SkFreeList_DEFINED
10
11#include "SkTInternalSList.h"
12
13/**
14 * An implementation of a self growing pool of objects.
15 * It maintains a pool of fully initialized objects. If an attempt is made to
16 * acquire one, and there are none left, it makes some more.
17 * It does not automatically reclaim them, they have to be given back to it.
18 * Constructors will be called on objects allocated by the pool at allocation
19 * time.
20 * All allocated objects will be destroyed and memory will be reclaimed when
21 * the pool is destroyed, so the pool must survive longer than you are using
22 * any item taken from it.
23 */
24template<typename T, int numItemsPerBlock = 4096/sizeof(T)> class SkTObjectPool {
25public:
26    SkTObjectPool() {}
27    ~SkTObjectPool() {
28        while (!fBlocks.isEmpty()) {
29            SkDELETE(fBlocks.pop());
30        }
31    }
32
33    /**
34     * Get an item from the pool.
35     * If the pool has no free items, it will allocate and construct some more.
36     * The returned item is only valid as long as the pool has not been
37     * destroyed, at that point all memory allocated by grow will have been
38     * reclaimed.
39     * This method is *not* thread safe.
40     */
41    T* acquire() {
42        if (fAvailable.isEmpty()) {
43            grow();
44        }
45        return fAvailable.pop();
46    }
47
48    /**
49     * Release an item into the pool.
50     * The item does not have to have come from the pool, but if it did not
51     * it must have a lifetime greater than the pool does.
52     * This method is *not* thread safe.
53     */
54    void release(T* entry) {
55        fAvailable.push(entry);
56    }
57
58    /**
59     * Takes all the items from an SkTInternalSList and adds them back to this
60     * pool. The other list will be left empty.
61     */
62    void releaseAll(SkTInternalSList<T>* other) {
63        fAvailable.pushAll(other);
64    }
65
66    /**
67     * Returns the number of items immediately available without having to
68     * construct any new ones.
69     */
70    int available() const { return fAvailable.getCount(); }
71
72    /**
73     * Returns the number of blocks of items the pool has allocated so far.
74     */
75    int blocks() const { return fBlocks.getCount(); }
76
77    /**
78     * Returns the number of items allocated by the pool in total.
79     */
80    int allocated() const { return fBlocks.getCount() * numItemsPerBlock; }
81
82private:
83    /**
84     * The type for a new block of entries for the list.
85     */
86    struct Block {
87        T entries[numItemsPerBlock];
88        SK_DECLARE_INTERNAL_SLIST_INTERFACE(Block);
89    };
90    SkTInternalSList<Block> fBlocks;
91    SkTInternalSList<T> fAvailable;
92
93    /**
94     * When the free list runs out of items, this method is called to allocate
95     * a new block of them.
96     * It calls the constructors and then pushes the nodes into the available
97     * list.
98     */
99    void grow() {
100        Block* block = SkNEW(Block);
101        fBlocks.push(block);
102        for(int index = 0; index < numItemsPerBlock; ++index) {
103            fAvailable.push(&block->entries[index]);
104        }
105    }
106
107};
108
109#endif
110