llvm-project.git/libc/src/search/hsearch.cpp, branch users/nico/python-1

[libc] Move libc_errno.h to libc/src/__support and make LIBC_ERRNO_MODE_SYSTEM to be header-only. (#143187)

2025-06-11T20:25:27+00:00

This is the first step in preparation for:
https://discourse.llvm.org/t/rfc-make-clang-builtin-math-functions-constexpr-with-llvm-libc-to-support-c-23-constexpr-math-functions/86450

[libc] Migrate to using LIBC_NAMESPACE_DECL for namespace declaration (#98597)

2024-07-12T16:28:41+00:00

This is a part of #97655.

Revert "[libc] Migrate to using LIBC_NAMESPACE_DECL for namespace declaration" (#98593)

2024-07-12T07:12:13+00:00

Reverts llvm/llvm-project#98075

bots are broken

[libc] Migrate to using LIBC_NAMESPACE_DECL for namespace declaration (#98075)

2024-07-11T19:35:22+00:00

This is a part of #97655.

[libc] fix aarch64 GCC build (#97932)

2024-07-07T19:12:47+00:00

This PR fix several build errors on aarch64 targets when building with
gcc:
- uninitialized values leading to `Werrors`
- undefined builtin functions
- glibc header pollution

[libc] [search] improve hsearch robustness (#73896)

2023-12-05T17:06:48+00:00

Following up the discussion at
https://github.com/llvm/llvm-project/pull/73469#discussion_r1409593911
by @nickdesaulniers.

According to FreeBSD implementation
(https://android.googlesource.com/platform/bionic/+/refs/heads/main/libc/upstream-freebsd/lib/libc/stdlib/hcreate.c),
`hsearch` is able to handle the cases where the global table is not
properly initialized. To do this, FreeBSD actually allows hash table to
be dynamically resized. If the global table is uninitialized at the
first call, the table will be initialized with a minimal size; hence
subsequent insertion will be reasonable as the table grows
automatically.

This patch mimic such behaviors. More precisely, this patch introduces:

1. a full table iterator that scans each element in the table,
2. a resize routine that is automatically triggered whenever the load
factor is reached where it iterates the old table and insert the entries
into a new one,
3. more tests that cover the growth of the table.

[libc] [search] implement hcreate(_r)/hsearch(_r)/hdestroy(_r) (#73469)

2023-11-29T02:02:25+00:00

This patch implements `hcreate(_r)/hsearch(_r)/hdestroy(_r)` as
specified in https://man7.org/linux/man-pages/man3/hsearch.3.html.

Notice that `neon/asimd` extension is not yet added in this patch. 

- The implementation is largely simplified from rust's
[`hashbrown`](https://github.com/rust-lang/hashbrown/blob/master/src/raw/mod.rs)
as we only consider fix-sized insertion-only hashtables. Technical
details are provided in code comments.

- This patch also contains a portable string hash function, which is
derived from [`aHash`](https://github.com/tkaitchuck/aHash)'s fallback
routine. Not using any SIMD acceleration, it has a good enough quality
(passing all SMHasher tests) and is not too bad in speed.

- Some general functionalities are added, such as `memory_size`,
`offset_to`(alignment), `next_power_of_two`, `is_power_of_two`.
`ctz/clz` are extended to support shorter integers.