Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

[Boqun Feng]

On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@xxxxxxxxx> wrote:
> >
> > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@xxxxxxxxxx> wrote:
> > > > This is a port of the Binder data structure introduced in commit
> > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > Rust.
> > >
> > > Stupid high-level side comment:
> > >
> > > That commit looks like it changed a simple linear rbtree scan (which
> > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > scan to an O(log n) rbtree lookup, just like how finding a free area
> >
> > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> 
> We need the smallest ID without a value, not the smallest ID in use.
> 

Ok, but it shouldn't be hard to write a Rust function that search that,
right? My point was mostly the Rust rbtree binding can do O(log n)
search. I have no idea about "even so, should we try something like Jann
suggested". And I think your other reply basically says no.

Regards,
Boqun

> Alice