casaroli opened a new pull request, #20932: URL: https://github.com/apache/nuttx/pull/20932
## Summary POSIX (XSI) `<search.h>` specifies binary search trees: `tsearch()`, `tfind()`, `tdelete()` and `twalk()`. NuttX has only the hash table functions. This PR adds them to `libs/libc/search` as an AVL tree, plus `tdestroy()`, the GNU extension that frees a tree: - The first member of a node is the key pointer, as POSIX requires. - The height stays below 1.44 log2(n + 2) for any order of keys. - `tdelete()` replaces a node with two children by its in-order predecessor node, so the other nodes do not move and pointers to them stay valid. It returns the parent of the removed node (`rootp` if the root was removed). - Insertion and deletion use a fixed path array (48 entries on 32-bit, 96 on 64-bit), no recursion; `twalk()` and `tdestroy()` recurse to the tree height. - `<search.h>` gets the `VISIT` type and the prototypes; `libc.csv` gets the entries. ## Impact New functions in libc. `<search.h>` now also has the POSIX names `VISIT`, `preorder`, `postorder`, `endorder` and `leaf`; no code in nuttx or nuttx-apps that includes `<search.h>` uses them. All build modes and architectures. Documentation (separate commit): the POSIX table marks the four functions as supported, and the libc search page describes the tree functions. ## Testing Test program `tsearchtest.c`: 2000 keys in random order; `tsearch()` returns the node and finds an existing key; `tfind()` of every key and of missing keys; `twalk()` visits all keys in order and the depth stays within the AVL bound (12 for 2000 keys); two thirds of the keys are deleted in random order (twice each); the other keys keep their node addresses; `tdestroy()` frees each key once. | | master | this PR | |---|---|---| | `tsearchtest.c` on `qemu-armv8a:knsh` (QEMU with HVF) | does not compile: `unknown type name 'VISIT'`, implicit declaration of `tsearch` | PASS (largest depth 12) | | ostest, `qemu-armv8a:knsh` and `qemu-armv8a:nsh` | status 0 | status 0 | Build, each OK: `qemu-armv8a:nsh` (flat, arm64), `qemu-armv8a:knsh` (kernel, arm64), `rv-virt:knsh64` (kernel, rv64), `rv-virt:pnsh64` (protected, rv64), `lm3s6965-ek:qemu-protected` (protected, armv7-m), and `qemu-armv8a:nsh` with CMake. No new warnings. `tools/checkpatch.sh -c -u -m -g` passes. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
