1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2010, 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 33 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H 34 #define SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H 35 36 namespace SEQAN_NAMESPACE_MAIN 37 { 38 ////////////////////////////////////////////////////////////////////////////// 39 // MultiPool Allocator 40 ////////////////////////////////////////////////////////////////////////////// 41 42 /** 43 .Spec.Multi Pool Allocator: 44 ..cat:Allocators 45 ..general:Class.Allocator 46 ..summary:Allocator that pools memory blocks. 47 ..signature:Allocator< MultiPool<ParentAllocator, BLOCKING_LIMIT> > 48 ..param.ParentAllocator:An allocator that is by the pool allocator used to allocate memory. 49 ...default:@Spec.Simple Allocator@ 50 ...note:The multi pool allocator only supports @Function.clear@ if this function is also implemented for $ParentAllocator$. 51 ..remarks:A pool allocator allocates several memory blocks at once. 52 ..param.BLOCKING_LIMIT:The maximum size for memory blocks to be pooled. 53 ...default:256 54 Freed blocks are not immediately deallocated but recycled in subsequential allocations. 55 This way, the number of calls to the heap manager is reduced, and that speeds up memory management. 56 ...text:Note that memory blocks larger than $BLOCKING_LIMIT$ are not pooled 57 but immediately allocated and deallocated using $ParentAllocator$. 58 ..include:seqan/basic.h 59 */ 60 61 62 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100> 63 struct MultiPool; 64 65 ////////////////////////////////////////////////////////////////////////////// 66 67 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator; 68 69 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_> 70 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> > 71 { 72 enum 73 { 74 BLOCKING_LIMIT = BLOCKING_LIMIT_, 75 GRANULARITY_BITS = 2, 76 BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS, 77 STORAGE_SIZE = 0xf80 78 }; 79 80 char * data_recycled_blocks [BLOCKING_COUNT]; 81 char * data_current_begin [BLOCKING_COUNT]; 82 char * data_current_free [BLOCKING_COUNT]; 83 Holder<TParentAllocator> data_parent_allocator; 84 85 Allocator() 86 { 87 SEQAN_CHECKPOINT 88 ::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 89 ::std::memset(data_current_begin, 0, sizeof(data_current_begin)); 90 ::std::memset(data_current_free, 0, sizeof(data_current_free)); 91 } 92 93 Allocator(TParentAllocator & parent_alloc) 94 { 95 SEQAN_CHECKPOINT 96 ::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 97 ::std::memset(data_current_begin, 0, sizeof(data_current_begin)); 98 ::std::memset(data_current_free, 0, sizeof(data_current_free)); 99 100 setValue(data_parent_allocator, parent_alloc); 101 } 102 103 //Dummy copy 104 Allocator(Allocator const &) 105 { 106 ::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 107 ::std::memset(data_current_begin, 0, sizeof(data_current_begin)); 108 ::std::memset(data_current_free, 0, sizeof(data_current_free)); 109 } 110 inline Allocator & 111 operator = (Allocator const &) 112 { 113 clear(*this); 114 return *this; 115 } 116 117 ~Allocator() 118 { 119 SEQAN_CHECKPOINT 120 clear(*this); 121 } 122 }; 123 ////////////////////////////////////////////////////////////////////////////// 124 125 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 126 inline TParentAllocator & 127 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me) 128 { 129 SEQAN_CHECKPOINT 130 return value(me.data_parent_allocator); 131 } 132 133 ////////////////////////////////////////////////////////////////////////////// 134 135 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 136 void 137 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me) 138 { 139 SEQAN_CHECKPOINT 140 ::std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks)); 141 ::std::memset(me.data_current_begin, 0, sizeof(me.data_current_begin)); 142 ::std::memset(me.data_current_free, 0, sizeof(me.data_current_free)); 143 144 clear(parentAllocator(me)); 145 } 146 147 ////////////////////////////////////////////////////////////////////////////// 148 149 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT> 150 inline unsigned int 151 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &, 152 size_t size_) 153 { 154 SEQAN_CHECKPOINT 155 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 156 157 SEQAN_ASSERT(size_) 158 159 if (size_ < BLOCKING_LIMIT) 160 {//blocks 161 return size_ >> TAllocator::GRANULARITY_BITS; 162 } 163 else 164 {//no blocking 165 return TAllocator::BLOCKING_COUNT; 166 } 167 } 168 169 170 ////////////////////////////////////////////////////////////////////////////// 171 172 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage> 173 inline void 174 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me, 175 TValue * & data, 176 TSize count, 177 Tag<TUsage> const tag_) 178 { 179 SEQAN_CHECKPOINT 180 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 181 182 size_t bytes_needed = count * sizeof(TValue); 183 char * ptr; 184 185 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed); 186 if (block_number == TAllocator::BLOCKING_COUNT) 187 {//no blocking 188 return allocate(parentAllocator(me), data, count, tag_); 189 } 190 191 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS; 192 193 if (me.data_recycled_blocks[block_number]) 194 {//use recycled 195 ptr = me.data_recycled_blocks[block_number]; 196 me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr); 197 } 198 else 199 {//use new 200 ptr = me.data_current_free[block_number]; 201 if (!ptr || (ptr + bytes_needed > me.data_current_begin[block_number] + TAllocator::STORAGE_SIZE)) 202 {//not enough free space in current storage: allocate new 203 allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_); 204 me.data_current_begin[block_number] = ptr; 205 } 206 me.data_current_free[block_number] = ptr + bytes_needed; 207 } 208 209 data = reinterpret_cast<TValue *>(ptr); 210 } 211 212 ////////////////////////////////////////////////////////////////////////////// 213 214 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage> 215 inline void 216 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me, 217 TValue * data, 218 TSize count, 219 Tag<TUsage> const tag_) 220 { 221 SEQAN_CHECKPOINT 222 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator; 223 224 size_t bytes_needed = count * sizeof(TValue); 225 226 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed); 227 if (block_number == TAllocator::BLOCKING_COUNT) 228 {//no blocking 229 return deallocate(parentAllocator(me), data, count, tag_); 230 } 231 232 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS; 233 234 //link in recycling list 235 *reinterpret_cast<char **>(data) = me.data_recycled_blocks[block_number]; 236 me.data_recycled_blocks[block_number] = reinterpret_cast<char *>(data); 237 } 238 239 ////////////////////////////////////////////////////////////////////////////// 240 241 } //namespace SEQAN_NAMESPACE_MAIN 242 243 #endif //#ifndef SEQAN_HEADER_... 244