Organization of breakpoint locations

[Thomas Neumann <tneumann at users dot sourceforge dot net>]

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