Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.8

Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | 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, typename 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.