From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2885 invoked by alias); 19 Feb 2007 10:38:37 -0000 Received: (qmail 2877 invoked by uid 22791); 19 Feb 2007 10:38:36 -0000 X-Spam-Check-By: sourceware.org Received: from pm1.terions.de (HELO pm1.terions.de) (83.137.96.25) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 19 Feb 2007 10:38:25 +0000 Received: (qmail 20003 invoked by uid 98); 19 Feb 2007 10:38:25 -0000 Received: from dslb-084-058-247-087.pools.arcor-ip.net (HELO ?192.168.0.2?) (tn@tneumann.de@84.58.247.87) by mail.s-s-l.net with SMTP; 19 Feb 2007 10:38:25 -0000 Message-ID: <45D97E30.2060008@users.sourceforge.net> Date: Mon, 19 Feb 2007 11:57:00 -0000 From: Thomas Neumann User-Agent: Thunderbird 1.5.0.9 (X11/20070103) MIME-Version: 1.0 To: gdb@sourceware.org Subject: Organization of breakpoint locations Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit 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/msg00195.txt.bz2 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