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 <swdllapi.h>
  23 #include <swtypes.hxx>
  24 #include <utility>
  25 #include <iterator>
  26 #include <type_traits>
  27 #include <boost/iterator/iterator_facade.hpp>
  28 #include <boost/intrusive/circular_list_algorithms.hpp>
  29
  30 namespace sw
  31 {
  32     template <typename value_type> class RingContainer;
  33     template <typename value_type> class RingIterator;
  34     /**
  35      * An intrusive container class double linking the contained nodes
  36      * @example sw/qa/core/uwriter.cxx
  37      */
  38     template <typename value_type>
  39     class Ring
  40     {
  41         public:
  42             typedef typename std::add_const<value_type>::type const_value_type;
  43             typedef RingContainer<value_type> ring_container;
  44             typedef RingContainer<const_value_type> const_ring_container;
  45             virtual ~Ring()
  46                 { unlink(); };
  47             /** algo::unlink is buggy! don't call it directly! */
  48             void unlink()
  49             {
  50                 algo::unlink(this);
  51                 pNext = this; // don't leave pointers to old list behind!
  52                 pPrev = this;
  53             }
  54             /**
  55              * Removes this item from its current ring container and adds it to
  56              * another ring container. If the item was not alone in the original
  57              * ring container, the other items in the ring will stay in the old
  58              * ring container.
  59              * Note: the newly created item will be inserted just before item pDestRing.
  60              * @param pDestRing the container to add this item to
  61              */
  62             void MoveTo( value_type* pDestRing );
  63             /** @return a stl-like container with begin()/end() for iteration */
  64             ring_container GetRingContainer();
  65             /** @return a stl-like container with begin()/end() for const iteration */
  66             const_ring_container GetRingContainer() const;
  67
  68         protected:
  69             /**
  70              * Creates a new item in a ring container all by itself.
  71              * Note: Ring instances can newer be outside a container. At most, they
  72              * are alone in one.
  73              */
  74             Ring()
  75                 : pNext(this)
  76                 , pPrev(this)
  77                 { }
  78             /**
  79              * Creates a new item and add it to an existing ring container.
  80              * Note: the newly created item will be inserted just before item pRing.
  81              * @param pRing ring container to add the created item to
  82              */
  83             Ring( value_type* pRing );
  84             /** @return the next item in the ring container */
  85             value_type* GetNextInRing()
  86                 { return static_cast<value_type *>(pNext); }
  87             /** @return the previous item in the ring container */
  88             value_type* GetPrevInRing()
  89                 { return static_cast<value_type *>(pPrev); }
  90             /** @return the next item in the ring container */
  91             const_value_type* GetNextInRing() const
  92                 { return static_cast<value_type *>(pNext); }
  93             /** @return the previous item in the ring container */
  94             const_value_type* GetPrevInRing() const
  95                 { return static_cast<value_type *>(pPrev); }
  96             /** @return true if and only if this item is alone in its ring */
  97             bool unique() const
  98                 { return algo::unique(static_cast< const_value_type* >(this)); }
  99
 100         private:
 101             /** internal implementation class -- not for external use */
 102             struct Ring_node_traits
 103             {
 104                 typedef Ring node;
 105                 typedef Ring* node_ptr;
 106                 typedef const Ring* const_node_ptr;
 107                 static node_ptr get_next(const_node_ptr n) { return const_cast<node_ptr>(n)->pNext; };
 108                 static void set_next(node_ptr n, node_ptr next) { n->pNext = next; };
 109                 static node_ptr get_previous(const_node_ptr n) { return const_cast<node_ptr>(n)->pPrev; };
 110                 static void set_previous(node_ptr n, node_ptr previous) { n->pPrev = previous; };
 111             };
 112 #if !defined(__clang__) && defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 7)
 113             // gcc 4.6 backwards compat hack, remove ASAP when we drop support
 114             template<typename gcc_hack_value> friend class sw::RingContainer;
 115             template<typename gcc_hack_value> friend class sw::RingIterator;
 116 #else
 117             friend ring_container;
 118             friend const_ring_container;
 119             friend typename ring_container::iterator;
 120             friend typename ring_container::const_iterator;
 121             friend typename const_ring_container::iterator;
 122             friend typename const_ring_container::const_iterator;
 123 #endif
 124             friend class boost::iterator_core_access;
 125             typedef boost::intrusive::circular_list_algorithms<Ring_node_traits> algo;
 126             Ring* pNext;
 127             Ring* pPrev;
 128     };
 129
 130     template <typename value_type>
 131     inline Ring<value_type>::Ring( value_type* pObj )
 132         : pNext(this)
 133         , pPrev(this)
 134     {
 135         if( pObj )
 136         {
 137             algo::link_before(pObj, this);
 138         }
 139     }
 140
 141     template <typename value_type>
 142     inline void Ring<value_type>::MoveTo(value_type* pDestRing)
 143     {
 144         value_type* pThis = static_cast< value_type* >(this);
 145         unlink();
 146         // insert into "new"
 147         if (pDestRing)
 148         {
 149             algo::link_before(pDestRing, pThis);
 150         }
 151     }
 152
 153     /**
 154      * helper class that provides Svalue_typeL-style container iteration to the ring
 155      */
 156     template <typename value_type>
 157     class RingContainer SAL_FINAL
 158     {
 159         private:
 160             /** the item in the ring where iteration starts */
 161             value_type* m_pStart;
 162             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 163
 164         public:
 165             RingContainer( value_type* pRing ) : m_pStart(pRing) {};
 166             typedef RingIterator<value_type> iterator;
 167             typedef RingIterator<const value_type> const_iterator;
 168             /**
 169              * iterator access
 170              * @code
 171              * for(SwPaM& rCurrentPaM : pPaM->GetRingContainer())
 172              *     do_stuff(rCurrentPaM); // this gets called on every SwPaM in the same ring as pPaM
 173              * @endcode
 174              */
 175             iterator begin();
 176             iterator end();
 177             const_iterator begin() const;
 178             const_iterator end() const;
 179             /** @return the number of elements in the container */
 180             size_t size() const
 181                 { return std::distance(begin(), end()); }
 182             /**
 183              * Merges two ring containers. All item from both ring containers will
 184              * be in the same ring container in the end.
 185              * Note: The items of this ring container will be inserted just before
 186              * item pDestRing
 187              * @param pDestRing the container to merge this container with
 188              */
 189             void merge( RingContainer< value_type > aDestRing )
 190             {
 191                 // first check that we aren't merged already, swapping would
 192                 // actually un-merge in this case!
 193                 assert(m_pStart->pPrev != aDestRing.m_pStart);
 194                 assert(m_pStart != aDestRing.m_pStart->pPrev);
 195                 std::swap(*(&m_pStart->pPrev->pNext), *(&aDestRing.m_pStart->pPrev->pNext));
 196                 std::swap(*(&m_pStart->pPrev), *(&aDestRing.m_pStart->pPrev));
 197             }
 198     };
 199
 200     template <typename value_type>
 201     class RingIterator SAL_FINAL : public boost::iterator_facade<
 202           RingIterator<value_type>
 203         , value_type
 204         , boost::forward_traversal_tag
 205         >
 206     {
 207         private:
 208             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 209         public:
 210             RingIterator()
 211                 : m_pCurrent(nullptr)
 212                 , m_pStart(nullptr)
 213             {}
 214             explicit RingIterator(nonconst_value_type* pRing, bool bStart = true)
 215                 : m_pCurrent(nullptr)
 216                 , m_pStart(pRing)
 217             {
 218                 if(!bStart)
 219                     m_pCurrent = m_pStart;
 220             }
 221
 222         private:
 223             friend class boost::iterator_core_access;
 224             void increment()
 225                 { m_pCurrent = m_pCurrent ? m_pCurrent->GetNextInRing() : m_pStart->GetNextInRing(); }
 226             bool equal(RingIterator const& other) const
 227             {
 228                 // we never want to compare iterators from
 229                 // different rings or starting points
 230                 assert(m_pStart == other.m_pStart);
 231                 return m_pCurrent == other.m_pCurrent;
 232             }
 233             value_type& dereference() const
 234                 { return m_pCurrent ? *m_pCurrent : * m_pStart; }
 235             /**
 236              * value_type is is:
 237              * - pointing to the current item in the iteration in general
 238              * - nullptr if on the first item (begin())
 239              * - m_pStart when beyond the last item (end())
 240              */
 241             nonconst_value_type* m_pCurrent;
 242             /** the first item of the iteration */
 243             nonconst_value_type* m_pStart;
 244     };
 245
 246     template <typename value_type>
 247     inline typename Ring<value_type>::ring_container Ring<value_type>::GetRingContainer()
 248         { return Ring<value_type>::ring_container(static_cast< value_type* >(this)); };
 249
 250     template <typename value_type>
 251     inline typename Ring<value_type>::const_ring_container Ring<value_type>::GetRingContainer() const
 252         { return Ring<value_type>::const_ring_container(static_cast< const_value_type* >(this)); };
 253
 254     template <typename value_type>
 255     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::begin()
 256         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 257
 258     template <typename value_type>
 259     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::end()
 260         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 261
 262     template <typename value_type>
 263     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::begin() const
 264         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 265
 266     template <typename value_type>
 267     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::end() const
 268         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 269 }
 270 #endif
 271
 272 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */