diff options
Diffstat (limited to 'sw/inc/ring.hxx')
| -rw-r--r-- | sw/inc/ring.hxx | 265 |
1 files changed, 265 insertions, 0 deletions
diff --git a/sw/inc/ring.hxx b/sw/inc/ring.hxx new file mode 100644 index 0000000000..e152899ec8 --- /dev/null +++ b/sw/inc/ring.hxx @@ -0,0 +1,265 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * 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 . + */ +#ifndef INCLUDED_SW_INC_RING_HXX +#define INCLUDED_SW_INC_RING_HXX + +#include <utility> +#include <sal/types.h> +#include <iterator> +#include <type_traits> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/intrusive/circular_list_algorithms.hpp> + +namespace sw +{ + template <typename value_type> class RingContainer; + template <typename value_type> class RingIterator; + /** + * An intrusive container class double linking the contained nodes + * @example sw/qa/core/uwriter.cxx + */ + template <typename value_type> + class SAL_WARN_UNUSED Ring + { + public: + typedef typename std::add_const<value_type>::type const_value_type; + typedef RingContainer<value_type> ring_container; + typedef RingContainer<const_value_type> const_ring_container; + virtual ~Ring() COVERITY_NOEXCEPT_FALSE + { unlink(); }; + /** algo::unlink is buggy! don't call it directly! */ + void unlink() + { + algo::unlink(this); + m_pNext = this; // don't leave pointers to old list behind! + m_pPrev = this; + } + /** + * Removes this item from its current ring container and adds it to + * another ring container. If the item was not alone in the original + * ring container, the other items in the ring will stay in the old + * ring container. + * Note: the newly created item will be inserted just before item pDestRing. + * @param pDestRing the container to add this item to + */ + void MoveTo( value_type* pDestRing ); + /** @return a stl-like container with begin()/end() for iteration */ + ring_container GetRingContainer(); + /** @return a stl-like container with begin()/end() for const iteration */ + const_ring_container GetRingContainer() const; + + protected: + /** + * Creates a new item in a ring container all by itself. + * Note: Ring instances can newer be outside a container. At most, they + * are alone in one. + */ + Ring() + : m_pNext(this) + , m_pPrev(this) + { } + /** + * Creates a new item and add it to an existing ring container. + * Note: the newly created item will be inserted just before item pRing. + * @param pRing ring container to add the created item to + */ + Ring( value_type* pRing ); + /** @return the next item in the ring container */ + value_type* GetNextInRing() + { return static_cast<value_type *>(m_pNext); } + /** @return the previous item in the ring container */ + value_type* GetPrevInRing() + { return static_cast<value_type *>(m_pPrev); } + /** @return the next item in the ring container */ + const_value_type* GetNextInRing() const + { return static_cast<value_type *>(m_pNext); } + /** @return the previous item in the ring container */ + const_value_type* GetPrevInRing() const + { return static_cast<value_type *>(m_pPrev); } + /** @return true if and only if this item is alone in its ring */ + bool unique() const + { return algo::unique(static_cast< const_value_type* >(this)); } + + private: + /** internal implementation class -- not for external use */ + struct Ring_node_traits + { + typedef Ring node; + typedef Ring* node_ptr; + typedef const Ring* const_node_ptr; + static node_ptr get_next(const_node_ptr n) { return const_cast<node_ptr>(n)->m_pNext; }; + static void set_next(node_ptr n, node_ptr next) { n->m_pNext = next; }; + static node_ptr get_previous(const_node_ptr n) { return const_cast<node_ptr>(n)->m_pPrev; }; + static void set_previous(node_ptr n, node_ptr previous) { n->m_pPrev = previous; }; + }; + friend ring_container; + friend const_ring_container; + friend typename ring_container::iterator; + friend typename ring_container::const_iterator; + friend typename const_ring_container::iterator; + friend typename const_ring_container::const_iterator; + friend class boost::iterator_core_access; + typedef boost::intrusive::circular_list_algorithms<Ring_node_traits> algo; + Ring* m_pNext; + Ring* m_pPrev; + }; + + template <typename value_type> + inline Ring<value_type>::Ring( value_type* pObj ) + : m_pNext(this) + , m_pPrev(this) + { + if( pObj ) + { + algo::link_before(pObj, this); + } + } + + template <typename value_type> + inline void Ring<value_type>::MoveTo(value_type* pDestRing) + { + value_type* pThis = static_cast< value_type* >(this); + unlink(); + // insert into "new" + if (pDestRing) + { + algo::link_before(pDestRing, pThis); + } + } + + /** + * helper class that provides Svalue_typeL-style container iteration to the ring + */ + template <typename value_type> + class SAL_WARN_UNUSED RingContainer final + { + private: + /** the item in the ring where iteration starts */ + value_type* m_pStart; + typedef typename std::remove_const<value_type>::type nonconst_value_type; + + public: + RingContainer( value_type* pRing ) : m_pStart(pRing) {}; + typedef RingIterator<value_type> iterator; + typedef RingIterator<const value_type> const_iterator; + /** + * iterator access + * @code + * for(SwPaM& rCurrentPaM : pPaM->GetRingContainer()) + * do_stuff(rCurrentPaM); // this gets called on every SwPaM in the same ring as pPaM + * @endcode + */ + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + /** @return the number of elements in the container */ + size_t size() const + { return std::distance(begin(), end()); } + /** + * Merges two ring containers. All item from both ring containers will + * be in the same ring container in the end. + * Note: The items of this ring container will be inserted just before + * item pDestRing + * @param pDestRing the container to merge this container with + */ + void merge( RingContainer< value_type > aDestRing ) + { + // first check that we aren't merged already, swapping would + // actually un-merge in this case! + assert(m_pStart->m_pPrev != aDestRing.m_pStart); + assert(m_pStart != aDestRing.m_pStart->m_pPrev); + std::swap(m_pStart->m_pPrev->m_pNext, aDestRing.m_pStart->m_pPrev->m_pNext); + std::swap(m_pStart->m_pPrev, aDestRing.m_pStart->m_pPrev); + } + }; + + template <typename value_type> + class RingIterator final : public boost::iterator_facade< + RingIterator<value_type> + , value_type + , boost::forward_traversal_tag + > + { + private: + typedef typename std::remove_const<value_type>::type nonconst_value_type; + public: + RingIterator() + : m_pCurrent(nullptr) + , m_pStart(nullptr) + {} + explicit RingIterator(nonconst_value_type* pRing, bool bStart = true) + : m_pCurrent(nullptr) + , m_pStart(pRing) + { + if(!bStart) + m_pCurrent = m_pStart; + } + + private: + friend class boost::iterator_core_access; + void increment() + { m_pCurrent = m_pCurrent ? m_pCurrent->GetNextInRing() : m_pStart->GetNextInRing(); } + bool equal(RingIterator const& other) const + { + // we never want to compare iterators from + // different rings or starting points + assert(m_pStart == other.m_pStart); + return m_pCurrent == other.m_pCurrent; + } + value_type& dereference() const + { return m_pCurrent ? *m_pCurrent : * m_pStart; } + /** + * value_type is: + * - pointing to the current item in the iteration in general + * - nullptr if on the first item (begin()) + * - m_pStart when beyond the last item (end()) + */ + nonconst_value_type* m_pCurrent; + /** the first item of the iteration */ + nonconst_value_type* m_pStart; + }; + + template <typename value_type> + inline typename Ring<value_type>::ring_container Ring<value_type>::GetRingContainer() + { return Ring<value_type>::ring_container(static_cast< value_type* >(this)); }; + + template <typename value_type> + inline typename Ring<value_type>::const_ring_container Ring<value_type>::GetRingContainer() const + { return Ring<value_type>::const_ring_container(static_cast< const_value_type* >(this)); }; + + template <typename value_type> + inline typename RingContainer<value_type>::iterator RingContainer<value_type>::begin() + { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart)); }; + + template <typename value_type> + inline typename RingContainer<value_type>::iterator RingContainer<value_type>::end() + { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart), false); }; + + template <typename value_type> + inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::begin() const + { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart)); }; + + template <typename value_type> + inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::end() const + { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart), false); }; +} +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |