SeqAn-1.1/seqan/basic/basic_allocator_multipool.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   7   This library is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU Lesser General Public
   9   License as published by the Free Software Foundation; either
  10   version 3 of the License, or (at your option) any later version.
  11
  12   This library is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17  ============================================================================
  18   $Id: basic_allocator_multipool.h,v 1.2 2009/02/19 01:51:23 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
  22 #define SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26 //////////////////////////////////////////////////////////////////////////////
  27 // MultiPool Allocator
  28 //////////////////////////////////////////////////////////////////////////////
  29
  30 /**
  31 .Spec.Multi Pool Allocator:
  32 ..cat:Allocators
  33 ..general:Class.Allocator
  34 ..summary:Allocator that pools memory blocks.
  35 ..signature:Allocator< MultiPool<ParentAllocator, BLOCKING_LIMIT> >
  36 ..param.ParentAllocator:An allocator that is by the pool allocator used to allocate memory.
  37 ...default:@Spec.Simple Allocator@
  38 ...note:The multi pool allocator only supports @Function.clear@ if this function is also implemented for $ParentAllocator$.
  39 ..remarks:A pool allocator allocates several memory blocks at once.
  40 ..param.BLOCKING_LIMIT:The maximum size for memory blocks to be pooled.
  41 ...default:256
  42 Freed blocks are not immediately deallocated but recycled in subsequential allocations.
  43 This way, the number of calls to the heap manager is reduced, and that speeds up memory management.
  44 ...text:Note that memory blocks larger than $BLOCKING_LIMIT$ are not pooled
  45 but immediately allocated and deallocated using $ParentAllocator$.
  46 */
  47
  48
  49 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100>
  50 struct MultiPool;
  51
  52 //////////////////////////////////////////////////////////////////////////////
  53
  54 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator;
  55
  56 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_>
  57 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> >
  58 {
  59         enum
  60         {
  61                 BLOCKING_LIMIT = BLOCKING_LIMIT_,
  62                 GRANULARITY_BITS = 2,
  63                 BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS,
  64                 STORAGE_SIZE = 0xf80
  65         };
  66
  67         char * data_recycled_blocks [BLOCKING_COUNT];
  68         char * data_current_begin [BLOCKING_COUNT];
  69         char * data_current_free [BLOCKING_COUNT];
  70         Holder<TParentAllocator> data_parent_allocator;
  71
  72         Allocator()
  73         {
  74 SEQAN_CHECKPOINT
  75                 memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
  76                 memset(data_current_begin, 0, sizeof(data_current_begin));
  77                 memset(data_current_free, 0, sizeof(data_current_free));
  78         }
  79
  80         Allocator(TParentAllocator & parent_alloc)
  81         {
  82 SEQAN_CHECKPOINT
  83                 memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
  84                 memset(data_current_begin, 0, sizeof(data_current_begin));
  85                 memset(data_current_free, 0, sizeof(data_current_free));
  86
  87                 setValue(data_parent_allocator, parent_alloc);
  88         }
  89
  90         //Dummy copy
  91         Allocator(Allocator const &)
  92         {
  93                 memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
  94                 memset(data_current_begin, 0, sizeof(data_current_begin));
  95                 memset(data_current_free, 0, sizeof(data_current_free));
  96         }
  97         inline Allocator &
  98         operator = (Allocator const &)
  99         {
 100                 clear(*this);
 101                 return *this;
 102         }
 103
 104         ~Allocator()
 105         {
 106 SEQAN_CHECKPOINT
 107                 clear(*this);
 108         }
 109 };
 110 //////////////////////////////////////////////////////////////////////////////
 111
 112 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
 113 inline TParentAllocator &
 114 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
 115 {
 116 SEQAN_CHECKPOINT
 117         return value(me.data_parent_allocator);
 118 }
 119
 120 //////////////////////////////////////////////////////////////////////////////
 121
 122 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
 123 void
 124 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
 125 {
 126 SEQAN_CHECKPOINT
 127         memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks));
 128         memset(me.data_current_begin, 0, sizeof(me.data_current_begin));
 129         memset(me.data_current_free, 0, sizeof(me.data_current_free));
 130
 131         clear(parentAllocator(me));
 132 }
 133
 134 //////////////////////////////////////////////////////////////////////////////
 135
 136 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
 137 inline unsigned int
 138 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &,
 139                                           size_t size_)
 140 {
 141 SEQAN_CHECKPOINT
 142         typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
 143
 144         SEQAN_ASSERT(size_)
 145
 146         if (size_ < BLOCKING_LIMIT)
 147         {//blocks
 148                 return size_ >> TAllocator::GRANULARITY_BITS;
 149         }
 150         else
 151         {//no blocking
 152                 return TAllocator::BLOCKING_COUNT;
 153         }
 154 }
 155
 156
 157 //////////////////////////////////////////////////////////////////////////////
 158
 159 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
 160 inline void
 161 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
 162                  TValue * & data,
 163                  TSize count,
 164                  Tag<TUsage> const tag_)
 165 {
 166 SEQAN_CHECKPOINT
 167         typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
 168
 169         size_t bytes_needed = count * sizeof(TValue);
 170         char * ptr;
 171
 172         unsigned int block_number =  _allocatorBlockNumber(me, bytes_needed);
 173         if (block_number == TAllocator::BLOCKING_COUNT)
 174         {//no blocking
 175                 return allocate(parentAllocator(me), data, count, tag_);
 176         }
 177
 178         bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
 179
 180         if (me.data_recycled_blocks[block_number])
 181         {//use recycled
 182                 ptr = me.data_recycled_blocks[block_number];
 183                 me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr);
 184         }
 185         else
 186         {//use new
 187                 ptr = me.data_current_free[block_number];
 188                 if (!ptr || (ptr + bytes_needed > me.data_current_begin[block_number] + TAllocator::STORAGE_SIZE))
 189                 {//not enough free space in current storage: allocate new
 190                         allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
 191                         me.data_current_begin[block_number] = ptr;
 192                 }
 193                 me.data_current_free[block_number] = ptr + bytes_needed;
 194         }
 195
 196         data = reinterpret_cast<TValue *>(ptr);
 197 }
 198
 199 //////////////////////////////////////////////////////////////////////////////
 200
 201 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
 202 inline void
 203 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
 204                    TValue * data,
 205                    TSize count,
 206                    Tag<TUsage> const tag_)
 207 {
 208 SEQAN_CHECKPOINT
 209         typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
 210
 211         size_t bytes_needed = count * sizeof(TValue);
 212
 213         unsigned int block_number = _allocatorBlockNumber(me, bytes_needed);
 214         if (block_number == TAllocator::BLOCKING_COUNT)
 215         {//no blocking
 216                 return deallocate(parentAllocator(me), data, count, tag_);
 217         }
 218
 219         bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
 220
 221         //link in recycling list
 222         *reinterpret_cast<char **>(data) = me.data_recycled_blocks[block_number];
 223         me.data_recycled_blocks[block_number] = reinterpret_cast<char *>(data);
 224 }
 225
 226 //////////////////////////////////////////////////////////////////////////////
 227
 228 } //namespace SEQAN_NAMESPACE_MAIN
 229
 230 #endif //#ifndef SEQAN_HEADER_...