Feature Request: Add Binary Search Tree (BST) Support to Heapless #608
Description
Problem
The heapless crate currently lacks a Binary Search Tree (BST) implementation. BSTs are essential for use cases like implementing process schedulers with priorities in kernel environments, where efficient ordered data structures are critical without relying on heap allocation.
Context
I discovered an existing scapegoat tree implementation at https://github.com/tnballo/scapegoat, which has been available for some time. However, it isn't tailored to my specific needs for kernel scheduling. As a result, I forked it to create https://github.com/stevefan1999-personal/escapegoat, adapting it for my use case.
Proposal
I suggest that heapless incorporate a BST data structure, potentially drawing inspiration from the scapegoat tree implementation. This could include:
- A heapless BST variant optimized for embedded and no-std environments.
- Balancing mechanisms to maintain efficiency, similar to scapegoat trees.
Benefits
- Enables efficient priority scheduling in kernels without heap dependencies.
- Expands
heapless's utility for real-time and embedded systems. - Leverages existing open-source work to accelerate development.
Additional Notes
The forked repo (https://github.com/stevefan1999-personal/escapegoat) demonstrates a proof-of-concept adaptation.
In particular, I have to remove the use of floating point due to the lack of FPU, or the missing guarantee for it, so instead I have to use fixed point arithmetic to do alpha/rebalancing factor calculation. Sadly, I also needed to calculate logarithm outlined in the paper, so I had to use bisection to find the binary power and approximate the logarithm, which makes it not O(1). Still, it works pretty well and fast in general, but I guess we could further eliminate the fixed crate by reinterpreting the algorithm to see if we can avoid the use of fractions at all.
Compatibility with heapless's existing APIs and no-std guarantees would be ideal.
Would the maintainers consider this addition? I'm happy to contribute or provide more details.