sw/inc/ring.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19 #ifndef INCLUDED_SW_INC_RING_HXX
  20 #define INCLUDED_SW_INC_RING_HXX
  21
  22 #include <utility>
  23 #include <sal/types.h>
  24 #include <iterator>
  25 #include <type_traits>
  26 #include <boost/iterator/iterator_facade.hpp>
  27 #include <boost/intrusive/circular_list_algorithms.hpp>
  28
  29 namespace sw
  30 {
  31     template <typename value_type> class RingContainer;
  32     template <typename value_type> class RingIterator;
  33     /**
  34      * An intrusive container class double linking the contained nodes
  35      * @example sw/qa/core/uwriter.cxx
  36      */
  37     template <typename value_type>
  38     class SAL_WARN_UNUSED Ring
  39     {
  40         public:
  41             typedef typename std::add_const<value_type>::type const_value_type;
  42             typedef RingContainer<value_type> ring_container;
  43             typedef RingContainer<const_value_type> const_ring_container;
  44             virtual ~Ring() COVERITY_NOEXCEPT_FALSE
  45                 { unlink(); };
  46             /** algo::unlink is buggy! don't call it directly! */
  47             void unlink()
  48             {
  49                 algo::unlink(this);
  50                 m_pNext = this; // don't leave pointers to old list behind!
  51                 m_pPrev = this;
  52             }
  53             /**
  54              * Removes this item from its current ring container and adds it to
  55              * another ring container. If the item was not alone in the original
  56              * ring container, the other items in the ring will stay in the old
  57              * ring container.
  58              * Note: the newly created item will be inserted just before item pDestRing.
  59              * @param pDestRing the container to add this item to
  60              */
  61             void MoveTo( value_type* pDestRing );
  62             /** @return a stl-like container with begin()/end() for iteration */
  63             ring_container GetRingContainer();
  64             /** @return a stl-like container with begin()/end() for const iteration */
  65             const_ring_container GetRingContainer() const;
  66
  67         protected:
  68             /**
  69              * Creates a new item in a ring container all by itself.
  70              * Note: Ring instances can newer be outside a container. At most, they
  71              * are alone in one.
  72              */
  73             Ring()
  74                 : m_pNext(this)
  75                 , m_pPrev(this)
  76                 { }
  77             /**
  78              * Creates a new item and add it to an existing ring container.
  79              * Note: the newly created item will be inserted just before item pRing.
  80              * @param pRing ring container to add the created item to
  81              */
  82             Ring( value_type* pRing );
  83             /** @return the next item in the ring container */
  84             value_type* GetNextInRing()
  85                 { return static_cast<value_type *>(m_pNext); }
  86             /** @return the previous item in the ring container */
  87             value_type* GetPrevInRing()
  88                 { return static_cast<value_type *>(m_pPrev); }
  89             /** @return the next item in the ring container */
  90             const_value_type* GetNextInRing() const
  91                 { return static_cast<value_type *>(m_pNext); }
  92             /** @return the previous item in the ring container */
  93             const_value_type* GetPrevInRing() const
  94                 { return static_cast<value_type *>(m_pPrev); }
  95             /** @return true if and only if this item is alone in its ring */
  96             bool unique() const
  97                 { return algo::unique(static_cast< const_value_type* >(this)); }
  98
  99         private:
 100             /** internal implementation class -- not for external use */
 101             struct Ring_node_traits
 102             {
 103                 typedef Ring node;
 104                 typedef Ring* node_ptr;
 105                 typedef const Ring* const_node_ptr;
 106                 static node_ptr get_next(const_node_ptr n) { return const_cast<node_ptr>(n)->m_pNext; };
 107                 static void set_next(node_ptr n, node_ptr next) { n->m_pNext = next; };
 108                 static node_ptr get_previous(const_node_ptr n) { return const_cast<node_ptr>(n)->m_pPrev; };
 109                 static void set_previous(node_ptr n, node_ptr previous) { n->m_pPrev = previous; };
 110             };
 111             friend ring_container;
 112             friend const_ring_container;
 113             friend typename ring_container::iterator;
 114             friend typename ring_container::const_iterator;
 115             friend typename const_ring_container::iterator;
 116             friend typename const_ring_container::const_iterator;
 117             friend class boost::iterator_core_access;
 118             typedef boost::intrusive::circular_list_algorithms<Ring_node_traits> algo;
 119             Ring* m_pNext;
 120             Ring* m_pPrev;
 121     };
 122
 123     template <typename value_type>
 124     inline Ring<value_type>::Ring( value_type* pObj )
 125         : m_pNext(this)
 126         , m_pPrev(this)
 127     {
 128         if( pObj )
 129         {
 130             algo::link_before(pObj, this);
 131         }
 132     }
 133
 134     template <typename value_type>
 135     inline void Ring<value_type>::MoveTo(value_type* pDestRing)
 136     {
 137         value_type* pThis = static_cast< value_type* >(this);
 138         unlink();
 139         // insert into "new"
 140         if (pDestRing)
 141         {
 142             algo::link_before(pDestRing, pThis);
 143         }
 144     }
 145
 146     /**
 147      * helper class that provides STL-style container iteration to the ring
 148      */
 149     template <typename value_type>
 150     class SAL_WARN_UNUSED RingContainer final
 151     {
 152         private:
 153             /** the item in the ring where iteration starts */
 154             value_type* m_pStart;
 155             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 156
 157         public:
 158             RingContainer( value_type* pRing ) : m_pStart(pRing) {};
 159             typedef RingIterator<value_type> iterator;
 160             typedef RingIterator<const value_type> const_iterator;
 161             /**
 162              * iterator access
 163              * @code
 164              * for(SwPaM& rCurrentPaM : pPaM->GetRingContainer())
 165              *     do_stuff(rCurrentPaM); // this gets called on every SwPaM in the same ring as pPaM
 166              * @endcode
 167              */
 168             iterator begin();
 169             iterator end();
 170             const_iterator begin() const;
 171             const_iterator end() const;
 172             /** @return the number of elements in the container */
 173             size_t size() const
 174                 { return std::distance(begin(), end()); }
 175             /**
 176              * Merges two ring containers. All item from both ring containers will
 177              * be in the same ring container in the end.
 178              * Note: The items of this ring container will be inserted just before
 179              * item pDestRing
 180              * @param pDestRing the container to merge this container with
 181              */
 182             void merge( RingContainer< value_type > aDestRing )
 183             {
 184                 // first check that we aren't merged already, swapping would
 185                 // actually un-merge in this case!
 186                 assert(m_pStart->m_pPrev != aDestRing.m_pStart);
 187                 assert(m_pStart != aDestRing.m_pStart->m_pPrev);
 188                 std::swap(m_pStart->m_pPrev->m_pNext, aDestRing.m_pStart->m_pPrev->m_pNext);
 189                 std::swap(m_pStart->m_pPrev, aDestRing.m_pStart->m_pPrev);
 190             }
 191     };
 192
 193     template <typename value_type>
 194     class RingIterator final : public boost::iterator_facade<
 195           RingIterator<value_type>
 196         , value_type
 197         , boost::forward_traversal_tag
 198         >
 199     {
 200         private:
 201             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 202         public:
 203             RingIterator()
 204                 : m_pCurrent(nullptr)
 205                 , m_pStart(nullptr)
 206             {}
 207             explicit RingIterator(nonconst_value_type* pRing, bool bStart = true)
 208                 : m_pCurrent(nullptr)
 209                 , m_pStart(pRing)
 210             {
 211                 if(!bStart)
 212                     m_pCurrent = m_pStart;
 213             }
 214
 215         private:
 216             friend class boost::iterator_core_access;
 217             void increment()
 218                 { m_pCurrent = m_pCurrent ? m_pCurrent->GetNextInRing() : m_pStart->GetNextInRing(); }
 219             bool equal(RingIterator const& other) const
 220             {
 221                 // we never want to compare iterators from
 222                 // different rings or starting points
 223                 assert(m_pStart == other.m_pStart);
 224                 return m_pCurrent == other.m_pCurrent;
 225             }
 226             value_type& dereference() const
 227                 { return m_pCurrent ? *m_pCurrent : * m_pStart; }
 228             /**
 229              * This is:
 230              * - pointing to the current item in the iteration in general
 231              * - nullptr if on the first item (begin())
 232              * - m_pStart when beyond the last item (end())
 233              */
 234             nonconst_value_type* m_pCurrent;
 235             /** the first item of the iteration */
 236             nonconst_value_type* m_pStart;
 237     };
 238
 239     template <typename value_type>
 240     inline typename Ring<value_type>::ring_container Ring<value_type>::GetRingContainer()
 241         { return Ring<value_type>::ring_container(static_cast< value_type* >(this)); };
 242
 243     template <typename value_type>
 244     inline typename Ring<value_type>::const_ring_container Ring<value_type>::GetRingContainer() const
 245         { return Ring<value_type>::const_ring_container(static_cast< const_value_type* >(this)); };
 246
 247     template <typename value_type>
 248     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::begin()
 249         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 250
 251     template <typename value_type>
 252     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::end()
 253         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 254
 255     template <typename value_type>
 256     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::begin() const
 257         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 258
 259     template <typename value_type>
 260     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::end() const
 261         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 262 }
 263 #endif
 264
 265 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */