public inbox for gdb-cvs@sourceware.org help / color / mirror / Atom feed
From: Christian Biesinger <cbiesinger@sourceware.org> To: gdb-cvs@sourceware.org Subject: [binutils-gdb] Replace bsearch with a std::lower_bound-based search Date: Tue, 29 Oct 2019 19:06:00 -0000 [thread overview] Message-ID: <20191029190648.91388.qmail@sourceware.org> (raw) https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=35e65c49df7d8fac3c0a32fa0d696988a9de675d commit 35e65c49df7d8fac3c0a32fa0d696988a9de675d Author: Christian Biesinger <cbiesinger@google.com> Date: Mon Oct 21 13:08:03 2019 -0500 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 Diff: --- gdb/ChangeLog | 7 +++++ gdb/Makefile.in | 1 + gdb/dwarf2-frame.c | 24 +++++++--------- gdb/gdbsupport/gdb_binary_search.h | 59 ++++++++++++++++++++++++++++++++++++++ 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 */
reply other threads:[~2019-10-29 19:06 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20191029190648.91388.qmail@sourceware.org \ --to=cbiesinger@sourceware.org \ --cc=gdb-cvs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).