1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, 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 // Author: Andreas Gogol-Doering <andreas.doering@mdc-berlin.de>
33 // ==========================================================================
34 // Allocator that pools blocks up to a given size.
35 // ==========================================================================
36 
37 #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_
38 #define SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_
39 
40 #include <seqan/basic/allocator_interface.h>
41 
42 namespace seqan {
43 
44 // ============================================================================
45 // Forwards
46 // ============================================================================
47 
48 // ============================================================================
49 // Tags, Classes, Enums
50 // ============================================================================
51 
52 /*!
53  * @class MultiPoolAllocator
54  * @extends Allocator
55  * @headerfile <seqan/basic.h>
56  * @brief Allocator that pools memory blocks.
57  *
58  * @signature template <typename TParentAllocator[, unsigned BLOCKING_LIMIT]>
59  *            class Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> >;
60  *
61  * @tparam TParentAllocator The parent allocator.
62  * @tparam BLOCKING_LIMIT The maximum size for memory blocks to be pooled (default is 256).
63  *
64  * Freed blocks are not immediately deallocated but recycled in subsequential allocations.  This way, the number of
65  * calls to the heap manager is reduced and that might speed up memory management.
66  *
67  * Note that memory block larger than <tt>BLOCKING_LIMIT</tt> are not pooled but immediately allocated and deallocated
68  * using <tt>ParentAllocator</tt>.
69  */
70 
71 template <typename TParentAllocator = Allocator<SimpleAlloc<Default> >, unsigned int BLOCKING_LIMIT = 0x100>
72 struct MultiPool;
73 
74 typedef Allocator<MultiPool<Allocator<SimpleAlloc<Default> >, 0x100> > PoolAllocator;
75 
76 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT_>
77 struct Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT_> >
78 {
79     enum
80     {
81         BLOCKING_LIMIT = BLOCKING_LIMIT_,
82         GRANULARITY_BITS = 2,
83         BLOCKING_COUNT = BLOCKING_LIMIT >> GRANULARITY_BITS,
84         STORAGE_SIZE = 0xf80
85     };
86 
87     char * data_recycled_blocks [BLOCKING_COUNT];
88     char * data_current_begin [BLOCKING_COUNT];
89     char * data_current_free [BLOCKING_COUNT];
90     Holder<TParentAllocator, Tristate> data_parent_allocator;
91 
92     Allocator()
93     {
94         // TODO(holtrew): Why not SeqAn's memset? or use using?
95         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
96         std::memset(data_current_begin, 0, sizeof(data_current_begin));
97         std::memset(data_current_free, 0, sizeof(data_current_free));
98     }
99 
100     Allocator(TParentAllocator & parent_alloc)
101     {
102         // TODO(holtrew): Why not SeqAn's memset? or use using?
103         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
104         std::memset(data_current_begin, 0, sizeof(data_current_begin));
105         std::memset(data_current_free, 0, sizeof(data_current_free));
106 
107         setValue(data_parent_allocator, parent_alloc);
108     }
109 
110     //Dummy copy
111     Allocator(Allocator const &)
112     {
113         // TODO(holtrew): Why not SeqAn's memset? or use using?
114         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
115         std::memset(data_current_begin, 0, sizeof(data_current_begin));
116         std::memset(data_current_free, 0, sizeof(data_current_free));
117     }
118 
119     inline Allocator &
120     operator=(Allocator const &)
121     {
122         clear(*this);
123         return *this;
124     }
125 
126     ~Allocator()
127     {
128         clear(*this);
129     }
130 };
131 
132 // ============================================================================
133 // Metafunctions
134 // ============================================================================
135 
136 // ============================================================================
137 // Functions
138 // ============================================================================
139 
140 // ----------------------------------------------------------------------------
141 // Function parentAllocator()
142 // ----------------------------------------------------------------------------
143 
144 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
145 inline TParentAllocator &
146 parentAllocator(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
147 {
148     return value(me.data_parent_allocator);
149 }
150 
151 // ----------------------------------------------------------------------------
152 // Function clear()
153 // ----------------------------------------------------------------------------
154 
155 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
156 void
157 clear(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me)
158 {
159     std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks));
160     std::memset(me.data_current_begin, 0, sizeof(me.data_current_begin));
161     std::memset(me.data_current_free, 0, sizeof(me.data_current_free));
162 
163     clear(parentAllocator(me));
164 }
165 
166 // ----------------------------------------------------------------------------
167 // Helper function _allocatorBlockNumber()
168 // ----------------------------------------------------------------------------
169 
170 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT>
171 inline unsigned int
172 _allocatorBlockNumber(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > &,
173                       size_t size_)
174 {
175     typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
176 
177     SEQAN_ASSERT_GT(size_, 0u);
178 
179     if (size_ < BLOCKING_LIMIT)
180     {//blocks
181         return size_ >> TAllocator::GRANULARITY_BITS;
182     }
183     else
184     {//no blocking
185         return TAllocator::BLOCKING_COUNT;
186     }
187 }
188 
189 // ----------------------------------------------------------------------------
190 // Function allocate()
191 // ----------------------------------------------------------------------------
192 
193 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
194 inline void
195 allocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
196          TValue * & data,
197          TSize count,
198          Tag<TUsage> const & tag_)
199 {
200     typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
201 
202     size_t bytes_needed = count * sizeof(TValue);
203     char * ptr;
204 
205     unsigned int block_number =  _allocatorBlockNumber(me, bytes_needed);
206     if (block_number == TAllocator::BLOCKING_COUNT)
207     {//no blocking
208         return allocate(parentAllocator(me), data, count, tag_);
209     }
210 
211     bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
212 
213     if (me.data_recycled_blocks[block_number])
214     {//use recycled
215         ptr = me.data_recycled_blocks[block_number];
216         me.data_recycled_blocks[block_number] = * reinterpret_cast<char **>(ptr);
217     }
218     else
219     {//use new
220         ptr = me.data_current_free[block_number];
221         if (!ptr || (ptr + bytes_needed > me.data_current_begin[block_number] + TAllocator::STORAGE_SIZE))
222         {//not enough free space in current storage: allocate new
223             allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
224             me.data_current_begin[block_number] = ptr;
225         }
226         me.data_current_free[block_number] = ptr + bytes_needed;
227     }
228 
229     data = reinterpret_cast<TValue *>(ptr);
230 }
231 
232 // ----------------------------------------------------------------------------
233 // Function deallocate()
234 // ----------------------------------------------------------------------------
235 
236 template <typename TParentAllocator, unsigned int BLOCKING_LIMIT, typename TValue, typename TSize, typename TUsage>
237 inline void
238 deallocate(Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > & me,
239            TValue * data,
240            TSize count,
241            Tag<TUsage> const tag_)
242 {
243     typedef Allocator<MultiPool<TParentAllocator, BLOCKING_LIMIT> > TAllocator;
244 
245     size_t bytes_needed = count * sizeof(TValue);
246 
247     unsigned int block_number = _allocatorBlockNumber(me, bytes_needed);
248     if (block_number == TAllocator::BLOCKING_COUNT)
249     {//no blocking
250         return deallocate(parentAllocator(me), data, count, tag_);
251     }
252 
253     bytes_needed = (block_number + 1) << TAllocator::GRANULARITY_BITS;
254 
255     //link in recycling list
256     *reinterpret_cast<char **>(data) = me.data_recycled_blocks[block_number];
257     me.data_recycled_blocks[block_number] = reinterpret_cast<char *>(data);
258 }
259 
260 }  // namespace seqan
261 
262 #endif  // #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_MULTIPOOL_H_
263