From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30022 invoked by alias); 18 Feb 2008 06:06:38 -0000 Received: (qmail 30010 invoked by uid 22791); 18 Feb 2008 06:06:37 -0000 X-Spam-Check-By: sourceware.org Received: from zigzag.lvk.cs.msu.su (HELO zigzag.lvk.cs.msu.su) (158.250.17.23) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 18 Feb 2008 06:06:20 +0000 Received: from Debian-exim by zigzag.lvk.cs.msu.su with spam-scanned (Exim 4.50) id 1JQz8n-0002Q8-7N for gdb@sources.redhat.com; Mon, 18 Feb 2008 09:06:16 +0300 Received: from localhost ([127.0.0.1] helo=ip6-localhost) by zigzag.lvk.cs.msu.su with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA:32) (Exim 4.50) id 1JQz8f-0002Pv-Ld; Mon, 18 Feb 2008 09:06:05 +0300 From: Vladimir Prus To: Nick Roberts Subject: Re: Variable objects and STL containers Date: Mon, 18 Feb 2008 08:12:00 -0000 User-Agent: KMail/1.9.6 (enterprise 0.20070907.709405) References: <18343.64413.689019.489727@kahikatea.snap.net.nz> <200802171014.18612.ghost@cs.msu.su> <20080217195449.831D78FC6D@kahikatea.snap.net.nz> In-Reply-To: <20080217195449.831D78FC6D@kahikatea.snap.net.nz> Cc: gdb@sources.redhat.com MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-15" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200802180906.12026.ghost@cs.msu.su> Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org X-SW-Source: 2008-02/txt/msg00123.txt.bz2 On Sunday 17 February 2008 22:54:49 you wrote: > > > Actually it looks doable for lists, maps etc if the children of a variable > > > object were stored as a list rather than a vector. This is so that a new > > > child can be added, or an old one deleted, at any point in the list. > > > > > > Ironically, the children were previously stored in a linked list and I > > > guess vectors were used because Nathan Sidwell has created an API in C for > > > them. There doesn't appear to be a similar API for lists, but since they > > > are more flexible, would it be possible to revert var->children to a > > > linked list? > > > > I'm afraid I don't see any such flexibility. Can you clarify? The vectors > > were used because they allowed to eliminate lots of custom list handling > > code, and I'm reluctant to go back. > > I can understand that you are reluctant to go back but I'm surprised that you > don't see the convenience. Until now the number of children has been fixed, so > vectors are probably a natural choice. With STL containers the number changes > and and it becomes advantageous to use lists. Taking maps, for example, they > appear to be stored as binary trees and GDB can traverse the tree (inorder) to > examine all the nodes. When it finds a new one, it needs to create a new child > *at that point* in the sequence of children. A vector can't do that. It can > only add or remove them at the end, so a list must be used. To be picky, vector can insert and remove elements in the middle, but that's O(N) operation. But in fact, that only matters if you happen to already know that an element was added at a certain position in the middle, which I think we don't. Instead, we get to traverse the list, and then construct a sequence of values, then compare the changes and report them. Suppose the old values were: 1 2 3 4 and new values are 1 2 5 3 4 We can either report that varobj 2 changed value from 3 to 5, that varobj 3 changed value from 4 to 3 and that new varobj was added at end. In this case, using vector is not a problem at all. Or we can report that new varobj was added at position 5. This sounds more attractive, but it's harder to properly detect minimal changes, and it's harder to communicate such change to gdb. And, it seems like a simple algorithm to detect changes will work just fine with vectors. - Volodya