17d62b00eSchristos /* C++ implementation of a binary search. 27d62b00eSchristos 3*6881a400Schristos Copyright (C) 2019-2023 Free Software Foundation, Inc. 47d62b00eSchristos 57d62b00eSchristos This file is part of GDB. 67d62b00eSchristos 77d62b00eSchristos This program is free software; you can redistribute it and/or modify 87d62b00eSchristos it under the terms of the GNU General Public License as published by 97d62b00eSchristos the Free Software Foundation; either version 3 of the License, or 107d62b00eSchristos (at your option) any later version. 117d62b00eSchristos 127d62b00eSchristos This program is distributed in the hope that it will be useful, 137d62b00eSchristos but WITHOUT ANY WARRANTY; without even the implied warranty of 147d62b00eSchristos MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 157d62b00eSchristos GNU General Public License for more details. 167d62b00eSchristos 177d62b00eSchristos You should have received a copy of the GNU General Public License 187d62b00eSchristos along with this program. If not, see <http://www.gnu.org/licenses/>. */ 197d62b00eSchristos 207d62b00eSchristos 217d62b00eSchristos #ifndef GDBSUPPORT_GDB_BINARY_SEARCH_H 227d62b00eSchristos #define GDBSUPPORT_GDB_BINARY_SEARCH_H 237d62b00eSchristos 247d62b00eSchristos #include <algorithm> 257d62b00eSchristos 267d62b00eSchristos namespace gdb { 277d62b00eSchristos 287d62b00eSchristos /* Implements a binary search using C++ iterators. 297d62b00eSchristos This differs from std::binary_search in that it returns an iterator for 307d62b00eSchristos the found element and in that the type of EL can be different from the 317d62b00eSchristos type of the elements in the container. 327d62b00eSchristos 337d62b00eSchristos COMP is a C-style comparison function with signature: 347d62b00eSchristos int comp(const value_type& a, const T& b); 357d62b00eSchristos It should return -1, 0 or 1 if a is less than, equal to, or greater than 367d62b00eSchristos b, respectively. 377d62b00eSchristos [first, last) must be sorted. 387d62b00eSchristos 397d62b00eSchristos The return value is an iterator pointing to the found element, or LAST if 407d62b00eSchristos no element was found. */ 417d62b00eSchristos template<typename It, typename T, typename Comp> 427d62b00eSchristos It binary_search (It first, It last, T el, Comp comp) 437d62b00eSchristos { 447d62b00eSchristos auto lt = [&] (const typename std::iterator_traits<It>::value_type &a, 457d62b00eSchristos const T &b) 467d62b00eSchristos { return comp (a, b) < 0; }; 477d62b00eSchristos 487d62b00eSchristos auto lb = std::lower_bound (first, last, el, lt); 497d62b00eSchristos if (lb != last) 507d62b00eSchristos { 517d62b00eSchristos if (comp (*lb, el) == 0) 527d62b00eSchristos return lb; 537d62b00eSchristos } 547d62b00eSchristos return last; 557d62b00eSchristos } 567d62b00eSchristos 577d62b00eSchristos } /* namespace gdb */ 587d62b00eSchristos 597d62b00eSchristos #endif /* GDBSUPPORT_GDB_BINARY_SEARCH_H */ 60