1949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/* 2949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Copyright 2014 Google Inc. 3949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * 4949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 5949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * found in the LICENSE file. 6949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 7949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 8949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#ifndef SkFreeList_DEFINED 9949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#define SkFreeList_DEFINED 10949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 11949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#include "SkTInternalSList.h" 12949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 13949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/** 14949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * An implementation of a self growing pool of objects. 15949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It maintains a pool of fully initialized objects. If an attempt is made to 16949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * acquire one, and there are none left, it makes some more. 17949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It does not automatically reclaim them, they have to be given back to it. 18949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Constructors will be called on objects allocated by the pool at allocation 19949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * time. 20949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * All allocated objects will be destroyed and memory will be reclaimed when 21949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * the pool is destroyed, so the pool must survive longer than you are using 22949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * any item taken from it. 23949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 24949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgtemplate<typename T, int numItemsPerBlock = 4096/sizeof(T)> class SkTObjectPool { 25949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgpublic: 26949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTObjectPool() {} 27949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org ~SkTObjectPool() { 28949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org while (!fBlocks.isEmpty()) { 29949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkDELETE(fBlocks.pop()); 30949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 31949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 32949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 33949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 34949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Get an item from the pool. 35949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * If the pool has no free items, it will allocate and construct some more. 36949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * The returned item is only valid as long as the pool has not been 37949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * destroyed, at that point all memory allocated by grow will have been 38949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * reclaimed. 39949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 40949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 41949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T* acquire() { 42949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org if (fAvailable.isEmpty()) { 43949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org grow(); 44949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 45949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return fAvailable.pop(); 46949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 47949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 48949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 49949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Release an item into the pool. 50949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * The item does not have to have come from the pool, but if it did not 51949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * it must have a lifetime greater than the pool does. 52949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 53949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 54949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void release(T* entry) { 55949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fAvailable.push(entry); 56949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 57949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 58949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 59949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Takes all the items from an SkTInternalSList and adds them back to this 60949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * pool. The other list will be left empty. 61949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 62949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void releaseAll(SkTInternalSList<T>* other) { 63949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fAvailable.pushAll(other); 64949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 65949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 66949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 67949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Returns the number of items immediately available without having to 68949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * construct any new ones. 69949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 70949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org int available() const { return fAvailable.getCount(); } 71949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 72949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 73949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Returns the number of blocks of items the pool has allocated so far. 74949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 75949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org int blocks() const { return fBlocks.getCount(); } 76949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 77a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org /** 78a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org * Returns the number of items allocated by the pool in total. 79a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org */ 80a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org int allocated() const { return fBlocks.getCount() * numItemsPerBlock; } 81a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org 82949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgprivate: 83949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 84949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * The type for a new block of entries for the list. 85949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 86949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org struct Block { 87949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T entries[numItemsPerBlock]; 88949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SK_DECLARE_INTERNAL_SLIST_INTERFACE(Block); 89949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org }; 90949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTInternalSList<Block> fBlocks; 91949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTInternalSList<T> fAvailable; 92949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 93949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 94949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * When the free list runs out of items, this method is called to allocate 95949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * a new block of them. 96949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It calls the constructors and then pushes the nodes into the available 97949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * list. 98949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 99949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void grow() { 100949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org Block* block = SkNEW(Block); 101949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fBlocks.push(block); 102949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org for(int index = 0; index < numItemsPerBlock; ++index) { 103949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fAvailable.push(&block->entries[index]); 104949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 105949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 106949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 107949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org}; 108949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 109949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#endif 110