michael@0: /*
michael@0:  * Copyright 2014 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef SkFreeList_DEFINED
michael@0: #define SkFreeList_DEFINED
michael@0: 
michael@0: #include "SkTInternalSList.h"
michael@0: 
michael@0: /**
michael@0:  * An implementation of a self growing pool of objects.
michael@0:  * It maintains a pool of fully initialized objects. If an attempt is made to
michael@0:  * acquire one, and there are none left, it makes some more.
michael@0:  * It does not automatically reclaim them, they have to be given back to it.
michael@0:  * Constructors will be called on objects allocated by the pool at allocation
michael@0:  * time.
michael@0:  * All allocated objects will be destroyed and memory will be reclaimed when
michael@0:  * the pool is destroyed, so the pool must survive longer than you are using
michael@0:  * any item taken from it.
michael@0:  */
michael@0: template<typename T, int numItemsPerBlock = 4096/sizeof(T)> class SkTObjectPool {
michael@0: public:
michael@0:     SkTObjectPool() {}
michael@0:     ~SkTObjectPool() {
michael@0:         while (!fBlocks.isEmpty()) {
michael@0:             SkDELETE(fBlocks.pop());
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Get an item from the pool.
michael@0:      * If the pool has no free items, it will allocate and construct some more.
michael@0:      * The returned item is only valid as long as the pool has not been
michael@0:      * destroyed, at that point all memory allocated by grow will have been
michael@0:      * reclaimed.
michael@0:      * This method is *not* thread safe.
michael@0:      */
michael@0:     T* acquire() {
michael@0:         if (fAvailable.isEmpty()) {
michael@0:             grow();
michael@0:         }
michael@0:         return fAvailable.pop();
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Release an item into the pool.
michael@0:      * The item does not have to have come from the pool, but if it did not
michael@0:      * it must have a lifetime greater than the pool does.
michael@0:      * This method is *not* thread safe.
michael@0:      */
michael@0:     void release(T* entry) {
michael@0:         fAvailable.push(entry);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Takes all the items from an SkTInternalSList and adds them back to this
michael@0:      * pool. The other list will be left empty.
michael@0:      */
michael@0:     void releaseAll(SkTInternalSList<T>* other) {
michael@0:         fAvailable.pushAll(other);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Returns the number of items immediately available without having to
michael@0:      * construct any new ones.
michael@0:      */
michael@0:     int available() const { return fAvailable.getCount(); }
michael@0: 
michael@0:     /**
michael@0:      * Returns the number of blocks of items the pool has allocated so far.
michael@0:      */
michael@0:     int blocks() const { return fBlocks.getCount(); }
michael@0: 
michael@0: private:
michael@0:     /**
michael@0:      * The type for a new block of entries for the list.
michael@0:      */
michael@0:     struct Block {
michael@0:         T entries[numItemsPerBlock];
michael@0:         SK_DECLARE_INTERNAL_SLIST_INTERFACE(Block);
michael@0:     };
michael@0:     SkTInternalSList<Block> fBlocks;
michael@0:     SkTInternalSList<T> fAvailable;
michael@0: 
michael@0:     /**
michael@0:      * When the free list runs out of items, this method is called to allocate
michael@0:      * a new block of them.
michael@0:      * It calls the constructors and then pushes the nodes into the available
michael@0:      * list.
michael@0:      */
michael@0:     void grow() {
michael@0:         Block* block = SkNEW(Block);
michael@0:         fBlocks.push(block);
michael@0:         for(int index = 0; index < numItemsPerBlock; ++index) {
michael@0:             fAvailable.push(&block->entries[index]);
michael@0:         }
michael@0:     }
michael@0: 
michael@0: };
michael@0: 
michael@0: #endif