1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2010, 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 
33 #ifndef SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
34 #define SEQAN_HEADER_BASIC_ALLOCATOR_MULTIPOOL_H
35 
36 namespace SEQAN_NAMESPACE_MAIN
37 {
38 //////////////////////////////////////////////////////////////////////////////
39 // MultiPool Allocator
40 //////////////////////////////////////////////////////////////////////////////
41 
42 /**
43 .Spec.Multi Pool Allocator:
44 ..cat:Allocators
45 ..general:Class.Allocator
46 ..summary:Allocator that pools memory blocks.
47 ..signature:Allocator< MultiPool<ParentAllocator, BLOCKING_LIMIT> >
48 ..param.ParentAllocator:An allocator that is by the pool allocator used to allocate memory.
49 ...default:@Spec.Simple Allocator@
50 ...note:The multi pool allocator only supports @Function.clear@ if this function is also implemented for $ParentAllocator$.
51 ..remarks:A pool allocator allocates several memory blocks at once.
52 ..param.BLOCKING_LIMIT:The maximum size for memory blocks to be pooled.
53 ...default:256
54 Freed blocks are not immediately deallocated but recycled in subsequential allocations.
55 This way, the number of calls to the heap manager is reduced, and that speeds up memory management.
56 ...text:Note that memory blocks larger than $BLOCKING_LIMIT$ are not pooled
57 but immediately allocated and deallocated using $ParentAllocator$.
58 ..include:seqan/basic.h
59 */
60 
61 
62 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100>
63 struct MultiPool;
64 
65 //////////////////////////////////////////////////////////////////////////////
66 
67 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator;
68 
69 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_>
70 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> >
71 {
72 	enum
73 	{
74 		BLOCKING_LIMIT = BLOCKING_LIMIT_,
75 		GRANULARITY_BITS = 2,
76 		BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS,
77 		STORAGE_SIZE = 0xf80
78 	};
79 
80 	char * data_recycled_blocks [BLOCKING_COUNT];
81 	char * data_current_begin [BLOCKING_COUNT];
82 	char * data_current_free [BLOCKING_COUNT];
83 	Holder<TParentAllocator> data_parent_allocator;
84 
85 	Allocator()
86 	{
87 SEQAN_CHECKPOINT
88 		::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
89 		::std::memset(data_current_begin, 0, sizeof(data_current_begin));
90 		::std::memset(data_current_free, 0, sizeof(data_current_free));
91 	}
92 
93 	Allocator(TParentAllocator & parent_alloc)
94 	{
95 SEQAN_CHECKPOINT
96 		::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
97 		::std::memset(data_current_begin, 0, sizeof(data_current_begin));
98 		::std::memset(data_current_free, 0, sizeof(data_current_free));
99 
100 		setValue(data_parent_allocator, parent_alloc);
101 	}
102 
103 	//Dummy copy
104 	Allocator(Allocator const &)
105 	{
106 		::std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
107 		::std::memset(data_current_begin, 0, sizeof(data_current_begin));
108 		::std::memset(data_current_free, 0, sizeof(data_current_free));
109 	}
110 	inline Allocator &
111 	operator = (Allocator const &)
112 	{
113 		clear(*this);
114 		return *this;
115 	}
116 
117 	~Allocator()
118 	{
119 SEQAN_CHECKPOINT
120 		clear(*this);
121 	}
122 };
123 //////////////////////////////////////////////////////////////////////////////
124 
125 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
126 inline TParentAllocator &
127 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
128 {
129 SEQAN_CHECKPOINT
130 	return value(me.data_parent_allocator);
131 }
132 
133 //////////////////////////////////////////////////////////////////////////////
134 
135 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
136 void
137 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
138 {
139 SEQAN_CHECKPOINT
140 	::std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks));
141 	::std::memset(me.data_current_begin, 0, sizeof(me.data_current_begin));
142 	::std::memset(me.data_current_free, 0, sizeof(me.data_current_free));
143 
144 	clear(parentAllocator(me));
145 }
146 
147 //////////////////////////////////////////////////////////////////////////////
148 
149 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
150 inline unsigned int
151 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &,
152 					  size_t size_)
153 {
154 SEQAN_CHECKPOINT
155 	typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
156 
157 	SEQAN_ASSERT(size_)
158 
159 	if (size_ < BLOCKING_LIMIT)
160 	{//blocks
161 		return size_ >> TAllocator::GRANULARITY_BITS;
162 	}
163 	else
164 	{//no blocking
165 		return TAllocator::BLOCKING_COUNT;
166 	}
167 }
168 
169 
170 //////////////////////////////////////////////////////////////////////////////
171 
172 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
173 inline void
174 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
175 		 TValue * & data,
176 		 TSize count,
177 		 Tag<TUsage> const tag_)
178 {
179 SEQAN_CHECKPOINT
180 	typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
181 
182 	size_t bytes_needed = count * sizeof(TValue);
183 	char * ptr;
184 
185 	unsigned int block_number =  _allocatorBlockNumber(me, bytes_needed);
186 	if (block_number == TAllocator::BLOCKING_COUNT)
187 	{//no blocking
188 		return allocate(parentAllocator(me), data, count, tag_);
189 	}
190 
191 	bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
192 
193 	if (me.data_recycled_blocks[block_number])
194 	{//use recycled
195 		ptr = me.data_recycled_blocks[block_number];
196 		me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr);
197 	}
198 	else
199 	{//use new
200 		ptr = me.data_current_free[block_number];
201 		if (!ptr || (ptr + bytes_needed > me.data_current_begin[block_number] + TAllocator::STORAGE_SIZE))
202 		{//not enough free space in current storage: allocate new
203 			allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
204 			me.data_current_begin[block_number] = ptr;
205 		}
206 		me.data_current_free[block_number] = ptr + bytes_needed;
207 	}
208 
209 	data = reinterpret_cast<TValue *>(ptr);
210 }
211 
212 //////////////////////////////////////////////////////////////////////////////
213 
214 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
215 inline void
216 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
217 		   TValue * data,
218 		   TSize count,
219 		   Tag<TUsage> const tag_)
220 {
221 SEQAN_CHECKPOINT
222 	typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
223 
224 	size_t bytes_needed = count * sizeof(TValue);
225 
226 	unsigned int block_number = _allocatorBlockNumber(me, bytes_needed);
227 	if (block_number == TAllocator::BLOCKING_COUNT)
228 	{//no blocking
229 		return deallocate(parentAllocator(me), data, count, tag_);
230 	}
231 
232 	bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
233 
234 	//link in recycling list
235 	*reinterpret_cast<char **>(data) = me.data_recycled_blocks[block_number];
236 	me.data_recycled_blocks[block_number] = reinterpret_cast<char *>(data);
237 }
238 
239 //////////////////////////////////////////////////////////////////////////////
240 
241 } //namespace SEQAN_NAMESPACE_MAIN
242 
243 #endif //#ifndef SEQAN_HEADER_...
244