1 #ifndef libjmmcg_core_intrusive_hpp
2 #define libjmmcg_core_intrusive_hpp
3
4 /******************************************************************************
5 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/intrusive.hpp 2086 2017-08-05 12:09:00Z jmmcg $
6 **
7 ** Copyright © 2011 by J.M.McGuiness, coder@hussar.me.uk
8 **
9 ** This library is free software; you can redistribute it and/or
10 ** modify it under the terms of the GNU Lesser General Public
11 ** License as published by the Free Software Foundation; either
12 ** version 2.1 of the License, or (at your option) any later version.
13 **
14 ** This library is distributed in the hope that it will be useful,
15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 ** Lesser General Public License for more details.
18 **
19 ** You should have received a copy of the GNU Lesser General Public
20 ** License along with this library; if not, write to the Free Software
21 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 */
23
24 #include "shared_ptr.hpp"
25
26 #include <algorithm>
27 #include <iterator>
28
29 namespace jmmcg { namespace intrusive {
30
31 namespace private_ {
32 template<class, class> class slist_iterator_internal;
33 }
34
35 template<class, class> class stack;
36 template<class, class> class slist;
37
38 /// Singly-linked intrusive node details. Inherit from this to provide the linkage structure and object-lifetime semantics of the list, which are specifically shared_ptr semantics.
39 /**
40 The use of the shared_ptr is very important: it solves the ABA problem that this implementation would otherwise suffer from.
41 */
42 template<
43 class LkT
44 >
45 class node_details_itf : virtual public sp_counter_itf_type<long> {
46 public:
47 using base_t=sp_counter_itf_type<long>;
48 using lock_traits=LkT;
49 using atomic_ctr_t=base_t;
50 using atomic_ptr_t=typename lock_traits::template atomic<node_details_itf *>;
51
52 atomic_ptr_t next;
53
54 virtual ~node_details_itf() noexcept(true) FORCE_INLINE {}
55
56 virtual tstring
57 to_string() const noexcept(false) FORCE_INLINE {
58 return "";
59 }
60
61 protected:
62 node_details_itf() noexcept(true) FORCE_INLINE
63 : next() {}
64 };
65
66 namespace private_ {
67
68 /// Hold the first node in the slist.
69 template<
70 class LkT
71 >
72 class node_details : public node_details_itf<LkT>, public sp_counter_type<typename node_details_itf<LkT>::atomic_ctr_t::value_type, typename node_details_itf<LkT>::lock_traits> {
73 public:
74 using base_t=node_details_itf<LkT>;
75 using base2_t=sp_counter_type<typename base_t::atomic_ctr_t::value_type, typename base_t::lock_traits>;
76 using atomic_ctr_t=typename base2_t::atomic_ctr_t;
77 using lock_traits=typename base_t::lock_traits;
78
79 constexpr node_details() noexcept(true) FORCE_INLINE
80 : base_t() {}
81 ~node_details() noexcept(true)=default;
82 void operator=(node_details const &)=delete;
83 void operator=(node_details &&)=delete;
84
85 tstring
86 to_string() const noexcept(false) FORCE_INLINE {
87 return base2_t::sp_to_string();
88 }
89 };
90
91 template<class V, class LkT> struct end;
92
93 /**
94 If you don't like the cut-down interface of this container, blame YAGNI & TDD.
95 */
96 template<class V, class LkT>
97 class slist_iterator_internal {
98 public:
99 using lock_traits=LkT;
100 typedef std::forward_iterator_tag iterator_category;
101 typedef std::ptrdiff_t difference_type;
102 typedef shared_ptr<V, lock_traits> value_type;
103 typedef shared_ptr<V, lock_traits> pointer;
104 typedef const shared_ptr<V, lock_traits> const_pointer;
105 typedef pointer & reference;
106 typedef const_pointer & const_reference;
107
108 typedef typename value_type::deleter_t deleter_t;
109 typedef typename value_type::ctr_type ctr_type;
110 typedef typename value_type::exception_type exception_type;
111
112 private:
113 using node_ptr_t=shared_ptr<node_details_itf<lock_traits>, lock_traits>;
114
115 BOOST_MPL_ASSERT((std::is_base_of<typename node_ptr_t::value_type, typename value_type::value_type>));
116
117 public:
118 explicit __stdcall slist_iterator_internal(const_reference n) noexcept(true) FORCE_INLINE
119 : node(n),
120 real_node(node.get().get() ? node->next : node.get()) {
121 assert(node.get().get() ? node->next==real_node.get() : true);
122 }
123 __stdcall slist_iterator_internal(slist_iterator_internal const &n) noexcept(true) FORCE_INLINE
124 : node(n.node),
125 real_node(node.get().get() ? node->next : node.get()) {
126 }
127
128 bool __fastcall operator==(slist_iterator_internal const &n) const noexcept(true) FORCE_INLINE {
129 if (node.get().get() && n.node.get().get()) {
130 return node->next==n.node->next;
131 } else if (!node.get() && !n.node.get()) {
132 return true;
133 } else if (node.get().get() && !n.node.get()) {
134 return node->next==n.node.get();
135 } else {
136 return false;
137 }
138 }
139 bool __fastcall operator!=(slist_iterator_internal const &n) const noexcept(true) FORCE_INLINE {
140 return !operator==(n);
141 }
142 bool __fastcall operator==(end<V, LkT> const &n) const noexcept(true) FORCE_INLINE;
143
144 slist_iterator_internal &__fastcall operator++() noexcept(true) FORCE_INLINE {
145 const typename node_ptr_t::atomic_ptr_t next_real_node(real_node.get().get() ? real_node->next : typename node_ptr_t::atomic_ptr_t());
146 node=real_node;
147 real_node=node_ptr_t(next_real_node);
148 assert(node.get().get() ? node->next==real_node.get() : true);
149 return *this;
150 }
151 slist_iterator_internal __fastcall operator++(int) noexcept(true) FORCE_INLINE {
152 const slist_iterator_internal tmp(*this);
153 ++*this;
154 return tmp;
155 }
156 pointer __fastcall operator*() noexcept(true) FORCE_INLINE {
157 return pointer(real_node);
158 }
159 const_pointer __fastcall operator*() const noexcept(true) FORCE_INLINE {
160 return const_pointer(real_node);
161 }
162 pointer __fastcall operator->() noexcept(true) FORCE_INLINE {
163 return pointer(real_node);
164 }
165 const_pointer __fastcall operator->() const noexcept(true) FORCE_INLINE {
166 return const_pointer(real_node);
167 }
168
169 friend tostream &
170 operator<<(tostream &os, slist_iterator_internal const &i) {
171 os<<"node="<<i.node
172 <<", real_node="<<i.real_node;
173 return os;
174 }
175
176 private:
177 friend class stack<V, LkT>;
178 friend class slist<V, LkT>;
179
180 /**
181 Note how, like slist::penultimate_, node is one-before-the-node-we-want, which allows us to slist::erase() in constant time.
182 */
183 node_ptr_t node;
184 node_ptr_t real_node;
185 };
186 template<class V, class LkT>
187 class slist_iterator_internal<V const, LkT> {
188 public:
189 using lock_traits=LkT;
190 typedef std::forward_iterator_tag iterator_category;
191 typedef std::ptrdiff_t difference_type;
192 typedef shared_ptr<V, lock_traits> value_type;
193 typedef shared_ptr<V, lock_traits> pointer;
194 typedef const shared_ptr<V, lock_traits> const_pointer;
195 typedef pointer & reference;
196 typedef const_pointer & const_reference;
197
198 typedef typename value_type::deleter_t deleter_t;
199 typedef typename value_type::ctr_type ctr_type;
200 typedef typename value_type::exception_type exception_type;
201
202 private:
203 using node_ptr_t=shared_ptr<node_details_itf<lock_traits>, lock_traits>;
204
205 BOOST_MPL_ASSERT((std::is_base_of<typename node_ptr_t::value_type, typename value_type::value_type>));
206
207 public:
208 explicit __stdcall slist_iterator_internal(const_reference n) noexcept(true) FORCE_INLINE
209 : node(n), real_node(node.get().get() ? node->next : node.get()) {
210 assert(node.get().get() ? node->next==real_node.get().get() : true);
211 }
212 explicit __stdcall slist_iterator_internal(node_ptr_t n) noexcept(true) FORCE_INLINE
213 : node(n), real_node(node.get().get() ? node->next : node.get()) {
214 assert(node.get().get() ? node->next==real_node.get() : true);
215 }
216 __stdcall slist_iterator_internal(slist_iterator_internal const &n) noexcept(true) FORCE_INLINE
217 : node(n.node), real_node(node.get().get() ? node->next : node.get()) {
218 }
219
220 bool __fastcall operator==(slist_iterator_internal const &n) const noexcept(true) FORCE_INLINE {
221 if (node.get().get() && n.node.get().get()) {
222 return node->next==n.node->next;
223 } else if (!node.get() && !n.node.get()) {
224 return true;
225 } else if (node.get().get() && !n.node.get()) {
226 return node->next==n.node.get();
227 } else {
228 return false;
229 }
230 }
231 bool __fastcall operator!=(slist_iterator_internal const &n) const noexcept(true) FORCE_INLINE {
232 return !operator==(n);
233 }
234
235 slist_iterator_internal &__fastcall operator++() noexcept(true) FORCE_INLINE {
236 const typename node_ptr_t::atomic_ptr_t next_real_node(real_node.get().get() ? real_node->next : typename node_ptr_t::atomic_ptr_t());
237 node=real_node;
238 real_node=node_ptr_t(next_real_node);
239 assert(node.get().get() ? node->next==real_node.get() : true);
240 return *this;
241 }
242 slist_iterator_internal __fastcall operator++(int) noexcept(true) FORCE_INLINE {
243 const slist_iterator_internal tmp(*this);
244 ++*this;
245 return tmp;
246 }
247 const_pointer __fastcall operator*() const noexcept(true) FORCE_INLINE {
248 return const_pointer(real_node);
249 }
250 const_pointer __fastcall operator->() const noexcept(true) FORCE_INLINE {
251 return const_pointer(real_node);
252 }
253
254 friend tostream &
255 operator<<(tostream &os, slist_iterator_internal const &i) {
256 os<<"node="<<i.node
257 <<", real_node="<<i.real_node;
258 return os;
259 }
260
261 private:
262 friend class stack<V, LkT>;
263 friend class slist<V, LkT>;
264
265 /**
266 Note how, like slist::penultimate_, node is one-before-the-node-we-want, which allows us to slist::erase() in constant time.
267 */
268 node_ptr_t node;
269 node_ptr_t real_node;
270 };
271
272 template<class V, class LkT>
273 struct end : public slist_iterator_internal<V, LkT> {
274 typedef slist_iterator_internal<V, LkT> base_t;
275 typedef typename base_t::value_type value_type;
276
277 constexpr __stdcall end() FORCE_INLINE
278 : base_t(value_type()) {
279 }
280 constexpr bool __fastcall operator==(end const &) const noexcept(true) FORCE_INLINE {
281 return true;
282 }
283 constexpr bool __fastcall operator!=(end const &n) const noexcept(true) FORCE_INLINE {
284 return !operator==(n);
285 }
286 };
287
288 template<class V, class LkT> inline bool FORCE_INLINE
289 slist_iterator_internal<V, LkT>::operator==(end<V, LkT> const &n) const noexcept(true) {
290 return node.get().get() ? node->next==n.node.get().get() : !node.get();
291 }
292
293 }
294
295 /// A "good enough for PPD" implementation of a singly-linked, hybrid, intrusive, pointer-based stack.
296 /**
297 When inserting a node, no memory allocations are required, which is good in a multi-threading environment as it reduces calls to any memory allocator.
298 If you don't like the cut-down interface of this container, blame YAGNI & TDD.
299
300 \see boost::stack, std::stack
301 */
302 template<
303 class V, ///< The type of the contained objects, which must be intrusive, and publicly inherit from node_details.
304 class LkT ///< The lock_traits that providing the (potentially) atomic operations to be used upon pointers to the value_type.
305 >
306 class stack : protected non_copyable {
307 protected:
308 using node_details_t=private_::node_details<LkT>;
309 using atomic_ptr_t=typename node_details_t::base_t::atomic_ptr_t;
310
311 public:
312 using lock_traits=typename node_details_t::lock_traits;
313 typedef std::size_t size_type;
314 typedef shared_ptr<V, LkT> value_type;
315 typedef typename lock_traits::template atomic_counter_type<unsigned long> size_ctr_t;
316 typedef private_::slist_iterator_internal<V, LkT> iterator;
317 typedef private_::slist_iterator_internal<V const, LkT> const_iterator;
318 typedef typename iterator::difference_type difference_type;
319 typedef typename iterator::pointer pointer;
320 typedef typename iterator::reference reference;
321 typedef typename const_iterator::const_pointer const_pointer;
322 typedef typename const_iterator::const_reference const_reference;
323
324 typedef typename value_type::deleter_t deleter_t;
325 typedef typename value_type::ctr_type ctr_type;
326 typedef typename value_type::exception_type exception_type;
327 /**
328 To assist in allowing compile-time computation of the algorithmic order of the threading model.
329 */
330 static constexpr ppd::generic_traits::memory_access_modes memory_access_mode=(
331 atomic_ptr_t::memory_access_mode==ppd::generic_traits::memory_access_modes::crew_memory_access
332 && size_ctr_t::memory_access_mode==ppd::generic_traits::memory_access_modes::crew_memory_access
333 ? ppd::generic_traits::memory_access_modes::crew_memory_access
334 : ppd::generic_traits::memory_access_modes::erew_memory_access
335 );
336
337 BOOST_MPL_ASSERT((std::is_base_of<typename node_details_t::base_t, typename value_type::value_type>));
338
339 __stdcall stack() noexcept(true) FORCE_INLINE;
340 stack(stack &&) noexcept(true) FORCE_INLINE;
341 /**
342 Algorithmic complexity: O(n)
343 */
344 virtual __stdcall ~stack() noexcept(true) FORCE_INLINE;
345
346 /**
347 Algorithmic complexity: O(1)
348 */
349 iterator __fastcall begin() noexcept(true) FORCE_INLINE;
350 /**
351 Algorithmic complexity: O(1)
352 */
353 const_iterator __fastcall begin() const noexcept(true) FORCE_INLINE;
354 /**
355 Algorithmic complexity: O(1)
356 */
357 iterator __fastcall end() noexcept(true) FORCE_INLINE;
358 /**
359 Algorithmic complexity: O(1)
360 */
361 const_iterator __fastcall end() const noexcept(true) FORCE_INLINE;
362 /// Return true if the container is empty, false otherwise.
363 /**
364 Algorithmic complexity: O(1)
365
366 \return True if the container is empty, false otherwise.
367 */
368 bool __fastcall empty() const noexcept(true) FORCE_INLINE;
369 /// Atomically return the number of elements in the container.
370 /**
371 Algorithmic complexity: O(1)
372
373 \return The number of elements in the container.
374 */
375 size_type __fastcall size() const noexcept(true) FORCE_INLINE;
376 /// Non-atomically return the number of elements in the container.
377 /**
378 Algorithmic complexity: O(n)
379 Mainly used for verifying list integrity in testing. Not much use for anything else.
380
381 \return The number of elements in the container.
382 */
383 size_type __fastcall size_n() const noexcept(true) FORCE_INLINE;
384 /// Remove the element from the container.
385 /**
386 Algorithmic complexity: O(1)
387
388 \param v Iterator to the element to be removed.
389 */
390 void __fastcall erase(iterator v) noexcept(true) FORCE_INLINE;
391 /// Non-atomically remove the element from the container.
392 /**
393 Algorithmic complexity: O(n).
394
395 \param v The value equivalent to the element to be removed.
396 \return The number of elements erased from the list, at most 1.
397 */
398 size_type __fastcall erase(const_reference v) noexcept(true) FORCE_INLINE;
399 /// Remove all of the elements from the container.
400 /**
401 Calls the dtor for each element within the container.
402 Algorithmic complexity: O(n)
403 */
404 void __fastcall clear() noexcept(true) FORCE_INLINE;
405 /**
406 Algorithmic complexity: O(1)
407
408 \return The top of the stack.
409 */
410 value_type __fastcall top() noexcept(true) FORCE_INLINE;
411 /**
412 Algorithmic complexity: O(1)
413
414 \return The top of the stack.
415 */
416 value_type __fastcall top() const noexcept(true) FORCE_INLINE;
417 /**
418 Algorithmic complexity: O(1)
419
420 \param v The element to be added.
421 */
422 void __fastcall push(value_type const &v) noexcept(true) FORCE_INLINE;
423 /**
424 Algorithmic complexity: O(1)
425
426 \param v The element to be added.
427 */
428 void __fastcall push(value_type &&v) noexcept(true) FORCE_INLINE;
429 /**
430 Algorithmic complexity: O(1)
431
432 \param v The element to be added.
433 */
434 void __fastcall push_front(value_type const &v) noexcept(true) FORCE_INLINE;
435 /**
436 Algorithmic complexity: O(1)
437
438 \param v The element to be added.
439 */
440 void __fastcall push_front(value_type &&v) noexcept(true) FORCE_INLINE;
441 /**
442 Algorithmic complexity: O(1)
443 */
444 void __fastcall pop() noexcept(true) FORCE_INLINE;
445 /**
446 Algorithmic complexity: O(1)
447 */
448 void __fastcall pop_front() noexcept(true) FORCE_INLINE;
449 /**
450 Algorithmic complexity: O(1)
451 This method assumes that only one thread is popping at a time, and that the container is not empty.
452 */
453 value_type __fastcall pop_top_nochk() noexcept(true) FORCE_INLINE;
454
455 protected:
456 mutable node_details_t prefront_;
457 size_ctr_t size_ctr;
458
459 typename node_details_t::base_t::atomic_ptr_t
460 unlink_node(typename node_details_t::base_t::atomic_ptr_t &node) noexcept(true) FORCE_INLINE;
461
462 /**
463 Algorithmic complexity: O(1)
464
465 \param i The iterator immediately after which the element should be added.
466 \param v The element to be added.
467
468 \see push()
469 */
470 static void insert(typename node_details_t::base_t::atomic_ptr_t i, value_type v) noexcept(true) FORCE_INLINE;
471 void insert(value_type v) noexcept(true) FORCE_INLINE;
472 };
473
474 /// A "good enough for PPD" implementation of a singly-linked, hybrid, intrusive, pointer-based list.
475 /**
476 When inserting a node, no memory allocations are required, which is good in a multi-threading environment as it reduces calls to any memory allocator.
477 If you don't like the cut-down interface of this container, blame YAGNI & TDD.
478
479 \see boost::instrusive::slist, boost::slist, std::list
480 */
481 template<
482 class V, ///< The type of the contained objects, which must be intrusive, and publicly inherit from node_details.
483 class LkT ///< The lock_traits that providing the (potentially) atomic operations to be used upon pointers to the value_type.
484 >
485 class slist : public stack<V, LkT> {
486 public:
487 typedef stack<V, LkT> base_t;
488 typedef typename base_t::value_type value_type;
489 typedef typename base_t::lock_traits lock_traits;
490 typedef typename base_t::size_ctr_t size_ctr_t;
491 typedef typename base_t::size_type size_type;
492 typedef typename base_t::iterator iterator;
493 typedef typename base_t::const_iterator const_iterator;
494 typedef typename base_t::difference_type difference_type;
495 typedef typename base_t::pointer pointer;
496 typedef typename base_t::reference reference;
497 typedef typename base_t::const_pointer const_pointer;
498 typedef typename base_t::const_reference const_reference;
499
500 typedef typename base_t::deleter_t deleter_t;
501 typedef typename base_t::ctr_type ctr_type;
502 typedef typename base_t::exception_type exception_type;
503
504 using base_t::erase;
505
506 __stdcall slist() noexcept(true) FORCE_INLINE;
507 slist(slist &&) noexcept(true) FORCE_INLINE;
508 /**
509 Algorithmic complexity: O(n)
510 */
511 __stdcall ~slist() noexcept(true) FORCE_INLINE;
512
513 /// Find if the element is within the container.
514 /**
515 Algorithmic complexity: O(n).
516
517 \param v The element to be found.
518 \return The iterator to the element within the container, or end() otherwise.
519 */
520 iterator __fastcall find(const_reference v) noexcept(true) FORCE_INLINE;
521 /// Find if the element is within the container.
522 /**
523 Algorithmic complexity: O(n).
524
525 \param v The element to be found.
526 \return The iterator to the element within the container, or end() otherwise.
527 */
528 const_iterator __fastcall find(const_reference v) const noexcept(true) FORCE_INLINE;
529 /// Remove the element from the container.
530 /**
531 Algorithmic complexity: O(n).
532
533 \param v The value equivalent to the element to be removed.
534 \return The number of elements erased from the list, at most 1.
535 */
536 size_type __fastcall erase(const_reference v) noexcept(true) FORCE_INLINE;
537 /**
538 Algorithmic complexity: O(1)
539 */
540 value_type __fastcall front() noexcept(true) FORCE_INLINE;
541 /**
542 Algorithmic complexity: O(1)
543
544 \return The front of the list.
545 */
546 value_type __fastcall front() const noexcept(true) FORCE_INLINE;
547 /**
548 Algorithmic complexity: O(1)
549 */
550 value_type __fastcall back() noexcept(true) FORCE_INLINE;
551 /**
552 Algorithmic complexity: O(1)
553 */
554 value_type __fastcall back() const noexcept(true) FORCE_INLINE;
555 /**
556 Algorithmic complexity: O(1)
557
558 \param v The element to be added.
559 */
560 void __fastcall push_front(value_type const &v) noexcept(true) FORCE_INLINE;
561 /**
562 Algorithmic complexity: O(1)
563
564 \param v The element to be added.
565 */
566 void __fastcall push_front(value_type &&v) noexcept(true) FORCE_INLINE;
567 /**
568 Algorithmic complexity: O(1)
569 */
570 void __fastcall pop_front() noexcept(true) FORCE_INLINE;
571 /**
572 Note that this is NOT atomic! So NOT thread-safe.
573 Algorithmic complexity: O(1)
574
575 \param v The element to be added.
576 */
577 void __fastcall push_back(value_type const &v) noexcept(true) FORCE_INLINE;
578 /**
579 Note that this is NOT atomic! So NOT thread-safe.
580 Algorithmic complexity: O(1)
581
582 \param v The element to be added.
583 */
584 void __fastcall push_back(value_type &&v) noexcept(true) FORCE_INLINE;
585
586 /**
587 Algorithmic complexity: O(n)
588
589 \return True if the internal iterators are consistent.
590 */
591 bool penultimate_reachable_from_prefront() const noexcept(true) FORCE_INLINE;
592
593 private:
594 typedef typename base_t::node_details_t node_details_t;
595 /**
596 Note that penultimate_ is not "end()", but the penultimate node in the container, which allows us to push_back() in constant time.
597
598 \see end()
599 */
600 typename node_details_t::base_t::atomic_ptr_t penultimate_;
601
602 static void move_penultimate(typename node_details_t::base_t::atomic_ptr_t &ptr) noexcept(true) FORCE_INLINE;
603 };
604
605 } }
606
607 #include "intrusive_impl.hpp"
608
609 #endif