1 /* Intrusive double linked list for GDB, the GNU debugger.
2 Copyright (C) 2021 Free Software Foundation, Inc.
4 This file is part of GDB.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 #ifndef GDBSUPPORT_INTRUSIVE_LIST_H
20 #define GDBSUPPORT_INTRUSIVE_LIST_H
22 #define INTRUSIVE_LIST_UNLINKED_VALUE ((T *) -1)
24 /* A list node. The elements put in an intrusive_list either inherit
25 from this, or have a field of this type. */
27 struct intrusive_list_node
29 bool is_linked () const
31 return next
!= INTRUSIVE_LIST_UNLINKED_VALUE
;
34 T
*next
= INTRUSIVE_LIST_UNLINKED_VALUE
;
35 T
*prev
= INTRUSIVE_LIST_UNLINKED_VALUE
;
38 /* Follows a couple types used by intrusive_list as template parameter to find
39 the intrusive_list_node for a given element. One for lists where the
40 elements inherit intrusive_list_node, and another for elements that keep the
41 node as member field. */
43 /* For element types that inherit from intrusive_list_node. */
46 struct intrusive_base_node
48 static intrusive_list_node
<T
> *as_node (T
*elem
)
52 /* For element types that keep the node as member field. */
54 template<typename T
, intrusive_list_node
<T
> T::*MemberNode
>
55 struct intrusive_member_node
57 static intrusive_list_node
<T
> *as_node (T
*elem
)
58 { return &(elem
->*MemberNode
); }
61 /* Common code for forward and reverse iterators. */
63 template<typename T
, typename AsNode
, typename SelfType
>
64 struct intrusive_list_base_iterator
66 using self_type
= SelfType
;
67 using iterator_category
= std::bidirectional_iterator_tag
;
70 using const_pointer
= const T
*;
71 using reference
= T
&;
72 using const_reference
= const T
&;
73 using difference_type
= ptrdiff_t;
74 using size_type
= size_t;
75 using node_type
= intrusive_list_node
<T
>;
77 /* Create an iterator pointing to ELEM. */
78 explicit intrusive_list_base_iterator (T
*elem
)
82 /* Create a past-the-end iterator. */
83 intrusive_list_base_iterator ()
87 reference
operator* () const
90 pointer
operator-> () const
93 bool operator== (const self_type
&other
) const
94 { return m_elem
== other
.m_elem
; }
96 bool operator!= (const self_type
&other
) const
97 { return m_elem
!= other
.m_elem
; }
100 static node_type
*as_node (T
*elem
)
101 { return AsNode::as_node (elem
); }
103 /* A past-end-the iterator points to the list's head. */
107 /* Forward iterator for an intrusive_list. */
109 template<typename T
, typename AsNode
= intrusive_base_node
<T
>>
110 struct intrusive_list_iterator
111 : public intrusive_list_base_iterator
112 <T
, AsNode
, intrusive_list_iterator
<T
, AsNode
>>
114 using base
= intrusive_list_base_iterator
115 <T
, AsNode
, intrusive_list_iterator
<T
, AsNode
>>;
116 using self_type
= typename
base::self_type
;
117 using node_type
= typename
base::node_type
;
119 /* Inherit constructor and M_NODE visibility from base. */
123 self_type
&operator++ ()
125 node_type
*node
= this->as_node (m_elem
);
130 self_type
operator++ (int)
132 self_type temp
= *this;
133 node_type
*node
= this->as_node (m_elem
);
138 self_type
&operator-- ()
140 node_type
*node
= this->as_node (m_elem
);
145 self_type
operator-- (int)
147 self_type temp
= *this;
148 node_type
*node
= this->as_node (m_elem
);
154 /* Reverse iterator for an intrusive_list. */
156 template<typename T
, typename AsNode
= intrusive_base_node
<T
>>
157 struct intrusive_list_reverse_iterator
158 : public intrusive_list_base_iterator
159 <T
, AsNode
, intrusive_list_reverse_iterator
<T
, AsNode
>>
161 using base
= intrusive_list_base_iterator
162 <T
, AsNode
, intrusive_list_reverse_iterator
<T
, AsNode
>>;
163 using self_type
= typename
base::self_type
;
165 /* Inherit constructor and M_NODE visibility from base. */
168 using node_type
= typename
base::node_type
;
170 self_type
&operator++ ()
172 node_type
*node
= this->as_node (m_elem
);
177 self_type
operator++ (int)
179 self_type temp
= *this;
180 node_type
*node
= this->as_node (m_elem
);
185 self_type
&operator-- ()
187 node_type
*node
= this->as_node (m_elem
);
192 self_type
operator-- (int)
194 self_type temp
= *this;
195 node_type
*node
= this->as_node (m_elem
);
201 /* An intrusive double-linked list.
203 T is the type of the elements to link. The type T must either:
205 - inherit from intrusive_list_node<T>
206 - have an intrusive_list_node<T> member
208 AsNode is a type with an as_node static method used to get a node from an
209 element. If elements inherit from intrusive_list_node<T>, use the default
210 intrusive_base_node<T>. If elements have an intrusive_list_node<T> member,
213 intrusive_member_node<T, &T::member>
215 where `member` is the name of the member. */
217 template <typename T
, typename AsNode
= intrusive_base_node
<T
>>
221 using value_type
= T
;
223 using const_pointer
= const T
*;
224 using reference
= T
&;
225 using const_reference
= const T
&;
226 using difference_type
= ptrdiff_t;
227 using size_type
= size_t;
228 using iterator
= intrusive_list_iterator
<T
, AsNode
>;
229 using reverse_iterator
= intrusive_list_reverse_iterator
<T
, AsNode
>;
230 using const_iterator
= const intrusive_list_iterator
<T
, AsNode
>;
231 using const_reverse_iterator
232 = const intrusive_list_reverse_iterator
<T
, AsNode
>;
233 using node_type
= intrusive_list_node
<T
>;
235 intrusive_list () = default;
242 intrusive_list (intrusive_list
&&other
)
243 : m_front (other
.m_front
),
244 m_back (other
.m_back
)
246 other
.m_front
= nullptr;
247 other
.m_back
= nullptr;
250 intrusive_list
&operator= (intrusive_list
&&other
)
252 m_front
= other
.m_front
;
253 m_back
= other
.m_back
;
254 other
.m_front
= nullptr;
255 other
.m_back
= nullptr;
260 void swap (intrusive_list
&other
)
262 std::swap (m_front
, other
.m_front
);
263 std::swap (m_back
, other
.m_back
);
266 iterator
iterator_to (reference value
)
268 return iterator (&value
);
271 const_iterator
iterator_to (const_reference value
)
273 return const_iterator (&value
);
278 gdb_assert (!this->empty ());
282 const_reference
front () const
284 gdb_assert (!this->empty ());
290 gdb_assert (!this->empty ());
294 const_reference
back () const
296 gdb_assert (!this->empty ());
300 void push_front (reference elem
)
302 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
304 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
305 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
308 this->push_empty (elem
);
310 this->push_front_non_empty (elem
);
313 void push_back (reference elem
)
315 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
317 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
318 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
321 this->push_empty (elem
);
323 this->push_back_non_empty (elem
);
326 /* Inserts ELEM before POS. */
327 void insert (const_iterator pos
, reference elem
)
330 return this->push_empty (elem
);
332 if (pos
== this->begin ())
333 return this->push_front_non_empty (elem
);
335 if (pos
== this->end ())
336 return this->push_back_non_empty (elem
);
338 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
340 intrusive_list_node
<T
> *pos_node
= as_node (pos_elem
);
341 T
*prev_elem
= pos_node
->prev
;
342 intrusive_list_node
<T
> *prev_node
= as_node (prev_elem
);
344 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
345 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
347 elem_node
->prev
= prev_elem
;
348 prev_node
->next
= &elem
;
349 elem_node
->next
= pos_elem
;
350 pos_node
->prev
= &elem
;
353 /* Move elements from LIST at the end of the current list. */
354 void splice (intrusive_list
&&other
)
361 *this = std::move (other
);
365 /* [A ... B] + [C ... D] */
367 node_type
*b_node
= as_node (b_elem
);
368 T
*c_elem
= other
.m_front
;
369 node_type
*c_node
= as_node (c_elem
);
370 T
*d_elem
= other
.m_back
;
372 b_node
->next
= c_elem
;
373 c_node
->prev
= b_elem
;
376 other
.m_front
= nullptr;
377 other
.m_back
= nullptr;
382 gdb_assert (!this->empty ());
383 erase_element (*m_front
);
388 gdb_assert (!this->empty ());
389 erase_element (*m_back
);
393 /* Push ELEM in the list, knowing the list is empty. */
394 void push_empty (T
&elem
)
396 gdb_assert (this->empty ());
398 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
400 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
401 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
405 elem_node
->prev
= nullptr;
406 elem_node
->next
= nullptr;
409 /* Push ELEM at the front of the list, knowing the list is not empty. */
410 void push_front_non_empty (T
&elem
)
412 gdb_assert (!this->empty ());
414 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
415 intrusive_list_node
<T
> *front_node
= as_node (m_front
);
417 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
418 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
420 elem_node
->next
= m_front
;
421 front_node
->prev
= &elem
;
422 elem_node
->prev
= nullptr;
426 /* Push ELEM at the back of the list, knowing the list is not empty. */
427 void push_back_non_empty (T
&elem
)
429 gdb_assert (!this->empty ());
431 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
432 intrusive_list_node
<T
> *back_node
= as_node (m_back
);
434 gdb_assert (elem_node
->next
== INTRUSIVE_LIST_UNLINKED_VALUE
);
435 gdb_assert (elem_node
->prev
== INTRUSIVE_LIST_UNLINKED_VALUE
);
437 elem_node
->prev
= m_back
;
438 back_node
->next
= &elem
;
439 elem_node
->next
= nullptr;
443 void erase_element (T
&elem
)
445 intrusive_list_node
<T
> *elem_node
= as_node (&elem
);
447 gdb_assert (elem_node
->prev
!= INTRUSIVE_LIST_UNLINKED_VALUE
);
448 gdb_assert (elem_node
->next
!= INTRUSIVE_LIST_UNLINKED_VALUE
);
450 if (m_front
== &elem
)
452 gdb_assert (elem_node
->prev
== nullptr);
453 m_front
= elem_node
->next
;
457 gdb_assert (elem_node
->prev
!= nullptr);
458 intrusive_list_node
<T
> *prev_node
= as_node (elem_node
->prev
);
459 prev_node
->next
= elem_node
->next
;
464 gdb_assert (elem_node
->next
== nullptr);
465 m_back
= elem_node
->prev
;
469 gdb_assert (elem_node
->next
!= nullptr);
470 intrusive_list_node
<T
> *next_node
= as_node (elem_node
->next
);
471 next_node
->prev
= elem_node
->prev
;
474 elem_node
->next
= INTRUSIVE_LIST_UNLINKED_VALUE
;
475 elem_node
->prev
= INTRUSIVE_LIST_UNLINKED_VALUE
;
479 /* Remove the element pointed by I from the list. The element
480 pointed by I is not destroyed. */
481 iterator
erase (const_iterator i
)
491 /* Erase all the elements. The elements are not destroyed. */
494 while (!this->empty ())
498 /* Erase all the elements. Disposer::operator()(pointer) is called
499 for each of the removed elements. */
500 template<typename Disposer
>
501 void clear_and_dispose (Disposer disposer
)
503 while (!this->empty ())
505 pointer p
= &front ();
513 return m_front
== nullptr;
516 iterator
begin () noexcept
518 return iterator (m_front
);
521 const_iterator
begin () const noexcept
523 return const_iterator (m_front
);
526 const_iterator
cbegin () const noexcept
528 return const_iterator (m_front
);
531 iterator
end () noexcept
536 const_iterator
end () const noexcept
541 const_iterator
cend () const noexcept
546 reverse_iterator
rbegin () noexcept
548 return reverse_iterator (m_back
);
551 const_reverse_iterator
rbegin () const noexcept
553 return const_reverse_iterator (m_back
);
556 const_reverse_iterator
crbegin () const noexcept
558 return const_reverse_iterator (m_back
);
561 reverse_iterator
rend () noexcept
566 const_reverse_iterator
rend () const noexcept
571 const_reverse_iterator
crend () const noexcept
577 static node_type
*as_node (T
*elem
)
579 return AsNode::as_node (elem
);
582 T
*m_front
= nullptr;
586 #endif /* GDBSUPPORT_INTRUSIVE_LIST_H */