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

[Jan Kratochvil <jan dot kratochvil at redhat dot com>]

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);