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 // General purpose allocator. 35 // ========================================================================== 36 37 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_H_ 38 #define SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_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 SimpleAllocator 54 * @extends Allocator 55 * @headerfile <seqan/basic.h> 56 * @brief General purpose allocator. 57 * 58 * @signature template <typename TParentAllocator> 59 * class Allocator<SimpleAlloc<TParentAllocator> >; 60 * 61 * @tparam TParentAllocator An allocator that is used by the simple allocator to allocate memory. 62 * 63 * The tag Default used as TparentAllocator means that the default implementations of <tt>allocate</tt> and 64 * <tt>deallocate</tt> are used. 65 */ 66 67 template <typename TParentAllocator = Default> 68 struct SimpleAlloc; 69 70 typedef Allocator<SimpleAlloc<Default> > SimpleAllocator; 71 72 template <typename TParentAllocator> 73 struct Allocator<SimpleAlloc<TParentAllocator> > 74 { 75 struct Header 76 { 77 Header * left; 78 Header * right; 79 size_t size; 80 }; 81 82 Header * data_storages; 83 Holder<TParentAllocator, Tristate> data_parent_allocator; 84 85 Allocator() 86 : data_storages(0) 87 { 88 } 89 90 Allocator(TParentAllocator & parent_alloc) 91 : data_storages(0) 92 { 93 setValue(data_parent_allocator, parent_alloc); 94 } 95 96 //Dummy copy 97 Allocator(Allocator const &) 98 : data_storages(0) 99 { 100 } 101 102 inline Allocator & 103 operator = (Allocator const &) 104 { 105 clear(*this); 106 return *this; 107 } 108 109 ~Allocator() 110 { 111 clear(*this); 112 } 113 }; 114 115 // ============================================================================ 116 // Metafunctions 117 // ============================================================================ 118 119 // ============================================================================ 120 // Functions 121 // ============================================================================ 122 123 // ---------------------------------------------------------------------------- 124 // Function parentAllocator() 125 // ---------------------------------------------------------------------------- 126 127 template <typename TParentAllocator> 128 inline TParentAllocator & 129 parentAllocator(Allocator<SimpleAlloc<TParentAllocator> > & me) 130 { 131 return value(me.data_parent_allocator); 132 } 133 134 // ---------------------------------------------------------------------------- 135 // Function clear() 136 // ---------------------------------------------------------------------------- 137 138 /*! 139 * @fn Allocator#clear 140 * @brief Deallocates all memory blocks. 141 * 142 * @signature void clear(allocator); 143 * 144 * @param[in,out] The allocator to clear. 145 * 146 * @section Remarks 147 * 148 * This function deallocates all memory block sthat were allocated using <tt>allocate()</tt> for <tt>allocator</tt>. 149 * The memory is not pooled but directly passed back to the heap manager. 150 */ 151 152 // TODO(holtgrew): Using #-functions messes up search results. 153 template <typename TParentAllocator> 154 void 155 clear(Allocator<SimpleAlloc<TParentAllocator> > & me) 156 { 157 typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator; 158 159 while (me.data_storages) 160 { 161 typename TAllocator::Header * next_storage = me.data_storages->right; 162 deallocate(parentAllocator(me), reinterpret_cast<char *>(me.data_storages), me.data_storages->size); 163 me.data_storages = next_storage; 164 } 165 } 166 167 // ---------------------------------------------------------------------------- 168 // Function allocate() 169 // ---------------------------------------------------------------------------- 170 171 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 172 inline void 173 allocate(Allocator<SimpleAlloc<TParentAllocator> > & me, 174 TValue * & data, 175 TSize count, 176 Tag<TUsage> const &) 177 { 178 typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator; 179 typedef typename TAllocator::Header THeader; 180 181 //compute needed bytes 182 size_t bytes_needed = count * sizeof(TValue) + sizeof(THeader); 183 184 //allocate storage from parent 185 char * ptr; 186 allocate(parentAllocator(me), ptr, bytes_needed, TagAllocateStorage()); 187 188 THeader * new_block = reinterpret_cast<THeader *>(ptr); 189 new_block->left = 0; 190 new_block->right = me.data_storages; 191 new_block->size = bytes_needed; 192 193 if (me.data_storages) 194 { 195 me.data_storages->left = new_block; 196 } 197 me.data_storages = new_block; 198 199 //return data 200 data = reinterpret_cast<TValue *>(ptr + sizeof(THeader)); 201 } 202 203 // ---------------------------------------------------------------------------- 204 // Function deallocate() 205 // ---------------------------------------------------------------------------- 206 207 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage> 208 inline void 209 deallocate(Allocator<SimpleAlloc<TParentAllocator> > & me, 210 TValue * data, 211 TSize, 212 Tag<TUsage> const &) 213 { 214 typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator; 215 typedef typename TAllocator::Header THeader; 216 217 //update links 218 THeader & header = *(reinterpret_cast<THeader *>(data) - 1); 219 if (header.left) 220 { 221 header.left->right = header.right; 222 } 223 else 224 { 225 me.data_storages = header.right; 226 } 227 if (header.right) 228 { 229 header.right->left = header.left; 230 } 231 232 //deallocate storage using parent 233 char * ptr = reinterpret_cast<char *>(& header); 234 deallocate(parentAllocator(me), ptr, header.size); 235 } 236 237 } // namespace seqan 238 239 #endif // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_H_ 240