libs/qm-dsp/thread/BlockAllocator.h

   1 /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
   2
   3 /*
   4     QM DSP Library
   5
   6     Centre for Digital Music, Queen Mary, University of London.
   7
   8     This file is derived from the FSB Allocator by Juha Nieminen.  The
   9     underlying method is unchanged, but the class has been refactored
  10     to permit multiple separate allocators (e.g. one per thread)
  11     rather than use a single global one (and to fit house style).
  12
  13 Copyright (c) 2008 Juha Nieminen
  14
  15 Permission is hereby granted, free of charge, to any person obtaining a copy
  16 of this software and associated documentation files (the "Software"), to deal
  17 in the Software without restriction, including without limitation the rights
  18 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  19 copies of the Software, and to permit persons to whom the Software is
  20 furnished to do so, subject to the following conditions:
  21
  22 The above copyright notice and this permission notice shall be included in
  23 all copies or substantial portions of the Software.
  24
  25 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  26 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  27 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  28 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  29 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  30 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  31 THE SOFTWARE.
  32 */
  33
  34 #ifndef _BLOCK_ALLOCATOR_H_
  35 #define _BLOCK_ALLOCATOR_H_
  36
  37 #include <cstdlib>
  38
  39 /**
  40  * BlockAllocator is a simple allocator for fixed-size (usually small)
  41  * chunks of memory.  The size of an element is specified in the
  42  * BlockAllocator constructor, and the functions allocate() and
  43  * deallocate() are used to obtain and release a single element at a
  44  * time.
  45  *
  46  * BlockAllocator may be an appropriate class to use in situations
  47  * involving a very large number of allocations and deallocations of
  48  * simple, identical objects across multiple threads (a hard situation
  49  * for a generic system malloc implementation to handle well).  Retain
  50  * one BlockAllocator per thread (the class itself is not
  51  * thread-safe), and ensure that each thread uses its own allocator
  52  * exclusively.
  53  *
  54  * BlockAllocator is based on Juha Nieminen's more general
  55  * FSBAllocator.
  56  */
  57 class BlockAllocator
  58 {
  59 public:
  60     typedef std::size_t data_t;
  61
  62     BlockAllocator(int elementSize) : m_sz(elementSize) { }
  63
  64     void *
  65     allocate()
  66     {
  67         if (m_freelist.empty()) {
  68             m_freelist.push_back(m_blocks.data.size());
  69             m_blocks.data.push_back(Block(this));
  70         }
  71
  72         const data_t index = m_freelist.back();
  73         Block &block = m_blocks.data[index];
  74         void *retval = block.allocate(index);
  75         if (block.isFull()) m_freelist.pop_back();
  76
  77         return retval;
  78     }
  79
  80     void
  81     deallocate(void *ptr)
  82     {
  83         if (!ptr) return;
  84
  85         data_t *unitPtr = (data_t *)ptr;
  86         const data_t blockIndex = unitPtr[elementSizeInDataUnits()];
  87         Block& block = m_blocks.data[blockIndex];
  88
  89         if (block.isFull()) m_freelist.push_back(blockIndex);
  90         block.deallocate(unitPtr);
  91     }
  92
  93 private:
  94     inline data_t elementsPerBlock() const {
  95         return 512;
  96     }
  97     inline data_t dataSize() const {
  98         return sizeof(data_t);
  99     }
 100     inline data_t elementSizeInDataUnits() const {
 101         return (m_sz + (dataSize() - 1)) / dataSize();
 102     }
 103     inline data_t unitSizeInDataUnits() const {
 104         return elementSizeInDataUnits() + 1;
 105     }
 106     inline data_t blockSizeInDataUnits() const {
 107         return elementsPerBlock() * unitSizeInDataUnits();
 108     }
 109
 110     class Block
 111     {
 112     public:
 113         Block(BlockAllocator *a) :
 114             m_a(a),
 115             m_block(0),
 116             m_firstFreeUnit(data_t(-1)),
 117             m_allocated(0),
 118             m_end(0)
 119         {}
 120
 121         ~Block() {
 122             delete[] m_block;
 123         }
 124
 125         bool isFull() const {
 126             return m_allocated == m_a->elementsPerBlock();
 127         }
 128
 129         void clear() {
 130             delete[] m_block;
 131             m_block = 0;
 132             m_firstFreeUnit = data_t(-1);
 133         }
 134
 135         void *allocate(data_t index) {
 136
 137             if (m_firstFreeUnit == data_t(-1)) {
 138
 139                 if (!m_block) {
 140                     m_block = new data_t[m_a->blockSizeInDataUnits()];
 141                     m_end = 0;
 142                 }
 143
 144                 data_t *retval = m_block + m_end;
 145                 m_end += m_a->unitSizeInDataUnits();
 146                 retval[m_a->elementSizeInDataUnits()] = index;
 147                 ++m_allocated;
 148                 return retval;
 149
 150             } else {
 151
 152                 data_t *retval = m_block + m_firstFreeUnit;
 153                 m_firstFreeUnit = *retval;
 154                 ++m_allocated;
 155                 return retval;
 156             }
 157         }
 158
 159         void deallocate(data_t *ptr) {
 160
 161             *ptr = m_firstFreeUnit;
 162             m_firstFreeUnit = ptr - m_block;
 163
 164             if (--m_allocated == 0) clear();
 165         }
 166
 167     private:
 168         const BlockAllocator *m_a;
 169         data_t *m_block;
 170         data_t m_firstFreeUnit;
 171         data_t m_allocated;
 172         data_t m_end;
 173     };
 174
 175     struct Blocks
 176     {
 177         std::vector<Block> data;
 178
 179         Blocks() {
 180             data.reserve(1024);
 181         }
 182     };
 183
 184     const int m_sz;
 185     Blocks m_blocks;
 186     std::vector<data_t> m_freelist;
 187 };
 188
 189 #endif