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>
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.
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.
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.
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.
