## Xalan-C++ API Documentation

### The Xalan C++ XSLT Processor Version 1.10

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

# 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
    00020
    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 XalanDeque<Type, ConstructionTraits>                            ThisType;
    00176     typedef XalanDequeIterator<XalanDequeIteratorTraits<value_type>, ThisType>      iterator;
    00177     typedef XalanDequeIterator<XalanDequeConstIteratorTraits<value_type>, ThisType>     const_iterator;
    00178
    00179 #if defined(XALAN_HAS_STD_ITERATORS)
    00180     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator>          reverse_iterator_;
    00181     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator>    const_reverse_iterator_;
    00182 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
    00183     typedef XALAN_STD_QUALIFIER reverse_iterator<
    00184         iterator,
    00185         XALAN_STD_QUALIFIER random_access_iterator_tag,
    00186         value_type> reverse_iterator_;
    00187     typedef XALAN_STD_QUALIFIER reverse_iterator<
    00188         const_iterator,
    00189         XALAN_STD_QUALIFIER random_access_iterator_tag,
    00190         const value_type> const_reverse_iterator_;
    00191 #else
    00192     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator, value_type>                          reverse_iterator_;
    00193     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator, value_type, const_reference>   const_reverse_iterator_;
    00194 #endif
    00195
    00196     typedef reverse_iterator_           reverse_iterator;
    00197     typedef const_reverse_iterator_     const_reverse_iterator;
    00198
    00199     XalanDeque(
    00200             MemoryManagerType& memoryManager,
    00201             size_type initialSize = 0,
    00202             size_type blockSize = 10) :
    00203         m_memoryManager(&memoryManager),
    00204         m_blockSize(blockSize),
    00205         m_blockIndex(memoryManager,
    00206                     initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)),
    00207         m_freeBlockVector(memoryManager)
    00208     {
    00209         typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager);
    00210
    00211         XALAN_STD_QUALIFIER fill_n(XALAN_STD_QUALIFIER back_inserter(*this), initialSize, defaultValue.value);
    00212     }
    00213
    00214     XalanDeque(const XalanDeque& theRhs, MemoryManagerType& memoryManager) :
    00215         m_memoryManager(&memoryManager),
    00216         m_blockSize(theRhs.m_blockSize),
    00217         m_blockIndex(*theRhs.m_memoryManager,
    00218                     theRhs.size() / theRhs.m_blockSize + (theRhs.size() % theRhs.m_blockSize == 0 ? 0 : 1)),
    00219         m_freeBlockVector(memoryManager)
    00220     {
    00221         XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
    00222     }
    00223
    00224    static XalanDeque*
    00225    create(
    00226             MemoryManagerType&  theManager,
    00227             size_type initialSize = 0,
    00228             size_type blockSize = 10)
    00229     {
    00230         typedef XalanDeque ThisType;
    00231
    00232         XalanMemMgrAutoPtr<ThisType, false> theGuard( theManager , (ThisType*)theManager.allocate(sizeof(ThisType)));
    00233
    00234         ThisType* theResult = theGuard.get();
    00235
    00236         new (theResult) ThisType(theManager, initialSize, blockSize);
    00237
    00238         theGuard.release();
    00239
    00240         return theResult;
    00241     }
    00242
    00243     ~XalanDeque()
    00244     {
    00245         clear();
    00246         typename BlockIndexType::iterator iter = m_freeBlockVector.begin();
    00247
    00248         while (iter != m_freeBlockVector.end())
    00249         {
    00250             (*iter)->~XalanVector<Type, ConstructionTraits>();
    00251             deallocate(*iter);
    00252             ++iter;
    00253         }
    00254     }
    00255
    00256     iterator begin()
    00257     {
    00258         return iterator(this, 0);
    00259     }
    00260
    00261     const_iterator begin() const
    00262     {
    00263         return const_iterator(const_cast<XalanDeque*>(this), 0);
    00264     }
    00265
    00266     iterator end()
    00267     {
    00268         return iterator(this, size());
    00269     }
    00270
    00271     const_iterator end() const
    00272     {
    00273          return const_iterator(const_cast<XalanDeque*>(this), size());
    00274     }
    00275
    00276     const_reverse_iterator rbegin() const
    00277     {
    00278         return const_reverse_iterator(end());
    00279     }
    00280
    00281     const_reverse_iterator rend() const
    00282     {
    00283         return const_reverse_iterator(begin());
    00284     }
    00285
    00286     bool empty() const
    00287     {
    00288         return m_blockIndex.empty();
    00289     }
    00290
    00291     size_type size() const
    00292     {
    00293        if (m_blockIndex.empty())
    00294        {
    00295            return 0;
    00296        }
    00297        else
    00298        {
    00299            return (m_blockIndex.size() - 1) * m_blockSize
    00300                +  m_blockIndex.back()->size();
    00301        }
    00302     }
    00303
    00304     value_type& back()
    00305     {
    00306         return m_blockIndex.back()->back();
    00307     }
    00308
    00309     value_type& operator[](size_type index)
    00310     {
    00311         BlockType & block = *(m_blockIndex[index / m_blockSize]);
    00312         return block[index % m_blockSize];
    00313     }
    00314
    00315     const value_type& operator[](size_type index) const
    00316     {
    00317         BlockType & block = *(m_blockIndex[index / m_blockSize]);
    00318         return block[index % m_blockSize];
    00319     }
    00320
    00321     void clear()
    00322     {
    00323         typename BlockIndexType::iterator iter = m_blockIndex.begin();
    00324
    00325         m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size());
    00326
    00327         while (iter != m_blockIndex.end())
    00328         {
    00329             (*iter)->clear();
    00330             m_freeBlockVector.push_back(*iter);
    00331             ++iter;
    00332         }
    00333
    00334         m_blockIndex.clear();
    00335     }
    00336
    00337     void push_back(const value_type & value)
    00338     {
    00339         if (m_blockIndex.empty() ||
    00340             m_blockIndex.back()->size() >= m_blockSize)
    00341         {
    00342             m_blockIndex.push_back(getNewBlock());
    00343         }
    00344
    00345         m_blockIndex.back()->push_back(value);
    00346     }
    00347
    00348     void pop_back()
    00349     {
    00350         BlockType & lastBlock = *(m_blockIndex.back());
    00351         lastBlock.pop_back();
    00352         if (lastBlock.empty())
    00353         {
    00354             m_freeBlockVector.push_back(&lastBlock);
    00355             m_blockIndex.pop_back();
    00356         }
    00357     }
    00358
    00359     void resize(size_type newSize)
    00360     {
    00361         typename ConstructionTraits::Constructor::ConstructableType defaultValue(*m_memoryManager);
    00362         if (newSize > size())
    00363         {
    00364             for (size_type i = 0; i < newSize - size(); ++i)
    00365             {
    00366                 push_back(defaultValue.value);
    00367             }
    00368         }
    00369         else
    00370         {
    00371             for (size_type i = 0; i < size() - newSize; ++i)
    00372             {
    00373                 pop_back();
    00374             }
    00375         }
    00376     }
    00377
    00378     void swap(XalanDeque& theRhs)
    00379     {
    00380         MemoryManagerType* tempMemoryManager = m_memoryManager;
    00381         m_memoryManager = theRhs.m_memoryManager;
    00382         theRhs.m_memoryManager = tempMemoryManager;
    00383
    00384         theRhs.m_blockIndex.swap(m_blockIndex);
    00385         theRhs.m_freeBlockVector.swap(m_freeBlockVector);
    00386     }
    00387
    00388     XalanDeque & operator=(const XalanDeque & theRhs)
    00389     {
    00390         clear();
    00391         XALAN_STD_QUALIFIER copy(theRhs.begin(), theRhs.end(), XALAN_STD_QUALIFIER back_inserter(*this));
    00392         return *this;
    00393     }
    00394
    00395     MemoryManagerType&
    00396     getMemoryManager()
    00397     {
    00398         assert (m_memoryManager != 0);
    00399
    00400         return *m_memoryManager;
    00401     }
    00402 protected:
    00403
    00404     BlockType* getNewBlock()
    00405     {
    00406         BlockType * newBlock;
    00407
    00408         if (m_freeBlockVector.empty())
    00409         {
    00410             newBlock = allocate(1);
    00411             new (&*newBlock) BlockType(*m_memoryManager, m_blockSize);
    00412         }
    00413         else
    00414         {
    00415             newBlock = m_freeBlockVector.back();
    00416             m_freeBlockVector.pop_back();
    00417         }
    00418
    00419         assert (newBlock != 0);
    00420
    00421         return newBlock;
    00422     }
    00423
    00424     BlockType*
    00425     allocate(size_type  size)
    00426     {
    00427         const size_type     theBytesNeeded = size * sizeof(BlockType);
    00428
    00429         BlockType* pointer = (BlockType*)m_memoryManager->allocate(theBytesNeeded);
    00430
    00431         assert(pointer != 0);
    00432
    00433         return pointer;
    00434      }
    00435
    00436     void
    00437     deallocate(BlockType*  pointer)
    00438     {
    00439         m_memoryManager->deallocate(pointer);
    00440     }
    00441
    00442     MemoryManagerType*  m_memoryManager;
    00443     const size_type     m_blockSize;
    00444
    00445     BlockIndexType     m_blockIndex;
    00446     BlockIndexType     m_freeBlockVector;
    00447
    00448 private:
    00449     // Not implemented
    00450     XalanDeque();
    00451     XalanDeque(const XalanDeque&);
    00452
    00453 };
    00454
    00455
    00456
    00457 XALAN_CPP_NAMESPACE_END
    00458
    00459
    00460
    00461 #endif  // XALANDEQUE_HEADER_GUARD_1357924680
    00462

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