beenull/ladybird
1
0
Fork 0
mirror of https://github.com/LadybirdBrowser/ladybird.git synced 2024-11-21 15:10:19 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions 6
ladybird/AK/BinarySearch.h

73 lines
1.5 KiB
C
Raw Permalink Normal View History

Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
/*
Meta: Update my e-mail address everywhere
2024-10-04 11:19:50 +00:00
* Copyright (c) 2018-2020, Andreas Kling <andreas@ladybird.org>
Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
*
Everything: Move to SPDX license identifiers in all files. SPDX License Identifiers are a more compact / standardized way of representing file license information. See: https://spdx.dev/resources/use/#identifiers This was done with the `ambr` search and replace tool. ambr --no-parent-ignore --key-from-file --rep-from-file key.txt rep.txt *
2021-04-22 08:24:48 +00:00
* SPDX-License-Identifier: BSD-2-Clause
Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
*/
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
#pragma once
Kernel: Optimize VM range deallocation a bit Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19 12:18:27 +00:00
#include <AK/StdLibExtras.h>
Shell: Cache PATH for faster tab completion This patch reduces the O(n) tab completion to something like O(log(n)). The cache is just a sorted vector of strings and we binary search it to get a string matching our input, and then check the surrounding strings to see if we need to remove any characters. Also we no longer stat each file every time. Also added an #include in BinarySearch since it was using size_t. Oops. If `export` is called, we recache. Need to implement the `hash` builtin for when an executable has been added to a directory in PATH.
2019-12-03 06:36:46 +00:00
#include <AK/Types.h>
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
namespace AK {
AK: Deal with unsigned integers in binary search.
2021-01-01 20:32:59 +00:00
struct DefaultComparator {
template<typename T, typename S>
AK: Add `nodiscard` attribute to BinarySearch functions
2022-06-26 16:20:38 +00:00
[[nodiscard]] constexpr int operator()(T& lhs, S& rhs)
AK: Deal with unsigned integers in binary search.
2021-01-01 20:32:59 +00:00
{
if (lhs > rhs)
return 1;
if (lhs < rhs)
return -1;
return 0;
}
AK: Make binary_search signature more generic.
2020-12-29 15:13:16 +00:00
};
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
AK: Deal with unsigned integers in binary search.
2021-01-01 20:32:59 +00:00
template<typename Container, typename Needle, typename Comparator = DefaultComparator>
AK: Make binary_search signature more generic.
2020-12-29 15:13:16 +00:00
constexpr auto binary_search(
Container&& haystack,
Needle&& needle,
size_t* nearby_index = nullptr,
Comparator comparator = Comparator {}) -> decltype(&haystack[0])
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
{
AK: Fix overflow and mixed-signedness issues in binary_search() (#2961)
2020-08-02 19:10:35 +00:00
if (haystack.size() == 0) {
if (nearby_index)
*nearby_index = 0;
return nullptr;
}
size_t low = 0;
size_t high = haystack.size() - 1;
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
while (low <= high) {
AK: Deal with unsigned integers in binary search.
2021-01-01 20:32:59 +00:00
size_t middle = low + (high - low) / 2;
int comparison = comparator(needle, haystack[middle]);
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
if (comparison < 0)
AK: Fix overflow and mixed-signedness issues in binary_search() (#2961)
2020-08-02 19:10:35 +00:00
if (middle != 0)
high = middle - 1;
else
break;
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
else if (comparison > 0)
low = middle + 1;
Kernel: Optimize VM range deallocation a bit Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19 12:18:27 +00:00
else {
if (nearby_index)
*nearby_index = middle;
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
return &haystack[middle];
Kernel: Optimize VM range deallocation a bit Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19 12:18:27 +00:00
}
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
}
Kernel: Optimize VM range deallocation a bit Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19 12:18:27 +00:00
if (nearby_index)
AK: Fix overflow and mixed-signedness issues in binary_search() (#2961)
2020-08-02 19:10:35 +00:00
*nearby_index = min(low, high);
Kernel: Optimize VM range deallocation a bit Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19 12:18:27 +00:00
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
return nullptr;
}
}
AK: Make it possible to not `using` AK classes into the global namespace This patch adds the `USING_AK_GLOBALLY` macro which is enabled by default, but can be overridden by build flags. This is a step towards integrating Jakt and AK types.
2022-11-26 11:18:30 +00:00
#if USING_AK_GLOBALLY
AK: Add a BinarySearch template implementation binary_search takes a haystack, a size, a needle and a compare function. The compare function should return negative if a < b, positive if a > b and 0 if a == b. The "sane default" compare function is integral_compare which implements this with subtraction a - b. binary_search returns a pointer to a matching element, NOT necessarily the FIRST matching element. It returns a nullptr if the element was not found. This patch includes tests for binary_search.
2019-12-02 04:19:57 +00:00
using AK::binary_search;
AK: Make it possible to not `using` AK classes into the global namespace This patch adds the `USING_AK_GLOBALLY` macro which is enabled by default, but can be overridden by build flags. This is a step towards integrating Jakt and AK types.
2022-11-26 11:18:30 +00:00
#endif
Reference in a new issue Copy permalink