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 // General purpose allocator.
35 // ==========================================================================
36 
37 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_H_
38 #define SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_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 SimpleAllocator
54  * @extends Allocator
55  * @headerfile <seqan/basic.h>
56  * @brief General purpose allocator.
57  *
58  * @signature template <typename TParentAllocator>
59  *            class Allocator<SimpleAlloc<TParentAllocator> >;
60  *
61  * @tparam TParentAllocator An allocator that is used by the simple allocator to allocate memory.
62  *
63  * The tag Default used as TparentAllocator means that the default implementations of <tt>allocate</tt> and
64  * <tt>deallocate</tt> are used.
65  */
66 
67 template <typename TParentAllocator = Default>
68 struct SimpleAlloc;
69 
70 typedef Allocator<SimpleAlloc<Default> > SimpleAllocator;
71 
72 template <typename TParentAllocator>
73 struct Allocator<SimpleAlloc<TParentAllocator> >
74 {
75     struct Header
76     {
77         Header * left;
78         Header * right;
79         size_t size;
80     };
81 
82     Header * data_storages;
83     Holder<TParentAllocator, Tristate> data_parent_allocator;
84 
85     Allocator()
86         : data_storages(0)
87     {
88     }
89 
90     Allocator(TParentAllocator & parent_alloc)
91         : data_storages(0)
92     {
93         setValue(data_parent_allocator, parent_alloc);
94     }
95 
96     //Dummy copy
97     Allocator(Allocator const &)
98         : data_storages(0)
99     {
100     }
101 
102     inline Allocator &
103     operator = (Allocator const &)
104     {
105         clear(*this);
106         return *this;
107     }
108 
109     ~Allocator()
110     {
111         clear(*this);
112     }
113 };
114 
115 // ============================================================================
116 // Metafunctions
117 // ============================================================================
118 
119 // ============================================================================
120 // Functions
121 // ============================================================================
122 
123 // ----------------------------------------------------------------------------
124 // Function parentAllocator()
125 // ----------------------------------------------------------------------------
126 
127 template <typename TParentAllocator>
128 inline TParentAllocator &
129 parentAllocator(Allocator<SimpleAlloc<TParentAllocator> > & me)
130 {
131     return value(me.data_parent_allocator);
132 }
133 
134 // ----------------------------------------------------------------------------
135 // Function clear()
136 // ----------------------------------------------------------------------------
137 
138 /*!
139  * @fn Allocator#clear
140  * @brief Deallocates all memory blocks.
141  *
142  * @signature void clear(allocator);
143  *
144  * @param[in,out] The allocator to clear.
145  *
146  * @section Remarks
147  *
148  * This function deallocates all memory block sthat were allocated using <tt>allocate()</tt> for <tt>allocator</tt>.
149  * The memory is not pooled but directly passed back to the heap manager.
150  */
151 
152 // TODO(holtgrew): Using #-functions messes up search results.
153 template <typename TParentAllocator>
154 void
155 clear(Allocator<SimpleAlloc<TParentAllocator> > & me)
156 {
157     typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
158 
159     while (me.data_storages)
160     {
161         typename TAllocator::Header * next_storage = me.data_storages->right;
162         deallocate(parentAllocator(me), reinterpret_cast<char *>(me.data_storages), me.data_storages->size);
163         me.data_storages = next_storage;
164     }
165 }
166 
167 // ----------------------------------------------------------------------------
168 // Function allocate()
169 // ----------------------------------------------------------------------------
170 
171 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
172 inline void
173 allocate(Allocator<SimpleAlloc<TParentAllocator> > & me,
174          TValue * & data,
175          TSize count,
176          Tag<TUsage> const &)
177 {
178     typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
179     typedef typename TAllocator::Header THeader;
180 
181     //compute needed bytes
182     size_t bytes_needed = count * sizeof(TValue) + sizeof(THeader);
183 
184     //allocate storage from parent
185     char * ptr;
186     allocate(parentAllocator(me), ptr, bytes_needed, TagAllocateStorage());
187 
188     THeader * new_block = reinterpret_cast<THeader *>(ptr);
189     new_block->left = 0;
190     new_block->right = me.data_storages;
191     new_block->size = bytes_needed;
192 
193     if (me.data_storages)
194     {
195         me.data_storages->left = new_block;
196     }
197     me.data_storages = new_block;
198 
199     //return data
200     data = reinterpret_cast<TValue *>(ptr + sizeof(THeader));
201 }
202 
203 // ----------------------------------------------------------------------------
204 // Function deallocate()
205 // ----------------------------------------------------------------------------
206 
207 template <typename TParentAllocator, typename TValue, typename TSize, typename TUsage>
208 inline void
209 deallocate(Allocator<SimpleAlloc<TParentAllocator> > & me,
210            TValue * data,
211            TSize,
212            Tag<TUsage> const &)
213 {
214     typedef Allocator<SimpleAlloc<TParentAllocator> > TAllocator;
215     typedef typename TAllocator::Header THeader;
216 
217     //update links
218     THeader & header = *(reinterpret_cast<THeader *>(data) - 1);
219     if (header.left)
220     {
221         header.left->right = header.right;
222     }
223     else
224     {
225         me.data_storages = header.right;
226     }
227     if (header.right)
228     {
229         header.right->left = header.left;
230     }
231 
232     //deallocate storage using parent
233     char * ptr = reinterpret_cast<char *>(& header);
234     deallocate(parentAllocator(me), ptr, header.size);
235 }
236 
237 }  // namespace seqan
238 
239 #endif  // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ALLOCATOR_SIMPLE_H_
240