Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.9

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

XalanDeque.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 
00021 #if !defined(XALANDEQUE_HEADER_GUARD_1357924680)
00022 #define XALANDEQUE_HEADER_GUARD_1357924680
00023 
00024 
00025 
00026 // Base include file.  Must be first.
00027 #include <xalanc/Include/PlatformDefinitions.hpp>
00028 
00029 
00030 
00031 #include <xalanc/Include/XalanVector.hpp>
00032 #include <xalanc/Include/XalanMemoryManagement.hpp> 
00033 
00034 
00035 
00036 XALAN_CPP_NAMESPACE_BEGIN
00037 
00038 
00039 
00040 template <class Value>
00041 struct XalanDequeIteratorTraits
00042 {
00043     typedef Value           value_type;
00044     typedef Value&          reference;
00045     typedef Value*          pointer;
00046     typedef const Value&    const_reference;
00047 };
00048 
00049 template <class Value>
00050 struct XalanDequeConstIteratorTraits
00051 {
00052     typedef Value           value_type;
00053     typedef const Value&    reference;
00054     typedef const Value*    pointer;
00055     typedef const Value&    const_reference;
00056 };
00057 
00058 template <class XalanDequeTraits, class XalanDeque>
00059 struct  XalanDequeIterator
00060 {
00061     typedef size_t  size_type;
00062     typedef typename XalanDequeTraits::value_type       value_type;
00063     typedef typename XalanDequeTraits::reference        reference;
00064     typedef typename XalanDequeTraits::pointer          pointer;
00065     typedef typename XalanDequeTraits::const_reference  const_reference;
00066     typedef ptrdiff_t                                   difference_type;
00067 
00068     typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> Iterator;
00069 
00070     typedef XALAN_STD_QUALIFIER random_access_iterator_tag iterator_category;
00071 
00072     XalanDequeIterator(XalanDeque*  deque,
00073                        size_type    pos) :
00074         m_deque(deque),
00075         m_pos(pos)
00076     {
00077     }
00078 
00079     XalanDequeIterator(const Iterator & iterator) :
00080         m_deque(iterator.m_deque),
00081         m_pos(iterator.m_pos)
00082     {
00083     }
00084 
00085     XalanDequeIterator& operator=(const Iterator & iterator)
00086     {
00087         m_deque = iterator.m_deque;
00088         m_pos = iterator.m_pos;
00089         return *this;
00090     }
00091 
00092     XalanDequeIterator& operator++()
00093     {
00094         ++m_pos;
00095         return *this;
00096     }
00097 
00098     XalanDequeIterator operator++(int)
00099     {
00100         XalanDequeIterator temp = *this;
00101         ++m_pos;
00102         return temp;
00103     }
00104 
00105     XalanDequeIterator& operator--()
00106     {   
00107         --m_pos;
00108         return *this;
00109     }
00110 
00111     pointer operator->()
00112     {
00113         return &(*m_deque[m_pos]);
00114     }
00115 
00116     reference operator*()
00117     {
00118         return (*m_deque)[m_pos];
00119     }
00120 
00121     const_reference operator*() const
00122     {
00123         return (*m_deque)[m_pos];
00124     }
00125 
00126     XalanDequeIterator operator+(difference_type difference) const
00127     {
00128         return XalanDequeIterator(m_deque, m_pos + difference);
00129     }
00130 
00131     XalanDequeIterator operator-(difference_type difference) const
00132     {
00133         return XalanDequeIterator(m_deque, m_pos - difference);
00134     }
00135 
00136     difference_type operator-(const XalanDequeIterator &theRhs) const
00137     {
00138         return m_pos - theRhs.m_pos;
00139     }
00140 
00141     bool operator==(const XalanDequeIterator & theRhs) const
00142     {
00143         return (theRhs.m_deque == m_deque)
00144             &&  theRhs.m_pos == m_pos;
00145     }
00146 
00147     bool operator!=(const XalanDequeIterator & theRhs) const
00148     {
00149         return !(theRhs == *this);
00150     }
00151 
00152     XalanDeque* m_deque;
00153     size_type   m_pos;
00154 };
00155 
00159 template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> >
00160 class XalanDeque
00161 {
00162 public:
00163 
00164  
00165     typedef size_t  size_type;
00166 
00167     typedef Type            value_type;
00168     typedef Type&           reference;
00169     typedef const Type&     const_reference;
00170 
00171     typedef XalanVector<Type, ConstructionTraits>       BlockType;
00172 
00173     typedef XalanVector<BlockType*> BlockIndexType;
00174 
00175     typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, XalanDeque> iterator;
00176     typedef XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, XalanDeque> const_iterator;
00177 
00178 #if defined(XALAN_HAS_STD_ITERATORS)
00179     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator>          reverse_iterator_;
00180     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator>    const_reverse_iterator_;
00181 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
00182     typedef XALAN_STD_QUALIFIER reverse_iterator<
00183         iterator,
00184         XALAN_STD_QUALIFIER random_access_iterator_tag,
00185         value_type> reverse_iterator_;
00186     typedef XALAN_STD_QUALIFIER reverse_iterator<
00187         const_iterator,
00188         XALAN_STD_QUALIFIER random_access_iterator_tag,
00189         const value_type> const_reverse_iterator_;
00190 #else
00191     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator, value_type>                          reverse_iterator_;
00192     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator, value_type, const_reference>   const_reverse_iterator_;
00193 #endif
00194 
00195     typedef reverse_iterator_           reverse_iterator;
00196     typedef const_reverse_iterator_     const_reverse_iterator;
00197 
00198     XalanDeque(
00199             MemoryManagerType& memoryManager,
00200             size_type initialSize = 0,
00201             size_type blockSize = 10) :
00202         m_memoryManager(&memoryManager),
00203         m_blockSize(blockSize),
00204         m_blockIndex(memoryManager,
00205                     initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)),                    
00206         m_freeBlockVector(memoryManager)
00207     {
00208         typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager);
00209 
00210         XALAN_STD_QUALIFIER fill_n(XALAN_STD_QUALIFIER back_inserter(*this), initialSize, defaultValue.value);
00211     }
00212 
00213     XalanDeque(const XalanDeque& theRhs, MemoryManagerType& memoryManager) :
00214         m_memoryManager(&memoryManager),
00215         m_blockSize(theRhs.m_blockSize),
00216         m_blockIndex(*theRhs.m_memoryManager,
00217                     theRhs.size() / theRhs.m_blockSize + (theRhs.size() % theRhs.m_blockSize == 0 ? 0 : 1)),
00218         m_freeBlockVector(memoryManager)
00219     {
00220         XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
00221     }
00222     
00223    static XalanDeque*
00224    create(
00225             MemoryManagerType&  theManager,
00226             size_type initialSize = 0,
00227             size_type blockSize = 10)
00228     {
00229         typedef XalanDeque ThisType;
00230 
00231         XalanMemMgrAutoPtr<ThisType, false> theGuard( theManager , (ThisType*)theManager.allocate(sizeof(ThisType)));
00232 
00233         ThisType* theResult = theGuard.get();
00234 
00235         new (theResult) ThisType(theManager, initialSize, blockSize);
00236 
00237         theGuard.release();
00238 
00239         return theResult;
00240     }
00241      
00242     ~XalanDeque()
00243     {
00244         clear();
00245         typename BlockIndexType::iterator iter = m_freeBlockVector.begin();
00246 
00247         while (iter != m_freeBlockVector.end())
00248         {
00249             (*iter)->~XalanVector<Type, ConstructionTraits>();
00250             deallocate(*iter);
00251             ++iter;
00252         }
00253     }
00254 
00255     iterator begin()
00256     {
00257         return iterator(this, 0);
00258     }
00259 
00260     const_iterator begin() const
00261     {
00262         return const_iterator(const_cast<XalanDeque*>(this), 0);
00263     }
00264 
00265     iterator end()
00266     {
00267         return iterator(this, size());
00268     }
00269 
00270     const_iterator end() const
00271     {
00272          return const_iterator(const_cast<XalanDeque*>(this), size());
00273     }
00274 
00275     const_reverse_iterator rbegin() const
00276     {
00277         return const_reverse_iterator(end());
00278     }
00279 
00280     const_reverse_iterator rend() const
00281     {
00282         return const_reverse_iterator(begin());
00283     }
00284 
00285     bool empty() const
00286     {
00287         return m_blockIndex.empty();
00288     }
00289 
00290     size_type size() const
00291     {
00292        if (m_blockIndex.empty())
00293        {
00294            return 0;
00295        }
00296        else
00297        {
00298            return (m_blockIndex.size() - 1) * m_blockSize
00299                +  m_blockIndex.back()->size();
00300        }
00301     }
00302 
00303     value_type& back()
00304     {
00305         return m_blockIndex.back()->back();
00306     }
00307 
00308     value_type& operator[](size_type index)
00309     {
00310         BlockType & block = *(m_blockIndex[index / m_blockSize]);
00311         return block[index % m_blockSize];
00312     }
00313 
00314     const value_type& operator[](size_type index) const
00315     {
00316         BlockType & block = *(m_blockIndex[index / m_blockSize]);
00317         return block[index % m_blockSize];
00318     }
00319 
00320     void clear()
00321     {
00322         typename BlockIndexType::iterator iter = m_blockIndex.begin();
00323 
00324         m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size());
00325 
00326         while (iter != m_blockIndex.end())
00327         {
00328             (*iter)->clear();
00329             m_freeBlockVector.push_back(*iter);
00330             ++iter;
00331         }
00332         
00333         m_blockIndex.clear();
00334     }
00335 
00336     void push_back(const value_type & value)
00337     {
00338         if (m_blockIndex.empty() ||
00339             m_blockIndex.back()->size() >= m_blockSize)
00340         {
00341             m_blockIndex.push_back(getNewBlock());
00342         }
00343 
00344         m_blockIndex.back()->push_back(value);
00345     }
00346 
00347     void pop_back()
00348     {
00349         BlockType & lastBlock = *(m_blockIndex.back());
00350         lastBlock.pop_back();
00351         if (lastBlock.empty())
00352         {
00353             m_freeBlockVector.push_back(&lastBlock);
00354             m_blockIndex.pop_back();
00355         }
00356     }
00357 
00358     void resize(size_type newSize)
00359     {
00360         typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager);
00361         if (newSize > size())
00362         {
00363             for (size_type i = 0; i < newSize - size(); ++i)
00364             {
00365                 push_back(defaultValue.value);
00366             }
00367         }
00368         else
00369         {
00370             for (size_type i = 0; i < size() - newSize; ++i)
00371             {
00372                 pop_back();
00373             }
00374         }
00375     }
00376 
00377     void swap(XalanDeque& theRhs)
00378     {
00379         MemoryManagerType* tempMemoryManager = m_memoryManager;
00380         m_memoryManager = theRhs.m_memoryManager;
00381         theRhs.m_memoryManager = tempMemoryManager;
00382 
00383         theRhs.m_blockIndex.swap(m_blockIndex);
00384         theRhs.m_freeBlockVector.swap(m_freeBlockVector);
00385     }
00386 
00387     XalanDeque & operator=(const XalanDeque & theRhs) 
00388     {
00389         clear();
00390         XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
00391         return *this;
00392     }
00393 
00394     MemoryManagerType&
00395     getMemoryManager()
00396     {
00397         assert (m_memoryManager != 0);
00398 
00399         return *m_memoryManager;
00400     }
00401 protected:
00402 
00403     BlockType* getNewBlock()
00404     {
00405         BlockType * newBlock;
00406 
00407         if (m_freeBlockVector.empty())
00408         {
00409             newBlock = allocate(1);
00410             new (&*newBlock) BlockType(*m_memoryManager, m_blockSize);
00411         }
00412         else
00413         {
00414             newBlock = m_freeBlockVector.back();
00415             m_freeBlockVector.pop_back();
00416         }
00417 
00418         assert (newBlock != 0);
00419 
00420         return newBlock;
00421     }
00422 
00423     BlockType*
00424     allocate(size_type  size)
00425     {
00426         const size_type     theBytesNeeded = size * sizeof(BlockType);
00427 
00428         BlockType* pointer = (BlockType*)m_memoryManager->allocate(theBytesNeeded);
00429         
00430         assert(pointer != 0);
00431         
00432         return pointer;
00433      }
00434 
00435     void
00436     deallocate(BlockType*  pointer)
00437     {
00438         m_memoryManager->deallocate(pointer);
00439     }
00440 
00441     MemoryManagerType*  m_memoryManager;
00442     const size_type     m_blockSize;
00443 
00444     BlockIndexType     m_blockIndex; 
00445     BlockIndexType     m_freeBlockVector;
00446     
00447 private:
00448     // Not implemented
00449     XalanDeque();
00450     XalanDeque(const XalanDeque&);
00451     
00452 };
00453 
00454 
00455 
00456 XALAN_CPP_NAMESPACE_END
00457 
00458 
00459 
00460 #endif  // XALANDEQUE_HEADER_GUARD_1357924680
00461 

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.9
Copyright © 1999-2004 The Apache Software Foundation. All Rights Reserved.