The tests:
- __support/freelist_heap_fuzz.cpp
- fuzzing/string/strlen_fuzz.cpp
had build failures for different reasons. This patch fixes these
failures.
freelist_heap_fuzz.cpp had this error:
```
llvm-project/libc/fuzzing/__support/freelist_heap_fuzz.cpp:150:26: error: use of undeclared identifier 'Block'; did you mean '__llvm_libc_23_0_0_git::Block'?
150 | size_t alignment = Block::MIN_ALIGN;
| ^~~~~
| __llvm_libc_23_0_0_git::Block
```
The issue stems from the fact that Block was not available in scope. It
needs to be referenced via LIBC_NAMESPACE.
strlen_fuzz.cpp had this error:
```
In file included from Workspace/llvm-project/libc/fuzzing/string/strlen_fuzz.cpp:14:
In file included from /usr/lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/cstdint:38:
In file included from /usr/lib/gcc/x86_64-linux-gnu/13/../../../../include/x86_64-linux-gnu/c++/13/bits/c++config.h:679:
/usr/lib/gcc/x86_64-linux-gnu/13/../../../../include/x86_64-linux-gnu/c++/13/bits/os_defines.h:44:5: error: function-like macro '__GLIBC_PREREQ' is not defined
44 | #if __GLIBC_PREREQ(2,15) && defined(_GNU_SOURCE)
```
This issue is more cryptic to me, but I managed to fix it by changing
the includes from cstdint and cstring to stdint.h and string.h.
Related to #114695.
This PR adds a Weak AVL Tree for tsearch APIs. The symbol
implementations are coming in a
following up PR to avoid creating a huge patch. The work is based on
@MaskRay's recent post (see below).
A general self-balancing binary search tree where the node pointer can
be used as stable handles to the stored values.
The self-balancing strategy is the Weak AVL (WAVL) tree, based on the
following foundational references:
1. https://maskray.me/blog/2025-12-14-weak-avl-tree
2. https://reviews.freebsd.org/D25480
3. https://ics.uci.edu/~goodrich/teach/cs165/notes/WeakAVLTrees.pdf
4. https://dl.acm.org/doi/10.1145/2689412 (Rank-Balanced Trees)
WAVL trees belong to the rank-balanced binary search tree framework
(reference 4), alongside AVL and Red-Black trees.
Key Properties of WAVL Trees:
1. Relationship to Red-Black Trees: A WAVL tree can always be colored as
a
Red-Black tree.
2. Relationship to AVL Trees: An AVL tree meets all the requirements of
a
WAVL tree. Insertion-only WAVL trees maintain the same structure as AVL
trees.
Rank-Based Balancing:
In rank-balanced trees, each node is assigned a rank (conceptually
similar
to height). In AVL/WAVL, the rank difference between a parent and its
child is
strictly enforced to be either **1** or **2**.
- **AVL Trees:** Rank is equivalent to height. The strict condition is
that
there are no 2-2 nodes (a parent with rank difference 2 to both
children).
- **WAVL Trees:** The no 2-2 node rule is relaxed for internal nodes
during
the deletion fixup process, making WAVL trees less strictly balanced
than
AVL trees but easier to maintain than Red-Black trees.
Balancing Mechanics (Promotion/Demotion):
- **Null nodes** are considered to have rank -1.
- **External/leaf nodes** have rank 0.
- **Insertion:** Inserting a node may create a situation where a parent
and
child
have the same rank (difference 0). This is fixed by **promoting** the
rank
of the parent and propagating the fix upwards using at most two
rotations
(trinode fixup).
- **Deletion:** Deleting a node may result in a parent being 3 ranks
higher
than a child (difference 3). This is fixed by **demoting** the parent's
rank and propagating the fix upwards.
Implementation Detail:
The rank is **implicitly** maintained. We never store the full rank.
Instead,
a 2-bit tag is used on each node to record the rank difference to each
child:
- Bit cleared (0) -> Rank difference is **1**.
- Bit set (1) -> Rank difference is **2**.
---------
Co-authored-by: Michael Jones <michaelrj@google.com>
Previously we only checked the long double value of the provided double.
This meant we didn't check any values near the edge of the long double
range, which meant we were missing several bugs. This patch adds a
second long double value to check which is generated separately from the
double value and can be anywhere in the range.
Most platforms inherently have a size_t alignment of 4, but this isn't
true on every platform LLVM has some degree of backend support for.
Accordingly, it's simple enough to just set the min alignment of Block
to 4 and lose the static_assert.
Fuzz tests were set up incorrectly so updated trig functions to match
the correct format.
---------
Co-authored-by: Sriya Pratipati <sriyap@google.com>
The printf parser uses errno for setting up the %m conversion. It was
presumably getting this include indirectly until a recent change. This
patch adds a direct dependency to fix it.
FreeListHeap uses the _end symbol which conflicts with the _end symbol
defined by GPU start.cpp files so for now we exclude the test and the
fuzzer on GPU.
docgen relies on the convention that we have a file foo.cpp in
libc/src/\<header\>/. Because the above functions weren't in libc/src/strings/
but rather libc/src/string/, docgen could not find that we had implemented
these.
Rather than add special carve outs to docgen, let's fix up our sources for
these 7 functions to stick with the existing conventions the rest of the
codebase follows.
Link: #118860Fixes: #118875
This reverts commit 93b83642ee34d0092b94776728dad0117c2b72a1.
- Correct riscv32 assumption about alignment (bit of a hack).
- Fix test case where the largest_small and smallest sizes are the
same.
- Fix assertion expressions.
- Fix incorrect small size in freestore_test.
- There may only be one small size for high alignment and small
pointers (riscv32).
- Don't rely on stack alignment in FreeList test.
This reworks the free store implementation in libc's malloc to use a
dlmalloc-style binary trie of circularly linked FIFO free lists. This
data structure can be maintained in logarithmic time, but it still
permits a relatively small implementation compared to other
logarithmic-time ordered maps.
The implementation doesn't do the various bitwise tricks or
optimizations used in actual dlmalloc; it instead optimizes for
(relative) readability and minimum code size. Specific optimization can
be added as necessary given future profiling.
Verifies that sin function output is correct by comparing with MPFR
output. NaN and inf are not tested (as our output will vary compared to
MPFR), and signed zeroes are already tested in unit tests.
Context: https://github.com/llvm/llvm-project/pull/87017
- Add proxy header `libc/hdr/math_macros.h` that will:
- include `<math.h>` in overlay mode,
- include `"include/llvm-libc-macros/math-macros.h"` in full build mode.
- Its corresponding CMake target `libc.hdr.math_macros` will only depend
on `libc.include.math` and `libc.include.llvm-libc-macros.math_macros`
in full build mode.
- Replace all `#include "include/llvm-libc-macros/math-macros.h"` with
`#include "hdr/math_macros.h"`.
- Add dependency to `libc.hdr.math_macros` CMake target when using
`add_fp_unittest`.
- Update the remaining dependency.
- Update bazel overlay: add `libc:hdr_math_macros` target, and replacing
all dependency on `libc:llvm_libc_macros_math_macros` with
`libc:hdr_math_macros`.
Reverts llvm/llvm-project#86137
Some aarch64 compilers seem to consider that `uint128_t` is not
`is_trivially_constructible` which prevents `bit_cast`-ing.
This patch moves most of the multiprecision logic to the `multiword`
namespace and simplifies some logic in `BigInt`. It also fully
implements the mask and count functions and increases test coverage.
`math_extras.h` is also reworked to make it more concise.
Reland of #84991
A downstream overlay mode user ran into issues with the isnan macro not
working in our sources with a specific libc configuration. This patch
replaces the last direct includes of math.h with our internal
math_macros.h, along with the necessary build system changes.
