00001 /* 00002 * The Apache Software License, Version 1.1 00003 * 00004 * 00005 * Copyright (c) 1999-2002 The Apache Software Foundation. All rights 00006 * reserved. 00007 * 00008 * Redistribution and use in source and binary forms, with or without 00009 * modification, are permitted provided that the following conditions 00010 * are met: 00011 * 00012 * 1. Redistributions of source code must retain the above copyright 00013 * notice, this list of conditions and the following disclaimer. 00014 * 00015 * 2. Redistributions in binary form must reproduce the above copyright 00016 * notice, this list of conditions and the following disclaimer in 00017 * the documentation and/or other materials provided with the 00018 * distribution. 00019 * 00020 * 3. The end-user documentation included with the redistribution, 00021 * if any, must include the following acknowledgment: 00022 * "This product includes software developed by the 00023 * Apache Software Foundation (http://www.apache.org/)." 00024 * Alternately, this acknowledgment may appear in the software itself, 00025 * if and wherever such third-party acknowledgments normally appear. 00026 * 00027 * 4. The names "Xalan" and "Apache Software Foundation" must 00028 * not be used to endorse or promote products derived from this 00029 * software without prior written permission. For written 00030 * permission, please contact apache@apache.org. 00031 * 00032 * 5. Products derived from this software may not be called "Apache", 00033 * nor may "Apache" appear in their name, without prior written 00034 * permission of the Apache Software Foundation. 00035 * 00036 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 00037 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00038 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 00039 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 00040 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00041 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00042 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 00043 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 00044 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 00045 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 00046 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00047 * SUCH DAMAGE. 00048 * ==================================================================== 00049 * 00050 * This software consists of voluntary contributions made by many 00051 * individuals on behalf of the Apache Software Foundation and was 00052 * originally based on software copyright (c) 1999, International 00053 * Business Machines, Inc., http://www.ibm.com. For more 00054 * information on the Apache Software Foundation, please see 00055 * <http://www.apache.org/>. 00056 */ 00057 #if !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680) 00058 #define XALANARRAYALLOCATOR_HEADER_GUARD_1357924680 00059 00060 00061 00062 #include <xalanc/PlatformSupport/PlatformSupportDefinitions.hpp> 00063 00064 00065 00066 #include <cassert> 00067 #include <list> 00068 #include <utility> 00069 #include <vector> 00070 00071 00072 00073 XALAN_CPP_NAMESPACE_BEGIN 00074 00075 00076 00077 template<class Type> 00078 class XALAN_PLATFORMSUPPORT_EXPORT XalanArrayAllocator 00079 { 00080 public: 00081 00082 #if defined(XALAN_NO_STD_NAMESPACE) 00083 typedef vector<Type> VectorType; 00084 typedef typename VectorType::size_type size_type; 00085 typedef pair<size_type, VectorType> ListEntryType; 00086 typedef list<ListEntryType> ListType; 00087 #else 00088 typedef std::vector<Type> VectorType; 00089 typedef typename VectorType::size_type size_type; 00090 typedef std::pair<size_type, VectorType> ListEntryType; 00091 typedef std::list<ListEntryType> ListType; 00092 #endif 00093 00094 typedef Type value_type; 00095 00096 typedef typename ListType::iterator ListIteratorType; 00097 00098 // Default size for vector allocation. 00099 enum { eDefaultBlockSize = 500 }; 00100 00106 XalanArrayAllocator(size_type theBlockSize = eDefaultBlockSize) : 00107 m_list(), 00108 m_blockSize(theBlockSize), 00109 m_lastEntryFound(0) 00110 { 00111 } 00112 00113 ~XalanArrayAllocator() 00114 { 00115 } 00116 00120 void 00121 clear() 00122 { 00123 m_list.clear(); 00124 00125 m_lastEntryFound = 0; 00126 } 00127 00133 void 00134 reset() 00135 { 00136 if (m_list.empty() == true) 00137 { 00138 m_lastEntryFound = 0; 00139 } 00140 else 00141 { 00142 const ListIteratorType theEnd = m_list.end(); 00143 ListIteratorType theCurrent = m_list.begin(); 00144 00145 do 00146 { 00147 (*theCurrent).first = (*theCurrent).second.size(); 00148 00149 ++theCurrent; 00150 } while(theCurrent != theEnd); 00151 00152 m_lastEntryFound = &*m_list.begin(); 00153 } 00154 } 00155 00162 Type* 00163 allocate(size_type theCount) 00164 { 00165 // Handle the case of theCount being greater than the block size first... 00166 if (theCount >= m_blockSize) 00167 { 00168 return createEntry(theCount, theCount); 00169 } 00170 else 00171 { 00172 ListEntryType* theEntry = 00173 findEntry(theCount); 00174 00175 // Did we find a slot? 00176 if (theEntry == 0) 00177 { 00178 // Nope, create a new one... 00179 return createEntry(m_blockSize, theCount); 00180 } 00181 else 00182 { 00183 // The address we want is that of the first free element in the 00184 // vector... 00185 Type* const thePointer = 00186 &*theEntry->second.begin() + (theEntry->second.size() - theEntry->first); 00187 00188 // Resize the vector to the appropriate size... 00189 theEntry->first -= theCount; 00190 00191 return thePointer; 00192 } 00193 } 00194 } 00195 00196 private: 00197 00198 // Utility functions... 00199 Type* 00200 createEntry( 00201 size_type theBlockSize, 00202 size_type theCount) 00203 { 00204 assert(theBlockSize >= theCount); 00205 00206 // Push on a new entry. The entry has no open space, 00207 // since it's greater than our block size... 00208 m_list.push_back(ListEntryType(0, VectorType())); 00209 00210 // Get the new entry... 00211 ListEntryType& theNewEntry = m_list.back(); 00212 00213 // Resize the vector to the appropriate size... 00214 theNewEntry.second.resize(theBlockSize, VectorType::value_type(0)); 00215 00216 // Set the number of free spaces accordingly... 00217 theNewEntry.first = theBlockSize - theCount; 00218 00219 if (theNewEntry.first != 0) 00220 { 00221 m_lastEntryFound = &theNewEntry; 00222 } 00223 00224 // Return a pointer to the beginning of the allocated memory... 00225 return &*theNewEntry.second.begin(); 00226 } 00227 00228 ListEntryType* 00229 findEntry(size_type theCount) 00230 { 00231 // Search for an entry that has some free space. 00232 00233 if (m_lastEntryFound != 0 && m_lastEntryFound->first >= theCount) 00234 { 00235 return m_lastEntryFound; 00236 } 00237 else 00238 { 00239 const ListIteratorType theEnd = m_list.end(); 00240 ListIteratorType theCurrent = m_list.begin(); 00241 00242 ListEntryType* theEntry = 0; 00243 00244 while(theCurrent != theEnd) 00245 { 00246 // We're looking for the best fit, so 00247 // if the free space and the count we're 00248 // looking for are equal, that's pretty 00249 // much the best we can do... 00250 if ((*theCurrent).first == theCount) 00251 { 00252 theEntry = &*theCurrent; 00253 00254 break; 00255 } 00256 else if ((*theCurrent).first >= theCount) 00257 { 00258 // If we haven't found anything yet, the first 00259 // entry we find that's large enough becomes 00260 // our best fit. 00261 // 00262 // Otherwise, we'll assume that a smaller 00263 // slot is a better fit, though I may be 00264 // wrong about this... 00265 if (theEntry == 0 || 00266 (*theCurrent).first < theEntry->first) 00267 { 00268 // Nope, so this becomes our best-fit so far. 00269 theEntry = &*theCurrent; 00270 } 00271 00272 ++theCurrent; 00273 } 00274 else 00275 { 00276 // Won't fit, so just continue... 00277 ++theCurrent; 00278 } 00279 } 00280 00281 m_lastEntryFound = theEntry; 00282 00283 return theEntry; 00284 } 00285 } 00286 00287 // Not implemented... 00288 XalanArrayAllocator(const XalanArrayAllocator<Type>& theSource); 00289 00290 XalanArrayAllocator<Type>& 00291 operator=(const XalanArrayAllocator<Type>& theSource); 00292 00293 bool 00294 operator==(const XalanArrayAllocator<Type>& theRHS) const; 00295 00296 00297 // Data members... 00298 ListType m_list; 00299 00300 const size_type m_blockSize; 00301 00302 ListEntryType* m_lastEntryFound; 00303 }; 00304 00305 00306 00307 XALAN_CPP_NAMESPACE_END 00308 00309 00310 00311 #endif // !defined(XALANARRAYALLOCATOR_HEADER_GUARD_1357924680)
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
![]() |
Xalan-C++ XSLT Processor Version 1.6 |
|