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