Line data Source code
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 79318026 : virtual ~Ring()
46 79318026 : { unlink(); };
47 : /** algo::unlink is buggy! don't call it directly! */
48 212739948 : void unlink()
49 : {
50 212739948 : algo::unlink(this);
51 212739948 : pNext = this; // don't leave pointers to old list behind!
52 212739948 : pPrev = this;
53 212739948 : }
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 66714020 : Ring()
75 : : pNext(this)
76 66714020 : , pPrev(this)
77 66714020 : { }
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 138466918 : value_type* GetNextInRing()
86 138466918 : { return static_cast<value_type *>(pNext); }
87 : /** @return the previous item in the ring container */
88 140 : value_type* GetPrevInRing()
89 140 : { return static_cast<value_type *>(pPrev); }
90 : /** @return the next item in the ring container */
91 153 : const_value_type* GetNextInRing() const
92 153 : { 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 61439696 : bool unique() const
98 61439696 : { 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 274179644 : static node_ptr get_next(const_node_ptr n) { return const_cast<node_ptr>(n)->pNext; };
108 341708046 : static void set_next(node_ptr n, node_ptr next) { n->pNext = next; };
109 277223997 : static node_ptr get_previous(const_node_ptr n) { return const_cast<node_ptr>(n)->pPrev; };
110 341708046 : 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 12604186 : inline Ring<value_type>::Ring( value_type* pObj )
132 : : pNext(this)
133 12604186 : , pPrev(this)
134 : {
135 12604186 : if( pObj )
136 : {
137 822 : algo::link_before(pObj, this);
138 : }
139 12604186 : }
140 :
141 : template <typename value_type>
142 133421922 : inline void Ring<value_type>::MoveTo(value_type* pDestRing)
143 : {
144 133421922 : value_type* pThis = static_cast< value_type* >(this);
145 133421922 : unlink();
146 : // insert into "new"
147 133421922 : if (pDestRing)
148 : {
149 64483227 : algo::link_before(pDestRing, pThis);
150 : }
151 133421922 : }
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 135806575 : 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 10 : size_t size() const
181 10 : { 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 2 : 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 2 : std::swap(*(&m_pStart->pPrev->pNext), *(&aDestRing.m_pStart->pPrev->pNext));
196 2 : std::swap(*(&m_pStart->pPrev), *(&aDestRing.m_pStart->pPrev));
197 2 : }
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 271613142 : explicit RingIterator(nonconst_value_type* pRing, bool bStart = true)
215 : : m_pCurrent(nullptr)
216 271613142 : , m_pStart(pRing)
217 : {
218 271613142 : if(!bStart)
219 135806571 : m_pCurrent = m_pStart;
220 271613142 : }
221 :
222 : private:
223 : friend class boost::iterator_core_access;
224 137482767 : void increment()
225 137482767 : { m_pCurrent = m_pCurrent ? m_pCurrent->GetNextInRing() : m_pStart->GetNextInRing(); }
226 273289338 : 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 273289338 : return m_pCurrent == other.m_pCurrent;
232 : }
233 137513208 : value_type& dereference() const
234 137513208 : { 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 135797718 : inline typename Ring<value_type>::ring_container Ring<value_type>::GetRingContainer()
248 135797718 : { return Ring<value_type>::ring_container(static_cast< value_type* >(this)); };
249 :
250 : template <typename value_type>
251 8857 : inline typename Ring<value_type>::const_ring_container Ring<value_type>::GetRingContainer() const
252 8857 : { return Ring<value_type>::const_ring_container(static_cast< const_value_type* >(this)); };
253 :
254 : template <typename value_type>
255 135806561 : inline typename RingContainer<value_type>::iterator RingContainer<value_type>::begin()
256 135806561 : { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart)); };
257 :
258 : template <typename value_type>
259 135806561 : inline typename RingContainer<value_type>::iterator RingContainer<value_type>::end()
260 135806561 : { return RingContainer<value_type>::iterator(const_cast< nonconst_value_type* >(m_pStart), false); };
261 :
262 : template <typename value_type>
263 10 : inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::begin() const
264 10 : { return RingContainer<value_type>::const_iterator(const_cast< nonconst_value_type* >(m_pStart)); };
265 :
266 : template <typename value_type>
267 10 : inline typename RingContainer<value_type>::const_iterator RingContainer<value_type>::end() const
268 10 : { 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: */
|
