[PATCH 02/11] gdb: introduce intrusive_list, make thread_info use it
Lancelot SIX
lsix@lancelotsix.com
Tue Jun 22 23:13:19 GMT 2021
On Tue, Jun 22, 2021 at 12:56:55PM -0400, Simon Marchi via Gdb-patches wrote:
> 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}>"
Hi,
I do not know what are the compatibility constraints / minimum python
version required, but f-string do require at least python-3.6. This
covers all still supported python versions, but there might be distros
out-there that are not there yet (there are a few of those in this
file).
> + ).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):
The documentation for the function should probably go as a doc string,
not a comment before the function:
def _uses_member_node(self):
""" Return True if the list items use a node as a member. Return False
if they use a node as a base class.
"""
The same remark stands for the other method in this file.
Best,
Lancelot.
> + 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
s/memer/member/ ?
> + # 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