c@313: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */ c@313: c@313: /* c@313: QM DSP Library c@313: c@313: Centre for Digital Music, Queen Mary, University of London. c@313: c@313: This file is derived from the FSB Allocator by Juha Nieminen. The c@313: underlying method is unchanged, but the class has been refactored c@313: to permit multiple separate allocators (e.g. one per thread) c@313: rather than use a single global one (and to fit house style). c@313: c@313: Copyright (c) 2008 Juha Nieminen c@313: c@313: Permission is hereby granted, free of charge, to any person obtaining a copy c@313: of this software and associated documentation files (the "Software"), to deal c@313: in the Software without restriction, including without limitation the rights c@313: to use, copy, modify, merge, publish, distribute, sublicense, and/or sell c@313: copies of the Software, and to permit persons to whom the Software is c@313: furnished to do so, subject to the following conditions: c@313: c@313: The above copyright notice and this permission notice shall be included in c@313: all copies or substantial portions of the Software. c@313: c@313: THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR c@313: IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, c@313: FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE c@313: AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER c@313: LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, c@313: OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN c@313: THE SOFTWARE. c@313: */ c@313: c@313: #ifndef _BLOCK_ALLOCATOR_H_ c@313: #define _BLOCK_ALLOCATOR_H_ c@313: c@313: #include c@313: c@313: /** c@313: * BlockAllocator is a simple allocator for fixed-size (usually small) c@313: * chunks of memory. The size of an element is specified in the c@313: * BlockAllocator constructor, and the functions allocate() and c@313: * deallocate() are used to obtain and release a single element at a c@313: * time. c@313: * c@313: * BlockAllocator may be an appropriate class to use in situations c@313: * involving a very large number of allocations and deallocations of c@313: * simple, identical objects across multiple threads (a hard situation c@313: * for a generic system malloc implementation to handle well). Retain c@313: * one BlockAllocator per thread (the class itself is not c@313: * thread-safe), and ensure that each thread uses its own allocator c@313: * exclusively. c@313: * c@313: * BlockAllocator is based on Juha Nieminen's more general c@313: * FSBAllocator. c@313: */ c@313: class BlockAllocator c@313: { c@313: public: c@313: typedef std::size_t data_t; c@313: c@313: BlockAllocator(int elementSize) : m_sz(elementSize) { } c@313: c@313: void * c@313: allocate() c@313: { c@313: if (m_freelist.empty()) { c@313: m_freelist.push_back(m_blocks.data.size()); c@313: m_blocks.data.push_back(Block(this)); c@313: } c@313: c@313: const data_t index = m_freelist.back(); c@313: Block &block = m_blocks.data[index]; c@313: void *retval = block.allocate(index); c@313: if (block.isFull()) m_freelist.pop_back(); c@313: c@313: return retval; c@313: } c@313: c@313: void c@313: deallocate(void *ptr) c@313: { c@313: if (!ptr) return; c@313: c@313: data_t *unitPtr = (data_t *)ptr; c@313: const data_t blockIndex = unitPtr[elementSizeInDataUnits()]; c@313: Block& block = m_blocks.data[blockIndex]; c@313: c@313: if (block.isFull()) m_freelist.push_back(blockIndex); c@313: block.deallocate(unitPtr); c@313: } c@313: c@313: private: c@313: inline data_t elementsPerBlock() const { c@313: return 512; c@313: } c@313: inline data_t dataSize() const { c@313: return sizeof(data_t); c@313: } c@313: inline data_t elementSizeInDataUnits() const { c@313: return (m_sz + (dataSize() - 1)) / dataSize(); c@313: } c@313: inline data_t unitSizeInDataUnits() const { c@313: return elementSizeInDataUnits() + 1; c@313: } c@313: inline data_t blockSizeInDataUnits() const { c@313: return elementsPerBlock() * unitSizeInDataUnits(); c@313: } c@313: c@313: class Block c@313: { c@313: public: c@313: Block(BlockAllocator *a) : c@313: m_a(a), c@313: m_block(0), c@313: m_firstFreeUnit(data_t(-1)), c@313: m_allocated(0), c@313: m_end(0) c@313: {} c@313: c@313: ~Block() { c@313: delete[] m_block; c@313: } c@313: c@313: bool isFull() const { c@313: return m_allocated == m_a->elementsPerBlock(); c@313: } c@313: c@313: void clear() { c@313: delete[] m_block; c@313: m_block = 0; c@313: m_firstFreeUnit = data_t(-1); c@313: } c@313: c@313: void *allocate(data_t index) { c@313: c@313: if (m_firstFreeUnit == data_t(-1)) { c@313: c@313: if (!m_block) { c@313: m_block = new data_t[m_a->blockSizeInDataUnits()]; c@313: m_end = 0; c@313: } c@313: c@313: data_t *retval = m_block + m_end; c@313: m_end += m_a->unitSizeInDataUnits(); c@313: retval[m_a->elementSizeInDataUnits()] = index; c@313: ++m_allocated; c@313: return retval; c@313: c@313: } else { c@313: c@313: data_t *retval = m_block + m_firstFreeUnit; c@313: m_firstFreeUnit = *retval; c@313: ++m_allocated; c@313: return retval; c@313: } c@313: } c@313: c@313: void deallocate(data_t *ptr) { c@313: c@313: *ptr = m_firstFreeUnit; c@313: m_firstFreeUnit = ptr - m_block; c@313: c@313: if (--m_allocated == 0) clear(); c@313: } c@313: c@313: private: c@313: const BlockAllocator *m_a; c@313: data_t *m_block; c@313: data_t m_firstFreeUnit; c@313: data_t m_allocated; c@313: data_t m_end; c@313: }; c@313: c@313: struct Blocks c@313: { c@313: std::vector data; c@313: c@313: Blocks() { c@313: data.reserve(1024); c@313: } c@313: }; c@313: c@313: const int m_sz; c@313: Blocks m_blocks; c@313: std::vector m_freelist; c@313: }; c@313: c@313: #endif