[pushed] Replace bsearch with a std::lower_bound-based search
Sourceware to Gerrit sync (Code Review)
gerrit@gnutoolchain-gerrit.osci.io
Tue Oct 29 19:07:00 GMT 2019
Sourceware to Gerrit sync has submitted this change.
Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/403
......................................................................
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
---
M gdb/ChangeLog
M gdb/Makefile.in
M gdb/dwarf2-frame.c
A gdb/gdbsupport/gdb_binary_search.h
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 @@
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 @@
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 @@
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 @@
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 */
--
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I07e0a0e333f4062b27fc68d3a3f24881ebc68fd4
Gerrit-Change-Number: 403
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Tom Tromey <tromey@sourceware.org>
Gerrit-MessageType: merged
More information about the Gdb-patches
mailing list