Replace bsearch with a std::lower_bound-based search

This is more type-safe and can be faster due to inlining and
avoiding overhead from calling through a function pointer.

gdb/ChangeLog:

2019-10-29  Christian Biesinger  <cbiesinger@google.com>

	* Makefile.in (HFILES_NO_SRCDIR): Add gdb_binary_search.h.
	* dwarf2-frame.c (bsearch_fde_cmp): Update.
	(dwarf2_frame_find_fde): Replace bsearch with gdb::binary_search.
	* gdbsupport/gdb_binary_search.h: New file.

Change-Id: I07e0a0e333f4062b27fc68d3a3f24881ebc68fd4

4 files changed, 77 insertions, 14 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 5cf1ae7..c96b61a 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,5 +1,12 @@
 2019-10-29  Christian Biesinger  <cbiesinger@google.com>
 
+	* Makefile.in (HFILES_NO_SRCDIR): Add gdb_binary_search.h.
+	* dwarf2-frame.c (bsearch_fde_cmp): Update.
+	(dwarf2_frame_find_fde): Replace bsearch with gdb::binary_search.
+	* gdbsupport/gdb_binary_search.h: New file.
+
+2019-10-29  Christian Biesinger  <cbiesinger@google.com>
+
 	* NEWS: Mention new --with-system-gdbinit-dir option.
 	* config.in: Regenerate.
 	* configure: Regenerate.
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index c924373..4f431c3 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -1469,6 +1469,7 @@ HFILES_NO_SRCDIR = \
 	gdbsupport/format.h \
 	gdbsupport/gdb-dlfcn.h \
 	gdbsupport/gdb_assert.h \
+	gdbsupport/gdb_binary_search.h \
 	gdbsupport/gdb_tilde_expand.h \
 	gdbsupport/gdb_locale.h \
 	gdbsupport/gdb_proc_service.h \
diff --git a/gdb/dwarf2-frame.c b/gdb/dwarf2-frame.c
index c41db79..719e065 100644
--- a/gdb/dwarf2-frame.c
+++ b/gdb/dwarf2-frame.c
@@ -39,6 +39,7 @@
 #include "ax.h"
 #include "dwarf2loc.h"
 #include "dwarf2-frame-tailcall.h"
+#include "gdbsupport/gdb_binary_search.h"
 #if GDB_SELF_TEST
 #include "gdbsupport/selftest.h"
 #include "selftest-arch.h"
@@ -1652,15 +1653,12 @@ find_cie (const dwarf2_cie_table &cie_table, ULONGEST cie_pointer)
   return NULL;
 }
 
-static int
-bsearch_fde_cmp (const void *key, const void *element)
+static inline int
+bsearch_fde_cmp (const dwarf2_fde *fde, CORE_ADDR seek_pc)
 {
-  CORE_ADDR seek_pc = *(CORE_ADDR *) key;
-  struct dwarf2_fde *fde = *(struct dwarf2_fde **) element;
-
-  if (seek_pc < fde->initial_location)
+  if (fde->initial_location + fde->address_range <= seek_pc)
     return -1;
-  if (seek_pc < fde->initial_location + fde->address_range)
+  if (fde->initial_location <= seek_pc)
     return 0;
   return 1;
 }
@@ -1674,7 +1672,6 @@ dwarf2_frame_find_fde (CORE_ADDR *pc, CORE_ADDR *out_offset)
   for (objfile *objfile : current_program_space->objfiles ())
     {
       struct dwarf2_fde_table *fde_table;
-      struct dwarf2_fde **p_fde;
       CORE_ADDR offset;
       CORE_ADDR seek_pc;
 
@@ -1697,15 +1694,14 @@ dwarf2_frame_find_fde (CORE_ADDR *pc, CORE_ADDR *out_offset)
         continue;
 
       seek_pc = *pc - offset;
-      p_fde = ((struct dwarf2_fde **)
-	       bsearch (&seek_pc, fde_table->entries, fde_table->num_entries,
-                        sizeof (fde_table->entries[0]), bsearch_fde_cmp));
-      if (p_fde != NULL)
+      auto end = fde_table->entries + fde_table->num_entries;
+      auto it = gdb::binary_search (fde_table->entries, end, seek_pc, bsearch_fde_cmp);
+      if (it != end)
         {
-          *pc = (*p_fde)->initial_location + offset;
+          *pc = (*it)->initial_location + offset;
 	  if (out_offset)
 	    *out_offset = offset;
-          return *p_fde;
+          return *it;
         }
     }
   return NULL;
diff --git a/gdb/gdbsupport/gdb_binary_search.h b/gdb/gdbsupport/gdb_binary_search.h
new file mode 100644
index 0000000..0cb429e
--- /dev/null
+++ b/gdb/gdbsupport/gdb_binary_search.h
@@ -0,0 +1,59 @@
+/* C++ implementation of a binary search.
+
+   Copyright (C) 2019 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+
+#ifndef GDBSUPPORT_GDB_BINARY_SEARCH_H
+#define GDBSUPPORT_GDB_BINARY_SEARCH_H
+
+#include <algorithm>
+
+namespace gdb {
+
+/* Implements a binary search using C++ iterators.
+   This differs from std::binary_search in that it returns an interator for
+   the found element and in that the type of EL can be different from the
+   type of the elements in the countainer.
+
+   COMP is a C-style comparison function with signature:
+   int comp(const value_type& a, const T& b);
+   It should return -1, 0 or 1 if a is less than, equal to, or greater than
+   b, respectively.
+   [first, last) must be sorted.
+
+   The return value is an iterator pointing to the found element, or LAST if
+   no element was found.  */
+template<typename It, typename T, typename Comp>
+It binary_search (It first, It last, T el, Comp comp)
+{
+  auto lt = [&] (const typename std::iterator_traits<It>::value_type &a,
+		 const T &b)
+    { return comp (a, b) < 0; };
+
+  auto lb = std::lower_bound (first, last, el, lt);
+  if (lb != last)
+    {
+      if (comp (*lb, el) == 0)
+	return lb;
+    }
+  return last;
+}
+
+} /* namespace gdb */
+
+#endif /* GDBSUPPORT_GDB_BINARY_SEARCH_H */