Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.8

Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

XalanArrayAllocator.hpp

Go to the documentation of this file.
00001 /* 00002 * Copyright 1999-2004 The Apache Software Foundation. 00003 * 00004 * Licensed under the Apache License, Version 2.0 (the "License"); 00005 * you may not use this file except in compliance with the License. 00006 * You may obtain a copy of the License at 00007 * 00008 * http://www.apache.org/licenses/LICENSE-2.0 00009 * 00010 * Unless required by applicable law or agreed to in writing, software 00011 * distributed under the License is distributed on an "AS IS" BASIS, 00012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00013 * See the License for the specific language governing permissions and 00014 * limitations under the License. 00015 */ 00016 #if !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680) 00017 #define XALANARRAYALLOCATOR_HEADER_GUARD_1357924680 00018 00019 00020 00021 #include <xalanc/PlatformSupport/PlatformSupportDefinitions.hpp> 00022 00023 00024 00025 #include <cassert> 00026 #include <list> 00027 #include <utility> 00028 #include <vector> 00029 00030 00031 00032 XALAN_CPP_NAMESPACE_BEGIN 00033 00034 00035 00036 template<class Type> 00037 class XALAN_PLATFORMSUPPORT_EXPORT XalanArrayAllocator 00038 { 00039 public: 00040 00041 #if defined(XALAN_NO_STD_NAMESPACE) 00042 typedef vector<Type> VectorType; 00043 typedef typename VectorType::size_type size_type; 00044 typedef pair<size_type, VectorType> ListEntryType; 00045 typedef list<ListEntryType> ListType; 00046 #else 00047 typedef std::vector<Type> VectorType; 00048 typedef typename VectorType::size_type size_type; 00049 typedef std::pair<size_type, VectorType> ListEntryType; 00050 typedef std::list<ListEntryType> ListType; 00051 #endif 00052 00053 typedef Type value_type; 00054 00055 typedef typename ListType::iterator ListIteratorType; 00056 00057 // Default size for vector allocation. 00058 enum { eDefaultBlockSize = 500 }; 00059 00065 XalanArrayAllocator(size_type theBlockSize = eDefaultBlockSize) : 00066 m_list(), 00067 m_blockSize(theBlockSize), 00068 m_lastEntryFound(0) 00069 { 00070 } 00071 00072 ~XalanArrayAllocator() 00073 { 00074 } 00075 00079 void 00080 clear() 00081 { 00082 m_list.clear(); 00083 00084 m_lastEntryFound = 0; 00085 } 00086 00092 void 00093 reset() 00094 { 00095 if (m_list.empty() == true) 00096 { 00097 m_lastEntryFound = 0; 00098 } 00099 else 00100 { 00101 const ListIteratorType theEnd = m_list.end(); 00102 ListIteratorType theCurrent = m_list.begin(); 00103 00104 do 00105 { 00106 (*theCurrent).first = (*theCurrent).second.size(); 00107 00108 ++theCurrent; 00109 } while(theCurrent != theEnd); 00110 00111 m_lastEntryFound = &*m_list.begin(); 00112 } 00113 } 00114 00121 Type* 00122 allocate(size_type theCount) 00123 { 00124 // Handle the case of theCount being greater than the block size first... 00125 if (theCount >= m_blockSize) 00126 { 00127 return createEntry(theCount, theCount); 00128 } 00129 else 00130 { 00131 ListEntryType* theEntry = 00132 findEntry(theCount); 00133 00134 // Did we find a slot? 00135 if (theEntry == 0) 00136 { 00137 // Nope, create a new one... 00138 return createEntry(m_blockSize, theCount); 00139 } 00140 else 00141 { 00142 // The address we want is that of the first free element in the 00143 // vector... 00144 Type* const thePointer = 00145 &*theEntry->second.begin() + (theEntry->second.size() - theEntry->first); 00146 00147 // Resize the vector to the appropriate size... 00148 theEntry->first -= theCount; 00149 00150 return thePointer; 00151 } 00152 } 00153 } 00154 00155 private: 00156 00157 // Utility functions... 00158 Type* 00159 createEntry( 00160 size_type theBlockSize, 00161 size_type theCount) 00162 { 00163 assert(theBlockSize >= theCount); 00164 00165 // Push on a new entry. The entry has no open space, 00166 // since it's greater than our block size... 00167 m_list.push_back(ListEntryType(0, VectorType())); 00168 00169 // Get the new entry... 00170 ListEntryType& theNewEntry = m_list.back(); 00171 00172 // Resize the vector to the appropriate size... 00173 theNewEntry.second.resize(theBlockSize, VectorType::value_type(0)); 00174 00175 // Set the number of free spaces accordingly... 00176 theNewEntry.first = theBlockSize - theCount; 00177 00178 if (theNewEntry.first != 0) 00179 { 00180 m_lastEntryFound = &theNewEntry; 00181 } 00182 00183 // Return a pointer to the beginning of the allocated memory... 00184 return &*theNewEntry.second.begin(); 00185 } 00186 00187 ListEntryType* 00188 findEntry(size_type theCount) 00189 { 00190 // Search for an entry that has some free space. 00191 00192 if (m_lastEntryFound != 0 && m_lastEntryFound->first >= theCount) 00193 { 00194 return m_lastEntryFound; 00195 } 00196 else 00197 { 00198 const ListIteratorType theEnd = m_list.end(); 00199 ListIteratorType theCurrent = m_list.begin(); 00200 00201 ListEntryType* theEntry = 0; 00202 00203 while(theCurrent != theEnd) 00204 { 00205 // We're looking for the best fit, so 00206 // if the free space and the count we're 00207 // looking for are equal, that's pretty 00208 // much the best we can do... 00209 if ((*theCurrent).first == theCount) 00210 { 00211 theEntry = &*theCurrent; 00212 00213 break; 00214 } 00215 else if ((*theCurrent).first >= theCount) 00216 { 00217 // If we haven't found anything yet, the first 00218 // entry we find that's large enough becomes 00219 // our best fit. 00220 // 00221 // Otherwise, we'll assume that a smaller 00222 // slot is a better fit, though I may be 00223 // wrong about this... 00224 if (theEntry == 0 || 00225 (*theCurrent).first < theEntry->first) 00226 { 00227 // Nope, so this becomes our best-fit so far. 00228 theEntry = &*theCurrent; 00229 } 00230 00231 ++theCurrent; 00232 } 00233 else 00234 { 00235 // Won't fit, so just continue... 00236 ++theCurrent; 00237 } 00238 } 00239 00240 m_lastEntryFound = theEntry; 00241 00242 return theEntry; 00243 } 00244 } 00245 00246 // Not implemented... 00247 XalanArrayAllocator(const XalanArrayAllocator<Type>& theSource); 00248 00249 XalanArrayAllocator<Type>& 00250 operator=(const XalanArrayAllocator<Type>& theSource); 00251 00252 bool 00253 operator==(const XalanArrayAllocator<Type>& theRHS) const; 00254 00255 00256 // Data members... 00257 ListType m_list; 00258 00259 const size_type m_blockSize; 00260 00261 ListEntryType* m_lastEntryFound; 00262 }; 00263 00264 00265 00266 XALAN_CPP_NAMESPACE_END 00267 00268 00269 00270 #endif // !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680)

Interpreting class diagrams

Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.

Xalan-C++ XSLT Processor Version 1.8
Copyright © 1999-2004 The Apache Software Foundation. All Rights Reserved.