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 one or more consecutive memory blocks of a specific 35 // size. 36 // ========================================================================== 37 38 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_H_ 39 #define SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_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 template < 54 size_t SIZE, 55 size_t MAX_COUNT = 26, 56 typename TParentAllocator = Allocator<SimpleAlloc<Default> > > 57 struct ChunkPool; 58 59 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator> 60 struct Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > 61 { 62 enum 63 { 64 STORAGE_SIZE_1 = 0x1000UL, 65 STORAGE_SIZE_2 = SIZE * MAX_COUNT * 8, 66 STORAGE_SIZE_UPPER = (STORAGE_SIZE_1 > STORAGE_SIZE_2) ? STORAGE_SIZE_1 : STORAGE_SIZE_2, 67 ITEMS_PER_STORAGE = STORAGE_SIZE_UPPER / SIZE, 68 STORAGE_SIZE = ITEMS_PER_STORAGE * SIZE, 69 70 STORAGE_SIZE_MIN = SIZE * MAX_COUNT //minimal storage size 71 }; 72 73 char * data_recycled_blocks [MAX_COUNT]; 74 char * data_current_begin; 75 char * data_current_end; 76 char * data_current_free; 77 Holder<TParentAllocator, Tristate> data_parent_allocator; 78 79 Allocator() 80 { 81 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 82 data_current_end = data_current_free = 0; 83 //dont need to initialize data_current_begin 84 } 85 86 Allocator(size_t reserve_item_count) 87 { 88 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 89 90 size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN; 91 allocate( parentAllocator( *this ), data_current_begin, storage_size ); 92 data_current_end = data_current_begin + storage_size; 93 data_current_free = data_current_begin; 94 } 95 96 Allocator(TParentAllocator & parent_alloc) 97 { 98 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 99 data_current_end = data_current_free = 0; 100 //dont need to initialize data_current_begin 101 102 setValue(data_parent_allocator, parent_alloc); 103 } 104 105 Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc) 106 { 107 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 108 109 setValue(data_parent_allocator, parent_alloc); 110 111 size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN; 112 allocate( parentAllocator( *this ), data_current_begin, storage_size ); 113 data_current_end = data_current_begin + storage_size; 114 data_current_free = data_current_begin; 115 } 116 117 //Dummy copy 118 Allocator(Allocator const &) 119 { 120 std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks)); 121 data_current_end = data_current_free = 0; 122 //dont need to initialize data_current_begin 123 } 124 inline Allocator & 125 operator=(Allocator const &) 126 { 127 clear(*this); 128 return *this; 129 } 130 131 ~Allocator() 132 { 133 clear(*this); 134 } 135 }; 136 137 // ============================================================================ 138 // Metafunctions 139 // ============================================================================ 140 141 // ============================================================================ 142 // Functions 143 // ============================================================================ 144 145 // ---------------------------------------------------------------------------- 146 // Function parentAllocator() 147 // ---------------------------------------------------------------------------- 148 149 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator> 150 inline TParentAllocator & 151 parentAllocator(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me) 152 { 153 return value(me.data_parent_allocator); 154 } 155 156 // ---------------------------------------------------------------------------- 157 // Function clear() 158 // ---------------------------------------------------------------------------- 159 160 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator> 161 void 162 clear(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me) 163 { 164 std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks)); 165 me.data_current_end = me.data_current_free = 0; 166 167 clear(parentAllocator(me)); 168 } 169 170 // ---------------------------------------------------------------------------- 171 // Function allocate() 172 // ---------------------------------------------------------------------------- 173 174 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 175 inline void 176 allocate(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me, 177 TValue * & data, 178 TSize count, 179 Tag<TUsage> const tag_) 180 { 181 SEQAN_ASSERT_GT(count, static_cast<TSize>(0)); 182 183 typedef Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > TAllocator; 184 185 char * ptr; 186 187 if ((sizeof(TValue) != SIZE) || ((size_t) count > MAX_COUNT)) 188 {//no blocking 189 return allocate(parentAllocator(me), data, count, tag_); 190 } 191 192 size_t bytes_needed = count * SIZE; 193 if (me.data_recycled_blocks[count - 1]) 194 {//use recycled 195 ptr = me.data_recycled_blocks[count - 1]; 196 me.data_recycled_blocks[count - 1] = * reinterpret_cast<char **>(ptr); 197 } 198 else 199 {//use new 200 ptr = me.data_current_free; 201 if (ptr + bytes_needed > me.data_current_end) 202 {//not enough free space in current storage: allocate new 203 size_t rest_block_number = (me.data_current_end - me.data_current_free) / SIZE; 204 if (ptr && rest_block_number) 205 {//link rest to recycle list 206 *reinterpret_cast<char **>(ptr) = me.data_recycled_blocks[rest_block_number - 1]; 207 me.data_recycled_blocks[rest_block_number - 1] = reinterpret_cast<char *>(ptr); 208 } 209 210 allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_); 211 me.data_current_begin = ptr; 212 me.data_current_end = ptr + TAllocator::STORAGE_SIZE; 213 } 214 me.data_current_free = ptr + bytes_needed; 215 } 216 217 data = reinterpret_cast<TValue *>(ptr); 218 } 219 220 // ---------------------------------------------------------------------------- 221 // Function deallocate() 222 // ---------------------------------------------------------------------------- 223 224 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 225 inline void 226 deallocate(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me, 227 TValue * data, 228 TSize count, 229 Tag<TUsage> const tag_) 230 { 231 SEQAN_ASSERT_GT(count, 0); 232 233 if ((sizeof(TValue) != SIZE) || (static_cast<size_t>(count) > MAX_COUNT)) 234 {//no blocking 235 return deallocate(parentAllocator(me), data, count, tag_); 236 } 237 238 //link in recycling list 239 *reinterpret_cast<char **>(data) = me.data_recycled_blocks[count - 1]; 240 me.data_recycled_blocks[count - 1] = reinterpret_cast<char *>(data); 241 } 242 243 } // namespace seqan 244 245 #endif // SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_H_ 246