From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29590 invoked by alias); 21 Feb 2007 01:10:11 -0000 Received: (qmail 29580 invoked by uid 22791); 21 Feb 2007 01:10:10 -0000 X-Spam-Check-By: sourceware.org Received: from mx2.palmsource.com (HELO mx2.palmsource.com) (12.7.175.14) by sourceware.org (qpsmtpd/0.31) with ESMTP; Wed, 21 Feb 2007 01:10:05 +0000 Received: from localhost (localhost [127.0.0.1]) by localhost.domain.tld (Postfix) with ESMTP id 4C8C811D353; Tue, 20 Feb 2007 17:10:04 -0800 (PST) Received: from mx2.palmsource.com ([127.0.0.1]) by localhost (mx2.palmsource.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 03963-02-8; Tue, 20 Feb 2007 17:10:03 -0800 (PST) Received: from ussunex01.palmsource.com (unknown [192.168.101.9]) by mx2.palmsource.com (Postfix) with ESMTP id 18BBD11BBF8; Tue, 20 Feb 2007 17:10:03 -0800 (PST) Received: from 192.168.92.92 ([192.168.92.92]) by ussunex01.palmsource.com ([192.168.101.9]) via Exchange Front-End Server owa.palmsource.com ([10.0.20.17]) with Microsoft Exchange Server HTTP-DAV ; Wed, 21 Feb 2007 01:10:02 +0000 Received: from svmsnyderlnx by owa.palmsource.com; 20 Feb 2007 17:10:01 -0800 Subject: Re: Organization of breakpoint locations From: Michael Snyder To: Thomas Neumann Cc: gdb@sourceware.org In-Reply-To: <45D97E30.2060008@users.sourceforge.net> References: <45D97E30.2060008@users.sourceforge.net> Content-Type: text/plain Content-Transfer-Encoding: 7bit Date: Wed, 21 Feb 2007 01:53:00 -0000 Message-Id: <1172020201.19657.81.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 X-IsSubscribed: yes 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: 2007-02/txt/msg00220.txt.bz2 May I add a thought? The code and data structure for breakpoints is actually duplicated a number of times in Gdb -- tracepoints and checkpoints, that I know of, and probably others. Gdb also has lists of threads and so forth. I've thought that it would be nice to have something like a "gdb_list" data structure, so we could just reuse this code instead of repeatedly copying it. Maybe this is an opportunity? On Mon, 2007-02-19 at 11:38 +0100, Thomas Neumann wrote: > Hi, > > I would like some suggestions on the organization of breakpoint > locations in breakpoint.c. Currently, all breakpoint locations are > stored in a linear list. This does not scale if the number of > breakpoints is large, see PR 2230 for an example. Instead the > breakpoints should be stored in a suitable search structure (e.g. a > balanced tree). > > I have a patch that converts the list into a splay. Works fine, and the > bottleneck indeed goes away, but I am not satisfied with the approach > itself. Changing the data structure is quite simple due to the access > macros used, so I had to change less than 20 lines. Unfortunately my > patch is still big (about 450 lines), as it contains a complete splay > implementation. > > It would be nicer to reuse existing data structures instead of > implementing a new one. I thought about using splay-tree in libiberty, > but the breakpoint locations have some unique characteristics: 1. the > locations have to be organized by address, but the address is not > necessarily unique. So the search structure must handle duplicates. 2. > the test suite (and perhaps other code) expect that a breakpoint is > added "last" in the list, i.e. duplicate handling must keep an order > within the duplicates. 3. it must be possible to iterate over search > structure (directly, without callbacks), as otherwise a lot of code has > to be changed. > > The splay implementation from libiberty satisfies none of these > constraints. Is there perhaps something else in the gdb sources that I > can reuse? Or should I submit my (admittedly quite large) patch? But > this would probably no longer count as a "small changes" that according > to CONTRIBUTE do not require a copyright assignment. > > Thomas