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 class definition and generic interface. 35 // ========================================================================== 36 37 // TODO(holtgrew): Perform some benchmarks and use a better malloc, e.g. tcmalloc and see whether our allocator infrastructure is worth keeping around. 38 // TODO(holtgrew): Rename to allocator_base.h? 39 40 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_INTERFACE_H_ 41 #define SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_INTERFACE_H_ 42 43 namespace seqan { 44 45 // ============================================================================ 46 // Forwards 47 // ============================================================================ 48 49 struct Tristate_; 50 typedef Tag<Tristate_> Tristate; 51 template <typename TValue, typename TSpec> struct Holder; 52 53 // ============================================================================ 54 // Tags, Classes, Enums 55 // ============================================================================ 56 57 /*! 58 * @defgroup AllocatorUsageTags Allocator Usage Tags 59 * @brief The purpose of an allocated memory block. 60 * 61 * @tag AllocatorUsageTags#TagAllocateUnspecified 62 * @headerfile <seqan/basic.h> 63 * @brief Not specified. 64 * 65 * @tag AllocatorUsageTags#TagAllocateTemp 66 * @headerfile <seqan/basic.h> 67 * @brief Temporary memory. 68 * 69 * @tag AllocatorUsageTags#TagAllocateStorage 70 * @headerfile <seqan/basic.h> 71 * @brief Memory for storing container content. 72 */ 73 74 // TODO(holtgrew): ANY use/difference? 75 76 struct AllocateUnspecified_; 77 typedef Tag<AllocateUnspecified_> TagAllocateUnspecified; 78 79 struct AllocateTemp_; 80 typedef Tag<AllocateTemp_> TagAllocateTemp; 81 82 struct AllocateStorage_; 83 typedef Tag<AllocateStorage_> TagAllocateStorage; 84 85 struct AllocateAlignedMalloc_; 86 typedef Tag<AllocateAlignedMalloc_> TagAllocateAlignedMalloc; 87 88 /*! 89 * @class Allocator 90 * @headerfile <seqan/basic.h> 91 * @brief Manager for allocated memory. 92 * 93 * @signature template <typename TSpec> 94 * class Allocator; 95 * 96 * @tparam TSpec The specializing type. 97 * 98 * @section Remarks 99 * 100 * There are two reasons for using non-trivial allocators: 101 * 102 * <ol> 103 * <li>Allocators support the function @link Allocator#clear @endlink for a fast deallocation of all allocated 104 * memory blocks.</li> 105 * <li>Some allocators are faster in allocating an deallocating memory. Pool allocators like e.g. 106 * @link SinglePoolAllocator @endlink or @link MultiPoolAllocator @endlink speed up 107 * @link Allocator#allocate @endlink, @link Allocator#deallocate * @endlink, and 108 * @link Allocator#clear @endlink for pooled memory blocks.</li> 109 * </ol> 110 */ 111 112 template <typename TSpec> 113 struct Allocator; 114 115 // ============================================================================ 116 // Metafunctions 117 // ============================================================================ 118 119 //.Metafunction.Spec.param.T.type:Class.Allocator 120 121 template <typename TSpec> 122 struct Spec<Allocator<TSpec> > 123 { 124 typedef TSpec Type; 125 }; 126 127 // ============================================================================ 128 // Functions 129 // ============================================================================ 130 131 // ---------------------------------------------------------------------------- 132 // Function allocate() 133 // ---------------------------------------------------------------------------- 134 135 /*! 136 * @fn Allocator#allocate 137 * @headerfile <seqan/basic.h> 138 * @brief Allocates memory from heap. 139 * 140 * @signature void allocate(allocator, data, count[, usageTag]); 141 * 142 * @param[in] count Number of items that could be stored in the allocated memory. The type of the allocated 143 * items is given by the type of <tt>data</tt>. 144 * @param[in] usageTag A tag the specifies the purpose for the allocated memory. Values: 145 * @link AllocatorUsageTags @endlink. 146 * @param[in,out] allocator Allocator object. <tt>allocator</tt> is conceptually the "owner" of the allocated 147 * memory. Objects of all types can be used as allocators. If no special behavior is 148 * implemented, default functions allocation/deallocation are applied that uses standard 149 * <tt>new</tt> and <tt>delete</tt> operators. Types: Allocator 150 * 151 * @section Remarks 152 * 153 * The function allocates at least <tt>count*sizeof(data)</tt> bytes. The allocated memory is large enough to hold 154 * <tt>count</tt> objects of type <tt>T</tt>, where <tt>T *</tt> is type of <tt>data</tt>. 155 * 156 * These objects are not constructed by <tt>allocate</tt>. 157 * 158 * Use e.g. one of the functions @link valueConstruct @endlink, @link arrayConstruct @endlink, @link arrayConstructCopy 159 * @endlink or @link arrayFill @endlink to construct the objects. A <tt>new</tt> operator which is part of the C++ 160 * standard (defined in <tt><new></tt>) can also be used to construct objects at a given memory address. 161 * 162 * @section Remarks 163 * 164 * All allocated memory blocks should be deallocated by the corresponding function @link Allocator#deallocate @endlink. 165 */ 166 167 template <typename T, typename TValue, typename TSize> 168 inline void 169 allocate(T const & me, 170 TValue * & data, 171 TSize count) 172 { 173 allocate(me, data, count, TagAllocateUnspecified()); 174 } 175 176 template <typename T, typename TValue, typename TSize> 177 inline void 178 allocate(T & me, 179 TValue * & data, 180 TSize count) 181 { 182 allocate(me, data, count, TagAllocateUnspecified()); 183 } 184 185 template <typename T, typename TValue, typename TSize, typename TUsage> 186 inline void 187 allocate(T const &, 188 TValue * & data, 189 TSize count, 190 Tag<TUsage> const &) 191 { 192 // data = (TValue *) operator new(count * sizeof(TValue)); 193 #ifdef STDLIB_VS 194 data = (TValue *) _aligned_malloc(count * sizeof(TValue), __alignof(TValue)); 195 #else 196 /*#if _POSIX_C_SOURCE >= 200112L || _XOPEN_SOURCE >= 600 197 const size_t align = (__alignof__(TValue) < sizeof(void*)) ? sizeof(void*): __alignof__(TValue); 198 if (posix_memalign(&(void* &)data, align, count * sizeof(TValue))) 199 data = NULL; 200 #else 201 data = (TValue *) malloc(count * sizeof(TValue)); 202 #endif*/ 203 // suppress -Walloc-size-larger-than= warning; a simple static_cast does not work 204 // a working solution would be to downcast std::size_t to unsigned, but this 205 // would loose information; thus disabling this for gcc 7 and upwards 206 SEQAN_ASSERT_LEQ(static_cast<std::size_t>(count), std::numeric_limits<std::size_t>::max() / sizeof(TValue)); 207 # if defined(COMPILER_GCC) && __GNUC__ >= 7 208 # pragma GCC diagnostic push 209 # pragma GCC diagnostic ignored "-Walloc-size-larger-than=" 210 # endif //COMPILER_GCC 211 data = (TValue *) operator new(count * sizeof(TValue)); 212 # if defined(COMPILER_GCC) && __GNUC__ >= 7 213 # pragma GCC diagnostic pop 214 # endif //COMPILER_GCC 215 #endif 216 217 #ifdef SEQAN_PROFILE 218 if (data) 219 SEQAN_PROADD(SEQAN_PROMEMORY, count * sizeof(TValue)); 220 #endif 221 } 222 223 // NOTE(rrahn): Currently *new* does not support aligned memory, but we need it for dynamically 224 // allocated SimdVector class, so we overload the allocation to use mem_alloc for simd vector types. 225 // See following discussion: http://stackoverflow.com/questions/6973995/dynamic-aligned-memory-allocation-in-c11 226 template <typename T, typename TValue, typename TSize> 227 inline void 228 allocate(T const &, 229 TValue * & data, 230 TSize count, 231 TagAllocateAlignedMalloc const &) 232 { 233 #ifdef PLATFORM_WINDOWS_VS 234 data = (TValue *) _aligned_malloc(count * sizeof(TValue), __alignof(TValue)); 235 #else 236 #if _POSIX_C_SOURCE >= 200112L || _XOPEN_SOURCE >= 600 237 const size_t align = (__alignof__(TValue) < sizeof(void*)) ? sizeof(void*): __alignof__(TValue); 238 if (posix_memalign(&(void* &)data, align, count * sizeof(TValue))) 239 data = NULL; 240 #else 241 data = (TValue *) malloc(count * sizeof(TValue)); 242 #endif 243 #endif 244 } 245 246 template <typename T, typename TValue, typename TSize> 247 inline void 248 allocate(T &, 249 TValue * & data, 250 TSize count, 251 TagAllocateAlignedMalloc const &) 252 { 253 #ifdef PLATFORM_WINDOWS_VS 254 data = (TValue *) _aligned_malloc(count * sizeof(TValue), __alignof(TValue)); 255 #else 256 #if _POSIX_C_SOURCE >= 200112L || _XOPEN_SOURCE >= 600 257 const size_t align = (__alignof__(TValue) < sizeof(void*)) ? sizeof(void*) : __alignof__(TValue); 258 if (posix_memalign(&(void* &)data, align, count * sizeof(TValue))) 259 data = NULL; 260 #else 261 data = (TValue *) malloc(count * sizeof(TValue)); 262 #endif 263 #endif 264 } 265 266 // ---------------------------------------------------------------------------- 267 // Function deallocate() 268 // ---------------------------------------------------------------------------- 269 270 /*! 271 * @fn Allocator#deallocate 272 * @headerfile <seqan/basic.h> 273 * @brief Deallocates memory. 274 * 275 * @signature void deallocate(object, data, count[, usageTag]) 276 * 277 * @param[in,out] object Allocator object.<tt>object</tt> is conceptually the "owner" of the allocated memory. 278 * Objects of all types can be used as allocators. If no special behavior is implemented, 279 * default functions allocation/deallocation are applied that uses standard <tt>new</tt> 280 * and <tt>delete</tt> operators. Types: Allocator 281 * @param[out] data Pointer to allocated memory that was allocated by <tt>allocate</tt>. 282 * @param[in] count Number of items that could be stored in the allocated memory. 283 * @param[in] usageTag A tag the specifies the purpose for the allocated memory. 284 * Values: @link AllocatorUsageTags @endlink. 285 * 286 * The values for <tt>object</tt>, <tt>count</tt> and <tt>usageTag</tt> should be the same that was used when 287 * <tt>allocate</tt> was called. The value of <tt>data</tt> should be the same that was returned by <tt>allocate</tt>. 288 * 289 * <tt>deallocate</tt> does not destruct objects. 290 * 291 * Use e.g. one of the functions @link valueDestruct @endlink or @link arrayDestruct @endlink to destruct the objects. 292 * <tt>delete</tt> and <tt>delete []</tt> operators which are part of the C++ standard (defined in <tt><new></tt>) 293 * can also be used to destruct objects at a given memory address. 294 */ 295 296 template <typename T, typename TValue, typename TSize> 297 inline void 298 deallocate(T const & me, 299 TValue * data, 300 TSize const count) 301 { 302 deallocate(me, data, count, TagAllocateUnspecified()); 303 } 304 305 template <typename T, typename TValue, typename TSize> 306 inline void 307 deallocate(T & me, 308 TValue * data, 309 TSize const count) 310 { 311 deallocate(me, data, count, TagAllocateUnspecified()); 312 } 313 314 template <typename T, typename TValue, typename TSize, typename TUsage> 315 inline void 316 deallocate( 317 T const & /*me*/, 318 TValue * data, 319 #ifdef SEQAN_PROFILE 320 TSize count, 321 #else 322 TSize, 323 #endif 324 Tag<TUsage> const) 325 { 326 #ifdef SEQAN_PROFILE 327 if (data && count) // .. to use count if SEQAN_PROFILE is not defined 328 SEQAN_PROSUB(SEQAN_PROMEMORY, count * sizeof(TValue)); 329 #endif 330 // operator delete ((void *) data); 331 #ifdef STDLIB_VS 332 _aligned_free((void *) data); 333 #else 334 // free((void *) data); 335 operator delete ((void *) data); 336 #endif 337 } 338 339 template <typename T, typename TValue, typename TSize, typename TUsage> 340 inline void 341 deallocate( 342 T & /*me*/, 343 TValue * data, 344 #ifdef SEQAN_PROFILE 345 TSize count, 346 #else 347 TSize, 348 #endif 349 Tag<TUsage> const) 350 { 351 #ifdef SEQAN_PROFILE 352 if (data && count) // .. to use count if SEQAN_PROFILE is not defined 353 SEQAN_PROSUB(SEQAN_PROMEMORY, count * sizeof(TValue)); 354 #endif 355 // operator delete ((void *) data); 356 #ifdef STDLIB_VS 357 _aligned_free((void *) data); 358 #else 359 // free((void *) data); 360 operator delete ((void *) data); 361 #endif 362 } 363 364 // NOTE(rrahn): Currently *new* does not support aligned memory, but we need it for dynamically 365 // allocated SimdVector class, so we overload the allocation to use mem_alloc for simd vector types. 366 // See following discussion: http://stackoverflow.com/questions/6973995/dynamic-aligned-memory-allocation-in-c11 367 template <typename T, typename TValue, typename TSize> 368 inline void 369 deallocate( 370 T const & /*me*/, 371 TValue * data, 372 #ifdef SEQAN_PROFILE 373 TSize count, 374 #else 375 TSize, 376 #endif 377 TagAllocateAlignedMalloc const) 378 { 379 #ifdef SEQAN_PROFILE 380 if (data && count) // .. to use count if SEQAN_PROFILE is not defined 381 SEQAN_PROSUB(SEQAN_PROMEMORY, count * sizeof(TValue)); 382 #endif 383 #ifdef PLATFORM_WINDOWS_VS 384 _aligned_free((void *) data); 385 #else 386 free((void *) data); 387 #endif 388 } 389 390 template <typename T, typename TValue, typename TSize> 391 inline void 392 deallocate( 393 T & /*me*/, 394 TValue * data, 395 #ifdef SEQAN_PROFILE 396 TSize count, 397 #else 398 TSize, 399 #endif 400 TagAllocateAlignedMalloc const) 401 { 402 #ifdef SEQAN_PROFILE 403 if (data && count) // .. to use count if SEQAN_PROFILE is not defined 404 SEQAN_PROSUB(SEQAN_PROMEMORY, count * sizeof(TValue)); 405 #endif 406 // operator delete ((void *) data); 407 #ifdef PLATFORM_WINDOWS_VS 408 _aligned_free((void *) data); 409 #else 410 free((void *) data); 411 #endif 412 } 413 414 } // namespace seqan 415 416 #endif // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_INTERFACE_H_ 417