## 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.