[patch 4/8] Types GC [varobj_list to all_root_varobjs]

[patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Jan Kratochvil]

Hi,

this patch is completely optional and it can be dropped, just technically the
other patches depend on it.  I find the callback based iterator easier to use,
in fact there were bugs due to the current calling semantics (`floating'
lockup, memory leaks).

The new function all_root_varobjs really fully replaces varobj_list just
varobj_list gets finally dropped only in the patch 8/8.


Thanks,
Jan

gdb/
2009-05-25  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* mi/mi-cmd-var.c (mi_cmd_var_update): Remove variables var, rootlist,
	cr, nv.  Initialize CLEANUP and "changelist" uncoditionally.  Move the
	all variables handling code to ...
	(mi_cmd_var_update_iter): ... a new function.
	(struct mi_cmd_var_update): New.
	* varobj.c (varobj_list): Define the function now as static.
	(all_root_varobjs): New function.
	* varobj.h (varobj_list): Remove the declaration.
	(all_root_varobjs): New declaration.
---
 gdb/mi/mi-cmd-var.c |   96 ++++++++++++++++++++++++++++-----------------------
 gdb/varobj.c        |   20 ++++++++++-
 gdb/varobj.h        |    3 +-
 3 files changed, 74 insertions(+), 45 deletions(-)

diff --git a/gdb/mi/mi-cmd-var.c b/gdb/mi/mi-cmd-var.c
index 9de8d3d..688999c 100644
--- a/gdb/mi/mi-cmd-var.c
+++ b/gdb/mi/mi-cmd-var.c
@@ -542,15 +542,46 @@ mi_cmd_var_assign (char *command, char **argv, int argc)
   ui_out_field_string (uiout, "value", varobj_get_value (var));
 }
 
+/* Type used for parameters passing to mi_cmd_var_update_iter.  */
+
+struct mi_cmd_var_update
+  {
+    int only_floating;
+    enum print_values print_values;
+  };
+
+/* Helper for mi_cmd_var_update - update each VAR.  */
+
+static void
+mi_cmd_var_update_iter (struct varobj *var, void *data_pointer)
+{
+  struct mi_cmd_var_update *data = data_pointer;
+  int thread_id, thread_stopped;
+
+  thread_id = varobj_get_thread_id (var);
+
+  if (thread_id == -1 && is_stopped (inferior_ptid))
+    thread_stopped = 1;
+  else
+    {
+      struct thread_info *tp = find_thread_id (thread_id);
+
+      if (tp)
+	thread_stopped = is_stopped (tp->ptid);
+      else
+	thread_stopped = 1;
+    }
+
+  if (thread_stopped)
+    if (!data->only_floating || varobj_floating_p (var))
+      varobj_update_one (var, data->print_values, 0 /* implicit */);
+}
+
 void
 mi_cmd_var_update (char *command, char **argv, int argc)
 {
-  struct varobj *var;
-  struct varobj **rootlist;
-  struct varobj **cr;
   struct cleanup *cleanup;
   char *name;
-  int nv;
   enum print_values print_values;
 
   if (argc != 1 && argc != 2)
@@ -566,56 +597,35 @@ mi_cmd_var_update (char *command, char **argv, int argc)
   else
     print_values = PRINT_NO_VALUES;
 
+  if (mi_version (uiout) <= 1)
+    cleanup = make_cleanup_ui_out_tuple_begin_end (uiout, "changelist");
+  else
+    cleanup = make_cleanup_ui_out_list_begin_end (uiout, "changelist");
+
   /* Check if the parameter is a "*" which means that we want
      to update all variables */
 
   if ((*name == '*' || *name == '@') && (*(name + 1) == '\0'))
     {
-      nv = varobj_list (&rootlist);
-      cleanup = make_cleanup (xfree, rootlist);
-      if (mi_version (uiout) <= 1)
-        make_cleanup_ui_out_tuple_begin_end (uiout, "changelist");
-      else
-        make_cleanup_ui_out_list_begin_end (uiout, "changelist");
-      if (nv <= 0)
-	{
-	  do_cleanups (cleanup);
-	  return;
-	}
-      cr = rootlist;
-      while (*cr != NULL)
-	{
-	  int thread_id = varobj_get_thread_id (*cr);
-	  int thread_stopped = 0;
-	  if (thread_id == -1 && is_stopped (inferior_ptid))
-	    thread_stopped = 1;
-	  else
-	    {	      
-	      struct thread_info *tp = find_thread_id (thread_id);
-	      if (tp)
-		thread_stopped = is_stopped (tp->ptid);
-	      else
-		thread_stopped = 1;
-	    }
-	  if (thread_stopped)
-	    if (*name == '*' || varobj_floating_p (*cr))
-	      varobj_update_one (*cr, print_values, 0 /* implicit */);
-	  cr++;
-	}
-      do_cleanups (cleanup);
+      struct mi_cmd_var_update data;
+
+      data.only_floating = *name == '@';
+      data.print_values = print_values;
+
+      /* varobj_update_one automatically updates all the children of VAROBJ.
+	 Therefore update each VAROBJ only once by iterating only the root
+	 VAROBJs.  */
+
+      all_root_varobjs (mi_cmd_var_update_iter, &data);
     }
   else
     {
-      /* Get varobj handle, if a valid var obj name was specified */
-      var = varobj_get_handle (name);
+      struct varobj *var = varobj_get_handle (name);
 
-      if (mi_version (uiout) <= 1)
-        cleanup = make_cleanup_ui_out_tuple_begin_end (uiout, "changelist");
-      else
-        cleanup = make_cleanup_ui_out_list_begin_end (uiout, "changelist");
       varobj_update_one (var, print_values, 1 /* explicit */);
-      do_cleanups (cleanup);
     }
+
+  do_cleanups (cleanup);
 }
 
 /* Helper for mi_cmd_var_update().  */
diff --git a/gdb/varobj.c b/gdb/varobj.c
index e8556d7..718c690 100644
--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -946,7 +946,7 @@ varobj_set_value (struct varobj *var, char *expression)
 }
 
 /* Returns a malloc'ed list with all root variable objects */
-int
+static int
 varobj_list (struct varobj ***varlist)
 {
   struct varobj **cv;
@@ -2734,6 +2734,24 @@ java_value_of_variable (struct varobj *var, enum varobj_display_formats format)
 {
   return cplus_value_of_variable (var, format);
 }
+
+/* Iterate all the existing _root_ VAROBJs and call the FUNC callback for them
+   with an arbitrary caller supplied DATA pointer.  */
+
+void
+all_root_varobjs (void (*func) (struct varobj *var, void *data), void *data)
+{
+  struct varobj_root *var_root, *var_root_next;
+
+  /* Iterate "safely" - handle if the callee deletes its passed VAROBJ.  */
+
+  for (var_root = rootlist; var_root != NULL; var_root = var_root_next)
+    {
+      var_root_next = var_root->next;
+
+      (*func) (var_root->rootvar, data);
+    }
+}
 \f
 extern void _initialize_varobj (void);
 void
diff --git a/gdb/varobj.h b/gdb/varobj.h
index f2cdcf8..c1471d4 100644
--- a/gdb/varobj.h
+++ b/gdb/varobj.h
@@ -130,7 +130,8 @@ extern char *varobj_get_value (struct varobj *var);
 
 extern int varobj_set_value (struct varobj *var, char *expression);
 
-extern int varobj_list (struct varobj ***rootlist);
+extern void all_root_varobjs (void (*func) (struct varobj *var, void *data),
+			      void *data);
 
 extern VEC(varobj_update_result) *varobj_update (struct varobj **varp, 
 						 int explicit);
-- 
1.6.2.2

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Jan> this patch is completely optional and it can be dropped, just
Jan> technically the other patches depend on it.  I find the callback
Jan> based iterator easier to use, in fact there were bugs due to the
Jan> current calling semantics (`floating' lockup, memory leaks).

It seems reasonable to me, though it would be nice to have Volodya's
approval.

Details on the bugs that this fixes would be nice.
A test case would also be nice, assuming these are testable.

Tom

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Jan Kratochvil]

On Tue, 09 Jun 2009 22:50:42 +0200, Tom Tromey wrote:
> >>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
> 
> Jan> I find the callback based iterator easier to use,
[...]
> It seems reasonable to me, though it would be nice to have Volodya's
> approval.

Is it OK to check it in, Vladimir?  The patch would go in unchanged:
	http://sourceware.org/ml/gdb-patches/2009-05/msg00547.html

Regression re-tested now on {x86_64,i686}-fedora-linux-gnu.


> Jan> in fact there were bugs due to the
> Jan> current calling semantics (`floating' lockup, memory leaks).
> 
> Details on the bugs that this fixes would be nice.
> A test case would also be nice, assuming these are testable.

The `floating' lockup will get fixed by a later patch using this new
all_root_varobjs function.   A testcase for it was in a now-obsolete patch:
	[patch] Fix gdb.mi hang on floating VAROBJs
	http://sourceware.org/ml/gdb-patches/2009-05/msg00433.html
This patch itself still does not fix it.

The (small) memory caused by the current semantics you fixed by:
	RFA: fix PR 9350
	http://sourceware.org/ml/gdb-patches/2009-01/threads.html#00066
	7002b113b9e2afed981d3eb9d4157c98a3a3c447
	http://sources.redhat.com/cgi-bin/cvsweb.cgi/src/gdb/varobj.c.diff?cvsroot=src&r1=1.121&r2=1.122


Thanks,
Jan

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Vladimir Prus]

On Thursday 02 July 2009 Jan Kratochvil wrote:

> On Tue, 09 Jun 2009 22:50:42 +0200, Tom Tromey wrote:
> > >>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
> > 
> > Jan> I find the callback based iterator easier to use,
> [...]
> > It seems reasonable to me, though it would be nice to have Volodya's
> > approval.
> 
> Is it OK to check it in, Vladimir?  The patch would go in unchanged:
> 	http://sourceware.org/ml/gdb-patches/2009-05/msg00547.html
> 
> Regression re-tested now on {x86_64,i686}-fedora-linux-gnu.

Is this cleanup-only patch? I am a bit concerned that it appears
to increase code size, and all it does it changes explicit iteration
to callback iteration. Can we just make varobj.c expose vector of
varobjs?

> > Jan> in fact there were bugs due to the
> > Jan> current calling semantics (`floating' lockup, memory leaks).
> > 
> > Details on the bugs that this fixes would be nice.
> > A test case would also be nice, assuming these are testable.
> 
> The `floating' lockup will get fixed by a later patch using this new
> all_root_varobjs function.   A testcase for it was in a now-obsolete patch:
> 	[patch] Fix gdb.mi hang on floating VAROBJs
> 	http://sourceware.org/ml/gdb-patches/2009-05/msg00433.html
> This patch itself still does not fix it.

IIUC, the varobj_invalidate problem can be fixed with a small patch below.
Am I missing something? If no, such a patch is not in any way made easier
by callback iteration.

- Volodya

Index: gdb/varobj.c
===================================================================
RCS file: /cvs/src/src/gdb/varobj.c,v
retrieving revision 1.137
diff -u -p -r1.137 varobj.c
--- gdb/varobj.c        30 Jun 2009 09:24:47 -0000      1.137
+++ gdb/varobj.c        2 Jul 2009 10:08:22 -0000
@@ -3225,8 +3225,10 @@ varobj_invalidate (void)
          /* Floating varobjs are reparsed on each stop, so we don't care if
             the presently parsed expression refers to something that's gone.
             */
-         if ((*varp)->root->floating)
+         if ((*varp)->root->floating) {
+           varp++;
            continue;
+         }

          /* global var must be re-evaluated.  */
          if ((*varp)->root->valid_block == NULL)

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Jan Kratochvil]

On Thu, 02 Jul 2009 12:09:39 +0200, Vladimir Prus wrote:
> On Thursday 02 July 2009 Jan Kratochvil wrote:
> > Is it OK to check it in, Vladimir?  The patch would go in unchanged:
> > 	http://sourceware.org/ml/gdb-patches/2009-05/msg00547.html
> 
> Is this cleanup-only patch?

Yes.

> I am a bit concerned that it appears to increase code size,

all_root_varobjs fully replaced the varobj_list function which just could not
be deleted as it was still used by varobj_invalidate.  varobj_invalidate was
rewritten in a later patch where varobj_list could be finally dropped:
	[patch 8/8] Types GC [varobj]
	http://sourceware.org/ml/gdb-patches/2009-05/msg00551.html


> > The `floating' lockup will get fixed by a later patch using this new
> > all_root_varobjs function.   A testcase for it was in a now-obsolete patch:
> > 	[patch] Fix gdb.mi hang on floating VAROBJs
> > 	http://sourceware.org/ml/gdb-patches/2009-05/msg00433.html
> > This patch itself still does not fix it.
> 
> IIUC, the varobj_invalidate problem can be fixed with a small patch below.

Yes, such patch works.

Sending also a code style fixup on top of your fix to make the code more safe
preventing such errors in the future.

Please provide a ChangeLog entry to your fix, check it in and approve the
fixup + a testcase below.

The all_root_varobjs patch / VEC rewrite I will re-send afterwards.


Thanks,
Jan


gdb/
2009-07-02  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* mi/mi-cmd-var.c (mi_cmd_var_update): Replace a while loop by for loop.
	* varobj.c (varobj_invalidate): Replace a while loop by for loop.

gdb/testsuite/
2009-05-25  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* gdb.mi/mi2-var-cmd.exp (floating varobj invalidation): New test.

--- a/gdb/mi/mi-cmd-var.c
+++ b/gdb/mi/mi-cmd-var.c
@@ -606,8 +606,7 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 	  do_cleanups (cleanup);
 	  return;
 	}
-      cr = rootlist;
-      while (*cr != NULL)
+      for (cr = rootlist; *cr != NULL; cr++)
 	{
 	  int thread_id = varobj_get_thread_id (*cr);
 	  int thread_stopped = 0;
@@ -624,7 +623,6 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 	  if (thread_stopped)
 	    if (*name == '*' || varobj_floating_p (*cr))
 	      varobj_update_one (*cr, print_values, 0 /* implicit */);
-	  cr++;
 	}
       do_cleanups (cleanup);
     }
--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -3226,16 +3226,13 @@ varobj_invalidate (void)
 
   if (varobj_list (&all_rootvarobj) > 0)
     {
-      varp = all_rootvarobj;
-      while (*varp != NULL)
+      for (varp = all_rootvarobj; *varp != NULL; varp++)
 	{
 	  /* Floating varobjs are reparsed on each stop, so we don't care if
 	     the presently parsed expression refers to something that's gone.
 	     */
-	  if ((*varp)->root->floating) {
-	    varp++;
+	  if ((*varp)->root->floating)
 	    continue;
-	  }
 
 	  /* global var must be re-evaluated.  */     
 	  if ((*varp)->root->valid_block == NULL)
@@ -3257,8 +3254,6 @@ varobj_invalidate (void)
 	    }
 	  else /* locals must be invalidated.  */
 	    (*varp)->root->is_valid = 0;
-
-	  varp++;
 	}
     }
   xfree (all_rootvarobj);

--- a/gdb/testsuite/gdb.mi/mi2-var-cmd.exp
+++ b/gdb/testsuite/gdb.mi/mi2-var-cmd.exp
@@ -523,5 +523,9 @@ mi_gdb_test "-var-update selected_a" \
 	"\\^done,changelist=\\\[\{name=\"selected_a\",in_scope=\"true\",type_changed=\"true\",new_type=\"int\",new_num_children=\"0\"\}\\\]" \
 	"update selected_a in do_special_tests"
 
+mi_gdb_test "-file-exec-and-symbols ${binfile}" "\\^done" \
+	    "floating varobj invalidation"
+
+
 mi_gdb_exit
 return 0

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Vladimir Prus]

[-- Attachment #1: Type: Text/Plain, Size: 1626 bytes --]

On Sunday 05 July 2009 Jan Kratochvil wrote:

> On Thu, 02 Jul 2009 12:09:39 +0200, Vladimir Prus wrote:
> > On Thursday 02 July 2009 Jan Kratochvil wrote:
> > > Is it OK to check it in, Vladimir?  The patch would go in unchanged:
> > > 	http://sourceware.org/ml/gdb-patches/2009-05/msg00547.html
> > 
> > Is this cleanup-only patch?
> 
> Yes.
> 
> > I am a bit concerned that it appears to increase code size,
> 
> all_root_varobjs fully replaced the varobj_list function which just could not
> be deleted as it was still used by varobj_invalidate.  varobj_invalidate was
> rewritten in a later patch where varobj_list could be finally dropped:
> 	[patch 8/8] Types GC [varobj]
> 	http://sourceware.org/ml/gdb-patches/2009-05/msg00551.html

Is that patch awaiting review, or some newer version is forthcoming?

> > > The `floating' lockup will get fixed by a later patch using this new
> > > all_root_varobjs function.   A testcase for it was in a now-obsolete patch:
> > > 	[patch] Fix gdb.mi hang on floating VAROBJs
> > > 	http://sourceware.org/ml/gdb-patches/2009-05/msg00433.html
> > > This patch itself still does not fix it.
> > 
> > IIUC, the varobj_invalidate problem can be fixed with a small patch below.
> 
> Yes, such patch works.
> 
> Sending also a code style fixup on top of your fix to make the code more safe
> preventing such errors in the future.
> 
> Please provide a ChangeLog entry to your fix, check it in 

It now checked in, as attached.

> and approve the
> fixup + a testcase below.

This is OK, thanks.

> The all_root_varobjs patch / VEC rewrite I will re-send afterwards.

OK.

Thanks,
Volodya

[-- Attachment #2: hang.diff --]
[-- Type: text/x-patch, Size: 1288 bytes --]

Index: ChangeLog
===================================================================
RCS file: /cvs/src/src/gdb/ChangeLog,v
retrieving revision 1.10694
diff -u -p -r1.10694 ChangeLog
--- ChangeLog	7 Jul 2009 08:47:09 -0000	1.10694
+++ ChangeLog	7 Jul 2009 08:50:02 -0000
@@ -1,5 +1,12 @@
 2009-07-07  Vladimir Prus  <vladimir@codesourcery.com>
 
+	Fix hang in floating varobjs.
+
+	* varob.c (varobj_invalidate): Advance to next
+	element when processing floating varobj.
+
+2009-07-07  Vladimir Prus  <vladimir@codesourcery.com>
+
 	* varobj.c: Remove unnecessary include.
 
 2009-07-07  Tristan Gingold  <gingold@adacore.com>
Index: varobj.c
===================================================================
RCS file: /cvs/src/src/gdb/varobj.c,v
retrieving revision 1.140
diff -u -p -r1.140 varobj.c
--- varobj.c	7 Jul 2009 08:47:10 -0000	1.140
+++ varobj.c	7 Jul 2009 08:50:02 -0000
@@ -3231,8 +3231,10 @@ varobj_invalidate (void)
 	  /* Floating varobjs are reparsed on each stop, so we don't care if
 	     the presently parsed expression refers to something that's gone.
 	     */
-	  if ((*varp)->root->floating)
+	  if ((*varp)->root->floating) {
+	    varp++;
 	    continue;
+	  }
 
 	  /* global var must be re-evaluated.  */     
 	  if ((*varp)->root->valid_block == NULL)

Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]

[Jan Kratochvil]

On Tue, 07 Jul 2009 10:54:40 +0200, Vladimir Prus wrote:
> On Sunday 05 July 2009 Jan Kratochvil wrote:
> > 	[patch 8/8] Types GC [varobj]
> > 	http://sourceware.org/ml/gdb-patches/2009-05/msg00551.html
> 
> Is that patch awaiting review, or some newer version is forthcoming?

It is no longer a review candidate, thanks for the notice, marked it so.
	http://sourceware.org/ml/gdb-patches/2009-07/msg00181.html


> > and approve the
> > fixup + a testcase below.
> 
> This is OK, thanks.

Checked-in:
	http://sourceware.org/ml/gdb-cvs/2009-07/msg00061.html
	http://sourceware.org/ml/gdb-cvs/2009-07/msg00060.html


Thanks,
Jan

[patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Jan Kratochvil]

On Thu, 02 Jul 2009 12:09:39 +0200, Vladimir Prus wrote:
> Can we just make varobj.c expose vector of varobjs?

In general iterators are preferred over direct variable access in modern
programming.  It makes the implementation free to change the underlying data
structures to always use algorithms with optimal complexity.

Specifically the VEC structure (contiguous array) is not well suited as:
* It cannot effectively insert/remove elements while keeping the original order.
* Iterating such VEC while it is being changed is difficult.
* Current varobj_delete + install_variable API does not report the number of
  successfully deleted/inserted root items to make such iteration safe.

There are at least ways of implementing there the VEC:

VEC_safe_push + VEC_unordered_remove:
+ It is algorithmically optimal complexity.
- It no longer keeps the root variables order - this breaks the testsuite.
  Verified all the FAILs are just an order change having no real regressions.
  I will fix the testsuite if it gets approved this way.
  I believe frontends do not depend on the ordering, I would test
  Eclipse+Nemiver or some others upon recommendation.
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  varobj_delete + install_variable API change may be more appropriate.

VEC_safe_insert + VEC_ordered_remove:
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
- It is ineffective (two memmove calls per varobj_invalidate per rootvar).
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  * Guess the index / placement will match one remove + insert
  or
  * Extend the varobj_delete + install_variable API to return the exact number
    of removed and inserted rootvars.

Still I would prefer:

Iterator - so-called "safe" (keeping the next pointer) double link list:
+ It is algorithmically optimal complexity.
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
+ More simple usage at the caller (no varobj_root_get_var).
+ Separates the interface and implementation parts.
+ Easy iterating the list being changed by varobj_delete + install_variable
  in the meantime.  One just keeps the "next" pointer before calling them.

Regression tested all the 4 patches on {x86_64,i686}-fedora-linux-gnu.


Thanks,
Jan

[patch 1/4] varobj_list replacement, choice 1 of 3: VEC_safe_push + VEC_unordered_remove

[Jan Kratochvil]

Hi,

VEC_safe_push + VEC_unordered_remove:
+ It is algorithmically optimal complexity.
- It no longer keeps the root variables order - this breaks the testsuite.
  Verified all the FAILs are just an order change having no real regressions.
  I will fix the testsuite if it gets approved this way.
  I believe frontends do not depend on the ordering, I would test
  Eclipse+Nemiver or some others upon recommendation.
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  varobj_delete + install_variable API change may be more appropriate.


Thanks,
Jan


gdb/
2009-07-10  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Replace public function varobj_list by public VEC variable.
	* mi-cmd-var.c (mi_cmd_var_update): Replace variables rootlist and cr
	by ix, root and var.  Replace varobj_list call by varobj_roots
	iteration.
	* varobj.c (rootlist, rootcount, varobj_list): Remove.
	(varobj_roots, varobj_root_get_var): New.
	(install_variable): Replace the ROOTLIST linking by VEC_safe_push.
	(uninstall_variable): Replace the ROOTLIST unlinking by
	VEC_unordered_remove.
	(varobj_invalidate): Remove the variables all_rootvarobj and varp.
	New variables ix, limit and root.  Replace the varobj_list call by
	varobj_roots iteration.
	* varobj.h (varobj_root_p, varobj_roots): New.
	(varobj_list): Remove the prototype.
	(varobj_root_get_var): New prototype.

--- a/gdb/mi/mi-cmd-var.c
+++ b/gdb/mi/mi-cmd-var.c
@@ -596,14 +596,13 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 
   if ((*name == '*' || *name == '@') && (*(name + 1) == '\0'))
     {
-      struct varobj **rootlist, **cr;
+      int ix;
+      varobj_root_p root;
 
-      varobj_list (&rootlist);
-      make_cleanup (xfree, rootlist);
-
-      for (cr = rootlist; *cr != NULL; cr++)
+      for (ix = 0; VEC_iterate (varobj_root_p, varobj_roots, ix, root); ix++)
 	{
-	  int thread_id = varobj_get_thread_id (*cr);
+	  struct varobj *var = varobj_root_get_var (root);
+	  int thread_id = varobj_get_thread_id (var);
 	  int thread_stopped = 0;
 
 	  if (thread_id == -1 && is_stopped (inferior_ptid))
@@ -618,8 +617,8 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 	    }
 
 	  if (thread_stopped)
-	    if (*name == '*' || varobj_floating_p (*cr))
-	      varobj_update_one (*cr, print_values, 0 /* implicit */);
+	    if (*name == '*' || varobj_floating_p (var))
+	      varobj_update_one (var, print_values, 0 /* implicit */);
 	}
     }
   else
--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -422,9 +422,8 @@ enum vsections
 /* Mappings of varobj_display_formats enums to gdb's format codes */
 static int format_code[] = { 0, 't', 'd', 'x', 'o' };
 
-/* Header of the list of root variable objects */
-static struct varobj_root *rootlist;
-static int rootcount = 0;	/* number of root varobjs in the list */
+/* Public vector of varobj_root pointers.  */
+VEC (varobj_root_p) *varobj_roots;
 
 /* Prime number indicating the number of buckets in the hash table */
 /* A prime large enough to avoid too many colisions */
@@ -1169,37 +1168,6 @@ varobj_set_value (struct varobj *var, char *expression)
   return 1;
 }
 
-/* Returns a malloc'ed list with all root variable objects */
-int
-varobj_list (struct varobj ***varlist)
-{
-  struct varobj **cv;
-  struct varobj_root *croot;
-  int mycount = rootcount;
-
-  /* Alloc (rootcount + 1) entries for the result */
-  *varlist = xmalloc ((rootcount + 1) * sizeof (struct varobj *));
-
-  cv = *varlist;
-  croot = rootlist;
-  while ((croot != NULL) && (mycount > 0))
-    {
-      *cv = croot->rootvar;
-      mycount--;
-      cv++;
-      croot = croot->next;
-    }
-  /* Mark the end of the list */
-  *cv = NULL;
-
-  if (mycount || (croot != NULL))
-    warning
-      ("varobj_list: assertion failed - wrong tally of root vars (%d:%d)",
-       rootcount, mycount);
-
-  return rootcount;
-}
-
 /* Assign a new value to a variable object.  If INITIAL is non-zero,
    this is the first assignement after the variable object was just
    created, or changed type.  In that case, just assign the value 
@@ -1739,15 +1707,7 @@ install_variable (struct varobj *var)
 
   /* If root, add varobj to root list */
   if (is_root_p (var))
-    {
-      /* Add to list of root variables */
-      if (rootlist == NULL)
-	var->root->next = NULL;
-      else
-	var->root->next = rootlist;
-      rootlist = var->root;
-      rootcount++;
-    }
+    VEC_safe_push (varobj_root_p, varobj_roots, var->root);
 
   return 1;			/* OK */
 }
@@ -1799,33 +1759,24 @@ uninstall_variable (struct varobj *var)
   /* If root, remove varobj from root list */
   if (is_root_p (var))
     {
-      /* Remove from list of root variables */
-      if (rootlist == var->root)
-	rootlist = var->root->next;
-      else
+      varobj_root_p root;
+      int ix;
+
+      for (ix = 0; VEC_iterate (varobj_root_p, varobj_roots, ix, root); ix++)
+	if (varobj_root_get_var (root) == var)
+	  break;
+
+      if (root == NULL)
 	{
-	  prer = NULL;
-	  cr = rootlist;
-	  while ((cr != NULL) && (cr->rootvar != var))
-	    {
-	      prer = cr;
-	      cr = cr->next;
-	    }
-	  if (cr == NULL)
-	    {
-	      warning
-		("Assertion failed: Could not find varobj \"%s\" in root list",
-		 var->obj_name);
-	      return;
-	    }
-	  if (prer == NULL)
-	    rootlist = NULL;
-	  else
-	    prer->next = cr->next;
+	  warning
+	    ("Assertion failed: Could not find varobj \"%s\" in root list",
+	     var->obj_name);
+	  return;
 	}
-      rootcount--;
-    }
 
+      /* Remove from list of root variables */
+      VEC_unordered_remove (varobj_root_p, varobj_roots, ix);
+    }
 }
 
 /* Create and install a child of the parent of the given name */
@@ -3226,6 +3177,14 @@ When non-zero, varobj debugging is enabled."),
 			    &setlist, &showlist);
 }
 
+/* Return the varobj for this root node ROOT.  */
+
+struct varobj *
+varobj_root_get_var (varobj_root_p root)
+{
+  return root->rootvar;
+}
+
 /* Invalidate the varobjs that are tied to locals and re-create the ones that
    are defined on globals.
    Invalidated varobjs will be always printed in_scope="invalid".  */
@@ -3233,41 +3192,48 @@ When non-zero, varobj debugging is enabled."),
 void 
 varobj_invalidate (void)
 {
-  struct varobj **all_rootvarobj;
-  struct varobj **varp;
+  int ix, limit;
+
+  limit = VEC_length (varobj_root_p, varobj_roots);
 
-  if (varobj_list (&all_rootvarobj) > 0)
+  for (ix = 0; ix < limit; ix++)
     {
-      for (varp = all_rootvarobj; *varp != NULL; varp++)
-	{
-	  /* Floating varobjs are reparsed on each stop, so we don't care if
-	     the presently parsed expression refers to something that's gone.
-	     */
-	  if ((*varp)->root->floating)
-	    continue;
+      varobj_root_p root = VEC_index (varobj_root_p, varobj_roots, ix);
 
-	  /* global var must be re-evaluated.  */     
-	  if ((*varp)->root->valid_block == NULL)
-	    {
-	      struct varobj *tmp_var;
-
-	      /* Try to create a varobj with same expression.  If we succeed
-		 replace the old varobj, otherwise invalidate it.  */
-	      tmp_var = varobj_create (NULL, (*varp)->name, (CORE_ADDR) 0,
-				       USE_CURRENT_FRAME);
-	      if (tmp_var != NULL) 
-		{ 
-		  tmp_var->obj_name = xstrdup ((*varp)->obj_name);
-		  varobj_delete (*varp, NULL, 0);
-		  install_variable (tmp_var);
-		}
-	      else
-		(*varp)->root->is_valid = 0;
+      /* Floating varobjs are reparsed on each stop, so we don't care if the
+	 presently parsed expression refers to something that's gone.  */
+      if (root->floating)
+	continue;
+
+      /* global var must be re-evaluated.  */     
+      if (root->valid_block == NULL)
+	{
+	  struct varobj *var = varobj_root_get_var (root);
+	  struct varobj *tmp_var;
+
+	  /* Try to create a varobj with same expression.  If we succeed
+	     replace the old varobj, otherwise invalidate it.  */
+	  tmp_var = varobj_create (NULL, var->name, (CORE_ADDR) 0,
+				   USE_CURRENT_FRAME);
+	  if (tmp_var != NULL) 
+	    { 
+	      tmp_var->obj_name = xstrdup (var->obj_name);
+	      varobj_delete (var, NULL, 0);
+
+	      /* VAR got deleted from the vector VAROBJ_ROOTS and VAROBJ from
+	         the end of the vector got replaced at the current position IX
+		 - decrease IX to iterate the same position during the next
+		 loop.  As TMP_VAR is going to be appended at the end of vector
+		 decrease LIMIT to avoid a never ending loop iterating it.  */
+	      ix--;
+	      limit--;
+
+	      install_variable (tmp_var);
 	    }
-	  else /* locals must be invalidated.  */
-	    (*varp)->root->is_valid = 0;
+	  else
+	    root->is_valid = 0;
 	}
+      else /* locals must be invalidated.  */
+	root->is_valid = 0;
     }
-  xfree (all_rootvarobj);
-  return;
 }
--- a/gdb/varobj.h
+++ b/gdb/varobj.h
@@ -82,6 +82,15 @@ typedef struct varobj_update_result_t
 
 DEF_VEC_O (varobj_update_result);
 
+/* Public vector of varobj_root pointers.  DEF_VEC_O cannot be used as the
+   structure declaration is private.  */
+
+typedef struct varobj_root *varobj_root_p;
+
+DEF_VEC_P (varobj_root_p);
+
+extern VEC (varobj_root_p) *varobj_roots;
+
 /* API functions */
 
 extern struct varobj *varobj_create (char *objname,
@@ -137,11 +146,11 @@ extern char *varobj_get_value (struct varobj *var);
 
 extern int varobj_set_value (struct varobj *var, char *expression);
 
-extern int varobj_list (struct varobj ***rootlist);
-
 extern VEC(varobj_update_result) *varobj_update (struct varobj **varp, 
 						 int explicit);
 
+extern struct varobj *varobj_root_get_var (varobj_root_p root);
+
 extern void varobj_invalidate (void);
 
 extern int varobj_editable_p (struct varobj *var);

[patch 2/4] varobj_list replacement, choice 2 of 3: VEC_safe_insert + VEC_ordered_remove

[Jan Kratochvil]

Hi,

VEC_safe_insert + VEC_ordered_remove:
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
- It is ineffective (two memmove calls per varobj_invalidate per rootvar).
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  * Guess the index / placement will match one remove + insert
  or
  * Extend the varobj_delete + install_variable API to return the exact number
    of removed and inserted rootvars.


Thanks,
Jan


gdb/
2009-07-10  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Replace public function varobj_list by public VEC variable.
	* mi-cmd-var.c (mi_cmd_var_update): Replace variables rootlist and cr
	by ix, root and var.  Replace varobj_list call by varobj_roots
	iteration.
	* varobj.c (rootlist, rootcount, varobj_list): Remove.
	(varobj_roots, varobj_root_get_var): New.
	(install_variable): Replace the ROOTLIST linking by VEC_safe_insert.
	(uninstall_variable): Replace the ROOTLIST unlinking by
	VEC_ordered_remove.
	(varobj_invalidate): Remove the variables all_rootvarobj and varp.
	New variables ix and root.  Replace the varobj_list call by
	varobj_roots iteration.
	* varobj.h (varobj_root_p, varobj_roots): New.
	(varobj_list): Remove the prototype.
	(varobj_root_get_var): New prototype.

--- a/gdb/mi/mi-cmd-var.c
+++ b/gdb/mi/mi-cmd-var.c
@@ -596,14 +596,13 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 
   if ((*name == '*' || *name == '@') && (*(name + 1) == '\0'))
     {
-      struct varobj **rootlist, **cr;
+      int ix;
+      varobj_root_p root;
 
-      varobj_list (&rootlist);
-      make_cleanup (xfree, rootlist);
-
-      for (cr = rootlist; *cr != NULL; cr++)
+      for (ix = 0; VEC_iterate (varobj_root_p, varobj_roots, ix, root); ix++)
 	{
-	  int thread_id = varobj_get_thread_id (*cr);
+	  struct varobj *var = varobj_root_get_var (root);
+	  int thread_id = varobj_get_thread_id (var);
 	  int thread_stopped = 0;
 
 	  if (thread_id == -1 && is_stopped (inferior_ptid))
@@ -618,8 +617,8 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 	    }
 
 	  if (thread_stopped)
-	    if (*name == '*' || varobj_floating_p (*cr))
-	      varobj_update_one (*cr, print_values, 0 /* implicit */);
+	    if (*name == '*' || varobj_floating_p (var))
+	      varobj_update_one (var, print_values, 0 /* implicit */);
 	}
     }
   else
--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -422,9 +422,8 @@ enum vsections
 /* Mappings of varobj_display_formats enums to gdb's format codes */
 static int format_code[] = { 0, 't', 'd', 'x', 'o' };
 
-/* Header of the list of root variable objects */
-static struct varobj_root *rootlist;
-static int rootcount = 0;	/* number of root varobjs in the list */
+/* Public vector of varobj_root pointers.  */
+VEC (varobj_root_p) *varobj_roots;
 
 /* Prime number indicating the number of buckets in the hash table */
 /* A prime large enough to avoid too many colisions */
@@ -1169,37 +1168,6 @@ varobj_set_value (struct varobj *var, char *expression)
   return 1;
 }
 
-/* Returns a malloc'ed list with all root variable objects */
-int
-varobj_list (struct varobj ***varlist)
-{
-  struct varobj **cv;
-  struct varobj_root *croot;
-  int mycount = rootcount;
-
-  /* Alloc (rootcount + 1) entries for the result */
-  *varlist = xmalloc ((rootcount + 1) * sizeof (struct varobj *));
-
-  cv = *varlist;
-  croot = rootlist;
-  while ((croot != NULL) && (mycount > 0))
-    {
-      *cv = croot->rootvar;
-      mycount--;
-      cv++;
-      croot = croot->next;
-    }
-  /* Mark the end of the list */
-  *cv = NULL;
-
-  if (mycount || (croot != NULL))
-    warning
-      ("varobj_list: assertion failed - wrong tally of root vars (%d:%d)",
-       rootcount, mycount);
-
-  return rootcount;
-}
-
 /* Assign a new value to a variable object.  If INITIAL is non-zero,
    this is the first assignement after the variable object was just
    created, or changed type.  In that case, just assign the value 
@@ -1739,15 +1707,7 @@ install_variable (struct varobj *var)
 
   /* If root, add varobj to root list */
   if (is_root_p (var))
-    {
-      /* Add to list of root variables */
-      if (rootlist == NULL)
-	var->root->next = NULL;
-      else
-	var->root->next = rootlist;
-      rootlist = var->root;
-      rootcount++;
-    }
+    VEC_safe_insert (varobj_root_p, varobj_roots, 0, var->root);
 
   return 1;			/* OK */
 }
@@ -1799,33 +1759,24 @@ uninstall_variable (struct varobj *var)
   /* If root, remove varobj from root list */
   if (is_root_p (var))
     {
-      /* Remove from list of root variables */
-      if (rootlist == var->root)
-	rootlist = var->root->next;
-      else
+      varobj_root_p root;
+      int ix;
+
+      for (ix = 0; VEC_iterate (varobj_root_p, varobj_roots, ix, root); ix++)
+	if (varobj_root_get_var (root) == var)
+	  break;
+
+      if (root == NULL)
 	{
-	  prer = NULL;
-	  cr = rootlist;
-	  while ((cr != NULL) && (cr->rootvar != var))
-	    {
-	      prer = cr;
-	      cr = cr->next;
-	    }
-	  if (cr == NULL)
-	    {
-	      warning
-		("Assertion failed: Could not find varobj \"%s\" in root list",
-		 var->obj_name);
-	      return;
-	    }
-	  if (prer == NULL)
-	    rootlist = NULL;
-	  else
-	    prer->next = cr->next;
+	  warning
+	    ("Assertion failed: Could not find varobj \"%s\" in root list",
+	     var->obj_name);
+	  return;
 	}
-      rootcount--;
-    }
 
+      /* Remove from list of root variables */
+      VEC_ordered_remove (varobj_root_p, varobj_roots, ix);
+    }
 }
 
 /* Create and install a child of the parent of the given name */
@@ -3226,6 +3177,14 @@ When non-zero, varobj debugging is enabled."),
 			    &setlist, &showlist);
 }
 
+/* Return the varobj for this root node ROOT.  */
+
+struct varobj *
+varobj_root_get_var (varobj_root_p root)
+{
+  return root->rootvar;
+}
+
 /* Invalidate the varobjs that are tied to locals and re-create the ones that
    are defined on globals.
    Invalidated varobjs will be always printed in_scope="invalid".  */
@@ -3233,41 +3192,41 @@ When non-zero, varobj debugging is enabled."),
 void 
 varobj_invalidate (void)
 {
-  struct varobj **all_rootvarobj;
-  struct varobj **varp;
+  int ix;
+  varobj_root_p root;
 
-  if (varobj_list (&all_rootvarobj) > 0)
+  for (ix = 0; VEC_iterate (varobj_root_p, varobj_roots, ix, root); ix++)
     {
-      for (varp = all_rootvarobj; *varp != NULL; varp++)
-	{
-	  /* Floating varobjs are reparsed on each stop, so we don't care if
-	     the presently parsed expression refers to something that's gone.
-	     */
-	  if ((*varp)->root->floating)
-	    continue;
+      /* Floating varobjs are reparsed on each stop, so we don't care if the
+	 presently parsed expression refers to something that's gone.  */
+      if (root->floating)
+	continue;
 
-	  /* global var must be re-evaluated.  */     
-	  if ((*varp)->root->valid_block == NULL)
-	    {
-	      struct varobj *tmp_var;
-
-	      /* Try to create a varobj with same expression.  If we succeed
-		 replace the old varobj, otherwise invalidate it.  */
-	      tmp_var = varobj_create (NULL, (*varp)->name, (CORE_ADDR) 0,
-				       USE_CURRENT_FRAME);
-	      if (tmp_var != NULL) 
-		{ 
-		  tmp_var->obj_name = xstrdup ((*varp)->obj_name);
-		  varobj_delete (*varp, NULL, 0);
-		  install_variable (tmp_var);
-		}
-	      else
-		(*varp)->root->is_valid = 0;
+      /* global var must be re-evaluated.  */     
+      if (root->valid_block == NULL)
+	{
+	  struct varobj *var = varobj_root_get_var (root);
+	  struct varobj *tmp_var;
+
+	  /* Try to create a varobj with same expression.  If we succeed
+	     replace the old varobj, otherwise invalidate it.  */
+	  tmp_var = varobj_create (NULL, var->name, (CORE_ADDR) 0,
+				   USE_CURRENT_FRAME);
+	  if (tmp_var != NULL) 
+	    { 
+	      tmp_var->obj_name = xstrdup (var->obj_name);
+
+	      /* VAR gets removed shifting the remaining vector elements down.
+		 Then TMP_VAR gets inserted at the beginning of the vector
+		 shifting up all the elements up.  The remaining elements after
+		 the current IX one therefore remain at the same place.  */
+	      varobj_delete (var, NULL, 0);
+	      install_variable (tmp_var);
 	    }
-	  else /* locals must be invalidated.  */
-	    (*varp)->root->is_valid = 0;
+	  else
+	    root->is_valid = 0;
 	}
+      else /* locals must be invalidated.  */
+	root->is_valid = 0;
     }
-  xfree (all_rootvarobj);
-  return;
 }
--- a/gdb/varobj.h
+++ b/gdb/varobj.h
@@ -82,6 +82,15 @@ typedef struct varobj_update_result_t
 
 DEF_VEC_O (varobj_update_result);
 
+/* Public vector of varobj_root pointers.  DEF_VEC_O cannot be used as the
+   structure declaration is private.  */
+
+typedef struct varobj_root *varobj_root_p;
+
+DEF_VEC_P (varobj_root_p);
+
+extern VEC (varobj_root_p) *varobj_roots;
+
 /* API functions */
 
 extern struct varobj *varobj_create (char *objname,
@@ -137,11 +146,11 @@ extern char *varobj_get_value (struct varobj *var);
 
 extern int varobj_set_value (struct varobj *var, char *expression);
 
-extern int varobj_list (struct varobj ***rootlist);
-
 extern VEC(varobj_update_result) *varobj_update (struct varobj **varp, 
 						 int explicit);
 
+extern struct varobj *varobj_root_get_var (varobj_root_p root);
+
 extern void varobj_invalidate (void);
 
 extern int varobj_editable_p (struct varobj *var);

[patch 3/4] varobj_list replacement, choice 3 of 3: Iterator

[Jan Kratochvil]

Hi,

Iterator - so-called "safe" (keeping the next pointer) double link list:
+ It is algorithmically optimal complexity.
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
+ More simple usage at the caller (no varobj_root_get_var).
+ Separates the interface and implementation parts.
+ Easy iterating the list being changed by varobj_delete + install_variable
  in the meantime.  One just keeps the "next" pointer before calling them.


Thanks,
Jan


gdb/
2009-07-10  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Replace public function varobj_list by all_root_varobjs iterator.
	* mi/mi-cmd-var.c (struct mi_cmd_var_update, mi_cmd_var_update_iter):
	New.
	(mi_cmd_var_update): Replace the varobj_list call by all_root_varobjs.
	Remove the variables rootlist, cr.  New variable data.
	* varobj.c (rootcount, varobj_list): Remove.
	(install_variable, uninstall_variable): Remove the rootcount updates.
	(all_root_varobjs): New function.
	(varobj_invalidate): Use the all_root_varobjs call.  Move the code to...
	(varobj_invalidate_iter): ... a new function.
	* varobj.h (varobj_list): Remove the prototype.
	(all_root_varobjs): New prototype.

--- a/gdb/mi/mi-cmd-var.c
+++ b/gdb/mi/mi-cmd-var.c
@@ -566,6 +566,41 @@ mi_cmd_var_assign (char *command, char **argv, int argc)
   ui_out_field_string (uiout, "value", varobj_get_value (var));
 }
 
+/* Type used for parameters passing to mi_cmd_var_update_iter.  */
+
+struct mi_cmd_var_update
+  {
+    int only_floating;
+    enum print_values print_values;
+  };
+
+/* Helper for mi_cmd_var_update - update each VAR.  */
+
+static void
+mi_cmd_var_update_iter (struct varobj *var, void *data_pointer)
+{
+  struct mi_cmd_var_update *data = data_pointer;
+  int thread_id, thread_stopped;
+
+  thread_id = varobj_get_thread_id (var);
+
+  if (thread_id == -1 && is_stopped (inferior_ptid))
+    thread_stopped = 1;
+  else
+    {
+      struct thread_info *tp = find_thread_id (thread_id);
+
+      if (tp)
+	thread_stopped = is_stopped (tp->ptid);
+      else
+	thread_stopped = 1;
+    }
+
+  if (thread_stopped)
+    if (!data->only_floating || varobj_floating_p (var))
+      varobj_update_one (var, data->print_values, 0 /* implicit */);
+}
+
 void
 mi_cmd_var_update (char *command, char **argv, int argc)
 {
@@ -596,31 +631,16 @@ mi_cmd_var_update (char *command, char **argv, int argc)
 
   if ((*name == '*' || *name == '@') && (*(name + 1) == '\0'))
     {
-      struct varobj **rootlist, **cr;
+      struct mi_cmd_var_update data;
 
-      varobj_list (&rootlist);
-      make_cleanup (xfree, rootlist);
+      data.only_floating = *name == '@';
+      data.print_values = print_values;
 
-      for (cr = rootlist; *cr != NULL; cr++)
-	{
-	  int thread_id = varobj_get_thread_id (*cr);
-	  int thread_stopped = 0;
+      /* varobj_update_one automatically updates all the children of VAROBJ.
+	 Therefore update each VAROBJ only once by iterating only the root
+	 VAROBJs.  */
 
-	  if (thread_id == -1 && is_stopped (inferior_ptid))
-	    thread_stopped = 1;
-	  else
-	    {
-	      struct thread_info *tp = find_thread_id (thread_id);
-	      if (tp)
-		thread_stopped = is_stopped (tp->ptid);
-	      else
-		thread_stopped = 1;
-	    }
-
-	  if (thread_stopped)
-	    if (*name == '*' || varobj_floating_p (*cr))
-	      varobj_update_one (*cr, print_values, 0 /* implicit */);
-	}
+      all_root_varobjs (mi_cmd_var_update_iter, &data);
     }
   else
     {
--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -424,7 +424,6 @@ static int format_code[] = { 0, 't', 'd', 'x', 'o' };
 
 /* Header of the list of root variable objects */
 static struct varobj_root *rootlist;
-static int rootcount = 0;	/* number of root varobjs in the list */
 
 /* Prime number indicating the number of buckets in the hash table */
 /* A prime large enough to avoid too many colisions */
@@ -1169,37 +1168,6 @@ varobj_set_value (struct varobj *var, char *expression)
   return 1;
 }
 
-/* Returns a malloc'ed list with all root variable objects */
-int
-varobj_list (struct varobj ***varlist)
-{
-  struct varobj **cv;
-  struct varobj_root *croot;
-  int mycount = rootcount;
-
-  /* Alloc (rootcount + 1) entries for the result */
-  *varlist = xmalloc ((rootcount + 1) * sizeof (struct varobj *));
-
-  cv = *varlist;
-  croot = rootlist;
-  while ((croot != NULL) && (mycount > 0))
-    {
-      *cv = croot->rootvar;
-      mycount--;
-      cv++;
-      croot = croot->next;
-    }
-  /* Mark the end of the list */
-  *cv = NULL;
-
-  if (mycount || (croot != NULL))
-    warning
-      ("varobj_list: assertion failed - wrong tally of root vars (%d:%d)",
-       rootcount, mycount);
-
-  return rootcount;
-}
-
 /* Assign a new value to a variable object.  If INITIAL is non-zero,
    this is the first assignement after the variable object was just
    created, or changed type.  In that case, just assign the value 
@@ -1746,7 +1714,6 @@ install_variable (struct varobj *var)
       else
 	var->root->next = rootlist;
       rootlist = var->root;
-      rootcount++;
     }
 
   return 1;			/* OK */
@@ -1823,7 +1790,6 @@ uninstall_variable (struct varobj *var)
 	  else
 	    prer->next = cr->next;
 	}
-      rootcount--;
     }
 
 }
@@ -3206,6 +3172,24 @@ java_value_of_variable (struct varobj *var, enum varobj_display_formats format)
 {
   return cplus_value_of_variable (var, format);
 }
+
+/* Iterate all the existing _root_ VAROBJs and call the FUNC callback for them
+   with an arbitrary caller supplied DATA pointer.  */
+
+void
+all_root_varobjs (void (*func) (struct varobj *var, void *data), void *data)
+{
+  struct varobj_root *var_root, *var_root_next;
+
+  /* Iterate "safely" - handle if the callee deletes its passed VAROBJ.  */
+
+  for (var_root = rootlist; var_root != NULL; var_root = var_root_next)
+    {
+      var_root_next = var_root->next;
+
+      (*func) (var_root->rootvar, data);
+    }
+}
 \f
 extern void _initialize_varobj (void);
 void
@@ -3226,48 +3210,45 @@ When non-zero, varobj debugging is enabled."),
 			    &setlist, &showlist);
 }
 
-/* Invalidate the varobjs that are tied to locals and re-create the ones that
-   are defined on globals.
-   Invalidated varobjs will be always printed in_scope="invalid".  */
+/* Invalidate varobj VAR if it is tied to locals and re-create it if it is
+   defined on globals.  It is a helper for varobj_invalidate.  */
 
-void 
-varobj_invalidate (void)
+static void
+varobj_invalidate_iter (struct varobj *var, void *unused)
 {
-  struct varobj **all_rootvarobj;
-  struct varobj **varp;
+  /* Floating varobjs are reparsed on each stop, so we don't care if the
+     presently parsed expression refers to something that's gone.  */
+  if (var->root->floating)
+    return;
 
-  if (varobj_list (&all_rootvarobj) > 0)
+  /* global var must be re-evaluated.  */     
+  if (var->root->valid_block == NULL)
     {
-      for (varp = all_rootvarobj; *varp != NULL; varp++)
-	{
-	  /* Floating varobjs are reparsed on each stop, so we don't care if
-	     the presently parsed expression refers to something that's gone.
-	     */
-	  if ((*varp)->root->floating)
-	    continue;
+      struct varobj *tmp_var;
 
-	  /* global var must be re-evaluated.  */     
-	  if ((*varp)->root->valid_block == NULL)
-	    {
-	      struct varobj *tmp_var;
-
-	      /* Try to create a varobj with same expression.  If we succeed
-		 replace the old varobj, otherwise invalidate it.  */
-	      tmp_var = varobj_create (NULL, (*varp)->name, (CORE_ADDR) 0,
-				       USE_CURRENT_FRAME);
-	      if (tmp_var != NULL) 
-		{ 
-		  tmp_var->obj_name = xstrdup ((*varp)->obj_name);
-		  varobj_delete (*varp, NULL, 0);
-		  install_variable (tmp_var);
-		}
-	      else
-		(*varp)->root->is_valid = 0;
-	    }
-	  else /* locals must be invalidated.  */
-	    (*varp)->root->is_valid = 0;
+      /* Try to create a varobj with same expression.  If we succeed
+	 replace the old varobj, otherwise invalidate it.  */
+      tmp_var = varobj_create (NULL, var->name, (CORE_ADDR) 0,
+			       USE_CURRENT_FRAME);
+      if (tmp_var != NULL) 
+	{ 
+	  tmp_var->obj_name = xstrdup (var->obj_name);
+	  varobj_delete (var, NULL, 0);
+	  install_variable (tmp_var);
 	}
+      else
+	var->root->is_valid = 0;
     }
-  xfree (all_rootvarobj);
-  return;
+  else /* locals must be invalidated.  */
+    var->root->is_valid = 0;
+}
+
+/* Invalidate the varobjs that are tied to locals and re-create the ones that
+   are defined on globals.
+   Invalidated varobjs will be always printed in_scope="invalid".  */
+
+void 
+varobj_invalidate (void)
+{
+  all_root_varobjs (varobj_invalidate_iter, NULL);
 }
--- a/gdb/varobj.h
+++ b/gdb/varobj.h
@@ -137,7 +137,8 @@ extern char *varobj_get_value (struct varobj *var);
 
 extern int varobj_set_value (struct varobj *var, char *expression);
 
-extern int varobj_list (struct varobj ***rootlist);
+extern void all_root_varobjs (void (*func) (struct varobj *var, void *data),
+			      void *data);
 
 extern VEC(varobj_update_result) *varobj_update (struct varobj **varp, 
 						 int explicit);

[patch 4/4] varobj_list replacement, choice 3 of 3: Iterator optimization

[Jan Kratochvil]

Hi,

just a minor optimization - in fact only to keep its algorithm complexity on
par with "choice 1 of 3: VEC_safe_push + VEC_unordered_remove".


Thanks,
Jan


gdb/
2009-07-10  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Optimize O(n) varobj_root unlinking to O(1).
	* varobj.c (struct varobj_root): New field prev.
	(install_variable): New variable root.  Initialize the new field prev.
	(uninstall_variable): Remove the variables cr, prer.  Replace the
	element lookup by O(1) unlink using the new field prev.

--- a/gdb/varobj.c
+++ b/gdb/varobj.c
@@ -98,8 +98,8 @@ struct varobj_root
   /* The varobj for this root node. */
   struct varobj *rootvar;
 
-  /* Next root variable */
-  struct varobj_root *next;
+  /* Next and previous root variable (NULL for the last or first item).  */
+  struct varobj_root *next, *prev;
 };
 
 /* Every variable in the system has a structure of this type defined
@@ -1708,12 +1708,17 @@ install_variable (struct varobj *var)
   /* If root, add varobj to root list */
   if (is_root_p (var))
     {
-      /* Add to list of root variables */
-      if (rootlist == NULL)
-	var->root->next = NULL;
-      else
-	var->root->next = rootlist;
-      rootlist = var->root;
+      struct varobj_root *root = var->root;
+
+      /* Add to list of root variables.  */
+
+      root->next = rootlist;
+      rootlist = root;
+
+      if (root->next)
+	root->next->prev = root;
+
+      root->prev = NULL;
     }
 
   return 1;			/* OK */
@@ -1725,8 +1730,6 @@ uninstall_variable (struct varobj *var)
 {
   struct vlist *cv;
   struct vlist *prev;
-  struct varobj_root *cr;
-  struct varobj_root *prer;
   const char *chp;
   unsigned int index = 0;
   unsigned int i = 1;
@@ -1766,30 +1769,17 @@ uninstall_variable (struct varobj *var)
   /* If root, remove varobj from root list */
   if (is_root_p (var))
     {
-      /* Remove from list of root variables */
-      if (rootlist == var->root)
-	rootlist = var->root->next;
+      struct varobj_root *root = var->root;
+
+      /* Remove from list of root variables.  */
+
+      if (root->prev)
+	root->prev->next = root->next;
       else
-	{
-	  prer = NULL;
-	  cr = rootlist;
-	  while ((cr != NULL) && (cr->rootvar != var))
-	    {
-	      prer = cr;
-	      cr = cr->next;
-	    }
-	  if (cr == NULL)
-	    {
-	      warning
-		("Assertion failed: Could not find varobj \"%s\" in root list",
-		 var->obj_name);
-	      return;
-	    }
-	  if (prer == NULL)
-	    rootlist = NULL;
-	  else
-	    prer->next = cr->next;
-	}
+	rootlist = root->next;
+
+      if (root->next)
+	root->next->prev = root->prev;
     }
 
 }

Re: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Volodya> Can we just make varobj.c expose vector of varobjs?

Jan> In general iterators are preferred over direct variable access in
Jan> modern programming.

Yeah, but what about in gdb? ;)

Jan> Still I would prefer:
Jan> Iterator - so-called "safe" (keeping the next pointer) double link list:

This patch (assuming it was the 4/4 patch) seemed pretty clean to me.

I did not read all the patches.  I'm happy to do so and review them, but
I didn't want to overstep into Volodya's maintainership area.

Jan> Regression tested all the 4 patches on {x86_64,i686}-fedora-linux-gnu.

So, I have a few comments on this.

I understand from other mail that this patch is a prerequisite to the
type GC work.  However, I don't understand in what way it is needed.  I
probably missed something... could you either explain it or tell me
where to look?

Second, I did not see a response to any of these patches.  So, ping.

Third, I think it is strange to send four patches that do the same thing
in different ways.  I am certain that we can all communicate better than
this, and come to an agreement about direction beforehand.

Tom

Re: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Vladimir Prus]

On Wednesday 29 July 2009 Tom Tromey wrote:

> >>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
> 
> Volodya> Can we just make varobj.c expose vector of varobjs?
> 
> Jan> In general iterators are preferred over direct variable access in
> Jan> modern programming.
> 
> Yeah, but what about in gdb? ;)
> 
> Jan> Still I would prefer:
> Jan> Iterator - so-called "safe" (keeping the next pointer) double link list:
> 
> This patch (assuming it was the 4/4 patch) seemed pretty clean to me.

...

> I understand from other mail that this patch is a prerequisite to the
> type GC work.  However, I don't understand in what way it is needed.  I
> probably missed something... could you either explain it or tell me
> where to look?

In fact, I'm lost the big picture as well. If we want to optimize uninstall_variable,
then the 4/4 patch appears to be the simplest one that does the trick. However, if
that's a part of some bigger story, I'd be interested to understand it.

Thanks,
Volodya

Re: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Jan Kratochvil]

On Thu, 30 Jul 2009 08:45:51 +0200, Vladimir Prus wrote:
> On Wednesday 29 July 2009 Tom Tromey wrote:
> > I understand from other mail that this patch is a prerequisite to the
> > type GC work.  However, I don't understand in what way it is needed.  I
> > probably missed something... could you either explain it or tell me
> > where to look?
> 
> In fact, I'm lost the big picture as well. If we want to optimize uninstall_variable,
> then the 4/4 patch appears to be the simplest one that does the trick. However, if
> that's a part of some bigger story, I'd be interested to understand it.

The bigger story is:
------------------------------------------------------------------------------
The former Types GC code had to traverse varobj leaves (not just roots as does
current varobj_list()).  As I found the current varobj_list() calling
convention is IMO-inconvenient and calling convention of the 'roots' and 'all'
iterators/enumerators of varobjs should be the same I did not want to write
a new function using the IMO-inconvenient calling convention.  The new
function was called all_varobjs() in the obsoleted patch:
	[patch 8/8] Types GC [varobj]
	http://sourceware.org/ml/gdb-patches/2009-05/msg00551.html
So I rather IMO-fixed the calling convention of varobj_list() first so that
the later 'all' varobjs iterator can already use the new calling convention
while keeping the calling convention of the 'roots' and 'all' iterators the
same.

I found the new all_root_varobjs() iterator - patch 3/4 - to be clearly a win
over current varobj_list() - no matter how insignificant change it may be
- that just nobody so far has spent the time doing such code cleanup.
The patches 1/4, 2/4 and 4/4 were later created just to support accepting the
patch 3/4 and I probably would not submit 3/4 if I could imagine any problems
getting it accepted.

Moreover the Types GC changed from the former reference-counting to the
current mark-and-sweep where maybe the leaves traversal is no longer needed.
I have to check it more.

speculation: IIRC it should have been fixing one objfile-invalidating bug
where varobj leaf is using a different objfile due to TYPE_STUB referencing.
But it is a bug out of the critical path for Types GC.

In fact I do not like 1/4 or 2/4 to be accepted, they were created just to get
3/4 accepted.  Also I do not think the 4/4 performance improvement is worth
the reviewing time, it was also created just to get 3/4 accepted.
------------------------------------------------------------------------------

As I see 3/4 is not considered as a clear cleanup win.  Understood it as
rejected and I will be basing the next patches on the current varobj_list()
calling convention as the preferred one.


Thanks,
Jan

Re: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Vladimir Prus]

On Thursday 30 July 2009 Jan Kratochvil wrote:

> On Thu, 30 Jul 2009 08:45:51 +0200, Vladimir Prus wrote:
> > On Wednesday 29 July 2009 Tom Tromey wrote:
> > > I understand from other mail that this patch is a prerequisite to the
> > > type GC work.  However, I don't understand in what way it is needed.  I
> > > probably missed something... could you either explain it or tell me
> > > where to look?
> > 
> > In fact, I'm lost the big picture as well. If we want to optimize uninstall_variable,
> > then the 4/4 patch appears to be the simplest one that does the trick. However, if
> > that's a part of some bigger story, I'd be interested to understand it.
> 
> The bigger story is:
> ------------------------------------------------------------------------------
> The former Types GC code had to traverse varobj leaves (not just roots as does
> current varobj_list()).  As I found the current varobj_list() calling
> convention is IMO-inconvenient and calling convention of the 'roots' and 'all'
> iterators/enumerators of varobjs should be the same I did not want to write
> a new function using the IMO-inconvenient calling convention.  The new
> function was called all_varobjs() in the obsoleted patch:
> 	[patch 8/8] Types GC [varobj]
> 	http://sourceware.org/ml/gdb-patches/2009-05/msg00551.html
> So I rather IMO-fixed the calling convention of varobj_list() first so that
> the later 'all' varobjs iterator can already use the new calling convention
> while keeping the calling convention of the 'roots' and 'all' iterators the
> same.
> 
> I found the new all_root_varobjs() iterator - patch 3/4 - to be clearly a win
> over current varobj_list() - no matter how insignificant change it may be
> - that just nobody so far has spent the time doing such code cleanup.
> The patches 1/4, 2/4 and 4/4 were later created just to support accepting the
> patch 3/4 and I probably would not submit 3/4 if I could imagine any problems
> getting it accepted.
> 
> Moreover the Types GC changed from the former reference-counting to the
> current mark-and-sweep where maybe the leaves traversal is no longer needed.
> I have to check it more.
> 
> speculation: IIRC it should have been fixing one objfile-invalidating bug
> where varobj leaf is using a different objfile due to TYPE_STUB referencing.
> But it is a bug out of the critical path for Types GC.
> 
> In fact I do not like 1/4 or 2/4 to be accepted, they were created just to get
> 3/4 accepted.  Also I do not think the 4/4 performance improvement is worth
> the reviewing time, it was also created just to get 3/4 accepted.

I was confused -- I though 4/4 is meant is the preferred one.

> As I see 3/4 is not considered as a clear cleanup win.  Understood it as
> rejected and I will be basing the next patches on the current varobj_list()
> calling convention as the preferred one.

In fact, varobj_list() is surely messy, I was not sure if the callback-iteration
is better than vec. Of course, this question might be easier solved were we using
C++, which has both a pile of data types and iterators (non-callback-based).

However, we've probably spent too much time over matter than can be easily tweaked
in future. If your current patches depend on 3/4, please commit it -- no need
to rework things over that.

- Volodya

Re: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Jan Kratochvil]

On Thu, 30 Jul 2009 10:46:24 +0200, Vladimir Prus wrote:
> However, we've probably spent too much time over matter than can be easily tweaked
> in future. If your current patches depend on 3/4, please commit it -- no need
> to rework things over that.

Checked-in
	[patch 3/4] varobj_list replacement, choice 3 of 3: Iterator
	http://sourceware.org/ml/gdb-patches/2009-07/msg00317.html
as:
	http://sourceware.org/ml/gdb-cvs/2009-07/msg00188.html


Thanks,
Jan