1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, 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 of a given size;  Different-sized blocks are
35 // not pooled.
36 // ==========================================================================
37 
38 #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_
39 #define SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_
40 
41 #include <seqan/basic/allocator_interface.h>
42 
43 namespace seqan {
44 
45 // ============================================================================
46 // Forwards
47 // ============================================================================
48 
49 // ============================================================================
50 // Tags, Classes, Enums
51 // ============================================================================
52 
53 /*!
54  * @class SinglePoolAllocator
55  * @extends Allocator
56  * @headerfile <seqan/basic.h>
57  * @brief Allocator that pools memory blocks of a specific size.
58  *
59  * @signature template <unsigned SIZE, typename TParentAllocator>
60  *            class Allocator;
61  *
62  * @tparam SIZE             The size of the blocks.
63  * @tparam TParentAllocator The parent allocator to use.
64  *
65  * A pool allocator allocates several memory blocks at once.  Freed blocks are not immediately deallocated but
66  * recycled in subsequential allocations.  This way, the number of calls to the heap manager is reduced, and that
67  * might speed up memory management.
68  *
69  * The single pool allocator only pools memory blocks of size at most $SIZE$.  Blocks of other sizes are allocated and
70  * deallocated using an allocator of type $ParentAllocator$. Using the single pool allocator for blocksizes larger
71  * than a few KB is not advised.
72  */
73 
74 template <size_t SIZE, typename TParentAllocator = SimpleAllocator>
75 struct SinglePool;
76 
77 template <size_t SIZE, typename TParentAllocator>
78 struct Allocator<SinglePool<SIZE, TParentAllocator> >
79 {
80     enum
81     {
82         // item must be large enough to keep a pointer to the next free item
83         SIZE_PER_ITEM = SIZE < sizeof(void*)? sizeof(void*) : SIZE,
84         ITEMS_PER_BLOCK = (SIZE_PER_ITEM < 0x0100) ? 0x01000 / SIZE_PER_ITEM : 16,
85         STORAGE_SIZE = SIZE_PER_ITEM * ITEMS_PER_BLOCK,
86         STORAGE_SIZE_MIN = SIZE_PER_ITEM
87     };
88 
89     char * data_recycled_blocks;
90     char * data_current_begin;
91     char * data_current_end;
92     char * data_current_free;
93     Holder<TParentAllocator, Tristate> data_parent_allocator;
94 
95     Allocator() : data_recycled_blocks(), data_current_begin(), data_current_end(), data_current_free()
96     {}
97 
98     Allocator(size_t reserve_item_count) : data_recycled_blocks()
99     {
100         size_t storage_size = std::max(reserve_item_count * SIZE_PER_ITEM, STORAGE_SIZE_MIN);
101         allocate(parentAllocator(*this), data_current_begin, storage_size);
102         data_current_end = data_current_begin + storage_size;
103         data_current_free = data_current_begin;
104     }
105 
106     Allocator(TParentAllocator & parent_alloc)
107     {
108         setValue(data_parent_allocator, parent_alloc);
109 
110         data_recycled_blocks = data_current_end = data_current_free = 0;
111         //dont need to initialize data_current_begin
112     }
113 
114     Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc)
115     {
116         data_recycled_blocks = 0;
117 
118         setValue(data_parent_allocator, parent_alloc);
119 
120         size_t storage_size = std::max(reserve_item_count * SIZE_PER_ITEM, STORAGE_SIZE_MIN);
121         allocate(parentAllocator(*this), data_current_begin, storage_size);
122         data_current_end = data_current_begin + storage_size;
123         data_current_free = data_current_begin;
124     }
125 
126     // Dummy copy
127     Allocator(Allocator const &) :
128         data_recycled_blocks(), data_current_begin(), data_current_end(),
129         data_current_free()
130     {
131         data_recycled_blocks = data_current_end = data_current_free = 0;
132     }
133 
134     inline Allocator &
135     operator=(Allocator const &)
136     {
137         clear(*this);
138         return *this;
139     }
140 
141     ~Allocator()
142     {
143         clear(*this);
144     }
145 };
146 
147 // ============================================================================
148 // Metafunctions
149 // ============================================================================
150 
151 // ============================================================================
152 // Functions
153 // ============================================================================
154 
155 // ----------------------------------------------------------------------------
156 // Function parentAllocator()
157 // ----------------------------------------------------------------------------
158 
159 template <size_t SIZE, typename TParentAllocator>
160 inline TParentAllocator &
161 parentAllocator(Allocator<SinglePool<SIZE, TParentAllocator> > & me)
162 {
163     return value(me.data_parent_allocator);
164 }
165 
166 // ----------------------------------------------------------------------------
167 // Function clear()
168 // ----------------------------------------------------------------------------
169 
170 template <size_t SIZE, typename TParentAllocator>
171 void
172 clear(Allocator<SinglePool<SIZE, TParentAllocator> > & me)
173 {
174     me.data_recycled_blocks = me.data_current_end = me.data_current_free = 0;
175     clear(parentAllocator(me));
176 }
177 
178 // ----------------------------------------------------------------------------
179 // Function allocate()
180 // ----------------------------------------------------------------------------
181 
182 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
183 inline void
184 allocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me,
185          TValue * & data,
186          TSize count,
187          Tag<TUsage> const tag_)
188 {
189     typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator;
190     size_t bytes_needed = count * sizeof(TValue);
191 
192     if (bytes_needed > TAllocator::SIZE_PER_ITEM)
193     {//no blocking
194         allocate(parentAllocator(me), data, count, tag_);
195         return;
196     }
197 
198     if (bytes_needed < TAllocator::SIZE_PER_ITEM)
199         bytes_needed = TAllocator::SIZE_PER_ITEM;
200 
201     char * ptr;
202     if (me.data_recycled_blocks)
203     {//use recycled
204         ptr = me.data_recycled_blocks;
205         me.data_recycled_blocks = * reinterpret_cast<char **>(ptr);
206     }
207     else
208     {//use new
209         ptr = me.data_current_free;
210         if (ptr + bytes_needed > me.data_current_end)
211         {//not enough free space in current storage: allocate new
212             allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
213             me.data_current_begin = ptr;
214             me.data_current_end = ptr + TAllocator::STORAGE_SIZE;
215         }
216         me.data_current_free = ptr + bytes_needed;
217     }
218 
219     data = reinterpret_cast<TValue *>(ptr);
220 }
221 
222 // ----------------------------------------------------------------------------
223 // Function deallocate()
224 // ----------------------------------------------------------------------------
225 
226 template <size_t SIZE, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
227 inline void
228 deallocate(Allocator<SinglePool<SIZE, TParentAllocator> > & me,
229            TValue * data,
230            TSize count,
231            Tag<TUsage> const tag_)
232 {
233     typedef Allocator<SinglePool<SIZE, TParentAllocator> > TAllocator;
234 
235     size_t bytes_needed = count * sizeof(TValue);
236 
237     if (bytes_needed > TAllocator::SIZE_PER_ITEM)
238     {//no blocking
239         deallocate(parentAllocator(me), data, count, tag_);
240         return;
241     }
242 
243     //link in recycling list
244     *reinterpret_cast<char **>(data) = me.data_recycled_blocks;
245     me.data_recycled_blocks = reinterpret_cast<char *>(data);
246 }
247 
248 }  // namespace seqan
249 
250 #endif  // #ifndef SEQAN_BASIC_BASIC_ALLOCATOR_SINGLE_POOL_H_
251