Re: Organization of breakpoint locations

[Michael Snyder <Michael.Snyder@palmsource.com>]

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