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

# XalanList.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(XALANLIST_HEADER_GUARD_1357924680)
    00022 #define XALANLIST_HEADER_GUARD_1357924680
    00023
    00024
    00025
    00026 // Base include file.  Must be first.
    00027 #include <xalanc/Include/PlatformDefinitions.hpp>
    00028
    00029
    00030
    00031 #include <cstddef>
    00032 #include <algorithm>
    00033 #include <cassert>
    00034 #include <new>
    00035 #include <iterator>
    00036 #include <stdexcept>
    00037
    00038
    00039
    00040 #include <xalanc/Include/XalanMemoryManagement.hpp>
    00041
    00042
    00043
    00044 XALAN_CPP_NAMESPACE_BEGIN
    00045
    00046
    00047
    00048 template <class Value>
    00049 struct XalanListIteratorTraits
    00050 {
    00051     typedef Value   value_type;
    00052     typedef Value&  reference;
    00053     typedef Value*  pointer;
    00054 };
    00055
    00056 template <class Value>
    00057 struct XalanListConstIteratorTraits
    00058 {
    00059     typedef Value   value_type;
    00060     typedef const   Value&  reference;
    00061     typedef const   Value*  pointer;
    00062 };
    00063
    00064 template<class XalanListTraits, class Node>
    00065 struct XalanListIteratorBase
    00066 {
    00067     typedef typename XalanListTraits::value_type    value_type;
    00068     typedef typename XalanListTraits::reference     reference;
    00069     typedef typename XalanListTraits::pointer       pointer;
    00070
    00071     typedef ptrdiff_t       difference_type;
    00072
    00073     typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category;
    00074
    00075     typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node> iterator;
    00076
    00077     XalanListIteratorBase(Node& node) :
    00078         currentNode(&node)
    00079     {
    00080     }
    00081
    00082     XalanListIteratorBase(const iterator& theRhs) :
    00083         currentNode(theRhs.currentNode)
    00084     {
    00085     }
    00086
    00087     XalanListIteratorBase operator++()
    00088     {
    00089         currentNode = currentNode->next;
    00090         return *this;
    00091     }
    00092
    00093     XalanListIteratorBase operator++(int)
    00094     {
    00095         Node& origNode = *currentNode;
    00096         currentNode = currentNode->next;
    00097         return XalanListIteratorBase(origNode);
    00098     }
    00099
    00100     XalanListIteratorBase operator--()
    00101     {
    00102         currentNode = currentNode->prev;
    00103         return *this;
    00104     }
    00105
    00106     XalanListIteratorBase operator-(difference_type decrement) const
    00107     {
    00108         Node* node = currentNode;
    00109         while (decrement > 0)
    00110         {
    00111             node = node->prev;
    00112             --decrement;
    00113         };
    00114         return XalanListIteratorBase(*node);
    00115     }
    00116
    00117     reference operator*() const
    00118     {
    00119         return currentNode->value;
    00120     }
    00121
    00122     pointer operator->() const
    00123     {
    00124         return &currentNode->value;
    00125     }
    00126
    00127     const XalanListIteratorBase & operator=(const XalanListIteratorBase& theRhs)
    00128     {
    00129         currentNode = theRhs.currentNode;
    00130         return *this;
    00131     }
    00132
    00133     bool operator!=(const XalanListIteratorBase& theRhs) const
    00134     {
    00135         return !operator==(theRhs);
    00136     }
    00137
    00138     bool operator==(const XalanListIteratorBase& theRhs) const
    00139     {
    00140         return currentNode == theRhs.currentNode;
    00141     }
    00142
    00143     Node& node()
    00144     {
    00145         return *currentNode;
    00146     }
    00147
    00148     Node*   currentNode;
    00149 };
    00150
    00151
    00152
    00156 template <class Type>
    00157 class XalanList
    00158 {
    00159 public:
    00160
    00161
    00162     typedef Type                value_type;
    00163     typedef value_type*         pointer;
    00164     typedef const value_type*   const_pointer;
    00165     typedef value_type&         reference;
    00166     typedef const value_type&   const_reference;
    00167     typedef size_t              size_type;
    00168
    00169     typedef XalanList<value_type>     ThisType;
    00170
    00171     struct Node
    00172     {
    00173         Node(
    00174                 const value_type & theValue,
    00175                 Node& prevNode,
    00176                 Node& nextNode) :
    00177             value(theValue),
    00178             prev(&prevNode),
    00179             next(&nextNode)
    00180         {
    00181         }
    00182
    00183         value_type  value;
    00184         Node*       prev;
    00185         Node*       next;
    00186     };
    00187
    00188     typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node>        iterator;
    00189
    00190     typedef XalanListIteratorBase<XalanListConstIteratorTraits<value_type>, Node>   const_iterator;
    00191
    00192 #if defined(XALAN_HAS_STD_ITERATORS)
    00193     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator>  reverse_iterator_;
    00194     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator>    const_reverse_iterator_;
    00195 #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC)
    00196     typedef XALAN_STD_QUALIFIER reverse_iterator<
    00197         iterator,
    00198         XALAN_STD_QUALIFIER bidirectional_iterator_tag,
    00199         value_type> reverse_iterator_;
    00200     typedef XALAN_STD_QUALIFIER reverse_iterator<
    00201         const_iterator,
    00202         XALAN_STD_QUALIFIER bidirectional_iterator_tag,
    00203         const value_type> const_reverse_iterator_;
    00204 #else
    00205     typedef XALAN_STD_QUALIFIER reverse_iterator<iterator, value_type>                          reverse_iterator_;
    00206     typedef XALAN_STD_QUALIFIER reverse_iterator<const_iterator, value_type, const_reference>   const_reverse_iterator_;
    00207 #endif
    00208
    00209     typedef reverse_iterator_           reverse_iterator;
    00210     typedef const_reverse_iterator_     const_reverse_iterator;
    00211
    00212     typedef typename MemoryManagedConstructionTraits<value_type>::Constructor Constructor;
    00213
    00214     XalanList(
    00215             MemoryManagerType&  theManager) :
    00216         m_memoryManager(&theManager),
    00217         m_listHead(0),
    00218         m_freeListHeadPtr(0)
    00219     {
    00220     }
    00221
    00222     ~XalanList()
    00223     {
    00224         if (m_listHead != 0)
    00225         {
    00226             iterator pos = begin();
    00227             while (pos != end())
    00228             {
    00229                 destroyNode(pos++.node());
    00230             }
    00231
    00232             Node * freeNode = m_freeListHeadPtr;
    00233             while (freeNode != 0)
    00234             {
    00235                 Node * nextNode = freeNode->next;
    00236                 deallocate(freeNode);
    00237                 freeNode = nextNode;
    00238             }
    00239
    00240             deallocate(m_listHead);
    00241         }
    00242     }
    00243
    00244     MemoryManagerType&
    00245     getMemoryManager()
    00246     {
    00247         assert(m_memoryManager != 0 );
    00248
    00249         return *m_memoryManager;
    00250     }
    00251
    00252     const MemoryManagerType&
    00253     getMemoryManager() const
    00254     {
    00255         assert(m_memoryManager != 0 );
    00256
    00257         return *m_memoryManager;
    00258     }
    00259
    00260     iterator
    00261     begin()
    00262     {
    00263         return iterator(*(getListHead().next));
    00264     }
    00265
    00266     const_iterator
    00267     begin() const
    00268     {
    00269         return const_iterator(*(getListHead().next));
    00270     }
    00271
    00272     iterator
    00273     end()
    00274     {
    00275         return iterator(getListHead());
    00276     }
    00277
    00278     const_iterator
    00279     end() const
    00280     {
    00281         return const_iterator(getListHead());
    00282     }
    00283
    00284     reverse_iterator
    00285     rbegin()
    00286     {
    00287         return reverse_iterator(end());
    00288     }
    00289
    00290     const_reverse_iterator
    00291     rbegin() const
    00292     {
    00293         return const_reverse_iterator(end());
    00294     }
    00295
    00296     reverse_iterator
    00297     rend()
    00298     {
    00299         return reverse_iterator(begin());
    00300     }
    00301
    00302     const_reverse_iterator
    00303     rend() const
    00304     {
    00305         return const_reverse_iterator(begin());
    00306     }
    00307
    00308     reference
    00309     front()
    00310     {
    00311         return *begin();
    00312     }
    00313
    00314     reference
    00315     back()
    00316     {
    00317         return *(--end());
    00318     }
    00319
    00320     size_type
    00321     size() const
    00322     {
    00323         size_type size = 0;
    00324         const_iterator item = begin();
    00325         while (item != end())
    00326         {
    00327             ++size;
    00328             ++item;
    00329         }
    00330         return size;
    00331     }
    00332
    00333     bool
    00334     empty() const
    00335     {
    00336         return (begin() == end()) != 0;
    00337     }
    00338
    00339     void
    00340     push_back(const value_type&     data)
    00341     {
    00342         constructNode(data, end());
    00343     }
    00344
    00345     void
    00346     push_front(const value_type&    data)
    00347     {
    00348         constructNode(data, begin());
    00349     }
    00350
    00351     void
    00352     pop_front()
    00353     {
    00354         erase(begin());
    00355     }
    00356
    00357     void
    00358     pop_back()
    00359     {
    00360         erase(--end());
    00361     }
    00362
    00363     iterator
    00364     insert(const iterator& pos, const value_type& value)
    00365     {
    00366         return iterator(constructNode(value,pos));
    00367     }
    00368
    00369     void
    00370     erase(iterator pos)
    00371     {
    00372         assert(pos != end());
    00373         freeNode(pos.node());
    00374     }
    00375
    00376     void
    00377     splice(
    00378             iterator    pos,
    00379 #if defined(NDEBUG)
    00380             ThisType&   /* list */,
    00381 #else
    00382             ThisType&   list,
    00383 #endif
    00384             iterator    toInsert)
    00385     {
    00386         assert(m_memoryManager == list.m_memoryManager);
    00387
    00388         if (pos != toInsert)
    00389         {
    00390             Node & posNode = pos.node();
    00391             Node & toInsertNode = toInsert.node();
    00392
    00393             toInsertNode.prev->next = toInsertNode.next;
    00394             toInsertNode.next->prev = toInsertNode.prev;
    00395
    00396             toInsertNode.prev = posNode.prev;
    00397             toInsertNode.next = &posNode;
    00398
    00399             posNode.prev->next = &toInsertNode;
    00400             posNode.prev = &toInsertNode;
    00401         }
    00402     }
    00403
    00404     void
    00405     splice(
    00406             iterator    pos,
    00407 #if defined(NDEBUG)
    00408             ThisType&   /* list */,
    00409 #else
    00410             ThisType&   list,
    00411 #endif
    00412             iterator    toInsertFirst,
    00413             iterator    toInsertLast)
    00414     {
    00415         assert(m_memoryManager == list.m_memoryManager);
    00416
    00417         if (toInsertFirst != toInsertLast)
    00418         {
    00419             Node & posNode = pos.node();
    00420             Node & toInsertFirstNode = toInsertFirst.node();
    00421             Node & toInsertLastNode = *(toInsertLast.node().prev);
    00422
    00423             toInsertFirstNode.prev->next = toInsertLastNode.next;
    00424             toInsertLastNode.next->prev = toInsertFirstNode.prev;
    00425
    00426             toInsertFirstNode.prev = posNode.prev;
    00427             toInsertLastNode.next = &posNode;
    00428
    00429             posNode.prev->next = &toInsertFirstNode;
    00430             posNode.prev = &toInsertLastNode;
    00431         }
    00432     }
    00433
    00434     void
    00435     clear()
    00436     {
    00437         iterator pos = begin();
    00438         while (pos != end())
    00439         {
    00440             freeNode(pos++.node());
    00441         }
    00442     }
    00443
    00444     void swap(ThisType& theRHS)
    00445     {
    00446     #if defined(XALAN_NO_STD_NAMESPACE)
    00447         ::swap(m_memoryManager, theRHS.m_memoryManager);
    00448         ::swap(m_listHead, theRHS.m_listHead);
    00449         ::swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr);
    00450     #else
    00451         XALAN_STD_QUALIFIER swap(m_memoryManager, theRHS.m_memoryManager);
    00452         XALAN_STD_QUALIFIER swap(m_listHead, theRHS.m_listHead);
    00453         XALAN_STD_QUALIFIER swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr);
    00454     #endif
    00455     }
    00456
    00457
    00458 protected:
    00459
    00460     Node& constructNode(const value_type& data, iterator pos)
    00461     {
    00462         Node * newNode = 0;
    00463         Node * nextFreeNode = 0;
    00464
    00465         if (m_freeListHeadPtr != 0)
    00466         {
    00467             newNode = m_freeListHeadPtr;
    00468             nextFreeNode = m_freeListHeadPtr->next;
    00469         }
    00470         else
    00471         {
    00472            m_freeListHeadPtr = allocate(1);
    00473            newNode = m_freeListHeadPtr;
    00474         }
    00475
    00476         Constructor::construct(&newNode->value, data, *m_memoryManager);
    00477         new (&newNode->prev) Node*(pos.node().prev);
    00478         new (&newNode->next) Node*(&(pos.node()));
    00479
    00480         pos.node().prev->next = newNode;
    00481         pos.node().prev = newNode;
    00482
    00483         m_freeListHeadPtr = nextFreeNode;
    00484
    00485         return *newNode;
    00486     }
    00487
    00488     void freeNode(Node& node)
    00489     {
    00490         node.prev->next = node.next;
    00491         node.next->prev = node.prev;
    00492
    00493         node.~Node();
    00494         node.prev = 0;
    00495         node.next = m_freeListHeadPtr;
    00496         m_freeListHeadPtr = &node;
    00497     }
    00498
    00499     void destroyNode(Node& node)
    00500     {
    00501         assert(&node != m_listHead);
    00502         node.~Node();
    00503         deallocate(&node);
    00504     }
    00505
    00506     Node& getListHead()
    00507     {
    00508         if (0 == m_listHead)
    00509         {
    00510             m_listHead = allocate(1);
    00511             m_listHead->next = m_listHead;
    00512             m_listHead->prev = m_listHead;
    00513         }
    00514
    00515         return *m_listHead;
    00516     }
    00517
    00518     Node& getListHead() const
    00519     {
    00520         return const_cast<XalanList*>(this)->getListHead();
    00521     }
    00522
    00523     Node*
    00524     allocate(size_type  size)
    00525     {
    00526         const size_type     theBytesNeeded = size * sizeof(Node);
    00527
    00528         assert(m_memoryManager != 0);
    00529
    00530         void* pointer = m_memoryManager->allocate(theBytesNeeded);
    00531
    00532         assert( pointer != 0 );
    00533
    00534         return (Node*) pointer;
    00535     }
    00536
    00537
    00538     void
    00539     deallocate(Node*  pointer)
    00540     {
    00541         assert(m_memoryManager != 0);
    00542
    00543         m_memoryManager->deallocate(pointer);
    00544     }
    00545
    00546     MemoryManagerType * m_memoryManager;
    00547
    00548     Node*               m_listHead;
    00549
    00550     Node*               m_freeListHeadPtr;
    00551
    00552 private:
    00553     // not defined
    00554     XalanList();
    00555     XalanList(const XalanList& theRhs);
    00556
    00557     XalanList& operator=(const XalanList& theRhs);
    00558
    00559 };
    00560
    00561
    00562
    00563 XALAN_CPP_NAMESPACE_END
    00564
    00565 #endif  // XALANLIST_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.9 Copyright © 1999-2004 The Apache Software Foundation. All Rights Reserved.