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