[review] Replace callers of bsearch with gdb::binary_search

  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(-)
  

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;