CUFreeList.h

//
//  CUFreeList.h
//  Cornell Extensions to Cocos2D
//
//  This header provides a template for a free list class.  A free list allows you to
//  "recycle" memory.  As allocating and deleting memory is an expensive operation,
//  this has significant performance problems with systems that create a lot of short
//  live objects (e.g. particle systems).  Free lists solve this problem by replacing
//  the new operator with a method to manage your memory.
//
//  A free list can also allocate a block of memory at creation.  This allows you to
//  group all your initial allocations ahead of time. See the class documentation
//  for more information.
//
//  This is not a class.  It is a class template.  Templates do not have cpp files.
//  They only have a header file.  When you include the header, it compiles the specific
//  template used by your program. Hence all of the code for this templated class is
//  in this header.
//
//  Author: Walker White
//  Version: 11/15/15
//
#ifndef __CU_FREE_LIST_H__
#define __CU_FREE_LIST_H__

#include <queue>
#include <cocos2d.h>

NS_CC_BEGIN

#pragma mark -
#pragma mark FreeList Template

template <class T>
class CC_DLL FreeList {
protected:
    size_t _allocated;
    size_t _released;
    size_t _peaksize;
    
    T* _prealloc;
    size_t _capacity;
    
    queue<T*> _freeobjs;
    
    bool _expandable;
    queue<T*> _expansion;
    
public:
    FreeList(size_t capacity=0, bool expand=false) {
        _expandable = expand;
        _capacity  = capacity;
        _released  = 0;
        _allocated = 0;
        _prealloc = (_capacity > 0 ? new T[_capacity] : nullptr);
    }
    
    ~FreeList() {
        clear();
        if (_prealloc != nullptr) {
            delete[] _prealloc;
        }
    }

    
#pragma mark Accessors

    size_t getAvailable() const { return (_capacity-(long)_allocated)+_freeobjs.size(); }

    size_t getCapacity() const { return _capacity; }

    size_t getUsage() const { return _allocated-_released; }
    
    size_t getPeakUsage() const { return _peaksize; }
    
    bool isExpandable() const { return _expandable; }
    
    // TODO: COMMENT ME
    T* getPreallocated() { return _prealloc; }
    

#pragma mark Memory Managment

    virtual T* alloc();
    
    void free(T* obj);
    
    virtual void clear();
};


#pragma mark -
#pragma mark Method Implementations

template <class T>
T* FreeList<T>::alloc() {
    T* result = nullptr;
    if (!_freeobjs.empty()) {
        result = _freeobjs.front();
        _freeobjs.pop();
        _allocated++;
    } else if (_allocated < _capacity) {
        result = &_prealloc[_allocated];
        _allocated++;
    } else if (_expandable) {
        result = new T();
        _expansion.push(result);
        _allocated++;
    }
    _peaksize = (_peaksize < getUsage() ? getUsage() : _peaksize);
    return result;
}

template <class T>
void FreeList<T>::free(T* obj) {
    CCASSERT(obj != nullptr, "Attempt to free null pointer");
    _freeobjs.push(obj);
    obj->reset();
    _released++;
}

template <class T>
void FreeList<T>::clear() {
    // We own anything in expansion.  Clear it.
    while (!_expansion.empty()) {
        T* a = _expansion.front();
        _expansion.pop();
        delete a;
    }
    
    // Clear the preallocated
    for(int ii =0; ii < _capacity; ii++) {
        _prealloc[ii].reset();
    }
    
    // Clear everything else
    while (!_expansion.empty()) {
        _freeobjs.pop();
    }
    
    _allocated = 0;
    _released  = 0;
}

NS_CC_END

#endif /* defined(__CU_FREE_LIST_H__) */