This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
[patch 4/4] varobj_list replacement, choice 3 of 3: Iterator optimization
- From: Jan Kratochvil <jan dot kratochvil at redhat dot com>
- To: Vladimir Prus <vladimir at codesourcery dot com>
- Cc: Tom Tromey <tromey at redhat dot com>, gdb-patches at sourceware dot org
- Date: Fri, 10 Jul 2009 22:19:02 +0200
- Subject: [patch 4/4] varobj_list replacement, choice 3 of 3: Iterator optimization
- References: <20090525080233.GD13323@host0.dyn.jankratochvil.net> <m3ljo1i125.fsf@fleche.redhat.com> <20090702083705.GA14783@host0.dyn.jankratochvil.net> <200907021409.39886.vladimir@codesourcery.com>
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;
}
}