1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: Andreas Gogol-Doering <andreas.doering@mdc-berlin.de> 33 // ========================================================================== 34 // Allocator that pools blocks up to a given size. 35 // ========================================================================== 36 37 #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_ 38 #define SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_ 39 40 #include <seqan/basic/allocator_interface.h> 41 42 namespace seqan { 43 44 // ============================================================================ 45 // Forwards 46 // ============================================================================ 47 48 // ============================================================================ 49 // Tags, Classes, Enums 50 // ============================================================================ 51 52 /*! 53 * @class MultiPoolAllocator 54 * @extends Allocator 55 * @headerfile <seqan/basic.h> 56 * @brief Allocator that pools memory blocks. 57 * 58 * @signature template <typename TParentAllocator[, unsigned BLOCKING_LIMIT]> 59 * class Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> >; 60 * 61 * @tparam TParentAllocator The parent allocator. 62 * @tparam BLOCKING_LIMIT The maximum size for memory blocks to be pooled (default is 256). 63 * 64 * Freed blocks are not immediately deallocated but recycled in subsequential allocations. This way, the number of 65 * calls to the heap manager is reduced and that might speed up memory management. 66 * 67 * Note that memory block larger than <tt>BLOCKING_LIMIT</tt> are not pooled but immediately allocated and deallocated 68 * using <tt>ParentAllocator</tt>. 69 */ 70 71 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100> 72 struct MultiPool; 73 74 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator; 75 76 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_> 77 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> > 78 { 79 enum 80 { 81 BLOCKING_LIMIT = BLOCKING_LIMIT_, 82 GRANULARITY_BITS = 2, 83 BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS, 84 STORAGE_SIZE = 0xf80 85 }; 86 87 char * data_recycled_blocks [BLOCKING_COUNT]; 88 char * data_current_begin [BLOCKING_COUNT]; 89 char * data_current_free [BLOCKING_COUNT]; 90 Holder<TParentAllocator, Tristate> data_parent_allocator; 91 92 Allocator() 93 { 94 // TODO(holtrew): Why not SeqAn's memset? or use using? 95 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 96 std::memset(data_current_begin, 0, sizeof(data_current_begin)); 97 std::memset(data_current_free, 0, sizeof(data_current_free)); 98 } 99 100 Allocator(TParentAllocator & parent_alloc) 101 { 102 // TODO(holtrew): Why not SeqAn's memset? or use using? 103 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 104 std::memset(data_current_begin, 0, sizeof(data_current_begin)); 105 std::memset(data_current_free, 0, sizeof(data_current_free)); 106 107 setValue(data_parent_allocator, parent_alloc); 108 } 109 110 //Dummy copy 111 Allocator(Allocator const &) 112 { 113 // TODO(holtrew): Why not SeqAn's memset? or use using? 114 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 115 std::memset(data_current_begin, 0, sizeof(data_current_begin)); 116 std::memset(data_current_free, 0, sizeof(data_current_free)); 117 } 118 119 inline Allocator & 120 operator=(Allocator const &) 121 { 122 clear(*this); 123 return *this; 124 } 125 126 ~Allocator() 127 { 128 clear(*this); 129 } 130 }; 131 132 // ============================================================================ 133 // Metafunctions 134 // ============================================================================ 135 136 // ============================================================================ 137 // Functions 138 // ============================================================================ 139 140 // ---------------------------------------------------------------------------- 141 // Function parentAllocator() 142 // ---------------------------------------------------------------------------- 143 144 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 145 inline TParentAllocator & 146 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me) 147 { 148 return value(me.data_parent_allocator); 149 } 150 151 // ---------------------------------------------------------------------------- 152 // Function clear() 153 // ---------------------------------------------------------------------------- 154 155 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 156 void 157 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me) 158 { 159 std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks)); 160 std::memset(me.data_current_begin, 0, sizeof(me.data_current_begin)); 161 std::memset(me.data_current_free, 0, sizeof(me.data_current_free)); 162 163 clear(parentAllocator(me)); 164 } 165 166 // ---------------------------------------------------------------------------- 167 // Helper function _allocatorBlockNumber() 168 // ---------------------------------------------------------------------------- 169 170 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 171 inline unsigned int 172 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &, 173 size_t size_) 174 { 175 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 176 177 SEQAN_ASSERT_GT(size_, 0u); 178 179 if (size_ < BLOCKING_LIMIT) 180 {//blocks 181 return size_ >> TAllocator::GRANULARITY_BITS; 182 } 183 else 184 {//no blocking 185 return TAllocator::BLOCKING_COUNT; 186 } 187 } 188 189 // ---------------------------------------------------------------------------- 190 // Function allocate() 191 // ---------------------------------------------------------------------------- 192 193 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage> 194 inline void 195 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me, 196 TValue * & data, 197 TSize count, 198 Tag<TUsage> const & tag_) 199 { 200 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 201 202 size_t bytes_needed = count * sizeof(TValue); 203 char * ptr; 204 205 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed); 206 if (block_number == TAllocator::BLOCKING_COUNT) 207 {//no blocking 208 return allocate(parentAllocator(me), data, count, tag_); 209 } 210 211 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS; 212 213 if (me.data_recycled_blocks[block_number]) 214 {//use recycled 215 ptr = me.data_recycled_blocks[block_number]; 216 me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr); 217 } 218 else 219 {//use new 220 ptr = me.data_current_free[block_number]; 221 if (!ptr || (ptr + bytes_needed > me.data_current_begin[block_number] + TAllocator::STORAGE_SIZE)) 222 {//not enough free space in current storage: allocate new 223 allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_); 224 me.data_current_begin[block_number] = ptr; 225 } 226 me.data_current_free[block_number] = ptr + bytes_needed; 227 } 228 229 data = reinterpret_cast<TValue *>(ptr); 230 } 231 232 // ---------------------------------------------------------------------------- 233 // Function deallocate() 234 // ---------------------------------------------------------------------------- 235 236 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage> 237 inline void 238 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me, 239 TValue * data, 240 TSize count, 241 Tag<TUsage> const tag_) 242 { 243 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 244 245 size_t bytes_needed = count * sizeof(TValue); 246 247 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed); 248 if (block_number == TAllocator::BLOCKING_COUNT) 249 {//no blocking 250 return deallocate(parentAllocator(me), data, count, tag_); 251 } 252 253 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS; 254 255 //link in recycling list 256 *reinterpret_cast<char **>(data) = me.data_recycled_blocks[block_number]; 257 me.data_recycled_blocks[block_number] = reinterpret_cast<char *>(data); 258 } 259 260 } // namespace seqan 261 262 #endif // #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_ 263