From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29993 invoked by alias); 10 Jul 2009 20:21:17 -0000 Received: (qmail 29985 invoked by uid 22791); 10 Jul 2009 20:21:16 -0000 X-SWARE-Spam-Status: No, hits=-2.4 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx2.redhat.com (HELO mx2.redhat.com) (66.187.237.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 10 Jul 2009 20:21:07 +0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n6AKJ5tw018288; Fri, 10 Jul 2009 16:19:05 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n6AKJ4kP007993; Fri, 10 Jul 2009 16:19:04 -0400 Received: from host0.dyn.jankratochvil.net (sebastian-int.corp.redhat.com [172.16.52.221]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n6AKJ3iS027086; Fri, 10 Jul 2009 16:19:03 -0400 Received: from host0.dyn.jankratochvil.net (localhost [127.0.0.1]) by host0.dyn.jankratochvil.net (8.14.3/8.14.3) with ESMTP id n6AKJ2vm027316; Fri, 10 Jul 2009 22:19:02 +0200 Received: (from jkratoch@localhost) by host0.dyn.jankratochvil.net (8.14.3/8.14.3/Submit) id n6AKJ2Fe027315; Fri, 10 Jul 2009 22:19:02 +0200 Date: Fri, 10 Jul 2009 22:12:00 -0000 From: Jan Kratochvil To: Vladimir Prus Cc: Tom Tromey , gdb-patches@sourceware.org Subject: [patch 4/4] varobj_list replacement, choice 3 of 3: Iterator optimization Message-ID: <20090710201902.GE7014@host0.dyn.jankratochvil.net> References: <20090525080233.GD13323@host0.dyn.jankratochvil.net> <20090702083705.GA14783@host0.dyn.jankratochvil.net> <200907021409.39886.vladimir@codesourcery.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200907021409.39886.vladimir@codesourcery.com> User-Agent: Mutt/1.5.19 (2009-01-05) X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2009-07/txt/msg00320.txt.bz2 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 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; } }