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 
37 namespace XALAN_CPP_NAMESPACE {
38 
39 
40 
41 template<class Type>
43 {
44 public:
45 
47  typedef typename VectorType::size_type size_type;
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*
134  allocate(size_type theCount)
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 
168 private:
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)
xalanc::XalanArrayAllocator::allocate
Type * allocate(size_type theCount)
Allocate slots for the given number of Types instance and return the address of the slots.
Definition: XalanArrayAllocator.hpp:134
XALAN_CPP_NAMESPACE
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
Definition: XalanVersion.hpp:76
xalanc::XalanVector
Definition: XalanVector.hpp:58
XalanList.hpp
xalanc::size_type
size_t size_type
Definition: XalanMap.hpp:46
XalanVector.hpp
xalanc::operator==
bool operator==(const XalanVector< Type > &theLHS, const XalanVector< Type > &theRHS)
Definition: XalanVector.hpp:1118
xalanc::XalanArrayAllocator::reset
void reset()
Reset the instance, but keep all memory so it can be reused for allocations.
Definition: XalanArrayAllocator.hpp:105
xalanc::XalanArrayAllocator
Definition: XalanArrayAllocator.hpp:42
XALAN_PLATFORMSUPPORT_EXPORT
#define XALAN_PLATFORMSUPPORT_EXPORT
Definition: PlatformSupportDefinitions.hpp:35
PlatformSupportDefinitions.hpp
xalanc::XalanArrayAllocator::ListEntryType
std::pair< size_type, VectorType * > ListEntryType
Definition: XalanArrayAllocator.hpp:49
xalanc::XalanArrayAllocator::VectorType
XalanVector< Type > VectorType
Definition: XalanArrayAllocator.hpp:46
xalanc::XalanArrayAllocator::ListIteratorType
ListType::iterator ListIteratorType
Definition: XalanArrayAllocator.hpp:54
xalanc::XalanArrayAllocator::XalanArrayAllocator
XalanArrayAllocator(MemoryManager &theManager, size_type theBlockSize=eDefaultBlockSize)
Constructor.
Definition: XalanArrayAllocator.hpp:64
xalanc::XalanListIteratorBase
Definition: XalanList.hpp:63
xalanc::XalanArrayAllocator::ListType
XalanList< ListEntryType > ListType
Definition: XalanArrayAllocator.hpp:50
xalanc::XalanArrayAllocator::clear
void clear()
Clear the instance, and release all allocated memory.
Definition: XalanArrayAllocator.hpp:92
xalanc::XalanArrayAllocator::size_type
VectorType::size_type size_type
Definition: XalanArrayAllocator.hpp:47
xalanc::XalanArrayAllocator::value_type
Type value_type
Definition: XalanArrayAllocator.hpp:52
xalanc::XalanList< ListEntryType >
xalanc::XalanVector< XalanDOMChar >::size_type
size_t size_type
Definition: XalanVector.hpp:68
xalanc::XalanArrayAllocator::~XalanArrayAllocator
~XalanArrayAllocator()
Definition: XalanArrayAllocator.hpp:72