CUFreeList.h

//
//  CUFreeList.h
//  Cornell University Game Library (CUGL)
//
//  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.
//
//  CUGL zlib License:
//      This software is provided 'as-is', without any express or implied
//      warranty.  In no event will the authors be held liable for any damages
//      arising from the use of this software.
//
//      Permission is granted to anyone to use this software for any purpose,
//      including commercial applications, and to alter it and redistribute it
//      freely, subject to the following restrictions:
//
//      1. The origin of this software must not be misrepresented; you must not
//      claim that you wrote the original software. If you use this software
//      in a product, an acknowledgment in the product documentation would be
//      appreciated but is not required.
//
//      2. Altered source versions must be plainly marked as such, and must not
//      be misrepresented as being the original software.
//
//      3. This notice may not be removed or altered from any source distribution.
//
//  Author: Walker White
//  Version: 11/29/16
//
#ifndef __CU_FREE_LIST_H__
#define __CU_FREE_LIST_H__
#include <queue>

namespace cugl {
    
#pragma mark -
#pragma mark FreeList Template

template <class T>
class FreeList {
protected:
    size_t _allocated;
    size_t _released;
    size_t _peaksize;
    
    T* _prealloc;
    size_t _capacity;
    
    std::queue<T*> _freeobjs;
    
    bool _expandable;
    std::queue<T*> _expansion;
   
#pragma mark Constructors
public:
    FreeList() : _allocated(0), _released(0), _peaksize(0), _prealloc(nullptr),
                 _capacity(0), _expandable(false) { }
    
    ~FreeList() { dispose(); }
    
    void dispose() {
        clear();
        if (_prealloc != nullptr) {
            delete[] _prealloc;
        }
    }

    bool init(size_t capacity) {
        CUAssertLog(capacity, "An unexapandable free list must have non-zero capacity");
        _expandable = false;
        _capacity  = capacity;
        _released  = 0;
        _allocated = 0;
        _prealloc = (_capacity > 0 ? new T[_capacity] : nullptr);
        return _prealloc;
    }
        
    bool init(size_t capacity, bool expand) {
        CUAssertLog(capacity || expand, "The free list must be expandable or have capacity non-zero");
        _expandable = expand;
        _capacity  = capacity;
        _released  = 0;
        _allocated = 0;
        _prealloc = (_capacity > 0 ? new T[_capacity] : nullptr);
        return  _capacity == 0 || _prealloc;
    }

    static std::shared_ptr<FreeList<T>> alloc(size_t capacity=0, bool expand=false) {
        std::shared_ptr<FreeList<T>> result = std::make_shared<FreeList<T>>();
        return (result->init(capacity,expand) ? result : nullptr);
    }
    
    
#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; }
    
    const T* getPreallocated() const { return _prealloc; }
    
    
#pragma mark Memory Managment

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


#pragma mark -
#pragma mark Method Implementations

template <class T>
T* FreeList<T>::malloc() {
    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;
}

}
#endif /* __CU_FREE_LIST_H__ */