From patchwork Tue Oct 29 19:07:06 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Simon Marchi (Code Review)" X-Patchwork-Id: 35443 Received: (qmail 101923 invoked by alias); 29 Oct 2019 19:07:15 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Delivered-To: mailing list gdb-patches@sourceware.org Received: (qmail 101461 invoked by uid 89); 29 Oct 2019 19:07:12 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=ham version=3.3.1 spammy= X-HELO: mx1.osci.io Received: from polly.osci.io (HELO mx1.osci.io) (8.43.85.229) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 29 Oct 2019 19:07:10 +0000 Received: by mx1.osci.io (Postfix, from userid 994) id 90BDB2105B; Tue, 29 Oct 2019 15:07:08 -0400 (EDT) Received: from gnutoolchain-gerrit.osci.io (gnutoolchain-gerrit.osci.io [IPv6:2620:52:3:1:5054:ff:fe06:16ca]) by mx1.osci.io (Postfix) with ESMTP id 39F7420C06; Tue, 29 Oct 2019 15:07:07 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by gnutoolchain-gerrit.osci.io (Postfix) with ESMTP id 197E620AF6; Tue, 29 Oct 2019 15:07:07 -0400 (EDT) X-Gerrit-PatchSet: 2 Date: Tue, 29 Oct 2019 15:07:06 -0400 From: "Sourceware to Gerrit sync (Code Review)" To: Christian Biesinger , Tom Tromey , gdb-patches@sourceware.org Auto-Submitted: auto-generated X-Gerrit-MessageType: newpatchset Subject: [pushed] Replace bsearch with a std::lower_bound-based search X-Gerrit-Change-Id: I07e0a0e333f4062b27fc68d3a3f24881ebc68fd4 X-Gerrit-Change-Number: 403 X-Gerrit-ChangeURL: X-Gerrit-Commit: 35e65c49df7d8fac3c0a32fa0d696988a9de675d In-Reply-To: References: Reply-To: noreply@gnutoolchain-gerrit.osci.io, tromey@sourceware.org, cbiesinger@google.com, gdb-patches@sourceware.org MIME-Version: 1.0 Content-Disposition: inline User-Agent: Gerrit/3.0.3-74-g460fb0f7e9 Message-Id: <20191029190707.197E620AF6@gnutoolchain-gerrit.osci.io> The original change was created by Christian Biesinger. 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 * 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 + * 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. * 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 . */ + + +#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 */