SeqAn-1.1/seqan/basic/basic_allocator_singlepool.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_singlepool.h,v 1.1 2008/08/25 16:20:01 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_SINGLE_POOL_H
  22 #define SEQAN_HEADER_BASIC_ALLOCATOR_SINGLE_POOL_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26 //////////////////////////////////////////////////////////////////////////////
  27 // SinglePool Allocator
  28 //////////////////////////////////////////////////////////////////////////////
  29
  30 /**
  31 .Spec.Single Pool Allocator:
  32 ..cat:Allocators
  33 ..general:Class.Allocator
  34 ..summary:Allocator that pools memory blocks of specific size.
  35 ..signature:Allocator< SinglePool<SIZE, ParentAllocator> >
  36 ..param.SIZE:Size of memory blocks that are pooled.
  37 ...value:An unsigned integer with $SIZE >= sizeof(void *)$.
  38 ..param.ParentAllocator:An allocator that is by the pool allocator used to allocate memory.
  39 ...default:@Spec.Simple Allocator@
  40 ...note:The single pool allocator only supports @Function.clear@ if this function is also implemented for $ParentAllocator$.
  41 ..remarks:A pool allocator allocates several memory blocks at once.
  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:The single pool allocator only pools memory blocks of size $SIZE$.
  45 Blocks of other sizes are allocated and deallocated using an allocator of type $ParentAllocator$.
  46 ...text:Using the single pool allocator for blocksizes larger than some KB is not advised.
  47 */
  48
  49 template <size_t SIZE, typename TParentAllocator = SimpleAllocator>
  50 struct SinglePool;
  51
  52 //////////////////////////////////////////////////////////////////////////////
  53
  54 template <size_t SIZE, typename TParentAllocator>
  55 struct Allocator<SinglePool<SIZE, TParentAllocator> >
  56 {
  57         enum
  58         {
  59                 SIZE_PER_ITEM = SIZE,
  60                 ITEMS_PER_BLOCK = (SIZE_PER_ITEM < 0x0100) ? 0x01000 / SIZE_PER_ITEM : 16,
  61                 STORAGE_SIZE = SIZE * ITEMS_PER_BLOCK,
  62
  63                 STORAGE_SIZE_MIN = SIZE
  64         };
  65
  66         char * data_recycled_blocks;
  67         char * data_current_begin;
  68         char * data_current_end;
  69         char * data_current_free;
  70         Holder<TParentAllocator> data_parent_allocator;
  71
  72         Allocator()
  73         {
  74 SEQAN_CHECKPOINT
  75                 data_recycled_blocks = data_current_end = data_current_free = 0;
  76                 //dont need to initialize data_current_begin
  77         }
  78
  79         Allocator(size_t reserve_item_count)
  80         {
  81 SEQAN_CHECKPOINT
  82                 data_recycled_blocks = 0;
  83
  84                 size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN;
  85                 allocate( parentAllocator( *this ), data_current_begin, storage_size );
  86                 data_current_end = data_current_begin + storage_size;
  87                 data_current_free = data_current_begin;
  88         }
  89
  90         Allocator(TParentAllocator & parent_alloc)
  91         {
  92 SEQAN_CHECKPOINT
  93                 setValue(data_parent_allocator, parent_alloc);
  94
  95                 data_recycled_blocks = data_current_end = data_current_free = 0;
  96                 //dont need to initialize data_current_begin
  97         }
  98
  99         Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc)
 100         {
 101 SEQAN_CHECKPOINT
 102                 data_recycled_blocks = 0;
 103
 104                 setValue(data_parent_allocator, parent_alloc);
 105
 106                 size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN;
 107                 allocate( parentAllocator( *this ), data_current_begin, storage_size );
 108                 data_current_end = data_current_begin + storage_size;
 109                 data_current_free = data_current_begin;
 110         }
 111
 112         //Dummy copy
 113         Allocator(Allocator const &)
 114         {
 115                 data_recycled_blocks = data_current_end = data_current_free = 0;
 116                 //dont need to initialize data_current_begin
 117         }
 118         inline Allocator &
 119         operator = (Allocator const &)
 120         {
 121                 clear(*this);
 122                 return *this;
 123         }
 124
 125         ~Allocator()
 126         {
 127 SEQAN_CHECKPOINT
 128                 clear(*this);
 129         }
 130 };
 131 //////////////////////////////////////////////////////////////////////////////
 132
 133 template <size_t SIZE, typename TParentAllocator>
 134 inline TParentAllocator &
 135 parentAllocator(Allocator<SinglePool<SIZE, TParentAllocator> > & me)
 136 {
 137 SEQAN_CHECKPOINT
 138         return value(me.data_parent_allocator);
 139 }
 140
 141 //////////////////////////////////////////////////////////////////////////////
 142
 143 template <size_t SIZE, typename TParentAllocator>
 144 void
 145 clear(Allocator<SinglePool<SIZE, TParentAllocator> > & me)
 146 {
 147 SEQAN_CHECKPOINT
 148
 149         me.data_recycled_blocks = me.data_current_end = me.data_current_free = 0;
 150
 151         clear(parentAllocator(me));
 152 }
 153
 154 //////////////////////////////////////////////////////////////////////////////
 155
 156 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
 157 inline void
 158 allocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me,
 159                  TValue * & data,
 160                  TSize count,
 161                  Tag<TUsage> const tag_)
 162 {
 163 SEQAN_CHECKPOINT
 164         typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator;
 165         size_t bytes_needed = count * sizeof(TValue);
 166
 167         if (bytes_needed != TAllocator::SIZE_PER_ITEM)
 168         {//no blocking
 169                 allocate(parentAllocator(me), data, count, tag_);
 170                 return;
 171         }
 172
 173         char * ptr;
 174         if (me.data_recycled_blocks)
 175         {//use recycled
 176                 ptr = me.data_recycled_blocks;
 177                 me.data_recycled_blocks = * reinterpret_cast<char **>(ptr);
 178         }
 179         else
 180         {//use new
 181                 ptr = me.data_current_free;
 182                 if (ptr + bytes_needed > me.data_current_end)
 183                 {//not enough free space in current storage: allocate new
 184                         allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
 185                         me.data_current_begin = ptr;
 186                         me.data_current_end = ptr + TAllocator::STORAGE_SIZE;
 187                 }
 188                 me.data_current_free = ptr + bytes_needed;
 189         }
 190
 191         data = reinterpret_cast<TValue *>(ptr);
 192 }
 193
 194 //////////////////////////////////////////////////////////////////////////////
 195
 196 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
 197 inline void
 198 deallocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me,
 199                    TValue * data,
 200                    TSize count,
 201                    Tag<TUsage> const tag_)
 202 {
 203 SEQAN_CHECKPOINT
 204         typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator;
 205
 206         size_t bytes_needed = count * sizeof(TValue);
 207
 208         if (bytes_needed != TAllocator::SIZE_PER_ITEM)
 209         {//no blocking
 210                 deallocate(parentAllocator(me), data, count, tag_);
 211                 return;
 212         }
 213
 214         //link in recycling list
 215         *reinterpret_cast<char **>(data) = me.data_recycled_blocks;
 216         me.data_recycled_blocks = reinterpret_cast<char *>(data);
 217 }
 218
 219 //////////////////////////////////////////////////////////////////////////////
 220 //////////////////////////////////////////////////////////////////////////////
 221 // alternative Interface that takes a Type instead of a SIZE
 222 //////////////////////////////////////////////////////////////////////////////
 223
 224
 225 template <typename TValue, typename TParentAllocator = SimpleAllocator>
 226 struct SinglePool2;
 227
 228 template <typename TValue, typename TParentAllocator>
 229 struct Allocator<SinglePool2<TValue, TParentAllocator> >
 230 {
 231         Allocator<SinglePool<sizeof(TValue), TParentAllocator> > data_alloc;
 232
 233
 234         Allocator(size_t reserve_item_count)
 235                 : data_alloc(reserve_item_count)
 236         {
 237         }
 238
 239         Allocator(TParentAllocator & parent_alloc)
 240                 : data_alloc(parent_alloc)
 241         {
 242         }
 243
 244         Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc)
 245                 : data_alloc(reserve_item_count, parent_alloc)
 246
 247         {
 248         }
 249 };
 250
 251 //////////////////////////////////////////////////////////////////////////////
 252
 253 template <typename TValue, typename TParentAllocator>
 254 inline TParentAllocator &
 255 parentAllocator(Allocator<SinglePool2<TValue, TParentAllocator> > & me)
 256 {
 257 SEQAN_CHECKPOINT
 258         return parentAllocator(me.data_alloc);
 259 }
 260
 261 //////////////////////////////////////////////////////////////////////////////
 262
 263 template <typename TValue, typename TParentAllocator>
 264 void
 265 clear(Allocator<SinglePool2<TValue, TParentAllocator> > & me)
 266 {
 267 SEQAN_CHECKPOINT
 268         clear(me.data_alloc);
 269 }
 270
 271 //////////////////////////////////////////////////////////////////////////////
 272
 273 template <typename TValue, typename TParentAllocator, typename TValue2, typename TSize, typename TUsage>
 274 inline void
 275 allocate(Allocator<SinglePool2<TValue, TParentAllocator> > & me,
 276                  TValue2 * & data,
 277                  TSize count,
 278                  Tag<TUsage> const tag_)
 279 {
 280 SEQAN_CHECKPOINT
 281         allocate(me.data_alloc, data, count, tag_);
 282 }
 283
 284 template <typename TValue, typename TParentAllocator, typename TValue2, typename TSize, typename TUsage>
 285 inline void
 286 deallocate(Allocator<SinglePool2<TValue, TParentAllocator> > & me,
 287                    TValue2 * data,
 288                    TSize count,
 289                    Tag<TUsage> const tag_)
 290 {
 291 SEQAN_CHECKPOINT
 292         deallocate(me.data_alloc, data, count, tag_);
 293 }
 294
 295 //////////////////////////////////////////////////////////////////////////////
 296
 297 } //namespace SEQAN_NAMESPACE_MAIN
 298
 299 #endif //#ifndef SEQAN_HEADER_...