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  

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

dot

Xalan-C++ XSLT Processor Version 1.10
Copyright © 1999-2004 The Apache Software Foundation. All Rights Reserved.

Apache Logo