From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id 4MbNJrlu0mCPawAAWB0awg (envelope-from ) for ; Tue, 22 Jun 2021 19:14:01 -0400 Received: by simark.ca (Postfix, from userid 112) id 9AFA61F1F2; Tue, 22 Jun 2021 19:14:01 -0400 (EDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-1.1 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,MAILING_LIST_MULTI,URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.2 Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id 8BBD01EE14 for ; Tue, 22 Jun 2021 19:13:59 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CAF243955434 for ; Tue, 22 Jun 2021 23:13:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org CAF243955434 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624403638; bh=4S71zNmJ0bU29S5zRnXkijaWFxvNb1OZy4mlOrXfg8E=; h=Date:To:Subject:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=PLOJFE0BgZhaacrPi8OglEBVG7im4cX4Xpb2mIObFRlL59LX3PawpbE6DjYj2ni0o 1BN/G+JEsrWq57FojMv/TQeEESUT2IaKCdCAsLX/H6qM+1HenMz8pN7ekTaN6N72Ke dH6ALCxUdHnPvyNWHU6ZzjfRuDHqzGikDG5TGwmY= Received: from lndn.lancelotsix.com (vps-42846194.vps.ovh.net [IPv6:2001:41d0:801:2000::2400]) by sourceware.org (Postfix) with ESMTPS id B60E2385782A for ; Tue, 22 Jun 2021 23:13:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B60E2385782A Received: from ubuntu.lan (unknown [IPv6:2a02:390:9086::635]) by lndn.lancelotsix.com (Postfix) with ESMTPSA id 8FB40819E2; Tue, 22 Jun 2021 23:13:24 +0000 (UTC) Date: Tue, 22 Jun 2021 23:13:19 +0000 To: Simon Marchi , Pedro Alves Subject: Re: [PATCH 02/11] gdb: introduce intrusive_list, make thread_info use it Message-ID: <20210622231319.6hgxooumjnkns7pb@ubuntu.lan> References: <20210622165704.2404007-1-simon.marchi@polymtl.ca> <20210622165704.2404007-3-simon.marchi@polymtl.ca> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20210622165704.2404007-3-simon.marchi@polymtl.ca> X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.5.11 (lndn.lancelotsix.com [0.0.0.0]); Tue, 22 Jun 2021 23:13:24 +0000 (UTC) X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Lancelot SIX via Gdb-patches Reply-To: Lancelot SIX Cc: Simon Marchi , gdb-patches@sourceware.org Errors-To: gdb-patches-bounces+public-inbox=simark.ca@sourceware.org Sender: "Gdb-patches" On Tue, Jun 22, 2021 at 12:56:55PM -0400, Simon Marchi via Gdb-patches wrote: > From: Pedro Alves > > 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 doesn't work. > You need to instead use std::list, 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 > YYYY-MM-DD Simon Marchi > > 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. > : 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) : Change type to > intrusive_list. > : Adjust. > : 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) > : Remove. > : 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 > 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 > { > 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_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 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 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::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::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; > +using inf_threads_iterator > + = reference_to_pointer_iterator::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 . */ > + > +#include "defs.h" > + > +#include "gdbsupport/intrusive_list.h" > +#include "gdbsupport/selftest.h" > +#include > + > +/* 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 (const char *name) > + : name (name) > + {} > + > + const char *const name; > +}; > + > +using item_with_base_list = intrusive_list; > + > +/* 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 node; > +}; > + > +using item_with_member_node > + = intrusive_member_node; > +using item_with_member_list > + = intrusive_list; > + > +/* 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 > +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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 expected; > + std::unordered_set 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 > +static void > +test_intrusive_list () > +{ > + intrusive_list_test 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 (); > + test_intrusive_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 . */ > + > +#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 > +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 > +struct intrusive_base_node > +{ > + static intrusive_list_node *as_node (T *elem) > + { return elem; } > +}; > + > +/* For element types that keep the node as member field. */ > + > +template T::*MemberNode> > +struct intrusive_member_node > +{ > + static intrusive_list_node *as_node (T *elem) > + { return &(elem->*MemberNode); } > +}; > + > +/* Common code for forward and reverse iterators. */ > + > +template > +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; > + > + /* 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> > +struct intrusive_list_iterator > + : public intrusive_list_base_iterator > + > > +{ > + using base = intrusive_list_base_iterator > + >; > + 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> > +struct intrusive_list_reverse_iterator > + : public intrusive_list_base_iterator > + > > +{ > + using base = intrusive_list_base_iterator > + >; > + 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 > + - have an intrusive_list_node 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, use the default > + intrusive_base_node. If elements have an intrusive_list_node member, > + use: > + > + instrusive_member_node > + > + where `member` is the name of the member. */ > + > +template > > +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; > + using reverse_iterator = intrusive_list_reverse_iterator; > + using const_iterator = const intrusive_list_iterator; > + using const_reverse_iterator > + = const intrusive_list_reverse_iterator; > + using node_type = intrusive_list_node; > + > + 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 *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 *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 *elem_node = as_node (&elem); > + T *pos_elem = &*pos; > + intrusive_list_node *pos_node = as_node (pos_elem); > + T *prev_elem = pos_node->prev; > + intrusive_list_node *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 *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 *elem_node = as_node (&elem); > + intrusive_list_node *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 *elem_node = as_node (&elem); > + intrusive_list_node *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 *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 *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 *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 > + 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 . */ > + > +#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 > +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 > + reference_to_pointer_iterator (Args &&...args) > + : m_it (std::forward (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 >