1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
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.
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.
17 ============================================================================
18 $Id: basic_allocator_multipool.h,v 1.2 2009/02/19 01:51:23 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
22 #define SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
24 namespace SEQAN_NAMESPACE_MAIN
26 //////////////////////////////////////////////////////////////////////////////
27 // MultiPool Allocator
28 //////////////////////////////////////////////////////////////////////////////
31 .Spec.Multi Pool Allocator:
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.
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$.
49 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100>
52 //////////////////////////////////////////////////////////////////////////////
54 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator;
56 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_>
57 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> >
61 BLOCKING_LIMIT = BLOCKING_LIMIT_,
63 BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS,
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;
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));
80 Allocator(TParentAllocator & parent_alloc)
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));
87 setValue(data_parent_allocator, parent_alloc);
91 Allocator(Allocator const &)
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));
98 operator = (Allocator const &)
110 //////////////////////////////////////////////////////////////////////////////
112 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
113 inline TParentAllocator &
114 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
117 return value(me.data_parent_allocator);
120 //////////////////////////////////////////////////////////////////////////////
122 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
124 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
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));
131 clear(parentAllocator(me));
134 //////////////////////////////////////////////////////////////////////////////
136 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
138 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &,
142 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
146 if (size_ < BLOCKING_LIMIT)
148 return size_ >> TAllocator::GRANULARITY_BITS;
152 return TAllocator::BLOCKING_COUNT;
157 //////////////////////////////////////////////////////////////////////////////
159 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
161 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
164 Tag<TUsage> const tag_)
167 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
169 size_t bytes_needed = count * sizeof(TValue);
172 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed);
173 if (block_number == TAllocator::BLOCKING_COUNT)
175 return allocate(parentAllocator(me), data, count, tag_);
178 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
180 if (me.data_recycled_blocks[block_number])
182 ptr = me.data_recycled_blocks[block_number];
183 me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr);
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;
193 me.data_current_free[block_number] = ptr + bytes_needed;
196 data = reinterpret_cast<TValue *>(ptr);
199 //////////////////////////////////////////////////////////////////////////////
201 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
203 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
206 Tag<TUsage> const tag_)
209 typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
211 size_t bytes_needed = count * sizeof(TValue);
213 unsigned int block_number = _allocatorBlockNumber(me, bytes_needed);
214 if (block_number == TAllocator::BLOCKING_COUNT)
216 return deallocate(parentAllocator(me), data, count, tag_);
219 bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
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);
226 //////////////////////////////////////////////////////////////////////////////
228 } //namespace SEQAN_NAMESPACE_MAIN
230 #endif //#ifndef SEQAN_HEADER_...