Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.6

Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

XalanArrayAllocator.hpp

Go to the documentation of this file.
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)

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.6
Copyright © 2000, 2001, 2002, 2003 The Apache Software Foundation. All Rights Reserved.