1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2015, 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 of a given size; Different-sized blocks are 35 // not pooled. 36 // ========================================================================== 37 38 #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_ 39 #define SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_ 40 41 #include <seqan/basic/allocator_interface.h> 42 43 namespace seqan { 44 45 // ============================================================================ 46 // Forwards 47 // ============================================================================ 48 49 // ============================================================================ 50 // Tags, Classes, Enums 51 // ============================================================================ 52 53 /*! 54 * @class SinglePoolAllocator 55 * @extends Allocator 56 * @headerfile <seqan/basic.h> 57 * @brief Allocator that pools memory blocks of a specific size. 58 * 59 * @signature template <unsigned SIZE, typename TParentAllocator> 60 * class Allocator; 61 * 62 * @tparam SIZE The size of the blocks. 63 * @tparam TParentAllocator The parent allocator to use. 64 * 65 * A pool allocator allocates several memory blocks at once. Freed blocks are not immediately deallocated but 66 * recycled in subsequential allocations. This way, the number of calls to the heap manager is reduced, and that 67 * might speed up memory management. 68 * 69 * The single pool allocator only pools memory blocks of size at most $SIZE$. Blocks of other sizes are allocated and 70 * deallocated using an allocator of type $ParentAllocator$. Using the single pool allocator for blocksizes larger 71 * than a few KB is not advised. 72 */ 73 74 template <size_t SIZE, typename TParentAllocator = SimpleAllocator> 75 struct SinglePool; 76 77 template <size_t SIZE, typename TParentAllocator> 78 struct Allocator<SinglePool<SIZE, TParentAllocator> > 79 { 80 enum 81 { 82 // item must be large enough to keep a pointer to the next free item 83 SIZE_PER_ITEM = SIZE < sizeof(void*)? sizeof(void*) : SIZE, 84 ITEMS_PER_BLOCK = (SIZE_PER_ITEM < 0x0100) ? 0x01000 / SIZE_PER_ITEM : 16, 85 STORAGE_SIZE = SIZE_PER_ITEM * ITEMS_PER_BLOCK, 86 STORAGE_SIZE_MIN = SIZE_PER_ITEM 87 }; 88 89 char * data_recycled_blocks; 90 char * data_current_begin; 91 char * data_current_end; 92 char * data_current_free; 93 Holder<TParentAllocator, Tristate> data_parent_allocator; 94 95 Allocator() : data_recycled_blocks(), data_current_begin(), data_current_end(), data_current_free() 96 {} 97 98 Allocator(size_t reserve_item_count) : data_recycled_blocks() 99 { 100 size_t storage_size = std::max(reserve_item_count * SIZE_PER_ITEM, STORAGE_SIZE_MIN); 101 allocate(parentAllocator(*this), data_current_begin, storage_size); 102 data_current_end = data_current_begin + storage_size; 103 data_current_free = data_current_begin; 104 } 105 106 Allocator(TParentAllocator & parent_alloc) 107 { 108 setValue(data_parent_allocator, parent_alloc); 109 110 data_recycled_blocks = data_current_end = data_current_free = 0; 111 //dont need to initialize data_current_begin 112 } 113 114 Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc) 115 { 116 data_recycled_blocks = 0; 117 118 setValue(data_parent_allocator, parent_alloc); 119 120 size_t storage_size = std::max(reserve_item_count * SIZE_PER_ITEM, STORAGE_SIZE_MIN); 121 allocate(parentAllocator(*this), data_current_begin, storage_size); 122 data_current_end = data_current_begin + storage_size; 123 data_current_free = data_current_begin; 124 } 125 126 // Dummy copy 127 Allocator(Allocator const &) : 128 data_recycled_blocks(), data_current_begin(), data_current_end(), 129 data_current_free() 130 { 131 data_recycled_blocks = data_current_end = data_current_free = 0; 132 } 133 134 inline Allocator & 135 operator=(Allocator const &) 136 { 137 clear(*this); 138 return *this; 139 } 140 141 ~Allocator() 142 { 143 clear(*this); 144 } 145 }; 146 147 // ============================================================================ 148 // Metafunctions 149 // ============================================================================ 150 151 // ============================================================================ 152 // Functions 153 // ============================================================================ 154 155 // ---------------------------------------------------------------------------- 156 // Function parentAllocator() 157 // ---------------------------------------------------------------------------- 158 159 template <size_t SIZE, typename TParentAllocator> 160 inline TParentAllocator & 161 parentAllocator(Allocator<SinglePool<SIZE, TParentAllocator> > & me) 162 { 163 return value(me.data_parent_allocator); 164 } 165 166 // ---------------------------------------------------------------------------- 167 // Function clear() 168 // ---------------------------------------------------------------------------- 169 170 template <size_t SIZE, typename TParentAllocator> 171 void 172 clear(Allocator<SinglePool<SIZE, TParentAllocator> > & me) 173 { 174 me.data_recycled_blocks = me.data_current_end = me.data_current_free = 0; 175 clear(parentAllocator(me)); 176 } 177 178 // ---------------------------------------------------------------------------- 179 // Function allocate() 180 // ---------------------------------------------------------------------------- 181 182 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 183 inline void 184 allocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me, 185 TValue * & data, 186 TSize count, 187 Tag<TUsage> const tag_) 188 { 189 typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator; 190 size_t bytes_needed = count * sizeof(TValue); 191 192 if (bytes_needed > TAllocator::SIZE_PER_ITEM) 193 {//no blocking 194 allocate(parentAllocator(me), data, count, tag_); 195 return; 196 } 197 198 if (bytes_needed < TAllocator::SIZE_PER_ITEM) 199 bytes_needed = TAllocator::SIZE_PER_ITEM; 200 201 char * ptr; 202 if (me.data_recycled_blocks) 203 {//use recycled 204 ptr = me.data_recycled_blocks; 205 me.data_recycled_blocks = * reinterpret_cast<char **>(ptr); 206 } 207 else 208 {//use new 209 ptr = me.data_current_free; 210 if (ptr + bytes_needed > me.data_current_end) 211 {//not enough free space in current storage: allocate new 212 allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_); 213 me.data_current_begin = ptr; 214 me.data_current_end = ptr + TAllocator::STORAGE_SIZE; 215 } 216 me.data_current_free = ptr + bytes_needed; 217 } 218 219 data = reinterpret_cast<TValue *>(ptr); 220 } 221 222 // ---------------------------------------------------------------------------- 223 // Function deallocate() 224 // ---------------------------------------------------------------------------- 225 226 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 227 inline void 228 deallocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me, 229 TValue * data, 230 TSize count, 231 Tag<TUsage> const tag_) 232 { 233 typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator; 234 235 size_t bytes_needed = count * sizeof(TValue); 236 237 if (bytes_needed > TAllocator::SIZE_PER_ITEM) 238 {//no blocking 239 deallocate(parentAllocator(me), data, count, tag_); 240 return; 241 } 242 243 //link in recycling list 244 *reinterpret_cast<char **>(data) = me.data_recycled_blocks; 245 me.data_recycled_blocks = reinterpret_cast<char *>(data); 246 } 247 248 } // namespace seqan 249 250 #endif // #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_ 251