include/boost/corosio/detail/intrusive.hpp

100.0% Lines (120 / 120) 23.8% Branches (201 / 844) 89.5% Functions (213 / 238, 2 excl)

[ ] prev/next file n p prev/next uncovered line

intrusive.hpp

f(x) Functions (240)

Function Calls Lines Branches Blocks

Line	Branch	Hits	Source Code
1			//
2			// Copyright (c) 2025 Vinnie Falco ([email protected])
3			//
4			// Distributed under the Boost Software License, Version 1.0. (See accompanying
5			// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6			//
7			// Official repository: https://github.com/cppalliance/corosio
8			//
9
10			#ifndef BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
11			#define BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
12
13			namespace boost::corosio::detail {
14
15			/** An intrusive doubly linked list.
16
17			This container provides O(1) push and pop operations for
18			elements that derive from @ref node. Elements are not
19			copied or moved; they are linked directly into the list.
20
21			@tparam T The element type. Must derive from `intrusive_list<T>::node`.
22			*/
23			template<class T>
24			class intrusive_list
25			{
26			public:
27			/** Base class for list elements.
28
29			Derive from this class to make a type usable with
30			@ref intrusive_list. The `next_` and `prev_` pointers
31			are private and accessible only to the list.
32			*/
33		51687x	class node
34			{
35			friend class intrusive_list;
36
37			private:
38		51687x	T* next_ = nullptr;
39		51687x	T* prev_ = nullptr;
40			};
41
42			private:
43		168851x	T* head_ = nullptr;
44		168851x	T* tail_ = nullptr;
45
46			public:
47		506553x	intrusive_list() = default;
48
49		2x	intrusive_list(intrusive_list&& other) noexcept
50		1x	: head_(other.head_)
51		1x	, tail_(other.tail_)
52		1x	{
53		1x	other.head_ = nullptr;
54		1x	other.tail_ = nullptr;
55		2x	}
56
57			intrusive_list(intrusive_list const&) = delete;
58			intrusive_list& operator=(intrusive_list const&) = delete;
59			intrusive_list& operator=(intrusive_list&&) = delete;
60
61		22x	bool empty() const noexcept
62			{
63		22x	return head_ == nullptr;
64			}
65
66			/// Peek at the head element without removing it.
67		6x	T* front() const noexcept
68			{
69		6x	return head_;
70			}
71
72		45485x	void push_front(T* w) noexcept
73			{
74	6/34 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 29923 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 3042 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 10882 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 1454 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 183 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	45485x	auto* n = static_cast<node*>(w);
75		45485x	n->prev_ = nullptr;
76		45485x	n->next_ = head_;
77	10/34 ✓ Branch 0 taken 15352 times. ✓ Branch 1 taken 14572 times. ✓ Branch 2 taken 323 times. ✓ Branch 3 taken 2719 times. ✓ Branch 4 taken 6820 times. ✓ Branch 5 taken 4062 times. ✓ Branch 6 taken 80 times. ✓ Branch 7 taken 1374 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✓ Branch 24 taken 47 times. ✓ Branch 25 taken 136 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	45485x	if (head_)
78	5/34 ✗ Branch 0 not taken. ✓ Branch 1 taken 15352 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 323 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 6820 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 80 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 47 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	22622x	static_cast<node*>(head_)->prev_ = w;
79			else
80		22863x	tail_ = w;
81		45485x	head_ = w;
82		45485x	}
83
84		75378x	void push_back(T* w) noexcept
85			{
86	6/34 ✓ Branch 0 taken 3 times. ✓ Branch 1 taken 48352 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 3470 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 11718 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 1870 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 187 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	75378x	auto* n = static_cast<node*>(w);
87		75378x	n->next_ = nullptr;
88		75378x	n->prev_ = tail_;
89	12/36 ✓ Branch 0 taken 18159 times. ✓ Branch 1 taken 10860 times. ✓ Branch 2 taken 20767 times. ✓ Branch 3 taken 8852 times. ✓ Branch 4 taken 442 times. ✓ Branch 5 taken 2524 times. ✓ Branch 6 taken 9001 times. ✓ Branch 7 taken 2716 times. ✓ Branch 8 taken 434 times. ✓ Branch 9 taken 1436 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✗ Branch 25 not taken. ✓ Branch 26 taken 50 times. ✓ Branch 27 taken 137 times. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken. ✗ Branch 34 not taken. ✗ Branch 35 not taken.	75378x	if (tail_)
90	7/40 ✗ Branch 0 not taken. ✗ Branch 0 not taken. ✓ Branch 1 taken 15450 times. ✓ Branch 1 taken 20525 times. ✗ Branch 2 not taken. ✗ Branch 2 not taken. ✓ Branch 3 taken 242 times. ✓ Branch 3 taken 442 times. ✗ Branch 4 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 5 taken 9001 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 434 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 50 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	48853x	static_cast<node*>(tail_)->next_ = w;
91			else
92		26525x	head_ = w;
93		75378x	tail_ = w;
94		75378x	}
95
96		3x	void splice_back(intrusive_list& other) noexcept
97			{
98	2/2 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 2 times.	3x	if (other.empty())
99		1x	return;
100	2/2 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 1 time.	2x	if (tail_)
101			{
102		1x	static_cast<node*>(tail_)->next_ = other.head_;
103		1x	static_cast<node*>(other.head_)->prev_ = tail_;
104		1x	tail_ = other.tail_;
105		1x	}
106			else
107			{
108		1x	head_ = other.head_;
109		1x	tail_ = other.tail_;
110			}
111		2x	other.head_ = nullptr;
112		2x	other.tail_ = nullptr;
113		3x	}
114
115		243181x	T* pop_front() noexcept
116			{
117	12/36 ✓ Branch 0 taken 11577 times. ✓ Branch 1 taken 168532 times. ✓ Branch 2 taken 28643 times. ✓ Branch 3 taken 8249 times. ✓ Branch 4 taken 2539 times. ✓ Branch 5 taken 3631 times. ✓ Branch 6 taken 10882 times. ✓ Branch 7 taken 3660 times. ✓ Branch 8 taken 1454 times. ✓ Branch 9 taken 3469 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✗ Branch 25 not taken. ✓ Branch 26 taken 183 times. ✓ Branch 27 taken 362 times. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken. ✗ Branch 34 not taken. ✗ Branch 35 not taken.	243181x	if (!head_)
118		187903x	return nullptr;
119		55278x	T* w = head_;
120	6/34 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 29942 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 3043 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 10883 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 1454 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 183 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	55278x	head_ = static_cast<node*>(head_)->next_;
121	12/36 ✓ Branch 0 taken 3824 times. ✓ Branch 1 taken 7753 times. ✓ Branch 2 taken 14485 times. ✓ Branch 3 taken 14158 times. ✓ Branch 4 taken 81 times. ✓ Branch 5 taken 2458 times. ✓ Branch 6 taken 6820 times. ✓ Branch 7 taken 4062 times. ✓ Branch 8 taken 80 times. ✓ Branch 9 taken 1374 times. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✗ Branch 25 not taken. ✓ Branch 26 taken 47 times. ✓ Branch 27 taken 136 times. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken. ✗ Branch 34 not taken. ✗ Branch 35 not taken.	55278x	if (head_)
122	7/40 ✗ Branch 0 not taken. ✗ Branch 0 not taken. ✓ Branch 1 taken 1118 times. ✓ Branch 1 taken 14243 times. ✗ Branch 2 not taken. ✗ Branch 2 not taken. ✓ Branch 3 taken 242 times. ✓ Branch 3 taken 81 times. ✗ Branch 4 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 5 taken 6820 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 80 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 47 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	25337x	static_cast<node*>(head_)->prev_ = nullptr;
123			else
124		29941x	tail_ = nullptr;
125			// Defensive: clear stale linkage so remove() on a
126			// popped node cannot corrupt the list.
127	5/34 ✗ Branch 0 not taken. ✓ Branch 1 taken 29943 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 3043 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 10883 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 1454 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 183 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	55278x	auto* n = static_cast<node*>(w);
128		55278x	n->next_ = nullptr;
129		55278x	n->prev_ = nullptr;
130		55278x	return w;
131		243181x	}
132
133			/** Unlink @p w if it is a member of this list.
134
135			@pre @p w is either a genuine member of `*this` list, or is
136			fully detached (not linked in any `intrusive_list<T>`,
137			including a different instance over the same `T`). This is
138			not a membership test: `T::node` holds one shared `next_`/
139			`prev_` pair regardless of which list currently owns it, so a
140			node actually linked in a different list looks "not detached"
141			here and would be spliced out using this list's `head_`/
142			`tail_` for the boundary cases — corrupting both lists. A
143			caller that cannot rule that out needs its own bookkeeping
144			(e.g. a flag for which list currently owns the node) before
145			calling this.
146
147			@return True if @p w was linked in and has now been removed;
148			false if it was already detached (e.g. a reentrant call from
149			a self-referential keepalive dropping during the same
150			teardown that already popped it elsewhere). Callers that gate
151			a one-time action (recycling, deleting) on actually having
152			removed something rely on this to make that action idempotent.
153			*/
154		65586x	bool remove(T* w) noexcept
155			{
156	6/34 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 48338 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 3469 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 11717 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 1870 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 187 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	65586x	auto* n = static_cast<node*>(w);
157			// Already detached — nothing to do.
158	27/136 ✓ Branch 0 taken 23316 times. ✓ Branch 1 taken 25025 times. ✓ Branch 2 taken 12374 times. ✓ Branch 3 taken 10942 times. ✓ Branch 4 taken 2 times. ✓ Branch 5 taken 12372 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 2 times. ✓ Branch 8 taken 2870 times. ✓ Branch 9 taken 599 times. ✓ Branch 10 taken 2785 times. ✓ Branch 11 taken 85 times. ✗ Branch 12 not taken. ✓ Branch 13 taken 2785 times. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✓ Branch 16 taken 4645 times. ✓ Branch 17 taken 7072 times. ✓ Branch 18 taken 2716 times. ✓ Branch 19 taken 1929 times. ✗ Branch 20 not taken. ✓ Branch 21 taken 2716 times. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✓ Branch 24 taken 1520 times. ✓ Branch 25 taken 350 times. ✓ Branch 26 taken 1436 times. ✓ Branch 27 taken 84 times. ✗ Branch 28 not taken. ✓ Branch 29 taken 1436 times. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken. ✗ Branch 34 not taken. ✗ Branch 35 not taken. ✗ Branch 36 not taken. ✗ Branch 37 not taken. ✗ Branch 38 not taken. ✗ Branch 39 not taken. ✗ Branch 40 not taken. ✗ Branch 41 not taken. ✗ Branch 42 not taken. ✗ Branch 43 not taken. ✗ Branch 44 not taken. ✗ Branch 45 not taken. ✗ Branch 46 not taken. ✗ Branch 47 not taken. ✗ Branch 48 not taken. ✗ Branch 49 not taken. ✗ Branch 50 not taken. ✗ Branch 51 not taken. ✗ Branch 52 not taken. ✗ Branch 53 not taken. ✗ Branch 54 not taken. ✗ Branch 55 not taken. ✗ Branch 56 not taken. ✗ Branch 57 not taken. ✗ Branch 58 not taken. ✗ Branch 59 not taken. ✗ Branch 60 not taken. ✗ Branch 61 not taken. ✗ Branch 62 not taken. ✗ Branch 63 not taken. ✗ Branch 64 not taken. ✗ Branch 65 not taken. ✗ Branch 66 not taken. ✗ Branch 67 not taken. ✗ Branch 68 not taken. ✗ Branch 69 not taken. ✗ Branch 70 not taken. ✗ Branch 71 not taken. ✗ Branch 72 not taken. ✗ Branch 73 not taken. ✗ Branch 74 not taken. ✗ Branch 75 not taken. ✗ Branch 76 not taken. ✗ Branch 77 not taken. ✗ Branch 78 not taken. ✗ Branch 79 not taken. ✗ Branch 80 not taken. ✗ Branch 81 not taken. ✗ Branch 82 not taken. ✗ Branch 83 not taken. ✗ Branch 84 not taken. ✗ Branch 85 not taken. ✗ Branch 86 not taken. ✗ Branch 87 not taken. ✗ Branch 88 not taken. ✗ Branch 89 not taken. ✗ Branch 90 not taken. ✗ Branch 91 not taken. ✗ Branch 92 not taken. ✗ Branch 93 not taken. ✗ Branch 94 not taken. ✗ Branch 95 not taken. ✓ Branch 96 taken 186 times. ✓ Branch 97 taken 1 time. ✓ Branch 98 taken 137 times. ✓ Branch 99 taken 49 times. ✗ Branch 100 not taken. ✓ Branch 101 taken 137 times. ✗ Branch 102 not taken. ✗ Branch 103 not taken. ✗ Branch 104 not taken. ✗ Branch 105 not taken. ✗ Branch 106 not taken. ✗ Branch 107 not taken. ✗ Branch 108 not taken. ✗ Branch 109 not taken. ✗ Branch 110 not taken. ✗ Branch 111 not taken. ✗ Branch 112 not taken. ✗ Branch 113 not taken. ✗ Branch 114 not taken. ✗ Branch 115 not taken. ✗ Branch 116 not taken. ✗ Branch 117 not taken. ✗ Branch 118 not taken. ✗ Branch 119 not taken. ✗ Branch 120 not taken. ✗ Branch 121 not taken. ✗ Branch 122 not taken. ✗ Branch 123 not taken. ✗ Branch 124 not taken. ✗ Branch 125 not taken. ✗ Branch 126 not taken. ✗ Branch 127 not taken. ✗ Branch 128 not taken. ✗ Branch 129 not taken. ✗ Branch 130 not taken. ✗ Branch 131 not taken. ✗ Branch 132 not taken. ✗ Branch 133 not taken. ✗ Branch 134 not taken. ✗ Branch 135 not taken.	65586x	if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
159		2x	return false;
160	10/34 ✓ Branch 0 taken 15164 times. ✓ Branch 1 taken 33175 times. ✓ Branch 2 taken 91 times. ✓ Branch 3 taken 3378 times. ✓ Branch 4 taken 3860 times. ✓ Branch 5 taken 7857 times. ✓ Branch 6 taken 93 times. ✓ Branch 7 taken 1777 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✓ Branch 24 taken 50 times. ✓ Branch 25 taken 137 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	65582x	if (n->prev_)
161	5/34 ✗ Branch 0 not taken. ✓ Branch 1 taken 15163 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 91 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 3860 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 93 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 50 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	19258x	static_cast<node*>(n->prev_)->next_ = n->next_;
162			else
163		46324x	head_ = n->next_;
164	10/34 ✓ Branch 0 taken 25026 times. ✓ Branch 1 taken 23313 times. ✓ Branch 2 taken 599 times. ✓ Branch 3 taken 2870 times. ✓ Branch 4 taken 7072 times. ✓ Branch 5 taken 4645 times. ✓ Branch 6 taken 350 times. ✓ Branch 7 taken 1520 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✓ Branch 24 taken 1 time. ✓ Branch 25 taken 186 times. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	65582x	if (n->next_)
165	5/34 ✗ Branch 0 not taken. ✓ Branch 1 taken 25024 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 599 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 7072 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 350 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 17 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✗ Branch 22 not taken. ✗ Branch 23 not taken. ✗ Branch 24 not taken. ✓ Branch 25 taken 1 time. ✗ Branch 26 not taken. ✗ Branch 27 not taken. ✗ Branch 28 not taken. ✗ Branch 29 not taken. ✗ Branch 30 not taken. ✗ Branch 31 not taken. ✗ Branch 32 not taken. ✗ Branch 33 not taken.	33048x	static_cast<node*>(n->next_)->prev_ = n->prev_;
166			else
167		32534x	tail_ = n->prev_;
168		65582x	n->next_ = nullptr;
169		65582x	n->prev_ = nullptr;
170		65582x	return true;
171		65584x	}
172
173			/// Invoke @p f for each element in the list.
174			template<class F>
175		12634x	void for_each(F f)
176			{
177	36/132 ✓ Branch 0 taken 7454 times. ✓ Branch 1 taken 3101 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 7451 times. ✓ Branch 4 taken 7451 times. ✓ Branch 5 taken 3099 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 7451 times. ✓ Branch 8 taken 459 times. ✓ Branch 9 taken 1776 times. ✗ Branch 10 not taken. ✓ Branch 11 taken 459 times. ✓ Branch 12 taken 429 times. ✓ Branch 13 taken 1064 times. ✗ Branch 14 not taken. ✓ Branch 15 taken 429 times. ✓ Branch 16 taken 836 times. ✓ Branch 17 taken 679 times. ✗ Branch 18 not taken. ✓ Branch 19 taken 836 times. ✓ Branch 20 taken 836 times. ✓ Branch 21 taken 679 times. ✗ Branch 22 not taken. ✓ Branch 23 taken 836 times. ✓ Branch 24 taken 417 times. ✓ Branch 25 taken 1013 times. ✗ Branch 26 not taken. ✓ Branch 27 taken 417 times. ✓ Branch 28 taken 417 times. ✓ Branch 29 taken 1013 times. ✗ Branch 30 not taken. ✓ Branch 31 taken 417 times. ✓ Branch 32 taken 1 time. ✓ Branch 33 taken 1 time. ✗ Branch 34 not taken. ✓ Branch 35 taken 1 time. ✓ Branch 36 taken 1 time. ✓ Branch 37 taken 1 time. ✗ Branch 38 not taken. ✓ Branch 39 taken 1 time. ✗ Branch 40 not taken. ✗ Branch 41 not taken. ✗ Branch 42 not taken. ✗ Branch 43 not taken. ✗ Branch 44 not taken. ✗ Branch 45 not taken. ✗ Branch 46 not taken. ✗ Branch 47 not taken. ✗ Branch 48 not taken. ✗ Branch 49 not taken. ✗ Branch 50 not taken. ✗ Branch 51 not taken. ✗ Branch 52 not taken. ✗ Branch 53 not taken. ✗ Branch 54 not taken. ✗ Branch 55 not taken. ✗ Branch 56 not taken. ✗ Branch 57 not taken. ✗ Branch 58 not taken. ✗ Branch 59 not taken. ✗ Branch 60 not taken. ✗ Branch 61 not taken. ✗ Branch 62 not taken. ✗ Branch 63 not taken. ✗ Branch 64 not taken. ✗ Branch 65 not taken. ✗ Branch 66 not taken. ✗ Branch 67 not taken. ✗ Branch 68 not taken. ✗ Branch 69 not taken. ✗ Branch 70 not taken. ✗ Branch 71 not taken. ✗ Branch 72 not taken. ✗ Branch 73 not taken. ✗ Branch 74 not taken. ✗ Branch 75 not taken. ✗ Branch 76 not taken. ✗ Branch 77 not taken. ✗ Branch 78 not taken. ✗ Branch 79 not taken. ✗ Branch 80 not taken. ✗ Branch 81 not taken. ✗ Branch 82 not taken. ✗ Branch 83 not taken. ✗ Branch 84 not taken. ✗ Branch 85 not taken. ✗ Branch 86 not taken. ✗ Branch 87 not taken. ✗ Branch 88 not taken. ✗ Branch 89 not taken. ✗ Branch 90 not taken. ✗ Branch 91 not taken. ✓ Branch 92 taken 4 times. ✓ Branch 93 taken 104 times. ✗ Branch 94 not taken. ✓ Branch 95 taken 4 times. ✓ Branch 96 taken 4 times. ✓ Branch 97 taken 104 times. ✗ Branch 98 not taken. ✓ Branch 99 taken 4 times. ✗ Branch 100 not taken. ✗ Branch 101 not taken. ✗ Branch 102 not taken. ✗ Branch 103 not taken. ✗ Branch 104 not taken. ✗ Branch 105 not taken. ✗ Branch 106 not taken. ✗ Branch 107 not taken. ✗ Branch 108 not taken. ✗ Branch 109 not taken. ✗ Branch 110 not taken. ✗ Branch 111 not taken. ✗ Branch 112 not taken. ✗ Branch 113 not taken. ✗ Branch 114 not taken. ✗ Branch 115 not taken. ✗ Branch 116 not taken. ✗ Branch 117 not taken. ✗ Branch 118 not taken. ✗ Branch 119 not taken. ✗ Branch 120 not taken. ✗ Branch 121 not taken. ✗ Branch 122 not taken. ✗ Branch 123 not taken. ✗ Branch 124 not taken. ✗ Branch 125 not taken. ✗ Branch 126 not taken. ✗ Branch 127 not taken. ✗ Branch 128 not taken. ✗ Branch 129 not taken. ✗ Branch 130 not taken. ✗ Branch 131 not taken.	30943x	for (T* p = head_; p; p = static_cast<node*>(p)->next_)
178		18309x	f(p);
179		12634x	}
180			};
181
182			/** An intrusive singly linked FIFO queue.
183
184			This container provides O(1) push and pop operations for
185			elements that derive from @ref node. Elements are not
186			copied or moved; they are linked directly into the queue.
187
188			Unlike @ref intrusive_list, this uses only a single `next_`
189			pointer per node, saving memory at the cost of not supporting
190			O(1) removal of arbitrary elements.
191
192			@tparam T The element type. Must derive from `intrusive_queue<T>::node`.
193			*/
194			template<class T>
195			class intrusive_queue
196			{
197			public:
198			/** Base class for queue elements.
199
200			Derive from this class to make a type usable with
201			@ref intrusive_queue. The `next_` pointer is private
202			and accessible only to the queue.
203			*/
204		121885x	class node
205			{
206			friend class intrusive_queue;
207
208			private:
209		121885x	T* next_ = nullptr;
210			};
211
212			private:
213		9289x	T* head_ = nullptr;
214		9289x	T* tail_ = nullptr;
215
216			public:
217		27869x	intrusive_queue() = default;
218
219		2x	intrusive_queue(intrusive_queue&& other) noexcept
220		1x	: head_(other.head_)
221		1x	, tail_(other.tail_)
222		1x	{
223		1x	other.head_ = nullptr;
224		1x	other.tail_ = nullptr;
225		2x	}
226
227			intrusive_queue(intrusive_queue const&) = delete;
228			intrusive_queue& operator=(intrusive_queue const&) = delete;
229			intrusive_queue& operator=(intrusive_queue&&) = delete;
230
231		6768x	bool empty() const noexcept
232			{
233		6768x	return head_ == nullptr;
234			}
235
236		1246x	void push(T* w) noexcept
237			{
238		1246x	w->next_ = nullptr;
239	2/2 ✓ Branch 0 taken 282 times. ✓ Branch 1 taken 964 times.	1246x	if (tail_)
240		282x	tail_->next_ = w;
241			else
242		964x	head_ = w;
243		1246x	tail_ = w;
244		1246x	}
245
246		4651x	void splice(intrusive_queue& other) noexcept
247			{
248	2/2 ✓ Branch 0 taken 4628 times. ✓ Branch 1 taken 23 times.	4651x	if (other.empty())
249		4628x	return;
250	2/2 ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 22 times.	23x	if (tail_)
251		1x	tail_->next_ = other.head_;
252			else
253		22x	head_ = other.head_;
254		23x	tail_ = other.tail_;
255		23x	other.head_ = nullptr;
256		23x	other.tail_ = nullptr;
257		4651x	}
258
259		5896x	T* pop() noexcept
260			{
261	2/2 ✓ Branch 0 taken 1246 times. ✓ Branch 1 taken 4650 times.	5896x	if (!head_)
262		4650x	return nullptr;
263		1246x	T* w = head_;
264		1246x	head_ = head_->next_;
265	2/2 ✓ Branch 0 taken 283 times. ✓ Branch 1 taken 963 times.	1246x	if (!head_)
266		963x	tail_ = nullptr;
267			// Defensive: clear stale linkage on popped node.
268		1246x	w->next_ = nullptr;
269		1246x	return w;
270		5896x	}
271			};
272
273			} // namespace boost::corosio::detail
274
275			#endif
276