From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15155 invoked by alias); 19 Feb 2007 22:17:17 -0000 Received: (qmail 15144 invoked by uid 22791); 19 Feb 2007 22:17:15 -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 22:17:08 +0000 Received: (qmail 28624 invoked by uid 98); 19 Feb 2007 22:17:08 -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 22:17:08 -0000 Message-ID: <45DA21F6.1020802@users.sourceforge.net> Date: Tue, 20 Feb 2007 10:26:00 -0000 From: Thomas Neumann User-Agent: Thunderbird 1.5.0.9 (X11/20070103) MIME-Version: 1.0 To: Thomas Neumann CC: gdb@sourceware.org Subject: Re: Organization of breakpoint locations References: <45D97E30.2060008@users.sourceforge.net> <20070219115744.GC6815@caradoc.them.org> <45D99E03.1050309@users.sourceforge.net> <20070219130342.GA10857@caradoc.them.org> <45DA1FDB.8000800@users.sourceforge.net> In-Reply-To: <45DA1FDB.8000800@users.sourceforge.net> Content-Type: multipart/mixed; boundary="------------050609050309040509000501" 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/msg00206.txt.bz2 This is a multi-part message in MIME format. --------------050609050309040509000501 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 302 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 --------------050609050309040509000501 Content-Type: text/plain; name="breakpointsinsplay.patch" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="breakpointsinsplay.patch" Content-length: 5740 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; --------------050609050309040509000501--