ring.hxx

Go to the documentation of this file.

/* -*- 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;
    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(); };
            void unlink()
            {
                algo::unlink(this);
                m_pNext = this; // don't leave pointers to old list behind!
                m_pPrev = this;
            }
            void MoveTo( value_type* pDestRing );
            ring_container GetRingContainer();
            const_ring_container GetRingContainer() const;
 
        protected:
            Ring()
                : m_pNext(this)
                , m_pPrev(this)
                { }
            Ring( value_type* pRing );
            value_type* GetNextInRing()
                { return static_cast<value_type *>(m_pNext); }
            value_type* GetPrevInRing()
                { return static_cast<value_type *>(m_pPrev); }
            const_value_type* GetNextInRing() const
                { return static_cast<value_type *>(m_pNext); }
            const_value_type* GetPrevInRing() const
                { return static_cast<value_type *>(m_pPrev); }
            bool unique() const
                { return algo::unique(static_cast< const_value_type* >(this)); }
 
        private:
            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);
        }
    }
 
    template <typename value_type>
    class SAL_WARN_UNUSED RingContainer final
    {
        private:
            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 begin();
            iterator end();
            const_iterator begin() const;
            const_iterator end() const;
            size_t size() const
                { return std::distance(begin(), end()); }
            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; }
            nonconst_value_type* m_pCurrent;
            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: */