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

Message ID gerrit.1572811202000.I4c2c21a6870c5abffd87831ba024da3659bbfaa3@gnutoolchain-gerrit.osci.io
State New
Headers show
Series
  • [review] Replace callers of bsearch with gdb::binary_search
Related show

Commit Message

Simon Marchi (Code Review) Nov. 3, 2019, 8 p.m.
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(-)




-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I4c2c21a6870c5abffd87831ba024da3659bbfaa3
Gerrit-Change-Number: 491
Gerrit-PatchSet: 1
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-MessageType: newchange

Comments

Simon Marchi (Code Review) Nov. 15, 2019, 9:33 p.m. | #1
Christian Biesinger has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................


Patch Set 2:

Ping?


-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I4c2c21a6870c5abffd87831ba024da3659bbfaa3
Gerrit-Change-Number: 491
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Comment-Date: Fri, 15 Nov 2019 21:33:09 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: No
Gerrit-MessageType: comment
Simon Marchi (Code Review) Nov. 27, 2019, 10:55 p.m. | #2
Christian Biesinger has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/491
......................................................................


Patch Set 2:

ping


-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I4c2c21a6870c5abffd87831ba024da3659bbfaa3
Gerrit-Change-Number: 491
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Comment-Date: Wed, 27 Nov 2019 22:55:39 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: No
Gerrit-MessageType: comment
Simon Marchi (Code Review) Nov. 28, 2019, 3:34 a.m. | #3
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;

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I4c2c21a6870c5abffd87831ba024da3659bbfaa3
Gerrit-Change-Number: 491
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-Comment-Date: Thu, 28 Nov 2019 03:34:15 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
Gerrit-MessageType: comment

Patch

diff --git a/gdb/breakpoint.c b/gdb/breakpoint.c
index c9587ff..fc63c4d 100644
--- a/gdb/breakpoint.c
+++ b/gdb/breakpoint.c
@@ -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;
 }
 
diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index b5bc09f..36ae238 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -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;
 }