From 35e65c49df7d8fac3c0a32fa0d696988a9de675d Mon Sep 17 00:00:00 2001 From: Christian Biesinger Date: Mon, 21 Oct 2019 13:08:03 -0500 Subject: [PATCH] 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 * 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 --- 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(-) create mode 100644 gdb/gdbsupport/gdb_binary_search.h diff --git a/gdb/ChangeLog b/gdb/ChangeLog index 5cf1ae71af..c96b61a07e 100644 --- a/gdb/ChangeLog +++ b/gdb/ChangeLog @@ -1,3 +1,10 @@ +2019-10-29 Christian Biesinger + + * 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 * NEWS: Mention new --with-system-gdbinit-dir option. diff --git a/gdb/Makefile.in b/gdb/Makefile.in index c9243731aa..4f431c3c84 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 c41db791dc..719e06570d 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 0000000000..0cb429e820 --- /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 . */ + + +#ifndef GDBSUPPORT_GDB_BINARY_SEARCH_H +#define GDBSUPPORT_GDB_BINARY_SEARCH_H + +#include + +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 +It binary_search (It first, It last, T el, Comp comp) +{ + auto lt = [&] (const typename std::iterator_traits::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 */ -- 2.34.1