SeqAn-1.1/seqan/basic/basic_allocator_simple.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_simple.h,v 1.1 2008/08/25 16:20:02 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_SIMPLE_H
  22 #define SEQAN_HEADER_BASIC_ALLOCATOR_SIMPLE_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26 //////////////////////////////////////////////////////////////////////////////
  27
  28
  29 //////////////////////////////////////////////////////////////////////////////
  30 // SimpleAlloc Allocator
  31 //////////////////////////////////////////////////////////////////////////////
  32
  33 /**
  34 .Spec.Simple Allocator:
  35 ..cat:Allocators
  36 ..general:Class.Allocator
  37 ..summary:General purpose allocator.
  38 ..signature:Allocator< SimpleAlloc<ParentAllocator> >
  39 ..param.ParentAllocator:An allocator that is by the simple allocator used to allocate memory.
  40 ...default:@Tag.Default@
  41 ...remarks:@Tag.Default@ used as allocator means that the default implementations
  42 of @Function.allocate@ and @Function.deallocate@ are used.
  43 */
  44
  45 template <typename TParentAllocator = Default>
  46 struct SimpleAlloc;
  47
  48 //////////////////////////////////////////////////////////////////////////////
  49
  50
  51 typedef Allocator<SimpleAlloc<Default> > SimpleAllocator;
  52
  53 template <typename TParentAllocator>
  54 struct Allocator<SimpleAlloc<TParentAllocator> >
  55 {
  56         struct Header
  57         {
  58                 Header * left;
  59                 Header * right;
  60                 size_t size;
  61         };
  62
  63         Header * data_storages;
  64         Holder<TParentAllocator> data_parent_allocator;
  65
  66         Allocator():
  67                 data_storages(0)
  68         {
  69 SEQAN_CHECKPOINT
  70         }
  71
  72         Allocator(TParentAllocator & parent_alloc):
  73                 data_storages(0)
  74         {
  75 SEQAN_CHECKPOINT
  76                 setValue(data_parent_allocator, parent_alloc);
  77         }
  78
  79         //Dummy copy
  80         Allocator(Allocator const &):
  81                 data_storages(0)
  82         {
  83         }
  84         inline Allocator &
  85         operator = (Allocator const &)
  86         {
  87                 clear(*this);
  88                 return *this;
  89         }
  90
  91         ~Allocator()
  92         {
  93 SEQAN_CHECKPOINT
  94                 clear(*this);
  95         }
  96 };
  97
  98 //////////////////////////////////////////////////////////////////////////////
  99
 100 template <typename TParentAllocator>
 101 inline TParentAllocator &
 102 parentAllocator(Allocator<SimpleAlloc<TParentAllocator> > & me)
 103 {
 104 SEQAN_CHECKPOINT
 105         return value(me.data_parent_allocator);
 106 }
 107
 108 //////////////////////////////////////////////////////////////////////////////
 109 /**
 110 .Function.Allocator#clear:
 111 ..cat:Memory
 112 ..summary:Deallocates all memory blocks.
 113 ..signature:clear(allocator)
 114 ..param.allocator:Allocator object.
 115 ...type:Class.Allocator
 116 ...concept:Concept.Allocator
 117 ..remarks:This function deallocates all memory blocks
 118 that was allocated using @Function.allocate@ for $allocator$.
 119 The memory is not pooled but directly passed back to the heap manager.
 120 ..see:Function.allocate
 121 ..see:Function.deallocate
 122 */
 123 template <typename TParentAllocator>
 124 void
 125 clear(Allocator<SimpleAlloc<TParentAllocator> > & me)
 126 {
 127 SEQAN_CHECKPOINT
 128         typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
 129
 130         while (me.data_storages)
 131         {
 132                 typename TAllocator::Header * next_storage = me.data_storages->right;
 133                 deallocate(parentAllocator(me), reinterpret_cast<char *>(me.data_storages), me.data_storages->size);
 134                 me.data_storages = next_storage;
 135         }
 136 }
 137
 138 //////////////////////////////////////////////////////////////////////////////
 139
 140 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
 141 inline void
 142 allocate(Allocator<SimpleAlloc<TParentAllocator> > & me,
 143                  TValue * & data,
 144                  TSize count,
 145                  Tag<TUsage> const)
 146 {
 147 SEQAN_CHECKPOINT
 148         typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
 149         typedef typename TAllocator::Header THeader;
 150
 151         //compute needed bytes
 152         size_t bytes_needed = count * sizeof(TValue) + sizeof(THeader);
 153
 154         //allocate storage from parent
 155         char * ptr;
 156         allocate(parentAllocator(me), ptr, bytes_needed, TagAllocateStorage());
 157
 158         THeader * new_block = reinterpret_cast<THeader *>(ptr);
 159         new_block->left = 0;
 160         new_block->right = me.data_storages;
 161         new_block->size = bytes_needed;
 162
 163         if (me.data_storages)
 164         {
 165                 me.data_storages->left = new_block;
 166         }
 167         me.data_storages = new_block;
 168
 169         //return data
 170         data = reinterpret_cast<TValue *>(ptr + sizeof(THeader));
 171 }
 172
 173 //////////////////////////////////////////////////////////////////////////////
 174
 175 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
 176 inline void
 177 deallocate(Allocator<SimpleAlloc<TParentAllocator> > & me,
 178                    TValue * data,
 179                    TSize,
 180                    Tag<TUsage> const)
 181 {
 182 SEQAN_CHECKPOINT
 183         typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
 184         typedef typename TAllocator::Header THeader;
 185
 186         //update links
 187         THeader & header = *(reinterpret_cast<THeader *>(data) - 1);
 188         if (header.left)
 189         {
 190                 header.left->right = header.right;
 191         }
 192         else
 193         {
 194                 me.data_storages = header.right;
 195         }
 196         if (header.right)
 197         {
 198                 header.right->left = header.left;
 199         }
 200
 201         //deallocate storage using parent
 202         char * ptr = reinterpret_cast<char *>(& header);
 203         deallocate(parentAllocator(me), ptr, header.size);
 204 }
 205
 206 //////////////////////////////////////////////////////////////////////////////
 207
 208 } //namespace SEQAN_NAMESPACE_MAIN
 209
 210 #endif //#ifndef SEQAN_HEADER_...