From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26824 invoked by alias); 10 Jul 2009 20:13:25 -0000 Received: (qmail 26815 invoked by uid 22791); 10 Jul 2009 20:13:22 -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:13:15 +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 n6AKBD63016621; Fri, 10 Jul 2009 16:11:13 -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 n6AKBCmw005619; Fri, 10 Jul 2009 16:11:12 -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 n6AKB7jP025563; Fri, 10 Jul 2009 16:11:09 -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 n6AKB6kG025070; Fri, 10 Jul 2009 22:11:06 +0200 Received: (from jkratoch@localhost) by host0.dyn.jankratochvil.net (8.14.3/8.14.3/Submit) id n6AKB4eV025061; Fri, 10 Jul 2009 22:11:04 +0200 Date: Fri, 10 Jul 2009 20:17:00 -0000 From: Jan Kratochvil To: Vladimir Prus Cc: Tom Tromey , gdb-patches@sourceware.org Subject: [patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]] Message-ID: <20090710201104.GA7014@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/msg00316.txt.bz2 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