mirrors/zig
1
0
Fork 0
mirror of https://codeberg.org/ziglang/zig.git synced 2025-12-06 13:54:21 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions 1
36120 commits 46 branches 24 tags 576 MiB
Commit graph

57 commits

Author SHA1 Message Date
Andrew Kelley
e427ba9cd5 std.sort.partitionPoint: faster implementation (#30005) 
Migrated from https://github.com/ziglang/zig/pull/21419

Co-authored-by: Jonathan Hallstrom <lmj.hallstrom@gmail.com>
Reviewed-on: https://codeberg.org/ziglang/zig/pulls/30005
 2025-11-27 20:48:54 +01:00
Lucas Santos
509639717a std.equalRange: Compute lower and upper bounds simultaneously 
The current implementation of `equalRange` just calls `lowerRange` and `upperRange`, but a lot of
the work done by these two functions can be shared. Specifically, each iteration gives information about whether the lower bound or the upper bound can be tightened. This leads to fewer iterations and, since there is one comparison per iteration, fewer comparisons.
Implementation adapted from [GCC](519ec1cfe9/libstdc%2B%2B-v3/include/bits/stl_algo.h (L2063)).
This sample demonstrates the difference between the current implementation and mine:

```zig
fn S(comptime T: type) type {
    return struct {
        needle: T,
        count: *usize,

        pub fn order(context: @This(), item: T) std.math.Order {
            context.count.* += 1;
            return std.math.order(item, context.needle);
        }
        pub fn orderLength(context: @This(), item: []const u8) std.math.Order {
            context.count.* += 1;
            return std.math.order(item.len, context.needle);
        }
    };
}
pub fn main() !void {
    var count: usize = 0;

    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{}, S(i32){ .needle = 0, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 0, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 0, 1 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 2, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 2, 2 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 5, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 2, 3 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 5, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 64, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 6, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 100, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 2, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, S(i32){ .needle = 8, .count = &count }, S(i32).order));
    try std.testing.expectEqual(.{ 2, 2 }, equalRange(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, S(u32){ .needle = 5, .count = &count }, S(u32).order));
    try std.testing.expectEqual(.{ 1, 1 }, equalRange(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, S(f32){ .needle = -33.4, .count = &count }, S(f32).order));
    try std.testing.expectEqual(.{ 3, 5 }, equalRange(
        []const u8,
        &[_][]const u8{ "Mars", "Venus", "Earth", "Saturn", "Uranus", "Mercury", "Jupiter", "Neptune" },
        S(usize){ .needle = 6, .count = &count },
        S(usize).orderLength,
    ));

    std.debug.print("Count: {}\n", .{count});
}
```
For each comparison, we bump the count. With the current implementation, we get 57 comparisons. With mine, we get 43.

With contributions from @Olvilock.
This is my second attempt at this, since I messed up the [first one](https://github.com/ziglang/zig/pull/21290).
 2024-09-23 13:03:06 -07:00
Jay Petacat
812557bfde std: Restore conventional compareFn behavior for binarySearch 
PR #20927 made some improvements to the `binarySearch` API, but one
change I found surprising was the relationship between the left-hand and
right-hand parameters of `compareFn` was inverted. This is different
from how comparison functions typically behave, both in other parts of
Zig (e.g. `std.math.order`) and in other languages (e.g. C's `bsearch`).
Unless a strong reason can be identified and documented for doing
otherwise, I think it'll be better to stick with convention.

While writing this patch and changing things back to the way they were,
the predicates of `lowerBound` and `upperBound` seemed to be the only
areas that benefited from the inversion. I don't think that benefit is
worth the cost, personally. Calling `Order.invert()` in the predicates
accomplishes the same goal.
 2024-09-16 14:04:18 -07:00
Fri3dNstuff
a655c15c40
std.sort: Remove key argument from binary-search-like functions (#20927) 
closes #20110
 2024-08-04 22:02:15 +00:00
Andrew Kelley
33c7984183 add std.testing.random_seed 
closes #17609
 2024-07-23 11:43:12 -07:00
Alex Kladov
e03026507f
std: fuzz test sort stability (#20284) 
Stability of std sort was undertested before this change. Add a fuzz
test for more confidence.

Specifically, we used to have a single example test that used an array
of eight elements. That ends up exercising only a tiny fraction of
sorting logic, as it hits a hard-coded sorting network due to small
size.
 2024-06-20 12:38:54 -07:00
T. M
3518d22d56 std: Avoid overflowing in the midpoint calculation in upperBound 2024-05-28 20:44:42 -04:00
Andrew Kelley
12191c8a22 std: promote tests to doctests 
Now these show up as "example usage" in generated documentation.
 2024-03-21 14:11:46 -07:00
e4m2
8d56e472c9 Replace std.rand references with std.Random 2024-02-08 15:21:35 +01:00
John Schmidt
e487b576fa Changes to lowerBound/upperBound/equalRange 
The old definitions had some problems:

- In `lowerBound`, the `lhs` (left hand side) argument was passed on the
  right hand side.
- In `upperBound`, the `greaterThan` function needed to return
  `greaterThanOrEqual` for the function work, so either the name or the
  implementation is incorrect.

To fix both problems, define the functions in terms of a `lessThan` function that returns `lhs < rhs`.
The is more consistent with the rest of `sort.zig` and it's also how C++ implements lower/upperBound (1)(2).

(1) https://en.cppreference.com/w/cpp/algorithm/lower_bound
(2) https://en.cppreference.com/w/cpp/algorithm/upper_bound

- Rewrite doc comments.
- Add a couple of more test cases.
- Add docstring for std.sort.binarySearch
 2024-02-07 21:00:24 +01:00
Craig O'Connor
664c18544c Add lowerBound/upperBound/equalRange 
Authored by https://github.com/CraigglesO

Original Discussion: #9890

I already had to create these functions and test cases for my own
project so I decided to contribute to the main code base in hopes it
would simplify my own.

I realize this is still under discussion but this was a trivial amount
of work so I thought I could help nudge the discussion towards a
decision.

Why add these to the standard library

To better illustrate and solidify their value, the standard library's
"sort" module already contains several binary search queries on arrays
such as binarySearch and internal functions binaryFirst & binaryLast. A
final example of its use: the Zig code itself created and used a
bounding search in the linker.

There still lacks the ability to allow the programmer themselves to
search the array for a rough position and find an index to read &/
update.

Adding these functions would also help to complement dynamic structures
like ArrayList with it's insert function.

Example Case

I'm building a library in Zig for GIS geometry. To store points, lines,
and polygons each 3D point is first translated into what's called an
S2CellId. This is a fancy way of saying I reduce the Earth's spherical
data into a 1D Hilbert Curve with cm precision. This gives me 2
convenient truths:

    Hilbert Curves have locality of reference.
    All points can be stored inside a 1D array

Since lowerBound and upperBound to find data inside a radius for
instance. If I'm interested in a specific cell at a specific "level" and
want to iterate all duplicates, equalRange is a best fit.
 2024-02-07 21:00:24 +01:00
mlugg
51595d6b75
lib: correct unnecessary uses of 'var' 2023-11-19 09:55:07 +00:00
Jacob Young
fe93332ba2 x86_64: implement enough to pass unicode tests 
* implement vector comparison
 * implement reduce for bool vectors
 * fix `@memcpy` bug
 * enable passing std tests
 2023-10-23 22:42:18 -04:00
Jacob Young
27fe945a00 Revert "Revert "Merge pull request #17637 from jacobly0/x86_64-test-std"" 
This reverts commit 6f0198cadb.
 2023-10-22 15:46:43 -04:00
Andrew Kelley
6f0198cadb Revert "Merge pull request #17637 from jacobly0/x86_64-test-std" 
This reverts commit 0c99ba1eab, reversing
changes made to 5f92b070bf.

This caused a CI failure when it landed in master branch due to a
128-bit `@byteSwap` in std.mem.
 2023-10-22 12:16:35 -07:00
Jacob Young
32e85d44eb x86_64: disable failing tests, enable test-std testing 2023-10-21 10:55:41 -04:00
Andrew Kelley
cbb9b5d9f0 std: add unstable sorting to array hash maps 
closes #17426
 2023-10-08 16:54:31 -07:00
yujiri8
dae516dbdf
improve documentation of std.sort.*Context functions (#16145) 2023-06-27 00:51:06 -07:00
Ali Chraghi
6bd5479306 std.sort.block: add safety check for lessThan return value 2023-06-26 17:50:10 -07:00
Niles Salter
7d511d6428
[heapsort] Protect against integer overflow 
(Firstly, I changed `n` to `b`, as that is less confusing. It's not a length, it's a right boundary.)

The invariant maintained is `cur < b`. In the worst case `2*cur + 1` results in a maximum of `2b`. Since `2b` is not guaranteed to be lower than `maxInt`, we have to add one overflow check to `siftDown` to make sure we avoid undefined behavior.

LLVM also seems to have a nicer time compiling this version of the function. It is about 2x faster in my tests (I think LLVM was stumped by the `child += @intFromBool` line), and adding/removing the overflow check has a negligible performance difference on my machine. Of course, we could check `2b <= maxInt` in the parent function, and dispatch to a version of the function without the overflow check in the common case, but that probably is not worth the code size just to eliminate a single instruction.
 2023-06-22 17:32:28 +00:00
Eric Joldasov
50339f595a all: zig fmt and rename "@XToY" to "@YFromX" 
Signed-off-by: Eric Joldasov <bratishkaerik@getgoogleoff.me>
 2023-06-19 12:34:42 -07:00
Niles Salter
700ea694b2
Fix pdqSort+heapSort for ranges besides 0..len (#15982) 2023-06-13 16:55:58 -04:00
Ali Chraghi
3db3cf7790 std.sort: add pdqsort and heapsort 2023-05-23 17:55:59 -07:00
IntegratedQuantum
6e05620117 Document the sorting order in std.sort. 2023-05-17 18:26:49 -07:00
Andrew Kelley
6261c13731 update codebase to use @memset and @memcpy 2023-04-28 13:24:43 -07:00
Roman Frołow
0787b11f19
naming: mid for index and mid_item for item 2023-03-21 15:12:13 +02:00
Alexis Brodeur
98dd041d53 Relax std.sort.binarySearch requirements 
Forcing the key to be of the same type as the sorted items used during
the search is a valid use case.

There, however, exists some cases where the key and the items are of
heterogeneous types, like searching for a code point in ordered ranges
of code points:

```zig
const CodePoint = u21;
const CodePointRange = [2]CodePoint;

const valid_ranges = &[_]CodePointRange{
    // an ordered array of ranges
};

fn orderCodePointAndRange(
    context: void,
    code_point: CodePoint,
    range: CodePointRange
) std.math.Order {
    _ = context;
    if (code_point < range[0]) {
        return .lt;
    }
    if (code_point > range[1]) {
        return .gt;
    }
    return .eq;
}

fn isValidCodePoint(code_point: CodePoint) bool {
    return std.sort.binarySearch(
        CodePointRange,
        code_point,
        valid_ranges,
        void,
        orderCodePointAndRange
    ) != null;
}
```

It is so expected that `std.sort.binarySearch` should therefore support
both homogeneous and heterogeneous keys.
 2023-02-21 12:28:43 -05:00
Andrew Kelley
aeaef8c0ff update std lib and compiler sources to new for loop syntax 2023-02-18 19:17:21 -07:00
Andrew Kelley
6e49ba77f3 std: add sort method to ArrayHashMap and MultiArrayList 
This also adds `std.sort.sortContext` and
`std.sort.insertionSortContext` which are more advanced methods that
allow overriding the `swap` method. The former calls the latter for now
because reworking the main sort implementation is a big task that can be
done later without any changes to the API.
 2022-03-10 13:13:17 -05:00
Ominitay
c1a5ff34f3 std.rand: Refactor Random interface 
These changes have been made to resolve issue #10037. The `Random`
interface was implemented in such a way that causes significant slowdown
when calling the `fill` function of the rng used.

The `Random` interface is no longer stored in a field of the rng, and is
instead returned by the child function `random()` of the rng. This
avoids the performance issues caused by the interface.
 2021-10-27 16:07:48 -04:00
Andrew Kelley
6115cf2240 migrate from std.Target.current to @import("builtin").target 
closes #9388
closes #9321
 2021-10-04 23:48:55 -07:00
Andrew Kelley
d29871977f remove redundant license headers from zig standard library 
We already have a LICENSE file that covers the Zig Standard Library. We
no longer need to remind everyone that the license is MIT in every single
file.

Previously this was introduced to clarify the situation for a fork of
Zig that made Zig's LICENSE file harder to find, and replaced it with
their own license that required annual payments to their company.
However that fork now appears to be dead. So there is no need to
reinforce the copyright notice in every single file.
 2021-08-24 12:25:09 -07:00
Jacob G-W
9fffffb07b fix code broken from previous commit 2021-06-21 17:03:03 -07:00
Andrew Kelley
5619ce2406 Merge remote-tracking branch 'origin/master' into stage2-whole-file-astgen 
Conflicts:
 * doc/langref.html.in
 * lib/std/enums.zig
 * lib/std/fmt.zig
 * lib/std/hash/auto_hash.zig
 * lib/std/math.zig
 * lib/std/mem.zig
 * lib/std/meta.zig
 * test/behavior/alignof.zig
 * test/behavior/bitcast.zig
 * test/behavior/bugs/1421.zig
 * test/behavior/cast.zig
 * test/behavior/ptrcast.zig
 * test/behavior/type_info.zig
 * test/behavior/vector.zig

Master branch added `try` to a bunch of testing function calls, and some
lines also had changed how to refer to the native architecture and other
`@import("builtin")` stuff.
 2021-05-08 14:45:21 -07:00
Veikka Tuominen
fd77f2cfed std: update usage of std.testing 2021-05-08 15:15:30 +03:00
Andrew Kelley
429cd2b5dd std: change @import("builtin") to std.builtin 2021-04-15 19:06:39 -07:00
Andreas Karlsson
50af87a9e3 Fix example code in comments for asc and desc 2021-01-06 15:53:53 -08:00
Frank Denis
6c2e0c2046 Year++ 2020-12-31 15:45:24 -08:00
Andrew Kelley
4a69b11e74 add license header to all std lib files 
add SPDX license identifier
copyright ownership is zig contributors
 2020-08-20 16:07:04 -04:00
Vexu
e85fe13e44
run zig fmt on std lib and self hosted 2020-07-11 20:41:19 +03:00
Andrew Kelley
d4d954abd2 std.sort: give comparator functions a context parameter 2020-06-08 15:16:40 -04:00
Yuri Pieters
f5f77089b7 sort.binarySearch: Remove unneeded edge case check 2020-04-09 09:13:47 +01:00
Yuri Pieters
b7e72cc421 sort.binarySearch: test for regresson of #4980 2020-04-09 02:00:08 +01:00
Yuri Pieters
447dc2bb90 sort.binarySearch: fix integer underflow (#4980) 
When the key was smaller than any value in the array, an error was
ocurring with the mid being zero and having 1 subtracted from it.
 2020-04-09 01:58:57 +01:00
Andrew Kelley
9e7ae06249
std lib API deprecations for the upcoming 0.6.0 release 
See #3811
 2020-03-30 14:23:22 -04:00
Benjamin Feng
699c50a375 Switch a bunch of FBA to use testing.allocator 2020-02-12 17:17:56 -06:00
LemonBoy
db3aea3a0b Change API for binarySearch fn 2020-02-03 21:51:03 +01:00
LemonBoy
fd8d8afb24 stdlib: Add binary search function 2020-01-31 00:40:43 +01:00
Andrew Kelley
13259acbc3
std.sort.insertionSort: remove superfluous block 2020-01-28 16:22:09 -05:00
Robin Voetter
841a37ab59 Add std.sort.argMax and std.sort.argMin 2019-12-04 18:20:55 +01:00