and remove "release" from the enum tag names.
no functional change, however, despite the addition of
backwards-compatibile declarations in this patch, it is breaking because
expressions that use `==` or `!=` operators will not able to use the
deprecated names.
I predict these names to survive until the 1.0 tag without any more
breakage.
our pdq implementation uses an explicit stack of `Range` entries to avoid recursion.
The size of this stack was set to `log2(maxInt(usize) + 1)`. on 32-bit
targets like `wasm32-freestanding`, this would hit the maximum size,
causing OOB. there were two issues:
- `max_limit`, which controls how many imbalanced partitions are allowed
before the algorithm falls back to heapsort, was computed as
`floorPowerOfTwo(n) + 1` instead of `log2(n)` as in the original c++
reference implementation. e.g. for `n = 1_000_000`, this allowed 524289
bad partitions before heapsort would kick in, instead of 19.
this meant deeply imbalanced partitions could accumulate stack pushes
essentially without limit. However, i didn't observe any meaningful
difference in benchmarks.
- the worst-case stack depth is bounded by `log2(n) + max_limit`,
which approaches `2 * log2(n)`. The reference c++ and go implementation
doesn't have this problem because they don't use explicit stack buffer.
Implement BlockQuicksort (was a TODO item).
This avoids branch mispredictions on random data, yielding ~2x
speedup on large random arrays while leaving pre-sorted and
equal-element fast paths unaffected.
After partitioning, the pivot acts as a sentinel for the right
sub-partition, guaranteeing termination without a bounds check.
So we can skip the `j > a` check for all non-leftmost partitions.
Give a consistent ~10-50% speedup, with the biggest gains at smaller
sizes.
* std.sort.pdq: fix out-of-bounds access in partialInsertionSort
When sorting a sub-range that doesn't start at index 0, the
partialInsertionSort function could access indices below the range
start. The loop condition `while (j >= 1)` didn't respect the
arbitrary range boundaries [a, b).
This changes the condition to `while (j > a)` to ensure indices
never go below the range start, fixing the issue where pdqContext
would access out-of-bounds indices.
Fixes#25250
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
Most of this migration was performed automatically with `zig fmt`. There
were a few exceptions which I had to manually fix:
* `@alignCast` and `@addrSpaceCast` cannot be automatically rewritten
* `@truncate`'s fixup is incorrect for vectors
* Test cases are not formatted, and their error locations change
Paul Anderson