[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;
     }
 
 }