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 one or more consecutive memory blocks of a specific
35 // size.
36 // ==========================================================================
37 
38 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_H_
39 #define SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_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 template <
54     size_t SIZE,
55     size_t MAX_COUNT = 26,
56     typename TParentAllocator = Allocator<SimpleAlloc<Default> > >
57 struct ChunkPool;
58 
59 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator>
60 struct Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> >
61 {
62     enum
63     {
64         STORAGE_SIZE_1 = 0x1000UL,
65         STORAGE_SIZE_2 = SIZE * MAX_COUNT * 8,
66         STORAGE_SIZE_UPPER = (STORAGE_SIZE_1 > STORAGE_SIZE_2) ? STORAGE_SIZE_1 : STORAGE_SIZE_2,
67         ITEMS_PER_STORAGE = STORAGE_SIZE_UPPER / SIZE,
68         STORAGE_SIZE = ITEMS_PER_STORAGE * SIZE,
69 
70         STORAGE_SIZE_MIN = SIZE * MAX_COUNT //minimal storage size
71     };
72 
73     char * data_recycled_blocks [MAX_COUNT];
74     char * data_current_begin;
75     char * data_current_end;
76     char * data_current_free;
77     Holder<TParentAllocator, Tristate> data_parent_allocator;
78 
79     Allocator()
80     {
81         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
82         data_current_end = data_current_free = 0;
83         //dont need to initialize data_current_begin
84     }
85 
86     Allocator(size_t reserve_item_count)
87     {
88         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
89 
90         size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN;
91         allocate( parentAllocator( *this ), data_current_begin, storage_size );
92         data_current_end = data_current_begin + storage_size;
93         data_current_free = data_current_begin;
94     }
95 
96     Allocator(TParentAllocator & parent_alloc)
97     {
98         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
99         data_current_end = data_current_free = 0;
100         //dont need to initialize data_current_begin
101 
102         setValue(data_parent_allocator, parent_alloc);
103     }
104 
105     Allocator(size_t reserve_item_count, TParentAllocator & parent_alloc)
106     {
107         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
108 
109         setValue(data_parent_allocator, parent_alloc);
110 
111         size_t storage_size = (reserve_item_count * SIZE > STORAGE_SIZE_MIN) ? reserve_item_count * SIZE : STORAGE_SIZE_MIN;
112         allocate( parentAllocator( *this ), data_current_begin, storage_size );
113         data_current_end = data_current_begin + storage_size;
114         data_current_free = data_current_begin;
115     }
116 
117     //Dummy copy
118     Allocator(Allocator const &)
119     {
120         std::memset(data_recycled_blocks, 0, sizeof(data_recycled_blocks));
121         data_current_end = data_current_free = 0;
122         //dont need to initialize data_current_begin
123     }
124     inline Allocator &
125     operator=(Allocator const &)
126     {
127         clear(*this);
128         return *this;
129     }
130 
131     ~Allocator()
132     {
133         clear(*this);
134     }
135 };
136 
137 // ============================================================================
138 // Metafunctions
139 // ============================================================================
140 
141 // ============================================================================
142 // Functions
143 // ============================================================================
144 
145 // ----------------------------------------------------------------------------
146 // Function parentAllocator()
147 // ----------------------------------------------------------------------------
148 
149 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator>
150 inline TParentAllocator &
151 parentAllocator(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me)
152 {
153     return value(me.data_parent_allocator);
154 }
155 
156 // ----------------------------------------------------------------------------
157 // Function clear()
158 // ----------------------------------------------------------------------------
159 
160 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator>
161 void
162 clear(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me)
163 {
164     std::memset(me.data_recycled_blocks, 0, sizeof(me.data_recycled_blocks));
165     me.data_current_end = me.data_current_free = 0;
166 
167     clear(parentAllocator(me));
168 }
169 
170 // ----------------------------------------------------------------------------
171 // Function allocate()
172 // ----------------------------------------------------------------------------
173 
174 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
175 inline void
176 allocate(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me,
177          TValue * & data,
178          TSize count,
179          Tag<TUsage> const tag_)
180 {
181     SEQAN_ASSERT_GT(count, static_cast<TSize>(0));
182 
183     typedef Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > TAllocator;
184 
185     char * ptr;
186 
187     if ((sizeof(TValue) != SIZE) || ((size_t) count > MAX_COUNT))
188     {//no blocking
189         return allocate(parentAllocator(me), data, count, tag_);
190     }
191 
192     size_t bytes_needed = count * SIZE;
193     if (me.data_recycled_blocks[count - 1])
194     {//use recycled
195         ptr = me.data_recycled_blocks[count - 1];
196         me.data_recycled_blocks[count - 1] = * reinterpret_cast<char **>(ptr);
197     }
198     else
199     {//use new
200         ptr = me.data_current_free;
201         if (ptr + bytes_needed > me.data_current_end)
202         {//not enough free space in current storage: allocate new
203             size_t rest_block_number = (me.data_current_end - me.data_current_free) / SIZE;
204             if (ptr && rest_block_number)
205             {//link rest to recycle list
206                 *reinterpret_cast<char **>(ptr) = me.data_recycled_blocks[rest_block_number - 1];
207                 me.data_recycled_blocks[rest_block_number - 1] = reinterpret_cast<char *>(ptr);
208             }
209 
210             allocate(parentAllocator(me), ptr, (size_t) TAllocator::STORAGE_SIZE, tag_);
211             me.data_current_begin = ptr;
212             me.data_current_end = ptr + TAllocator::STORAGE_SIZE;
213         }
214         me.data_current_free = ptr + bytes_needed;
215     }
216 
217     data = reinterpret_cast<TValue *>(ptr);
218 }
219 
220 // ----------------------------------------------------------------------------
221 // Function deallocate()
222 // ----------------------------------------------------------------------------
223 
224 template <size_t SIZE, size_t MAX_COUNT, typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
225 inline void
226 deallocate(Allocator<ChunkPool<SIZE, MAX_COUNT, TParentAllocator> > & me,
227            TValue * data,
228            TSize count,
229            Tag<TUsage> const tag_)
230 {
231     SEQAN_ASSERT_GT(count, 0);
232 
233     if ((sizeof(TValue) != SIZE) || (static_cast<size_t>(count) > MAX_COUNT))
234     {//no blocking
235         return deallocate(parentAllocator(me), data, count, tag_);
236     }
237 
238     //link in recycling list
239     *reinterpret_cast<char **>(data) = me.data_recycled_blocks[count - 1];
240     me.data_recycled_blocks[count - 1] = reinterpret_cast<char *>(data);
241 }
242 
243 }  // namespace seqan
244 
245 #endif  // SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_CHUNKPOOL_H_
246