Organization of breakpoint locations

Organization of breakpoint locations

[Thomas Neumann]

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

Re: Organization of breakpoint locations

[Daniel Jacobowitz]

On Mon, Feb 19, 2007 at 11:38:40AM +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.

Have you tested this in any real world use yet?  This is only the
first limitation you'll encounter, I think.  For instance, every time
you step and then stop the program, GDB is going to remove every
breakpoint.  That's going to be just as slow.

> 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.

Why do you think that the splay tree in libiberty can't handle any of
these?  Your key would not be the address, but the address plus the
breakpoint sequence number.  That handles one and two.  Then you can
iterate over items using splay_tree_successor.  The key could be the
same pointer as the value, by the way - it just takes a clever
splay_tree_compare_fn.

Another way is to use the address as a key, but store a VEC of
breakpoints as the values, sorted by number.  That's messier though.

> 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.

To be honest, I don't think this will be a small change either way.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Organization of breakpoint locations

[Thomas Neumann]

Daniel Jacobowitz schrieb:
> Have you tested this in any real world use yet?  This is only the
> first limitation you'll encounter, I think.  For instance, every time
>   
hm, I only did manual tests yet. And for a single continue, even a scan
over 50000 breakpoints is not that bad. But I see your point:
Ultimately, this large number of breakpoints comes from automatic
program tracing, which will stop and continue thousands of times.

> these?  Your key would not be the address, but the address plus the
> breakpoint sequence number.  That handles one and two.  Then you can
>   
good idea. I thought that a breakpoint could have more than one
bp_location associated with it, preventing such a scheme (but even then
a breakpoint would probably not have more than one location with the
same address).
> To be honest, I don't think this will be a small change either way.
>   
I will give the libiberty splay a try, that should be easy. But if
resetting breakpoints is indeed as slow as you indicated, by patch is
probably pointless. What a shame. That would have been a very portable
and nice way to automatically trace execution flow.

Thomas

Re: Organization of breakpoint locations

[Daniel Jacobowitz]

On Mon, Feb 19, 2007 at 01:54:27PM +0100, Thomas Neumann wrote:
> > these?  Your key would not be the address, but the address plus the
> > breakpoint sequence number.  That handles one and two.  Then you can
> >   
> good idea. I thought that a breakpoint could have more than one
> bp_location associated with it, preventing such a scheme (but even then
> a breakpoint would probably not have more than one location with the
> same address).

It can't yet have more than one bp_location, but the separation is
there for a reason - I think the one to many mapping will arrive
sometime this year.  But I think we can add a sequence number to
bp_location's just like breakpoints have.

> > To be honest, I don't think this will be a small change either way.
> >   
> I will give the libiberty splay a try, that should be easy. But if
> resetting breakpoints is indeed as slow as you indicated, by patch is
> probably pointless. What a shame. That would have been a very portable
> and nice way to automatically trace execution flow.

I'd like GDB to be able to manage huge breakpoint lists; I'm just
warning you that a lot more work will have to be done first ;-)

One nice thing is that if you kill or crash GDB today, it tends 
to leave breakpoints removed.  If it didn't do this huge massive
removal, it probably wouldn't - perhaps we should add a signal handler
that takes care of that if we change it.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Organization of breakpoint locations

[Michael Veksler]

Daniel Jacobowitz wrote:
> One nice thing is that if you kill or crash GDB today, it tends 
> to leave breakpoints removed.  If it didn't do this huge massive
> removal, it probably wouldn't - perhaps we should add a signal handler
> that takes care of that if we change it.
>   
I always thought (speculated) that breakpoint removal was to simplify 
things like

    (gdb) x /i $pc

Where you don't want to see the INT instruction, but the original value.
GDB crash does sound like another reason.
Being curios, I'd like to ask what was the original reason for
this behavior? Does anyone know? I never saw it documented anywhere.

-- 
Michael Veksler
http:///tx.technion.ac.il/~mveksler

Re: Organization of breakpoint locations

[Daniel Jacobowitz]

On Mon, Feb 19, 2007 at 04:40:42PM +0200, Michael Veksler wrote:
> I always thought (speculated) that breakpoint removal was to simplify 
> things like
> 
>    (gdb) x /i $pc
> 
> Where you don't want to see the INT instruction, but the original value.

Some parts of GDB won't work if we leave breakpoints in.  But, it's
not hard to fix - we have the right helper routines for it nowadays.
Joel made some changes like this in the last year.

> GDB crash does sound like another reason.
> Being curios, I'd like to ask what was the original reason for
> this behavior? Does anyone know? I never saw it documented anywhere.

I don't know either; I'm just guessing.  It may have just been easiest
at the time and no one came back to think about it later.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Organization of breakpoint locations

[Thomas Neumann]

[-- Attachment #1: Type: text/plain, Size: 886 bytes --]

Daniel Jacobowitz schrieb:
> sometime this year.  But I think we can add a sequence number to
> bp_location's just like breakpoints have.
>   
and in fact a separate number seems to be needed, as the breakpoint
number is unknown (zero) when the breakpoint location is created. I did
not investigate this further and  just added a number to bp_location.
> I'd like GDB to be able to manage huge breakpoint lists; I'm just
> warning you that a lot more work will have to be done first ;-)
>   
ok, here is a first step: attached is small patch that stores the
breakpoint locations in a splay instead of a list. The patch is fairly
straight forward: mostly one compare function for splay-tree.c and a
number of iterator functions to simplify the access macros. It even
survived a make check. I hope this patch motivates someone to fix the
scalability issues with breakpoints ;-)


Thomas


[-- Attachment #2: breakpointsinsplay.patch --]
[-- Type: text/plain, Size: 5781 bytes --]

diff -r -u -b gdb-6.6.original/gdb/breakpoint.c gdb-6.6/gdb/breakpoint.c
--- gdb-6.6.original/gdb/breakpoint.c	2006-10-19 17:58:25.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.c	2007-02-19 22:46:09.283209500 +0100
@@ -53,6 +53,7 @@
 #include "solist.h"
 #include "observer.h"
 #include "exceptions.h"
+#include "splay-tree.h"
 
 #include "gdb-events.h"
 #include "mi/mi-common.h"
@@ -254,11 +255,16 @@
 
 /* Similar iterators for the low-level breakpoints.  */
 
-#define ALL_BP_LOCATIONS(B)  for (B = bp_location_chain; B; B = B->next)
+#define ALL_BP_LOCATIONS(B)							\
+	for (B = bp_location_tree_first();B!=NULL;B = bp_location_tree_next(B))
+
+#define ALL_BP_LOCATIONS_ADDR(B,a)				\
+	for (B = bp_location_tree_first_address(a);B!=NULL;	\
+             B = bp_location_tree_next_address(B,a))
 
 #define ALL_BP_LOCATIONS_SAFE(B,TMP)	\
-	for (B = bp_location_chain;	\
-	     B ? (TMP=B->next, 1): 0;	\
+	for (B = bp_location_tree_first();			\
+            (B!=NULL)?(TMP=bp_location_tree_next(B),1):0;	\
 	     B = TMP)
 
 /* True if breakpoint hit counts should be displayed in breakpoint info.  */
@@ -269,7 +275,9 @@
 
 struct breakpoint *breakpoint_chain;
 
-struct bp_location *bp_location_chain;
+static splay_tree bp_location_tree;
+
+static int bp_location_number;
 
 /* Number of last breakpoint made.  */
 
@@ -339,6 +347,76 @@
    error (_("catch of library unloads not yet implemented on this platform"))
 #endif
 
+/** Compare entries in the breakpoint tree */
+static int
+bp_location_tree_cmp (splay_tree_key l, splay_tree_key r)
+{
+  struct bp_location *lp=(struct bp_location*)l, *rp=(struct bp_location*)r;
+  if (lp->address < rp->address)
+    return -1;
+  if (lp->address > rp->address)
+    return 1;
+  if (lp->number < rp->number)
+    return -1;
+  if (lp->number > rp->number)
+    return 1;
+  return 0;
+}
+
+/** Find the first entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_first ()
+{
+  if (bp_location_tree == NULL)
+    return NULL;
+  return (struct bp_location*)splay_tree_min(bp_location_tree)->value;
+}
+
+/** Find the next entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_next (struct bp_location* b)
+{
+  splay_tree_node n = splay_tree_successor (bp_location_tree,
+                        (splay_tree_key)b);
+  if (n == NULL)
+    return NULL;
+  return (struct bp_location*)n->value;
+}
+
+/** Find the first entry in the breakpoint tree with a given address*/
+static struct bp_location*
+bp_location_tree_first_address (CORE_ADDR a)
+{
+  struct breakpoint b;
+  struct bp_location l,*r;
+  splay_tree_node n;
+
+  if (bp_location_tree == NULL)
+    return NULL;
+
+  b.number = INT_MIN;
+  l.owner = &b;
+  l.address = a;
+  n = splay_tree_successor (bp_location_tree,(splay_tree_key)&l);
+
+  if (n == NULL)
+    return NULL;
+  r = (struct bp_location*)n->value;
+  if (r->address != a)
+    return NULL;
+  return r;
+}
+
+/** Find the next entry in the breakpoint tree with a given address */
+static struct bp_location*
+bp_location_tree_next_address (struct bp_location* b, CORE_ADDR a)
+{
+  struct bp_location* r = bp_location_tree_next (b);
+  if ((r == NULL)||(r->address != a))
+     return NULL;
+  return r;
+}
+
 /* Return whether a breakpoint is an active enabled breakpoint.  */
 static int
 breakpoint_enabled (struct breakpoint *b)
@@ -3889,7 +3967,7 @@
   if (! breakpoint_address_is_meaningful (bpt))
     return;
 
-  ALL_BP_LOCATIONS (b)
+  ALL_BP_LOCATIONS_ADDR (b, address)
     if (b->owner->enable_state != bp_disabled
 	&& b->owner->enable_state != bp_shlib_disabled
 	&& !b->owner->pending
@@ -4054,18 +4132,6 @@
       internal_error (__FILE__, __LINE__, _("unknown breakpoint type"));
     }
 
-  /* Add this breakpoint to the end of the chain.  */
-
-  loc_p = bp_location_chain;
-  if (loc_p == 0)
-    bp_location_chain = loc;
-  else
-    {
-      while (loc_p->next)
-	loc_p = loc_p->next;
-      loc_p->next = loc;
-    }
-
   return loc;
 }
 
@@ -4095,6 +4161,14 @@
   b->loc->requested_address = sal.pc;
   b->loc->address = adjust_breakpoint_address (b->loc->requested_address,
                                                bptype);
+  /* Add this breakpoint at the back of the tree.  */
+  b->loc->number = bp_location_number ++;
+  if (bp_location_tree == NULL)
+    bp_location_tree = splay_tree_new (bp_location_tree_cmp, NULL, NULL);
+  splay_tree_insert (bp_location_tree,
+                     (splay_tree_key)b->loc,
+                     (splay_tree_value)b->loc);
+
   if (sal.symtab == NULL)
     b->source_file = NULL;
   else
@@ -6777,8 +6851,7 @@
   if (breakpoint_chain == bpt)
     breakpoint_chain = bpt->next;
 
-  if (bp_location_chain == bpt->loc)
-    bp_location_chain = bpt->loc->next;
+  splay_tree_remove (bp_location_tree, (splay_tree_key)bpt->loc);
 
   /* If we have callback-style exception catchpoints, don't go through
      the adjustments to the C++ runtime library etc. if the inferior
@@ -6809,13 +6882,6 @@
       break;
     }
 
-  ALL_BP_LOCATIONS (loc)
-    if (loc->next == bpt->loc)
-      {
-	loc->next = bpt->loc->next;
-	break;
-      }
-
   check_duplicates (bpt);
   /* If this breakpoint was inserted, and there is another breakpoint
      at the same address, we need to insert the other breakpoint.  */
diff -r -u -b gdb-6.6.original/gdb/breakpoint.h gdb-6.6/gdb/breakpoint.h
--- gdb-6.6.original/gdb/breakpoint.h	2006-04-18 21:20:06.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.h	2007-02-19 22:41:24.485410750 +0100
@@ -238,8 +238,8 @@
 
 struct bp_location
 {
-  /* Chain pointer to the next breakpoint location.  */
-  struct bp_location *next;
+  /* Unique number used for sorting */
+  int number;
 
   /* Type of this breakpoint location.  */
   enum bp_loc_type loc_type;

Re: Organization of breakpoint locations

[Thomas Neumann]

[-- Attachment #1: Type: text/plain, Size: 302 bytes --]

I should re-read my patches _before_ pressing send... Sorry for the
double post, my original patch set the wrong start number in
bp_location_tree_first_address. Which will not matter most of the time
(apparently not triggered by make check), but does not make sense . Here
is the fixed patch.

Thomas


[-- Attachment #2: breakpointsinsplay.patch --]
[-- Type: text/plain, Size: 5740 bytes --]

diff -r -u -b gdb-6.6.original/gdb/breakpoint.c gdb-6.6/gdb/breakpoint.c
--- gdb-6.6.original/gdb/breakpoint.c	2006-10-19 17:58:25.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.c	2007-02-19 23:10:32.858677250 +0100
@@ -53,6 +53,7 @@
 #include "solist.h"
 #include "observer.h"
 #include "exceptions.h"
+#include "splay-tree.h"
 
 #include "gdb-events.h"
 #include "mi/mi-common.h"
@@ -254,11 +255,16 @@
 
 /* Similar iterators for the low-level breakpoints.  */
 
-#define ALL_BP_LOCATIONS(B)  for (B = bp_location_chain; B; B = B->next)
+#define ALL_BP_LOCATIONS(B)							\
+	for (B = bp_location_tree_first();B!=NULL;B = bp_location_tree_next(B))
+
+#define ALL_BP_LOCATIONS_ADDR(B,a)				\
+	for (B = bp_location_tree_first_address(a);B!=NULL;	\
+             B = bp_location_tree_next_address(B,a))
 
 #define ALL_BP_LOCATIONS_SAFE(B,TMP)	\
-	for (B = bp_location_chain;	\
-	     B ? (TMP=B->next, 1): 0;	\
+	for (B = bp_location_tree_first();			\
+            (B!=NULL)?(TMP=bp_location_tree_next(B),1):0;	\
 	     B = TMP)
 
 /* True if breakpoint hit counts should be displayed in breakpoint info.  */
@@ -269,7 +275,9 @@
 
 struct breakpoint *breakpoint_chain;
 
-struct bp_location *bp_location_chain;
+static splay_tree bp_location_tree;
+
+static int bp_location_number;
 
 /* Number of last breakpoint made.  */
 
@@ -339,6 +347,74 @@
    error (_("catch of library unloads not yet implemented on this platform"))
 #endif
 
+/** Compare entries in the breakpoint tree */
+static int
+bp_location_tree_cmp (splay_tree_key l, splay_tree_key r)
+{
+  struct bp_location *lp=(struct bp_location*)l, *rp=(struct bp_location*)r;
+  if (lp->address < rp->address)
+    return -1;
+  if (lp->address > rp->address)
+    return 1;
+  if (lp->number < rp->number)
+    return -1;
+  if (lp->number > rp->number)
+    return 1;
+  return 0;
+}
+
+/** Find the first entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_first ()
+{
+  if (bp_location_tree == NULL)
+    return NULL;
+  return (struct bp_location*)splay_tree_min(bp_location_tree)->value;
+}
+
+/** Find the next entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_next (struct bp_location* b)
+{
+  splay_tree_node n = splay_tree_successor (bp_location_tree,
+                        (splay_tree_key)b);
+  if (n == NULL)
+    return NULL;
+  return (struct bp_location*)n->value;
+}
+
+/** Find the first entry in the breakpoint tree with a given address*/
+static struct bp_location*
+bp_location_tree_first_address (CORE_ADDR a)
+{
+  struct bp_location l,*r;
+  splay_tree_node n;
+
+  if (bp_location_tree == NULL)
+    return NULL;
+
+  l.address = a;
+  l.number = INT_MIN;
+  n = splay_tree_successor (bp_location_tree,(splay_tree_key)&l);
+
+  if (n == NULL)
+    return NULL;
+  r = (struct bp_location*)n->value;
+  if (r->address != a)
+    return NULL;
+  return r;
+}
+
+/** Find the next entry in the breakpoint tree with a given address */
+static struct bp_location*
+bp_location_tree_next_address (struct bp_location* b, CORE_ADDR a)
+{
+  struct bp_location* r = bp_location_tree_next (b);
+  if ((r == NULL)||(r->address != a))
+     return NULL;
+  return r;
+}
+
 /* Return whether a breakpoint is an active enabled breakpoint.  */
 static int
 breakpoint_enabled (struct breakpoint *b)
@@ -3889,7 +3965,7 @@
   if (! breakpoint_address_is_meaningful (bpt))
     return;
 
-  ALL_BP_LOCATIONS (b)
+  ALL_BP_LOCATIONS_ADDR (b, address)
     if (b->owner->enable_state != bp_disabled
 	&& b->owner->enable_state != bp_shlib_disabled
 	&& !b->owner->pending
@@ -4054,18 +4130,6 @@
       internal_error (__FILE__, __LINE__, _("unknown breakpoint type"));
     }
 
-  /* Add this breakpoint to the end of the chain.  */
-
-  loc_p = bp_location_chain;
-  if (loc_p == 0)
-    bp_location_chain = loc;
-  else
-    {
-      while (loc_p->next)
-	loc_p = loc_p->next;
-      loc_p->next = loc;
-    }
-
   return loc;
 }
 
@@ -4095,6 +4159,14 @@
   b->loc->requested_address = sal.pc;
   b->loc->address = adjust_breakpoint_address (b->loc->requested_address,
                                                bptype);
+  /* Add this breakpoint at the back of the tree.  */
+  b->loc->number = bp_location_number ++;
+  if (bp_location_tree == NULL)
+    bp_location_tree = splay_tree_new (bp_location_tree_cmp, NULL, NULL);
+  splay_tree_insert (bp_location_tree,
+                     (splay_tree_key)b->loc,
+                     (splay_tree_value)b->loc);
+
   if (sal.symtab == NULL)
     b->source_file = NULL;
   else
@@ -6777,8 +6849,7 @@
   if (breakpoint_chain == bpt)
     breakpoint_chain = bpt->next;
 
-  if (bp_location_chain == bpt->loc)
-    bp_location_chain = bpt->loc->next;
+  splay_tree_remove (bp_location_tree, (splay_tree_key)bpt->loc);
 
   /* If we have callback-style exception catchpoints, don't go through
      the adjustments to the C++ runtime library etc. if the inferior
@@ -6809,13 +6880,6 @@
       break;
     }
 
-  ALL_BP_LOCATIONS (loc)
-    if (loc->next == bpt->loc)
-      {
-	loc->next = bpt->loc->next;
-	break;
-      }
-
   check_duplicates (bpt);
   /* If this breakpoint was inserted, and there is another breakpoint
      at the same address, we need to insert the other breakpoint.  */
diff -r -u -b gdb-6.6.original/gdb/breakpoint.h gdb-6.6/gdb/breakpoint.h
--- gdb-6.6.original/gdb/breakpoint.h	2006-04-18 21:20:06.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.h	2007-02-19 22:41:24.485410750 +0100
@@ -238,8 +238,8 @@
 
 struct bp_location
 {
-  /* Chain pointer to the next breakpoint location.  */
-  struct bp_location *next;
+  /* Unique number used for sorting */
+  int number;
 
   /* Type of this breakpoint location.  */
   enum bp_loc_type loc_type;

Re: Organization of breakpoint locations

[Michael Snyder]

On Mon, 2007-02-19 at 06:57 -0500, Daniel Jacobowitz wrote:
> On Mon, Feb 19, 2007 at 11:38:40AM +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.
> 
> Have you tested this in any real world use yet?  This is only the
> first limitation you'll encounter, I think.  For instance, every time
> you step and then stop the program, GDB is going to remove every
> breakpoint.  That's going to be just as slow.

Maybe not.  If they're grouped by address, and if there are
a lot of duplicates, gdb could set/clear the breakpoint at
that address once, and then mark them all inserted or not.

Re: Organization of breakpoint locations

[Michael Snyder]

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