Xalan-C++ API Reference 1.12.0
XalanArrayAllocator.hpp
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18#if !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680)
19#define XALANARRAYALLOCATOR_HEADER_GUARD_1357924680
20
21
22
24
25
26
27#include <cassert>
28#include <utility>
29
30
31
34
35
36
37namespace XALAN_CPP_NAMESPACE {
38
39
40
41template<class Type>
43{
44public:
45
48
49 typedef std::pair<size_type, VectorType * > ListEntryType;
51
52 typedef Type value_type;
53
55
56 // Default size for vector allocation.
57 enum { eDefaultBlockSize = 500 };
58
59 /**
60 * Constructor.
61 *
62 * @param theBlockSize The block size when allocating.
63 */
64 XalanArrayAllocator(MemoryManager& theManager,
65 size_type theBlockSize = eDefaultBlockSize) :
66 m_list(theManager),
67 m_blockSize(theBlockSize),
68 m_lastEntryFound(0)
69 {
70 }
71
73 {
74 typename ListType::iterator iter = m_list.begin();
75
76 MemoryManager& theManager = m_list.getMemoryManager();
77
78 for( iter = m_list.begin(); iter != m_list.end(); ++iter)
79 {
80 if( (*iter).second != 0)
81 {
82 (*iter).second->VectorType::~VectorType();
83 theManager.deallocate((void*)(*iter).second);
84 }
85 }
86 }
87
88 /**
89 * Clear the instance, and release all allocated memory
90 */
91 void
93 {
94 m_list.clear();
95
96 m_lastEntryFound = 0;
97 }
98
99 /**
100 * Reset the instance, but keep all memory so it can be
101 * reused for allocations. This invalidates all previous
102 * allocations.
103 */
104 void
106 {
107 if (m_list.empty() == true)
108 {
109 m_lastEntryFound = 0;
110 }
111 else
112 {
113 const ListIteratorType theEnd = m_list.end();
114 ListIteratorType theCurrent = m_list.begin();
115
116 do
117 {
118 (*theCurrent).first = (*theCurrent).second->size();
119
120 ++theCurrent;
121 } while(theCurrent != theEnd);
122
123 m_lastEntryFound = &*m_list.begin();
124 }
125 }
126
127 /**
128 * Allocate slots for the given number of Types
129 * instance and return the address of the slots.
130 *
131 * @param theCount The number of slots to allocate
132 */
133 Type*
135 {
136 // Handle the case of theCount being greater than the block size first...
137 if (theCount >= m_blockSize)
138 {
139 return createEntry(theCount, theCount);
140 }
141 else
142 {
143 ListEntryType* theEntry =
144 findEntry(theCount);
145
146 // Did we find a slot?
147 if (theEntry == 0)
148 {
149 // Nope, create a new one...
150 return createEntry(m_blockSize, theCount);
151 }
152 else
153 {
154 // The address we want is that of the first free element in the
155 // vector...
156 assert( theEntry->second != 0);
157 Type* const thePointer =
158 &*theEntry->second->begin() + (theEntry->second->size() - theEntry->first);
159
160 // Resize the vector to the appropriate size...
161 theEntry->first -= theCount;
162
163 return thePointer;
164 }
165 }
166 }
167
168private:
169
170 // Utility functions...
171 Type*
172 createEntry(
173 size_type theBlockSize,
174 size_type theCount)
175 {
176 assert(theBlockSize >= theCount);
177
178 // Push on a new entry. The entry has no open space,
179 // since it's greater than our block size...
180 m_list.push_back(ListEntryType(0, VectorType::create(m_list.getMemoryManager())));
181
182 // Get the new entry...
183 ListEntryType& theNewEntry = m_list.back();
184
185 // Resize the vector to the appropriate size...
186 assert(theNewEntry.second);
187
188 theNewEntry.second->resize(theBlockSize, value_type());
189
190 // Set the number of free spaces accordingly...
191 theNewEntry.first = theBlockSize - theCount;
192
193 if (theNewEntry.first != 0)
194 {
195 m_lastEntryFound = &theNewEntry;
196 }
197
198 // Return a pointer to the beginning of the allocated memory...
199 return &*theNewEntry.second->begin();
200 }
201
202 ListEntryType*
203 findEntry(size_type theCount)
204 {
205 // Search for an entry that has some free space.
206
207 if (m_lastEntryFound != 0 && m_lastEntryFound->first >= theCount)
208 {
209 return m_lastEntryFound;
210 }
211 else
212 {
213 const ListIteratorType theEnd = m_list.end();
214 ListIteratorType theCurrent = m_list.begin();
215
216 ListEntryType* theEntry = 0;
217
218 while(theCurrent != theEnd)
219 {
220 // We're looking for the best fit, so
221 // if the free space and the count we're
222 // looking for are equal, that's pretty
223 // much the best we can do...
224 if ((*theCurrent).first == theCount)
225 {
226 theEntry = &*theCurrent;
227
228 break;
229 }
230 else if ((*theCurrent).first >= theCount)
231 {
232 // If we haven't found anything yet, the first
233 // entry we find that's large enough becomes
234 // our best fit.
235 //
236 // Otherwise, we'll assume that a smaller
237 // slot is a better fit, though I may be
238 // wrong about this...
239 if (theEntry == 0 ||
240 (*theCurrent).first < theEntry->first)
241 {
242 // Nope, so this becomes our best-fit so far.
243 theEntry = &*theCurrent;
244 }
245
246 ++theCurrent;
247 }
248 else
249 {
250 // Won't fit, so just continue...
251 ++theCurrent;
252 }
253 }
254
255 m_lastEntryFound = theEntry;
256
257 return theEntry;
258 }
259 }
260
261 // Not implemented...
262 XalanArrayAllocator(const XalanArrayAllocator<Type>& theSource);
263
264 XalanArrayAllocator<Type>&
265 operator=(const XalanArrayAllocator<Type>& theSource);
266
267 bool
268 operator==(const XalanArrayAllocator<Type>& theRHS) const;
269
270
271 // Data members...
272 ListType m_list;
273
274 const size_type m_blockSize;
275
276 ListEntryType* m_lastEntryFound;
277};
278
279
280
281}
282
283
284
285#endif // !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680)
#define XALAN_PLATFORMSUPPORT_EXPORT
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
XalanArrayAllocator(MemoryManager &theManager, size_type theBlockSize=eDefaultBlockSize)
Constructor.
VectorType::size_type size_type
XalanList< ListEntryType > ListType
std::pair< size_type, VectorType * > ListEntryType
void reset()
Reset the instance, but keep all memory so it can be reused for allocations.
Type * allocate(size_type theCount)
Allocate slots for the given number of Types instance and return the address of the slots.
void clear()
Clear the instance, and release all allocated memory.
Xalan implementation of a doubly linked list.
Definition: XalanList.hpp:156
size_t size_type
Definition: XalanMap.hpp:46
bool operator==(const XalanVector< Type > &theLHS, const XalanVector< Type > &theRHS)