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 SAL_WARN_UNUSED 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                 m_pNext = this; // don't leave pointers to old list behind!
  52                 m_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                 : m_pNext(this)
  76                 , m_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 *>(m_pNext); }
  87             /** @return the previous item in the ring container */
  88             value_type* GetPrevInRing()
  89                 { return static_cast<value_type *>(m_pPrev); }
  90             /** @return the next item in the ring container */
  91             const_value_type* GetNextInRing() const
  92                 { return static_cast<value_type *>(m_pNext); }
  93             /** @return the previous item in the ring container */
  94             const_value_type* GetPrevInRing() const
  95                 { return static_cast<value_type *>(m_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)->m_pNext; };
 108                 static void set_next(node_ptr n, node_ptr next) { n->m_pNext = next; };
 109                 static node_ptr get_previous(const_node_ptr n) { return const_cast<node_ptr>(n)->m_pPrev; };
 110                 static void set_previous(node_ptr n, node_ptr previous) { n->m_pPrev = previous; };
 111             };
 112             friend ring_container;
 113             friend const_ring_container;
 114             friend typename ring_container::iterator;
 115             friend typename ring_container::const_iterator;
 116             friend typename const_ring_container::iterator;
 117             friend typename const_ring_container::const_iterator;
 118             friend class boost::iterator_core_access;
 119             typedef boost::intrusive::circular_list_algorithms<Ring_node_traits> algo;
 120             Ring* m_pNext;
 121             Ring* m_pPrev;
 122     };
 123
 124     template <typename value_type>
 125     inline Ring<value_type>::Ring( value_type* pObj )
 126         : m_pNext(this)
 127         , m_pPrev(this)
 128     {
 129         if( pObj )
 130         {
 131             algo::link_before(pObj, this);
 132         }
 133     }
 134
 135     template <typename value_type>
 136     inline void Ring<value_type>::MoveTo(value_type* pDestRing)
 137     {
 138         value_type* pThis = static_cast< value_type* >(this);
 139         unlink();
 140         // insert into "new"
 141         if (pDestRing)
 142         {
 143             algo::link_before(pDestRing, pThis);
 144         }
 145     }
 146
 147     /**
 148      * helper class that provides Svalue_typeL-style container iteration to the ring
 149      */
 150     template <typename value_type>
 151     class SAL_WARN_UNUSED RingContainer final
 152     {
 153         private:
 154             /** the item in the ring where iteration starts */
 155             value_type* m_pStart;
 156             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 157
 158         public:
 159             RingContainer( value_type* pRing ) : m_pStart(pRing) {};
 160             typedef RingIterator<value_type> iterator;
 161             typedef RingIterator<const value_type> const_iterator;
 162             /**
 163              * iterator access
 164              * @code
 165              * for(SwPaM& rCurrentPaM : pPaM->GetRingContainer())
 166              *     do_stuff(rCurrentPaM); // this gets called on every SwPaM in the same ring as pPaM
 167              * @endcode
 168              */
 169             iterator begin();
 170             iterator end();
 171             const_iterator begin() const;
 172             const_iterator end() const;
 173             /** @return the number of elements in the container */
 174             size_t size() const
 175                 { return std::distance(begin(), end()); }
 176             /**
 177              * Merges two ring containers. All item from both ring containers will
 178              * be in the same ring container in the end.
 179              * Note: The items of this ring container will be inserted just before
 180              * item pDestRing
 181              * @param pDestRing the container to merge this container with
 182              */
 183             void merge( RingContainer< value_type > aDestRing )
 184             {
 185                 // first check that we aren't merged already, swapping would
 186                 // actually un-merge in this case!
 187                 assert(m_pStart->m_pPrev != aDestRing.m_pStart);
 188                 assert(m_pStart != aDestRing.m_pStart->m_pPrev);
 189                 std::swap(*(&m_pStart->m_pPrev->m_pNext), *(&aDestRing.m_pStart->m_pPrev->m_pNext));
 190                 std::swap(*(&m_pStart->m_pPrev), *(&aDestRing.m_pStart->m_pPrev));
 191             }
 192     };
 193
 194     template <typename value_type>
 195     class RingIterator final : public boost::iterator_facade<
 196           RingIterator<value_type>
 197         , value_type
 198         , boost::forward_traversal_tag
 199         >
 200     {
 201         private:
 202             typedef typename std::remove_const<value_type>::type nonconst_value_type;
 203         public:
 204             RingIterator()
 205                 : m_pCurrent(nullptr)
 206                 , m_pStart(nullptr)
 207             {}
 208             explicit RingIterator(nonconst_value_type* pRing, bool bStart = true)
 209                 : m_pCurrent(nullptr)
 210                 , m_pStart(pRing)
 211             {
 212                 if(!bStart)
 213                     m_pCurrent = m_pStart;
 214             }
 215
 216         private:
 217             friend class boost::iterator_core_access;
 218             void increment()
 219                 { m_pCurrent = m_pCurrent ? m_pCurrent->GetNextInRing() : m_pStart->GetNextInRing(); }
 220             bool equal(RingIterator const& other) const
 221             {
 222                 // we never want to compare iterators from
 223                 // different rings or starting points
 224                 assert(m_pStart == other.m_pStart);
 225                 return m_pCurrent == other.m_pCurrent;
 226             }
 227             value_type& dereference() const
 228                 { return m_pCurrent ? *m_pCurrent : * m_pStart; }
 229             /**
 230              * value_type is:
 231              * - pointing to the current item in the iteration in general
 232              * - nullptr if on the first item (begin())
 233              * - m_pStart when beyond the last item (end())
 234              */
 235             nonconst_value_type* m_pCurrent;
 236             /** the first item of the iteration */
 237             nonconst_value_type* m_pStart;
 238     };
 239
 240     template <typename value_type>
 241     inline typename Ring<value_type>::ring_container Ring<value_type>::GetRingContainer()
 242         { return Ring<value_type>::ring_container(static_cast< value_type* >(this)); };
 243
 244     template <typename value_type>
 245     inline typename Ring<value_type>::const_ring_container Ring<value_type>::GetRingContainer() const
 246         { return Ring<value_type>::const_ring_container(static_cast< const_value_type* >(this)); };
 247
 248     template <typename value_type>
 249     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::begin()
 250         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 251
 252     template <typename value_type>
 253     inline typename RingContainer<value_type>::iterator RingContainer<value_type>::end()
 254         { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 255
 256     template <typename value_type>
 257     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::begin() const
 258         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart)); };
 259
 260     template <typename value_type>
 261     inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::end() const
 262         { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
 263 }
 264 #endif
 265
 266 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */