[review] Replace callers of bsearch with gdb::binary_search
Commit Message
Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................
Replace callers of bsearch with gdb::binary_search
This is a bit more efficient and more type-safe.
Change-Id: I4c2c21a6870c5abffd87831ba024da3659bbfaa3
---
M gdb/breakpoint.c
M gdb/objfiles.c
2 files changed, 20 insertions(+), 36 deletions(-)
Comments
Christian Biesinger has posted comments on this change.
Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................
Patch Set 2:
Ping?
Christian Biesinger has posted comments on this change.
Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................
Patch Set 2:
ping
Simon Marchi has posted comments on this change.
Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................
Patch Set 2:
(5 comments)
| --- gdb/breakpoint.c
| +++ gdb/breakpoint.c
| @@ -765,45 +766,40 @@ show_condition_evaluation_mode (struct ui_file *file, int from_tty,
| _("Breakpoint condition evaluation "
| "mode is %s (currently %s).\n"),
| value,
| breakpoint_condition_evaluation_mode ());
| else
| fprintf_filtered (file, _("Breakpoint condition evaluation mode is %s.\n"),
| value);
| }
|
| /* A comparison function for bp_location AP and BP that is used by
PS2, Line 775:
These names need to be updated.
| bsearch. This comparison function only cares about addresses, unlike
| the more general bp_location_is_less_than function. */
|
| -static int
| -bp_locations_compare_addrs (const void *ap, const void *bp)
| -{
| - const struct bp_location *a = *(const struct bp_location **) ap;
| - const struct bp_location *b = *(const struct bp_location **) bp;
| -
| +static inline int
| +bp_locations_compare_addrs (const bp_location *a, const bp_location *b)
| +{
| if (a->address == b->address)
PS2, Line 782:
Orthogonal to this patch, but I wonder if the function could be simply
return ((a->address > b->address) - (a->address < b->address));
If both addresses are equal, it will give 0 - 0, resulting in 0. But
maybe it's actually on purpose because it's more efficient to do an
equality test first, I don't know.
| return 0;
| else
| return ((a->address > b->address) - (a->address < b->address));
| }
|
| /* Helper function to skip all bp_locations with addresses
| less than ADDRESS. It returns the first bp_location that
| is greater than or equal to ADDRESS. If none is found, just
| - return NULL. */
| + return NULL. TODO: That's not what this function implements,
| + it finds the first BP *at* address. Should it just call
| + std::lower_bound? */
PS2, Line 793:
Hmm, it is only ever used in the context of ALL_BP_LOCATIONS_AT_ADDR,
where we only care to find breakpoint locations *at* address. If
there is no breakpoint location at address, we'll return NULL, so the
loop will exit immediately. So I think the behavior is fine, the doc
and function should just be adjusted.
Note that it would work equally fine to use std::lower_bound. If
there's no breakpoint location at address, we'll return the first
location with a greater address, and the loop will exit immediately as
well. You choose.
|
| static struct bp_location **
| get_first_locp_gte_addr (CORE_ADDR address)
| {
| - struct bp_location dummy_loc;
| - struct bp_location *dummy_locp = &dummy_loc;
| - struct bp_location **locp_found = NULL;
| -
| /* Initialize the dummy location's address field. */
| + struct bp_location dummy_loc;
| dummy_loc.address = address;
PS2, Line 800:
When using the fancy C++ binary_search, I don't think you have to
create this dummy_loc anymore. Just pass the address to binary_search
and adjust the comparison function in consequence.
|
| + auto last = bp_locations + bp_locations_count;
| /* Find a close match to the first location at ADDRESS. */
| - locp_found = ((struct bp_location **)
| - bsearch (&dummy_locp, bp_locations, bp_locations_count,
| - sizeof (struct bp_location **),
| - bp_locations_compare_addrs));
| + bp_location **locp_found = gdb::binary_search (bp_locations, last, &dummy_loc,
| + bp_locations_compare_addrs);
...
| @@ -813,17 +808,13 @@ get_first_locp_gte_addr (CORE_ADDR address)
| + if (locp_found == last)
| return NULL;
|
| - /* We may have found a location that is at ADDRESS but is not the first in the
| - location's list. Go backwards (if possible) and locate the first one. */
| - while ((locp_found - 1) >= bp_locations
| - && (*(locp_found - 1))->address == address)
| - locp_found--;
| -
| + /* gdb::binary_search always returns the first element that matches. */
PS2, Line 811:
That indeed seems to be the case, but I don't think it's generally in
the contract of a "binary search". I think a binary search in general
would be free to return any of the matching elements. So if we rely
on this behavior of gdb::binary_search, I think we should document
this behavior in its documentation. Maybe an argument for using
std::lower_bound?
| return locp_found;
| }
|
| void
| set_breakpoint_condition (struct breakpoint *b, const char *exp,
| int from_tty)
| {
| xfree (b->cond_string);
| b->cond_string = NULL;
@@ -64,6 +64,7 @@
#include "dummy-frame.h"
#include "interps.h"
#include "gdbsupport/format.h"
+#include "gdbsupport/gdb_binary_search.h"
#include "thread-fsm.h"
#include "tid-parse.h"
#include "cli/cli-style.h"
@@ -775,12 +776,9 @@
bsearch. This comparison function only cares about addresses, unlike
the more general bp_location_is_less_than function. */
-static int
-bp_locations_compare_addrs (const void *ap, const void *bp)
+static inline int
+bp_locations_compare_addrs (const bp_location *a, const bp_location *b)
{
- const struct bp_location *a = *(const struct bp_location **) ap;
- const struct bp_location *b = *(const struct bp_location **) bp;
-
if (a->address == b->address)
return 0;
else
@@ -790,34 +788,27 @@
/* Helper function to skip all bp_locations with addresses
less than ADDRESS. It returns the first bp_location that
is greater than or equal to ADDRESS. If none is found, just
- return NULL. */
+ return NULL. TODO: That's not what this function implements,
+ it finds the first BP *at* address. Should it just call
+ std::lower_bound? */
static struct bp_location **
get_first_locp_gte_addr (CORE_ADDR address)
{
- struct bp_location dummy_loc;
- struct bp_location *dummy_locp = &dummy_loc;
- struct bp_location **locp_found = NULL;
-
/* Initialize the dummy location's address field. */
+ struct bp_location dummy_loc;
dummy_loc.address = address;
+ auto last = bp_locations + bp_locations_count;
/* Find a close match to the first location at ADDRESS. */
- locp_found = ((struct bp_location **)
- bsearch (&dummy_locp, bp_locations, bp_locations_count,
- sizeof (struct bp_location **),
- bp_locations_compare_addrs));
+ bp_location **locp_found = gdb::binary_search (bp_locations, last, &dummy_loc,
+ bp_locations_compare_addrs);
/* Nothing was found, nothing left to do. */
- if (locp_found == NULL)
+ if (locp_found == last)
return NULL;
- /* We may have found a location that is at ADDRESS but is not the first in the
- location's list. Go backwards (if possible) and locate the first one. */
- while ((locp_found - 1) >= bp_locations
- && (*(locp_found - 1))->address == address)
- locp_found--;
-
+ /* gdb::binary_search always returns the first element that matches. */
return locp_found;
}
@@ -52,6 +52,7 @@
#include "solist.h"
#include "gdb_bfd.h"
#include "btrace.h"
+#include "gdbsupport/gdb_binary_search.h"
#include "gdbsupport/pathstuff.h"
#include <vector>
@@ -1290,17 +1291,14 @@
/* Bsearch comparison function. */
-static int
-bsearch_cmp (const void *key, const void *elt)
+static inline int
+bsearch_cmp (const struct obj_section *section, const CORE_ADDR pc)
{
- const CORE_ADDR pc = *(CORE_ADDR *) key;
- const struct obj_section *section = *(const struct obj_section **) elt;
-
if (pc < obj_section_addr (section))
- return -1;
+ return 1;
if (pc < obj_section_endaddr (section))
return 0;
- return 1;
+ return -1;
}
/* Returns a section whose range includes PC or NULL if none found. */
@@ -1331,20 +1329,15 @@
pspace_info->section_map_dirty = 0;
}
- /* The C standard (ISO/IEC 9899:TC2) requires the BASE argument to
- bsearch be non-NULL. */
if (pspace_info->sections == NULL)
{
gdb_assert (pspace_info->num_sections == 0);
return NULL;
}
- sp = (struct obj_section **) bsearch (&pc,
- pspace_info->sections,
- pspace_info->num_sections,
- sizeof (*pspace_info->sections),
- bsearch_cmp);
- if (sp != NULL)
+ auto last = pspace_info->sections + pspace_info->num_sections;
+ sp = gdb::binary_search (pspace_info->sections, last, pc, bsearch_cmp);
+ if (sp != last)
return *sp;
return NULL;
}