[PATCH 02/11] gdb: introduce intrusive_list, make thread_info use it
Simon Marchi
simon.marchi@polymtl.ca
Tue Jun 22 16:56:55 GMT 2021
From: Pedro Alves <pedro@palves.net>
GDB currently has several objects that are put in a singly linked list,
by having the object's type have a "next" pointer directly. For
example, struct thread_info and struct inferior. Because these are
simply-linked lists, and we don't keep track of a "tail" pointer, when
we want to append a new element on the list, we need to walk the whole
list to find the current tail. It would be nice to get rid of that
walk. Removing elements from such lists also requires a walk, to find
the "previous" position relative to the element being removed. To
eliminate the need for that walk, we could make those lists
doubly-linked, by adding a "prev" pointer alongside "next". It would be
nice to avoid the boilerplace associated with maintaining such a list
manually, though. That is what the new intrusive_list type addresses.
With an intrusive list, it's also possible to move items out of the
list without destroying them, which is interesting in our case for
example for threads, when we exit them, but can't destroy them
immediately. We currently keep exited threads on the thread list, but
we could change that which would simplify some things.
Note that with std::list, element removal is O(N). I.e., with
std::list, we need to walk the list to find the iterator pointing to
the position to remove. However, we could store a list iterator
inside the object as soon as we put the object in the list, to address
it, because std::list iterators are not invalidated when other
elements are added/removed. However, if you need to put the same
object in more than one list, then std::list<object> doesn't work.
You need to instead use std::list<object *>, which is less efficient
for requiring extra memory allocations. For an example of an object
in multiple lists, see the step_over_next/step_over_prev fields in
thread_info:
/* Step-over chain. A thread is in the step-over queue if these are
non-NULL. If only a single thread is in the chain, then these
fields point to self. */
struct thread_info *step_over_prev = NULL;
struct thread_info *step_over_next = NULL;
The new intrusive_list type gives us the advantages of an intrusive
linked list, while avoiding the boilerplate associated with manually
maintaining it.
intrusive_list's API follows the standard container interface, and thus
std::list's interface. It is based the API of Boost's intrusive list,
here:
https://www.boost.org/doc/libs/1_73_0/doc/html/boost/intrusive/list.html
Our implementation is relatively simple, while Boost's is complicated
and intertwined due to a lot of customization options, which our version
doesn't have.
The easiest way to use an intrusive_list is to make the list's element
type inherit from intrusive_node. This adds a prev/next pointers to
the element type. However, to support putting the same object in more
than one list, intrusive_list supports putting the "node" info as a
field member, so you can have more than one such nodes, one per list.
As a first guinea pig, this patch makes the per-inferior thread list use
intrusive_list using the base class method.
Unlike Boost's implementation, ours is not a circular list. An earlier
version of the patch was circular: the instrusive_list type included an
intrusive_list_node "head". In this design, a node contained pointers
to the previous and next nodes, not the previous and next elements.
This wasn't great for when debugging GDB with GDB, as it was difficult
to get from a pointer to the node to a pointer to the element. With the
design proposed in this patch, nodes contain pointers to the previous
and next elements, making it easy to traverse the list by hand and
inspect each element.
The intrusive_list object contains pointers to the first and last
elements of the list. They are nullptr if the list is empty.
Each element's node contains a pointer to the previous and next
elements. The first element's previous pointer is nullptr and the last
element's next pointer is nullptr. Therefore, if there's a single
element in the list, both its previous and next pointers are nullptr.
To differentiate such an element from an element that is not linked into
a list, the previous and next pointers contain a special value (-1) when
the node is not linked. This is necessary to be able to reliably tell
if a given node is currently linked or not.
A begin() iterator points to the first item in the list. An end()
iterator contains nullptr. This makes iteration until end naturally
work, as advancing past the last element will make the iterator contain
nullptr, making it equal to the end iterator. If the list is empty,
a begin() iterator will contain nullptr from the start, and therefore be
immediately equal to the end.
Iterating on an intrusive_list yields references to objects (e.g.
`thread_info&`). The rest of GDB currently expects iterators and ranges
to yield pointers (e.g. `thread_info*`). To bridge the gap, add the
reference_to_pointer_iterator type. It is used to define
inf_threads_iterator.
Add a Python pretty-printer, to help inspecting intrusive lists when
debugging GDB with GDB. Here's an example of the output:
(top-gdb) p current_inferior_.m_obj.thread_list
$1 = intrusive list of thread_info = {0x61700002c000, 0x617000069080, 0x617000069400, 0x61700006d680, 0x61700006eb80}
It's not possible with current master, but with this patch [1] that I
hope will be merged eventually, it's possible to index the list and
access the pretty-printed value's children:
(top-gdb) p current_inferior_.m_obj.thread_list[1]
$2 = (thread_info *) 0x617000069080
(top-gdb) p current_inferior_.m_obj.thread_list[1].ptid
$3 = {
m_pid = 406499,
m_lwp = 406503,
m_tid = 0
}
Even though iterating the list in C++ yields references, the Python
pretty-printer yields pointers. The reason for this is that the output
of printing the thread list above would be unreadable, IMO, if each
thread_info object was printed in-line, since they contain so much
information. I think it's more useful to print pointers, and let the
user drill down as needed.
[1] https://sourceware.org/pipermail/gdb-patches/2021-April/178050.html
YYYY-MM-DD Pedro Alves <pedro@palves.net>
YYYY-MM-DD Simon Marchi <simon.marchi@efficios.com>
gdbsupport/ChangeLog:
* intrusive_list.h: New.
* filtered-iterator.h (class filtered_iterator): Add
constructor.
* safe-iterator.h (class basic_safe_iterator): Add defaulted
constructors.
gdb/ChangeLog:
* Makefile.in (SELFTESTS_SRCS): Add
unittests/intrusive_list-selftests.c.
* gdbthread.h (class thread_info): Inherit from
intrusive_list_node.
<next>: Remove.
(set_thread_exited): New declaration.
* thread.c (set_thread_exited): Make non-static.
(init_thread_list): Use clear_thread_list.
(new_thread): Adjust.
(delete_thread_1): Adjust.
(first_thread_of_inferior): Adjust.
(update_threads_executing): Adjust.
* inferior.h (class inferior) <thread_list>: Change type to
intrusive_list.
<threads, non_exited_threads, threads_safe>: Adjust.
<clear_thread_list>: New.
* inferior.c (inferior::clear_thread_list): New.
(delete_inferior): Use clear_thread_list.
(exit_inferior_1): Use clear_thread_list.
* scoped-mock-context.h (struct scoped_mock_context)
<restore_thread_list>: Remove.
<scoped_mock_context>: Insert mock thread in mock inferior's
thread list.
* thread-iter.h (inf_threads_iterator, inf_threads_range,
inf_non_exited_threads_range, safe_inf_threads_range): Change type.
(inf_threads_iterator): Define using next_iterator_intrusive.
* thread-iter.c (all_threads_iterator::all_threads_iterator):
Adjust.
(all_threads_iterator::advance): Adjust.
(all_matching_threads_iterator::all_matching_threads_iterator):
Adjust.
(all_matching_threads_iterator::advance): Adjust.
* unittests/intrusive_list-selftests.c: New.
Co-Authored-By: Simon Marchi <simon.marchi@efficios.com>
Change-Id: I3412a14dc77f25876d742dab8f44e0ba7c7586c0
---
gdb/Makefile.in | 1 +
gdb/gdb-gdb.py.in | 91 ++-
gdb/gdbthread.h | 13 +-
gdb/inferior.c | 24 +-
gdb/inferior.h | 14 +-
gdb/scoped-mock-context.h | 4 +-
gdb/thread-iter.c | 53 +-
gdb/thread-iter.h | 5 +-
gdb/thread.c | 61 +-
gdb/unittests/intrusive_list-selftests.c | 734 +++++++++++++++++++++
gdbsupport/intrusive_list.h | 559 ++++++++++++++++
gdbsupport/reference-to-pointer-iterator.h | 79 +++
12 files changed, 1554 insertions(+), 84 deletions(-)
create mode 100644 gdb/unittests/intrusive_list-selftests.c
create mode 100644 gdbsupport/intrusive_list.h
create mode 100644 gdbsupport/reference-to-pointer-iterator.h
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 1bc97885536e..b405950783c2 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -449,6 +449,7 @@ SELFTESTS_SRCS = \
unittests/function-view-selftests.c \
unittests/gdb_tilde_expand-selftests.c \
unittests/gmp-utils-selftests.c \
+ unittests/intrusive_list-selftests.c \
unittests/lookup_name_info-selftests.c \
unittests/memory-map-selftests.c \
unittests/memrange-selftests.c \
diff --git a/gdb/gdb-gdb.py.in b/gdb/gdb-gdb.py.in
index af9fcfedc2f3..7ff91bd779f9 100644
--- a/gdb/gdb-gdb.py.in
+++ b/gdb/gdb-gdb.py.in
@@ -276,16 +276,101 @@ class CoreAddrPrettyPrinter:
return hex(int(self._val))
+class IntrusiveListPrinter:
+ """Print a struct intrusive_list."""
+
+ def __init__(self, val):
+ self._val = val
+
+ # Type of linked items.
+ self._item_type = self._val.type.template_argument(0)
+ self._node_ptr_type = gdb.lookup_type(
+ f"intrusive_list_node<{self._item_type.tag}>"
+ ).pointer()
+
+ # Type of value -> node converter.
+ self._conv_type = self._val.type.template_argument(1)
+
+ if self._uses_member_node():
+ # The second template argument of intrusive_member_node is a member
+ # pointer value. Its value is the offset of the node member in the
+ # enclosing type.
+ member_node_ptr = self._conv_type.template_argument(1)
+ member_node_ptr = member_node_ptr.cast(gdb.lookup_type("int"))
+ self._member_node_offset = int(member_node_ptr)
+
+ # This is only needed in _as_node_ptr if using a member node. Look it
+ # up here so we only do it once.
+ self._char_ptr_type = gdb.lookup_type("char").pointer()
+
+ def display_hint(self):
+ return "array"
+
+ # Return True if the list items use a node as a member. Return False if
+ # they use a node as a base class.
+ def _uses_member_node(self):
+ if self._conv_type.name.startswith("intrusive_member_node<"):
+ return True
+ elif self._conv_type.name.startswith("intrusive_base_node<"):
+ return False
+ else:
+ raise RuntimeError(
+ f"Unexpected intrusive_list value -> node converter type: {self._conv_type.name}"
+ )
+
+ def to_string(self):
+ s = f"intrusive list of {self._item_type}"
+
+ if self._uses_member_node():
+ node_member = self._conv_type.template_argument(1)
+ s += f", linked through {node_member}"
+
+ return s
+
+ # Given ELEM_PTR, a pointer to a list element, return a pointer to the
+ # corresponding intrusive_list_node.
+ def _as_node_ptr(self, elem_ptr):
+ assert elem_ptr.type.code == gdb.TYPE_CODE_PTR
+
+ if self._uses_member_node():
+ # Node as a memer: add the member node offset from to the element's
+ # address to get the member node's address.
+ elem_char_ptr = elem_ptr.cast(self._char_ptr_type)
+ node_char_ptr = elem_char_ptr + self._member_node_offset
+ return node_char_ptr.cast(self._node_ptr_type)
+ else:
+ # Node as a base: just casting from node pointer to item pointer
+ # will adjust the pointer value.
+ return elem_ptr.cast(self._node_ptr_type)
+
+ # Generator that yields one tuple per list item.
+ def _children_generator(self):
+ elem_ptr = self._val["m_front"]
+ idx = 0
+ while elem_ptr != 0:
+ yield (str(idx), elem_ptr)
+ node_ptr = self._as_node_ptr(elem_ptr)
+ elem_ptr = node_ptr["next"]
+ idx += 1
+
+ def children(self):
+ return self._children_generator()
+
+
def type_lookup_function(val):
"""A routine that returns the correct pretty printer for VAL
if appropriate. Returns None otherwise.
"""
- if val.type.tag == "type":
+ tag = val.type.tag
+ name = val.type.name
+ if tag == "type":
return StructTypePrettyPrinter(val)
- elif val.type.tag == "main_type":
+ elif tag == "main_type":
return StructMainTypePrettyPrinter(val)
- elif val.type.name == "CORE_ADDR":
+ elif name == "CORE_ADDR":
return CoreAddrPrettyPrinter(val)
+ elif tag is not None and tag.startswith("intrusive_list<"):
+ return IntrusiveListPrinter(val)
return None
diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h
index f19c88f9bb4a..0e28b1de9ff0 100644
--- a/gdb/gdbthread.h
+++ b/gdb/gdbthread.h
@@ -33,6 +33,7 @@ struct symtab;
#include "gdbsupport/common-gdbthread.h"
#include "gdbsupport/forward-scope-exit.h"
#include "displaced-stepping.h"
+#include "gdbsupport/intrusive_list.h"
struct inferior;
struct process_stratum_target;
@@ -222,9 +223,12 @@ struct private_thread_info
delete_thread). All other thread references are considered weak
references. Placing a thread in the thread list is an implicit
strong reference, and is thus not accounted for in the thread's
- refcount. */
+ refcount.
-class thread_info : public refcounted_object
+ The intrusive_list_node base links threads in a per-inferior list. */
+
+class thread_info : public refcounted_object,
+ public intrusive_list_node<thread_info>
{
public:
explicit thread_info (inferior *inf, ptid_t ptid);
@@ -235,7 +239,6 @@ class thread_info : public refcounted_object
/* Mark this thread as running and notify observers. */
void set_running (bool running);
- struct thread_info *next = NULL;
ptid_t ptid; /* "Actual process id";
In fact, this may be overloaded with
kernel thread id, etc. */
@@ -435,6 +438,10 @@ extern void delete_thread (struct thread_info *thread);
this thread belonged to has already exited, for example. */
extern void delete_thread_silent (struct thread_info *thread);
+/* Mark the thread exited, but don't delete it or remove it from the
+ inferior thread list. */
+extern void set_thread_exited (thread_info *tp, bool silent);
+
/* Delete a step_resume_breakpoint from the thread database. */
extern void delete_step_resume_breakpoint (struct thread_info *);
diff --git a/gdb/inferior.c b/gdb/inferior.c
index 059839ec9626..693b196556d5 100644
--- a/gdb/inferior.c
+++ b/gdb/inferior.c
@@ -163,6 +163,19 @@ add_inferior (int pid)
return inf;
}
+/* See inferior.h. */
+
+void
+inferior::clear_thread_list (bool silent)
+{
+ thread_list.clear_and_dispose ([=] (thread_info *thr)
+ {
+ set_thread_exited (thr, silent);
+ if (thr->deletable ())
+ delete thr;
+ });
+}
+
void
delete_inferior (struct inferior *todel)
{
@@ -177,8 +190,7 @@ delete_inferior (struct inferior *todel)
if (!inf)
return;
- for (thread_info *tp : inf->threads_safe ())
- delete_thread_silent (tp);
+ inf->clear_thread_list (true);
if (infprev)
infprev->next = inf->next;
@@ -209,13 +221,7 @@ exit_inferior_1 (struct inferior *inftoex, int silent)
if (!inf)
return;
- for (thread_info *tp : inf->threads_safe ())
- {
- if (silent)
- delete_thread_silent (tp);
- else
- delete_thread (tp);
- }
+ inf->clear_thread_list (silent);
gdb::observers::inferior_exit.notify (inf);
diff --git a/gdb/inferior.h b/gdb/inferior.h
index c63990aabe0e..2ae9f9a5f9c4 100644
--- a/gdb/inferior.h
+++ b/gdb/inferior.h
@@ -390,8 +390,8 @@ class inferior : public refcounted_object
/* Pointer to next inferior in singly-linked list of inferiors. */
struct inferior *next = NULL;
- /* This inferior's thread list. */
- thread_info *thread_list = nullptr;
+ /* This inferior's thread list, sorted by creation order. */
+ intrusive_list<thread_info> thread_list;
/* Returns a range adapter covering the inferior's threads,
including exited threads. Used like this:
@@ -400,7 +400,7 @@ class inferior : public refcounted_object
{ .... }
*/
inf_threads_range threads ()
- { return inf_threads_range (this->thread_list); }
+ { return inf_threads_range (this->thread_list.begin ()); }
/* Returns a range adapter covering the inferior's non-exited
threads. Used like this:
@@ -409,7 +409,7 @@ class inferior : public refcounted_object
{ .... }
*/
inf_non_exited_threads_range non_exited_threads ()
- { return inf_non_exited_threads_range (this->thread_list); }
+ { return inf_non_exited_threads_range (this->thread_list.begin ()); }
/* Like inferior::threads(), but returns a range adapter that can be
used with range-for, safely. I.e., it is safe to delete the
@@ -420,7 +420,11 @@ class inferior : public refcounted_object
delete f;
*/
inline safe_inf_threads_range threads_safe ()
- { return safe_inf_threads_range (this->thread_list); }
+ { return safe_inf_threads_range (this->thread_list.begin ()); }
+
+ /* Delete all threads in the thread list. If SILENT, exit threads
+ silently. */
+ void clear_thread_list (bool silent);
/* Continuations-related methods. A continuation is an std::function
to be called to finish the execution of a command when running
diff --git a/gdb/scoped-mock-context.h b/gdb/scoped-mock-context.h
index 8d295ba1bbe6..37ffe5117423 100644
--- a/gdb/scoped-mock-context.h
+++ b/gdb/scoped-mock-context.h
@@ -44,9 +44,6 @@ struct scoped_mock_context
scoped_restore_current_pspace_and_thread restore_pspace_thread;
- scoped_restore_tmpl<thread_info *> restore_thread_list
- {&mock_inferior.thread_list, &mock_thread};
-
/* Add the mock inferior to the inferior list so that look ups by
target+ptid can find it. */
scoped_restore_tmpl<inferior *> restore_inferior_list
@@ -54,6 +51,7 @@ struct scoped_mock_context
explicit scoped_mock_context (gdbarch *gdbarch)
{
+ mock_inferior.thread_list.push_back (mock_thread);
mock_inferior.gdbarch = gdbarch;
mock_inferior.aspace = mock_pspace.aspace;
mock_inferior.pspace = &mock_pspace;
diff --git a/gdb/thread-iter.c b/gdb/thread-iter.c
index 012ca5fab090..a1cdd0206bd4 100644
--- a/gdb/thread-iter.c
+++ b/gdb/thread-iter.c
@@ -27,8 +27,15 @@ all_threads_iterator::all_threads_iterator (begin_t)
{
/* Advance M_INF/M_THR to the first thread's position. */
for (m_inf = inferior_list; m_inf != NULL; m_inf = m_inf->next)
- if ((m_thr = m_inf->thread_list) != NULL)
- return;
+ {
+ auto thr_iter = m_inf->thread_list.begin ();
+ if (thr_iter != m_inf->thread_list.end ())
+ {
+ m_thr = &*thr_iter;
+ return;
+ }
+ }
+ m_thr = nullptr;
}
/* See thread-iter.h. */
@@ -36,6 +43,8 @@ all_threads_iterator::all_threads_iterator (begin_t)
void
all_threads_iterator::advance ()
{
+ intrusive_list<thread_info>::iterator thr_iter (m_thr);
+
/* The loop below is written in the natural way as-if we'd always
start at the beginning of the inferior list. This fast forwards
the algorithm to the actual current position. */
@@ -43,14 +52,17 @@ all_threads_iterator::advance ()
for (; m_inf != NULL; m_inf = m_inf->next)
{
- m_thr = m_inf->thread_list;
- while (m_thr != NULL)
+ thr_iter = m_inf->thread_list.begin ();
+ while (thr_iter != m_inf->thread_list.end ())
{
+ m_thr = &*thr_iter;
return;
start:
- m_thr = m_thr->next;
+ ++thr_iter;
}
}
+
+ m_thr = nullptr;
}
/* See thread-iter.h. */
@@ -74,12 +86,18 @@ all_matching_threads_iterator::all_matching_threads_iterator
gdb_assert ((filter_target == nullptr && filter_ptid == minus_one_ptid)
|| filter_target->stratum () == process_stratum);
- m_thr = nullptr;
for (m_inf = inferior_list; m_inf != NULL; m_inf = m_inf->next)
if (m_inf_matches ())
- for (m_thr = m_inf->thread_list; m_thr != NULL; m_thr = m_thr->next)
- if (m_thr->ptid.matches (m_filter_ptid))
- return;
+ for (auto thr_iter = m_inf->thread_list.begin ();
+ thr_iter != m_inf->thread_list.end ();
+ ++thr_iter)
+ if (thr_iter->ptid.matches (m_filter_ptid))
+ {
+ m_thr = &*thr_iter;
+ return;
+ }
+
+ m_thr = nullptr;
}
/* See thread-iter.h. */
@@ -87,6 +105,8 @@ all_matching_threads_iterator::all_matching_threads_iterator
void
all_matching_threads_iterator::advance ()
{
+ intrusive_list<thread_info>::iterator thr_iter (m_thr);
+
/* The loop below is written in the natural way as-if we'd always
start at the beginning of the inferior list. This fast forwards
the algorithm to the actual current position. */
@@ -95,13 +115,18 @@ all_matching_threads_iterator::advance ()
for (; m_inf != NULL; m_inf = m_inf->next)
if (m_inf_matches ())
{
- m_thr = m_inf->thread_list;
- while (m_thr != NULL)
+ thr_iter = m_inf->thread_list.begin ();
+ while (thr_iter != m_inf->thread_list.end ())
{
- if (m_thr->ptid.matches (m_filter_ptid))
- return;
+ if (thr_iter->ptid.matches (m_filter_ptid))
+ {
+ m_thr = &*thr_iter;
+ return;
+ }
start:
- m_thr = m_thr->next;
+ ++thr_iter;
}
}
+
+ m_thr = nullptr;
}
diff --git a/gdb/thread-iter.h b/gdb/thread-iter.h
index 098af0f3241b..2e43034550e8 100644
--- a/gdb/thread-iter.h
+++ b/gdb/thread-iter.h
@@ -20,13 +20,16 @@
#define THREAD_ITER_H
#include "gdbsupport/filtered-iterator.h"
+#include "gdbsupport/iterator-range.h"
#include "gdbsupport/next-iterator.h"
+#include "gdbsupport/reference-to-pointer-iterator.h"
#include "gdbsupport/safe-iterator.h"
/* A forward iterator that iterates over a given inferior's
threads. */
-using inf_threads_iterator = next_iterator<thread_info>;
+using inf_threads_iterator
+ = reference_to_pointer_iterator<intrusive_list<thread_info>::iterator>;
/* A forward iterator that iterates over all threads of all
inferiors. */
diff --git a/gdb/thread.c b/gdb/thread.c
index f850f05ad48e..89f51c01c993 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -177,9 +177,9 @@ clear_thread_inferior_resources (struct thread_info *tp)
clear_inline_frame_state (tp);
}
-/* Set the TP's state as exited. */
+/* See gdbthread.h. */
-static void
+void
set_thread_exited (thread_info *tp, bool silent)
{
/* Dead threads don't need to step-over. Remove from chain. */
@@ -203,17 +203,8 @@ init_thread_list (void)
{
highest_thread_num = 0;
- for (thread_info *tp : all_threads_safe ())
- {
- inferior *inf = tp->inf;
-
- if (tp->deletable ())
- delete tp;
- else
- set_thread_exited (tp, 1);
-
- inf->thread_list = NULL;
- }
+ for (inferior *inf : all_inferiors ())
+ inf->clear_thread_list (true);
}
/* Allocate a new thread of inferior INF with target id PTID and add
@@ -224,21 +215,7 @@ new_thread (struct inferior *inf, ptid_t ptid)
{
thread_info *tp = new thread_info (inf, ptid);
- if (inf->thread_list == NULL)
- inf->thread_list = tp;
- else
- {
- struct thread_info *last;
-
- for (last = inf->thread_list; last->next != NULL; last = last->next)
- gdb_assert (ptid != last->ptid
- || last->state == THREAD_EXITED);
-
- gdb_assert (ptid != last->ptid
- || last->state == THREAD_EXITED);
-
- last->next = tp;
- }
+ inf->thread_list.push_back (*tp);
return tp;
}
@@ -462,29 +439,18 @@ delete_thread_1 (thread_info *thr, bool silent)
{
gdb_assert (thr != nullptr);
- struct thread_info *tp, *tpprev = NULL;
-
- for (tp = thr->inf->thread_list; tp; tpprev = tp, tp = tp->next)
- if (tp == thr)
- break;
+ set_thread_exited (thr, silent);
- if (!tp)
- return;
-
- set_thread_exited (tp, silent);
-
- if (!tp->deletable ())
+ if (!thr->deletable ())
{
/* Will be really deleted some other time. */
return;
}
- if (tpprev)
- tpprev->next = tp->next;
- else
- tp->inf->thread_list = tp->next;
+ auto it = thr->inf->thread_list.iterator_to (*thr);
+ thr->inf->thread_list.erase (it);
- delete tp;
+ delete thr;
}
/* See gdbthread.h. */
@@ -629,7 +595,10 @@ in_thread_list (process_stratum_target *targ, ptid_t ptid)
thread_info *
first_thread_of_inferior (inferior *inf)
{
- return inf->thread_list;
+ if (inf->thread_list.empty ())
+ return nullptr;
+
+ return &inf->thread_list.front ();
}
thread_info *
@@ -2018,7 +1987,7 @@ update_threads_executing (void)
/* If the process has no threads, then it must be we have a
process-exit event pending. */
- if (inf->thread_list == NULL)
+ if (inf->thread_list.empty ())
{
targ->threads_executing = true;
return;
diff --git a/gdb/unittests/intrusive_list-selftests.c b/gdb/unittests/intrusive_list-selftests.c
new file mode 100644
index 000000000000..3ccff54b5ff9
--- /dev/null
+++ b/gdb/unittests/intrusive_list-selftests.c
@@ -0,0 +1,734 @@
+/* Tests fpr intrusive double linked list for GDB, the GNU debugger.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "defs.h"
+
+#include "gdbsupport/intrusive_list.h"
+#include "gdbsupport/selftest.h"
+#include <unordered_set>
+
+/* An item type using intrusive_list_node by inheriting from it and its
+ corresponding list type. Put another base before intrusive_list_node
+ so that a pointer to the node != a pointer to the item. */
+
+struct other_base
+{
+ int n = 1;
+};
+
+struct item_with_base : public other_base,
+ public intrusive_list_node<item_with_base>
+{
+ item_with_base (const char *name)
+ : name (name)
+ {}
+
+ const char *const name;
+};
+
+using item_with_base_list = intrusive_list<item_with_base>;
+
+/* An item type using intrusive_list_node as a field and its corresponding
+ list type. Put the other field before the node, so that a pointer to the
+ node != a pointer to the item. */
+
+struct item_with_member
+{
+ item_with_member (const char *name)
+ : name (name)
+ {}
+
+ const char *const name;
+ intrusive_list_node<item_with_member> node;
+};
+
+using item_with_member_node
+ = intrusive_member_node<item_with_member, &item_with_member::node>;
+using item_with_member_list
+ = intrusive_list<item_with_member, item_with_member_node>;
+
+/* To run all tests using both the base and member methods, all tests are
+ declared in this templated class, which is instantiated once for each
+ list type. */
+
+template <typename ListType>
+struct intrusive_list_test
+{
+ using item_type = typename ListType::value_type;
+
+ /* Verify that LIST contains exactly the items in EXPECTED.
+
+ Traverse the list forward and backwards to exercise all links. */
+
+ static void
+ verify_items (const ListType &list,
+ gdb::array_view<const typename ListType::value_type *> expected)
+ {
+ int i = 0;
+
+ for (typename ListType::iterator it = list.begin ();
+ it != list.end ();
+ ++it)
+ {
+ const item_type &item = *it;
+
+ gdb_assert (i < expected.size ());
+ gdb_assert (&item == expected[i]);
+
+ ++i;
+ }
+
+ gdb_assert (i == expected.size ());
+
+ for (typename ListType::reverse_iterator it = list.rbegin ();
+ it != list.rend ();
+ ++it)
+ {
+ const item_type &item = *it;
+
+ --i;
+
+ gdb_assert (i >= 0);
+ gdb_assert (&item == expected[i]);
+ }
+
+ gdb_assert (i == 0);
+ }
+
+ static void
+ test_move_constructor ()
+ {
+ {
+ /* Other list is not empty. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list1;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list1.push_back (b);
+ list1.push_back (c);
+
+ ListType list2 (std::move (list1));
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a, &b, &c};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Other list contains 1 element. */
+ item_type a ("a");
+ ListType list1;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+
+ ListType list2 (std::move (list1));
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Other list is empty. */
+ ListType list1;
+ std::vector<const item_type *> expected;
+
+ ListType list2 (std::move (list1));
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+ }
+
+ static void
+ test_move_assignment ()
+ {
+ {
+ /* Both lists are not empty. */
+ item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list1.push_back (b);
+ list1.push_back (c);
+
+ list2.push_back (d);
+ list2.push_back (e);
+
+ list2 = std::move (list1);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a, &b, &c};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* rhs list is empty. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list2.push_back (a);
+ list2.push_back (b);
+ list2.push_back (c);
+
+ list2 = std::move (list1);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* lhs list is empty. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list1.push_back (b);
+ list1.push_back (c);
+
+ list2 = std::move (list1);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a, &b, &c};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Both lists contain 1 item. */
+ item_type a ("a"), b ("b");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list2.push_back (b);
+
+ list2 = std::move (list1);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Both lists are empty. */
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list2 = std::move (list1);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+ }
+
+ static void
+ test_swap ()
+ {
+ {
+ /* Two non-empty lists. */
+ item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list1.push_back (b);
+ list1.push_back (c);
+
+ list2.push_back (d);
+ list2.push_back (e);
+
+ std::swap (list1, list2);
+
+ expected = {&d, &e};
+ verify_items (list1, expected);
+
+ expected = {&a, &b, &c};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Other is empty. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+ list1.push_back (b);
+ list1.push_back (c);
+
+ std::swap (list1, list2);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a, &b, &c};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* *this is empty. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list2.push_back (a);
+ list2.push_back (b);
+ list2.push_back (c);
+
+ std::swap (list1, list2);
+
+ expected = {&a, &b, &c};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Both lists empty. */
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ std::swap (list1, list2);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+
+ {
+ /* Swap one element twice. */
+ item_type a ("a");
+ ListType list1;
+ ListType list2;
+ std::vector<const item_type *> expected;
+
+ list1.push_back (a);
+
+ std::swap (list1, list2);
+
+ expected = {};
+ verify_items (list1, expected);
+
+ expected = {&a};
+ verify_items (list2, expected);
+
+ std::swap (list1, list2);
+
+ expected = {&a};
+ verify_items (list1, expected);
+
+ expected = {};
+ verify_items (list2, expected);
+ }
+ }
+
+ static void
+ test_front_back ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ const ListType &clist = list;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ gdb_assert (&list.front () == &a);
+ gdb_assert (&clist.front () == &a);
+ gdb_assert (&list.back () == &c);
+ gdb_assert (&clist.back () == &c);
+ }
+
+ static void
+ test_push_front ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ expected = {};
+ verify_items (list, expected);
+
+ list.push_front (a);
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.push_front (b);
+ expected = {&b, &a};
+ verify_items (list, expected);
+
+ list.push_front (c);
+ expected = {&c, &b, &a};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_push_back ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ expected = {};
+ verify_items (list, expected);
+
+ list.push_back (a);
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.push_back (b);
+ expected = {&a, &b};
+ verify_items (list, expected);
+
+ list.push_back (c);
+ expected = {&a, &b, &c};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_insert ()
+ {
+ std::vector<const item_type *> expected;
+
+ {
+ /* Insert at beginning. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+
+
+ list.insert (list.begin (), a);
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.insert (list.begin (), b);
+ expected = {&b, &a};
+ verify_items (list, expected);
+
+ list.insert (list.begin (), c);
+ expected = {&c, &b, &a};
+ verify_items (list, expected);
+ }
+
+ {
+ /* Insert at end. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+
+
+ list.insert (list.end (), a);
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.insert (list.end (), b);
+ expected = {&a, &b};
+ verify_items (list, expected);
+
+ list.insert (list.end (), c);
+ expected = {&a, &b, &c};
+ verify_items (list, expected);
+ }
+
+ {
+ /* Insert in the middle. */
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+
+ list.push_back (a);
+ list.push_back (b);
+
+ list.insert (list.iterator_to (b), c);
+ expected = {&a, &c, &b};
+ verify_items (list, expected);
+ }
+
+ {
+ /* Insert in empty list. */
+ item_type a ("a");
+ ListType list;
+
+ list.insert (list.end (), a);
+ expected = {&a};
+ verify_items (list, expected);
+ }
+ }
+
+ static void
+ test_pop_front ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ list.pop_front ();
+ expected = {&b, &c};
+ verify_items (list, expected);
+
+ list.pop_front ();
+ expected = {&c};
+ verify_items (list, expected);
+
+ list.pop_front ();
+ expected = {};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_pop_back ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ list.pop_back();
+ expected = {&a, &b};
+ verify_items (list, expected);
+
+ list.pop_back ();
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.pop_back ();
+ expected = {};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_erase ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ list.erase (list.iterator_to (b));
+ expected = {&a, &c};
+ verify_items (list, expected);
+
+ list.erase (list.iterator_to (c));
+ expected = {&a};
+ verify_items (list, expected);
+
+ list.erase (list.iterator_to (a));
+ expected = {};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_clear ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ list.clear ();
+ expected = {};
+ verify_items (list, expected);
+
+ /* Verify idempotency. */
+ list.clear ();
+ expected = {};
+ verify_items (list, expected);
+ }
+
+ static void
+ test_clear_and_dispose ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ std::vector<const item_type *> expected;
+ std::unordered_set<const item_type *> disposer_seen;
+ int disposer_calls = 0;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ auto disposer = [&] (const item_type *item)
+ {
+ disposer_seen.insert (item);
+ disposer_calls++;
+ };
+ list.clear_and_dispose (disposer);
+
+ expected = {};
+ verify_items (list, expected);
+ gdb_assert (disposer_calls == 3);
+ gdb_assert (disposer_seen.find (&a) != disposer_seen.end ());
+ gdb_assert (disposer_seen.find (&b) != disposer_seen.end ());
+ gdb_assert (disposer_seen.find (&c) != disposer_seen.end ());
+
+ /* Verify idempotency. */
+ list.clear_and_dispose (disposer);
+ gdb_assert (disposer_calls == 3);
+ }
+
+ static void
+ test_empty ()
+ {
+ item_type a ("a");
+ ListType list;
+
+ gdb_assert (list.empty ());
+ list.push_back (a);
+ gdb_assert (!list.empty ());
+ list.erase (list.iterator_to (a));
+ gdb_assert (list.empty ());
+ }
+
+ static void
+ test_begin_end ()
+ {
+ item_type a ("a"), b ("b"), c ("c");
+ ListType list;
+ const ListType &clist = list;
+
+ list.push_back (a);
+ list.push_back (b);
+ list.push_back (c);
+
+ gdb_assert (&*list.begin () == &a);
+ gdb_assert (&*list.cbegin () == &a);
+ gdb_assert (&*clist.begin () == &a);
+ gdb_assert (&*list.rbegin () == &c);
+ gdb_assert (&*list.crbegin () == &c);
+ gdb_assert (&*clist.rbegin () == &c);
+
+ /* At least check that they compile. */
+ list.end ();
+ list.cend ();
+ clist.end ();
+ list.rend ();
+ list.crend ();
+ clist.end ();
+ }
+};
+
+template <typename ListType>
+static void
+test_intrusive_list ()
+{
+ intrusive_list_test<ListType> tests;
+
+ tests.test_move_constructor ();
+ tests.test_move_assignment ();
+ tests.test_swap ();
+ tests.test_front_back ();
+ tests.test_push_front ();
+ tests.test_push_back ();
+ tests.test_insert ();
+ tests.test_pop_front ();
+ tests.test_pop_back ();
+ tests.test_erase ();
+ tests.test_clear ();
+ tests.test_clear_and_dispose ();
+ tests.test_empty ();
+ tests.test_begin_end ();
+}
+
+static void
+test_node_is_linked ()
+{
+ {
+ item_with_base a ("a");
+ item_with_base_list list;
+
+ gdb_assert (!a.is_linked ());
+ list.push_back (a);
+ gdb_assert (a.is_linked ());
+ list.pop_back ();
+ gdb_assert (!a.is_linked ());
+ }
+
+ {
+ item_with_member a ("a");
+ item_with_member_list list;
+
+ gdb_assert (!a.node.is_linked ());
+ list.push_back (a);
+ gdb_assert (a.node.is_linked ());
+ list.pop_back ();
+ gdb_assert (!a.node.is_linked ());
+ }
+}
+
+static void
+test_intrusive_list ()
+{
+ test_intrusive_list<item_with_base_list> ();
+ test_intrusive_list<item_with_member_list> ();
+ test_node_is_linked ();
+}
+
+void _initialize_intrusive_list_selftests ();
+void
+_initialize_intrusive_list_selftests ()
+{
+ selftests::register_test
+ ("intrusive_list", test_intrusive_list);
+}
diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h
new file mode 100644
index 000000000000..8e98e5b2c1a5
--- /dev/null
+++ b/gdbsupport/intrusive_list.h
@@ -0,0 +1,559 @@
+/* Intrusive double linked list for GDB, the GNU debugger.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef GDBSUPPORT_INTRUSIVE_LIST_H
+#define GDBSUPPORT_INTRUSIVE_LIST_H
+
+#define UNLINKED_VALUE ((T *) -1)
+
+/* A list node. The elements put in an intrusive_list either inherit
+ from this, or have a field of this type. */
+template<typename T>
+struct intrusive_list_node
+{
+ bool is_linked () const
+ {
+ return next != UNLINKED_VALUE;
+ }
+
+ T *next = UNLINKED_VALUE;
+ T *prev = UNLINKED_VALUE;
+};
+
+/* Follows a couple types used by intrusive_list as template parameter to find
+ the intrusive_list_node for a given element. One for lists where the
+ elements inherit intrusive_list_node, and another for elements that keep the
+ node as member field. */
+
+/* For element types that inherit from intrusive_list_node. */
+
+template<typename T>
+struct intrusive_base_node
+{
+ static intrusive_list_node<T> *as_node (T *elem)
+ { return elem; }
+};
+
+/* For element types that keep the node as member field. */
+
+template<typename T, intrusive_list_node<T> T::*MemberNode>
+struct intrusive_member_node
+{
+ static intrusive_list_node<T> *as_node (T *elem)
+ { return &(elem->*MemberNode); }
+};
+
+/* Common code for forward and reverse iterators. */
+
+template<typename T, typename AsNode, typename SelfType>
+struct intrusive_list_base_iterator
+{
+ using self_type = SelfType;
+ using iterator_category = std::bidirectional_iterator_tag;
+ using value_type = T;
+ using pointer = T *;
+ using const_pointer = const T *;
+ using reference = T &;
+ using const_reference = const T &;
+ using difference_type = ptrdiff_t;
+ using size_type = size_t;
+ using node_type = intrusive_list_node<T>;
+
+ /* Create an iterator pointing to ELEM. */
+ explicit intrusive_list_base_iterator (T *elem)
+ : m_elem (elem)
+ {}
+
+ /* Create a past-the-end iterator. */
+ intrusive_list_base_iterator ()
+ : m_elem (nullptr)
+ {}
+
+ reference operator* () const
+ { return *m_elem; }
+
+ pointer operator-> () const
+ { return m_elem; }
+
+ bool operator== (const self_type &other) const
+ { return m_elem == other.m_elem; }
+
+ bool operator!= (const self_type &other) const
+ { return m_elem != other.m_elem; }
+
+protected:
+ static node_type *as_node (T *elem)
+ { return AsNode::as_node (elem); }
+
+ /* A past-end-the iterator points to the list's head. */
+ pointer m_elem;
+};
+
+/* Forward iterator for an intrusive_list. */
+
+template<typename T, typename AsNode = intrusive_base_node<T>>
+struct intrusive_list_iterator
+ : public intrusive_list_base_iterator
+ <T, AsNode, intrusive_list_iterator<T, AsNode>>
+{
+ using base = intrusive_list_base_iterator
+ <T, AsNode, intrusive_list_iterator<T, AsNode>>;
+ using self_type = typename base::self_type;
+ using node_type = typename base::node_type;
+
+ /* Inherit constructor and M_NODE visibility from base. */
+ using base::base;
+ using base::m_elem;
+
+ self_type &operator++ ()
+ {
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->next;
+ return *this;
+ }
+
+ self_type operator++ (int)
+ {
+ self_type temp = *this;
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->next;
+ return temp;
+ }
+
+ self_type &operator-- ()
+ {
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->prev;
+ return *this;
+ }
+
+ self_type operator-- (int)
+ {
+ self_type temp = *this;
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->prev;
+ return temp;
+ }
+};
+
+/* Reverse iterator for an intrusive_list. */
+
+template<typename T, typename AsNode = intrusive_base_node<T>>
+struct intrusive_list_reverse_iterator
+ : public intrusive_list_base_iterator
+ <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>
+{
+ using base = intrusive_list_base_iterator
+ <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>;
+ using self_type = typename base::self_type;
+
+ /* Inherit constructor and M_NODE visibility from base. */
+ using base::base;
+ using base::m_elem;
+ using node_type = typename base::node_type;
+
+ self_type &operator++ ()
+ {
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->prev;
+ return *this;
+ }
+
+ self_type operator++ (int)
+ {
+ self_type temp = *this;
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->prev;
+ return temp;
+ }
+
+ self_type &operator-- ()
+ {
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->next;
+ return *this;
+ }
+
+ self_type operator-- (int)
+ {
+ self_type temp = *this;
+ node_type *node = this->as_node (m_elem);
+ m_elem = node->next;
+ return temp;
+ }
+};
+
+/* An intrusive double-linked list.
+
+ T is the type of the elements to link. The type T must either:
+
+ - inherit from intrusive_list_node<T>
+ - have an intrusive_list_node<T> member
+
+ AsNode is a type with an as_node static method used to get a node from an
+ element. If elements inherit from intrusive_list_node<T>, use the default
+ intrusive_base_node<T>. If elements have an intrusive_list_node<T> member,
+ use:
+
+ instrusive_member_node<T, &T::member>
+
+ where `member` is the name of the member. */
+
+template <typename T, typename AsNode = intrusive_base_node<T>>
+class intrusive_list
+{
+public:
+ using value_type = T;
+ using pointer = T *;
+ using const_pointer = const T *;
+ using reference = T &;
+ using const_reference = const T &;
+ using difference_type = ptrdiff_t;
+ using size_type = size_t;
+ using iterator = intrusive_list_iterator<T, AsNode>;
+ using reverse_iterator = intrusive_list_reverse_iterator<T, AsNode>;
+ using const_iterator = const intrusive_list_iterator<T, AsNode>;
+ using const_reverse_iterator
+ = const intrusive_list_reverse_iterator<T, AsNode>;
+ using node_type = intrusive_list_node<T>;
+
+ intrusive_list () = default;
+
+ ~intrusive_list ()
+ {
+ clear ();
+ }
+
+ intrusive_list (intrusive_list &&other)
+ : m_front (other.m_front),
+ m_back (other.m_back)
+ {
+ other.m_front = nullptr;
+ other.m_back = nullptr;
+ }
+
+ intrusive_list &operator= (intrusive_list &&other)
+ {
+ m_front = other.m_front;
+ m_back = other.m_back;
+ other.m_front = nullptr;
+ other.m_back = nullptr;
+
+ return *this;
+ }
+
+ void swap (intrusive_list &other)
+ {
+ std::swap (m_front, other.m_front);
+ std::swap (m_back, other.m_back);
+ }
+
+ iterator iterator_to (reference value)
+ {
+ return iterator (&value);
+ }
+
+ const_iterator iterator_to (const_reference value)
+ {
+ return const_iterator (&value);
+ }
+
+ reference front ()
+ {
+ gdb_assert (!this->empty ());
+ return *m_front;
+ }
+
+ const_reference front () const
+ {
+ gdb_assert (!this->empty ());
+ return *m_front;
+ }
+
+ reference back ()
+ {
+ gdb_assert (!this->empty ());
+ return *m_back;
+ }
+
+ const_reference back () const
+ {
+ gdb_assert (!this->empty ());
+ return *m_back;
+ }
+
+ void push_front (reference elem)
+ {
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ if (this->empty ())
+ this->push_empty (elem);
+ else
+ this->push_front_non_empty (elem);
+ }
+
+ void push_back (reference elem)
+ {
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ if (this->empty ())
+ this->push_empty (elem);
+ else
+ this->push_back_non_empty (elem);
+ }
+
+ /* Inserts ELEM before POS. */
+ void insert (const_iterator pos, reference elem)
+ {
+ if (this->empty ())
+ return this->push_empty (elem);
+
+ if (pos == this->begin ())
+ return this->push_front_non_empty (elem);
+
+ if (pos == this->end ())
+ return this->push_back_non_empty (elem);
+
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+ T *pos_elem = &*pos;
+ intrusive_list_node<T> *pos_node = as_node (pos_elem);
+ T *prev_elem = pos_node->prev;
+ intrusive_list_node<T> *prev_node = as_node (prev_elem);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ elem_node->prev = prev_elem;
+ prev_node->next = &elem;
+ elem_node->next = pos_elem;
+ pos_node->prev = &elem;
+ }
+
+ void pop_front ()
+ {
+ gdb_assert (!this->empty ());
+ erase_element (*m_front);
+ }
+
+ void pop_back ()
+ {
+ gdb_assert (!this->empty ());
+ erase_element (*m_back);
+ }
+
+private:
+ /* Push ELEM in the list, knowing the list is empty. */
+ void push_empty (T &elem)
+ {
+ gdb_assert (this->empty ());
+
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ m_front = &elem;
+ m_back = &elem;
+ elem_node->prev = nullptr;
+ elem_node->next = nullptr;
+ }
+
+ /* Push ELEM at the front of the list, knowing the list is not empty. */
+ void push_front_non_empty (T &elem)
+ {
+ gdb_assert (!this->empty ());
+
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+ intrusive_list_node<T> *front_node = as_node (m_front);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ elem_node->next = m_front;
+ front_node->prev = &elem;
+ elem_node->prev = nullptr;
+ m_front = &elem;
+ }
+
+ /* Push ELEM at the back of the list, knowing the list is not empty. */
+ void push_back_non_empty (T &elem)
+ {
+ gdb_assert (!this->empty ());
+
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+ intrusive_list_node<T> *back_node = as_node (m_back);
+
+ gdb_assert (elem_node->next == UNLINKED_VALUE);
+ gdb_assert (elem_node->prev == UNLINKED_VALUE);
+
+ elem_node->prev = m_back;
+ back_node->next = &elem;
+ elem_node->next = nullptr;
+ m_back = &elem;
+ }
+
+ void erase_element (T &elem)
+ {
+ intrusive_list_node<T> *elem_node = as_node (&elem);
+
+ gdb_assert (elem_node->prev != UNLINKED_VALUE);
+ gdb_assert (elem_node->next != UNLINKED_VALUE);
+
+ if (m_front == &elem)
+ {
+ gdb_assert (elem_node->prev == nullptr);
+ m_front = elem_node->next;
+ }
+ else
+ {
+ gdb_assert (elem_node->prev != nullptr);
+ intrusive_list_node<T> *prev_node = as_node (elem_node->prev);
+ prev_node->next = elem_node->next;
+ }
+
+ if (m_back == &elem)
+ {
+ gdb_assert (elem_node->next == nullptr);
+ m_back = elem_node->prev;
+ }
+ else
+ {
+ gdb_assert (elem_node->next != nullptr);
+ intrusive_list_node<T> *next_node = as_node (elem_node->next);
+ next_node->prev = elem_node->prev;
+ }
+
+ elem_node->next = UNLINKED_VALUE;
+ elem_node->prev = UNLINKED_VALUE;
+ }
+
+public:
+ /* Remove the element pointed by I from the list. The element
+ pointed by I is not destroyed. */
+ iterator erase (const_iterator i)
+ {
+ iterator ret = i;
+ ++ret;
+
+ erase_element (*i);
+
+ return ret;
+ }
+
+ /* Erase all the elements. The elements are not destroyed. */
+ void clear ()
+ {
+ while (!this->empty ())
+ pop_front ();
+ }
+
+ /* Erase all the elements. Disposer::operator()(pointer) is called
+ for each of the removed elements. */
+ template<typename Disposer>
+ void clear_and_dispose (Disposer disposer)
+ {
+ while (!this->empty ())
+ {
+ pointer p = &front ();
+ pop_front ();
+ disposer (p);
+ }
+ }
+
+ bool empty () const
+ {
+ return m_front == nullptr;
+ }
+
+ iterator begin () noexcept
+ {
+ return iterator (m_front);
+ }
+
+ const_iterator begin () const noexcept
+ {
+ return const_iterator (m_front);
+ }
+
+ const_iterator cbegin () const noexcept
+ {
+ return const_iterator (m_front);
+ }
+
+ iterator end () noexcept
+ {
+ return {};
+ }
+
+ const_iterator end () const noexcept
+ {
+ return {};
+ }
+
+ const_iterator cend () const noexcept
+ {
+ return {};
+ }
+
+ reverse_iterator rbegin () noexcept
+ {
+ return reverse_iterator (m_back);
+ }
+
+ const_reverse_iterator rbegin () const noexcept
+ {
+ return const_reverse_iterator (m_back);
+ }
+
+ const_reverse_iterator crbegin () const noexcept
+ {
+ return const_reverse_iterator (m_back);
+ }
+
+ reverse_iterator rend () noexcept
+ {
+ return {};
+ }
+
+ const_reverse_iterator rend () const noexcept
+ {
+ return {};
+ }
+
+ const_reverse_iterator crend () const noexcept
+ {
+ return {};
+ }
+
+private:
+ static node_type *as_node (T *elem)
+ {
+ return AsNode::as_node (elem);
+ }
+
+ T *m_front = nullptr;
+ T *m_back = nullptr;
+};
+
+#endif /* GDBSUPPORT_INTRUSIVE_LIST_H */
diff --git a/gdbsupport/reference-to-pointer-iterator.h b/gdbsupport/reference-to-pointer-iterator.h
new file mode 100644
index 000000000000..7303fa4a04ae
--- /dev/null
+++ b/gdbsupport/reference-to-pointer-iterator.h
@@ -0,0 +1,79 @@
+/* An iterator wrapper that yields pointers instead of references.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H
+#define GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H
+
+/* Wrap an iterator that yields references to objects so that it yields
+ pointers to objects instead.
+
+ This is useful for example to bridge the gap between iterators on intrusive
+ lists, which yield references, and the rest of GDB, which for legacy reasons
+ expects to iterate on pointers. */
+
+template <typename IteratorType>
+struct reference_to_pointer_iterator
+{
+ using self_type = reference_to_pointer_iterator;
+ using value_type = typename IteratorType::value_type *;
+ using reference = typename IteratorType::value_type *&;
+ using pointer = typename IteratorType::value_type **;
+ using iterator_category = typename IteratorType::iterator_category;
+ using difference_type = typename IteratorType::difference_type;
+
+ /* Construct a reference_to_pointer_iterator, passing args to the underyling
+ iterator. */
+ template <typename... Args>
+ reference_to_pointer_iterator (Args &&...args)
+ : m_it (std::forward<Args> (args)...)
+ {}
+
+ /* Create a past-the-end iterator.
+
+ Assumes that default-constructing an underlying iterator creates a
+ past-the-end iterator. */
+ reference_to_pointer_iterator ()
+ {}
+
+ /* Need these as the variadic constructor would be a better match
+ otherwise. */
+ reference_to_pointer_iterator (reference_to_pointer_iterator &) = default;
+ reference_to_pointer_iterator (const reference_to_pointer_iterator &) = default;
+ reference_to_pointer_iterator (reference_to_pointer_iterator &&) = default;
+
+ value_type operator* () const
+ { return &*m_it; }
+
+ self_type &operator++ ()
+ {
+ ++m_it;
+ return *this;
+ }
+
+ bool operator== (const self_type &other) const
+ { return m_it == other.m_it; }
+
+ bool operator!= (const self_type &other) const
+ { return m_it != other.m_it; }
+
+private:
+ /* The underlying iterator. */
+ IteratorType m_it;
+};
+
+#endif /* GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H */
--
2.32.0
More information about the Gdb-patches
mailing list