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

1 files changed, 59 insertions, 0 deletions

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 */