| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #if !defined(XALANLIST_HEADER_GUARD_1357924680) |
| #define XALANLIST_HEADER_GUARD_1357924680 |
| |
| |
| |
| // Base include file. Must be first. |
| #include <xalanc/Include/PlatformDefinitions.hpp> |
| |
| |
| |
| #include <cstddef> |
| #include <algorithm> |
| #include <cassert> |
| #include <new> |
| #include <iterator> |
| #include <stdexcept> |
| |
| |
| |
| #include <xalanc/Include/XalanMemoryManagement.hpp> |
| |
| |
| |
| namespace XALAN_CPP_NAMESPACE { |
| |
| |
| |
| template <class Value> |
| struct XalanListIteratorTraits |
| { |
| typedef Value value_type; |
| typedef Value& reference; |
| typedef Value* pointer; |
| }; |
| |
| template <class Value> |
| struct XalanListConstIteratorTraits |
| { |
| typedef Value value_type; |
| typedef const Value& reference; |
| typedef const Value* pointer; |
| }; |
| |
| template<class XalanListTraits, class Node> |
| struct XalanListIteratorBase |
| { |
| typedef typename XalanListTraits::value_type value_type; |
| typedef typename XalanListTraits::reference reference; |
| typedef typename XalanListTraits::pointer pointer; |
| |
| typedef ptrdiff_t difference_type; |
| |
| typedef std::bidirectional_iterator_tag iterator_category; |
| |
| typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node> iterator; |
| |
| XalanListIteratorBase(Node& node) : |
| currentNode(&node) |
| { |
| } |
| |
| XalanListIteratorBase(const iterator& theRhs) : |
| currentNode(theRhs.currentNode) |
| { |
| } |
| |
| XalanListIteratorBase operator++() |
| { |
| currentNode = currentNode->next; |
| return *this; |
| } |
| |
| XalanListIteratorBase operator++(int) |
| { |
| Node& origNode = *currentNode; |
| currentNode = currentNode->next; |
| return XalanListIteratorBase(origNode); |
| } |
| |
| XalanListIteratorBase operator--() |
| { |
| currentNode = currentNode->prev; |
| return *this; |
| } |
| |
| XalanListIteratorBase operator-(difference_type decrement) const |
| { |
| Node* node = currentNode; |
| while (decrement > 0) |
| { |
| node = node->prev; |
| --decrement; |
| }; |
| return XalanListIteratorBase(*node); |
| } |
| |
| reference operator*() const |
| { |
| return currentNode->value; |
| } |
| |
| pointer operator->() const |
| { |
| return ¤tNode->value; |
| } |
| |
| const XalanListIteratorBase & operator=(const XalanListIteratorBase& theRhs) |
| { |
| currentNode = theRhs.currentNode; |
| return *this; |
| } |
| |
| bool operator!=(const XalanListIteratorBase& theRhs) const |
| { |
| return !operator==(theRhs); |
| } |
| |
| bool operator==(const XalanListIteratorBase& theRhs) const |
| { |
| return currentNode == theRhs.currentNode; |
| } |
| |
| Node& node() |
| { |
| return *currentNode; |
| } |
| |
| Node* currentNode; |
| }; |
| |
| |
| |
| /** |
| * Xalan implementation of a doubly linked list |
| */ |
| template <class Type> |
| class XalanList |
| { |
| public: |
| |
| |
| typedef Type value_type; |
| typedef value_type* pointer; |
| typedef const value_type* const_pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef size_t size_type; |
| |
| typedef XalanList<value_type> ThisType; |
| |
| struct Node |
| { |
| Node( |
| const value_type & theValue, |
| Node& prevNode, |
| Node& nextNode) : |
| value(theValue), |
| prev(&prevNode), |
| next(&nextNode) |
| { |
| } |
| |
| value_type value; |
| Node* prev; |
| Node* next; |
| }; |
| |
| typedef XalanListIteratorBase<XalanListIteratorTraits<value_type>, Node> iterator; |
| typedef XalanListIteratorBase<XalanListConstIteratorTraits<value_type>, Node> const_iterator; |
| |
| #if defined(XALAN_HAS_STD_ITERATORS) |
| typedef std::reverse_iterator<iterator> reverse_iterator_; |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator_; |
| #elif defined(XALAN_RW_NO_CLASS_PARTIAL_SPEC) |
| typedef typename iterator::iterator_category iterator_category; |
| |
| // This is a specific case for the Rogue Wave STL on Solaris. |
| typedef std::reverse_iterator< |
| iterator, |
| iterator_category, |
| value_type> reverse_iterator_; |
| |
| typedef std::reverse_iterator< |
| const_iterator, |
| iterator_category, |
| const value_type> const_reverse_iterator_; |
| #else |
| typedef std::reverse_iterator< |
| iterator, |
| value_type> reverse_iterator_; |
| |
| typedef std::reverse_iterator< |
| const_iterator, |
| value_type, |
| const_reference> const_reverse_iterator_; |
| #endif |
| |
| typedef reverse_iterator_ reverse_iterator; |
| typedef const_reverse_iterator_ const_reverse_iterator; |
| |
| typedef typename MemoryManagedConstructionTraits<value_type>::Constructor Constructor; |
| |
| XalanList( |
| MemoryManager& theManager) : |
| m_memoryManager(&theManager), |
| m_listHead(0), |
| m_freeListHeadPtr(0) |
| { |
| } |
| |
| ~XalanList() |
| { |
| if (m_listHead != 0) |
| { |
| iterator pos = begin(); |
| while (pos != end()) |
| { |
| destroyNode(pos++.node()); |
| } |
| |
| Node * freeNode = m_freeListHeadPtr; |
| while (freeNode != 0) |
| { |
| Node * nextNode = freeNode->next; |
| deallocate(freeNode); |
| freeNode = nextNode; |
| } |
| |
| deallocate(m_listHead); |
| } |
| } |
| |
| MemoryManager& |
| getMemoryManager() |
| { |
| assert(m_memoryManager != 0 ); |
| |
| return *m_memoryManager; |
| } |
| |
| const MemoryManager& |
| getMemoryManager() const |
| { |
| assert(m_memoryManager != 0 ); |
| |
| return *m_memoryManager; |
| } |
| |
| iterator |
| begin() |
| { |
| return iterator(*(getListHead().next)); |
| } |
| |
| const_iterator |
| begin() const |
| { |
| return const_iterator(*(getListHead().next)); |
| } |
| |
| iterator |
| end() |
| { |
| return iterator(getListHead()); |
| } |
| |
| const_iterator |
| end() const |
| { |
| return const_iterator(getListHead()); |
| } |
| |
| reverse_iterator |
| rbegin() |
| { |
| return reverse_iterator(end()); |
| } |
| |
| const_reverse_iterator |
| rbegin() const |
| { |
| return const_reverse_iterator(end()); |
| } |
| |
| reverse_iterator |
| rend() |
| { |
| return reverse_iterator(begin()); |
| } |
| |
| const_reverse_iterator |
| rend() const |
| { |
| return const_reverse_iterator(begin()); |
| } |
| |
| reference |
| front() |
| { |
| return *begin(); |
| } |
| |
| reference |
| back() |
| { |
| return *(--end()); |
| } |
| |
| size_type |
| size() const |
| { |
| size_type size = 0; |
| const_iterator item = begin(); |
| while (item != end()) |
| { |
| ++size; |
| ++item; |
| } |
| return size; |
| } |
| |
| bool |
| empty() const |
| { |
| return (begin() == end()) != 0; |
| } |
| |
| void |
| push_back(const value_type& data) |
| { |
| constructNode(data, end()); |
| } |
| |
| void |
| push_front(const value_type& data) |
| { |
| constructNode(data, begin()); |
| } |
| |
| void |
| pop_front() |
| { |
| erase(begin()); |
| } |
| |
| void |
| pop_back() |
| { |
| erase(--end()); |
| } |
| |
| iterator |
| insert(const iterator& pos, const value_type& value) |
| { |
| return iterator(constructNode(value,pos)); |
| } |
| |
| void |
| erase(iterator pos) |
| { |
| assert(pos != end()); |
| freeNode(pos.node()); |
| } |
| |
| void |
| splice( |
| iterator pos, |
| #if defined(NDEBUG) |
| ThisType& /* list */, |
| #else |
| ThisType& list, |
| #endif |
| iterator toInsert) |
| { |
| assert(m_memoryManager == list.m_memoryManager); |
| |
| if (pos != toInsert) |
| { |
| Node & posNode = pos.node(); |
| Node & toInsertNode = toInsert.node(); |
| |
| toInsertNode.prev->next = toInsertNode.next; |
| toInsertNode.next->prev = toInsertNode.prev; |
| |
| toInsertNode.prev = posNode.prev; |
| toInsertNode.next = &posNode; |
| |
| posNode.prev->next = &toInsertNode; |
| posNode.prev = &toInsertNode; |
| } |
| } |
| |
| void |
| splice( |
| iterator pos, |
| #if defined(NDEBUG) |
| ThisType& /* list */, |
| #else |
| ThisType& list, |
| #endif |
| iterator toInsertFirst, |
| iterator toInsertLast) |
| { |
| assert(m_memoryManager == list.m_memoryManager); |
| |
| if (toInsertFirst != toInsertLast) |
| { |
| Node & posNode = pos.node(); |
| Node & toInsertFirstNode = toInsertFirst.node(); |
| Node & toInsertLastNode = *(toInsertLast.node().prev); |
| |
| toInsertFirstNode.prev->next = toInsertLastNode.next; |
| toInsertLastNode.next->prev = toInsertFirstNode.prev; |
| |
| toInsertFirstNode.prev = posNode.prev; |
| toInsertLastNode.next = &posNode; |
| |
| posNode.prev->next = &toInsertFirstNode; |
| posNode.prev = &toInsertLastNode; |
| } |
| } |
| |
| void |
| clear() |
| { |
| iterator pos = begin(); |
| while (pos != end()) |
| { |
| freeNode(pos++.node()); |
| } |
| } |
| |
| void swap(ThisType& theRHS) |
| { |
| std::swap(m_memoryManager, theRHS.m_memoryManager); |
| std::swap(m_listHead, theRHS.m_listHead); |
| std::swap(m_freeListHeadPtr, theRHS.m_freeListHeadPtr); |
| } |
| |
| |
| protected: |
| |
| Node& constructNode(const value_type& data, iterator pos) |
| { |
| Node * newNode = 0; |
| Node * nextFreeNode = 0; |
| |
| if (m_freeListHeadPtr != 0) |
| { |
| newNode = m_freeListHeadPtr; |
| nextFreeNode = m_freeListHeadPtr->next; |
| } |
| else |
| { |
| m_freeListHeadPtr = allocate(1); |
| newNode = m_freeListHeadPtr; |
| } |
| |
| Constructor::construct(&newNode->value, data, *m_memoryManager); |
| new (&newNode->prev) Node*(pos.node().prev); |
| new (&newNode->next) Node*(&(pos.node())); |
| |
| pos.node().prev->next = newNode; |
| pos.node().prev = newNode; |
| |
| m_freeListHeadPtr = nextFreeNode; |
| |
| return *newNode; |
| } |
| |
| void freeNode(Node& node) |
| { |
| node.prev->next = node.next; |
| node.next->prev = node.prev; |
| |
| node.~Node(); |
| node.prev = 0; |
| node.next = m_freeListHeadPtr; |
| m_freeListHeadPtr = &node; |
| } |
| |
| void destroyNode(Node& node) |
| { |
| assert(&node != m_listHead); |
| node.~Node(); |
| deallocate(&node); |
| } |
| |
| Node& getListHead() |
| { |
| if (0 == m_listHead) |
| { |
| m_listHead = allocate(1); |
| m_listHead->next = m_listHead; |
| m_listHead->prev = m_listHead; |
| } |
| |
| return *m_listHead; |
| } |
| |
| Node& getListHead() const |
| { |
| return const_cast<XalanList*>(this)->getListHead(); |
| } |
| |
| Node* |
| allocate(size_type size) |
| { |
| const size_type theBytesNeeded = size * sizeof(Node); |
| |
| assert(m_memoryManager != 0); |
| |
| void* pointer = m_memoryManager->allocate(theBytesNeeded); |
| |
| assert( pointer != 0 ); |
| |
| return (Node*) pointer; |
| } |
| |
| |
| void |
| deallocate(Node* pointer) |
| { |
| assert(m_memoryManager != 0); |
| |
| m_memoryManager->deallocate(pointer); |
| } |
| |
| MemoryManager * m_memoryManager; |
| |
| Node* m_listHead; |
| |
| Node* m_freeListHeadPtr; |
| |
| private: |
| // not defined |
| XalanList(); |
| XalanList(const XalanList& theRhs); |
| |
| XalanList& operator=(const XalanList& theRhs); |
| |
| }; |
| |
| |
| |
| } |
| |
| #endif // XALANLIST_HEADER_GUARD_1357924680 |