Re: RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock wrapper)

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* Mathieu Desnoyers (mathieu.desnoyers@efficios.com) wrote:
> * Sasha Levin (levinsasha928@gmail.com) wrote:
> > On Sun, 2011-05-29 at 22:54 -0400, Mathieu Desnoyers wrote:
> > > Please note that what I currently have is a normal rbtree, not an
> > > interval rbtree. Can you elaborate on your use-case so I can try to
> > > figure out how we could augment it to support the interval rbtree you
> > > need ?
> > 
> > We don't need anything specific for interval rbtree. The rbtree used in
> > the kernel provides augmentation functions for insert and erase (see
> > rb_augment_insert() and rb_augment_erase_begin() +
> > rb_augment_erase_end()).
> > What they basically do is call a user-provided callback for each node
> > from the newly inserted (or deepest after deletion) node up to the root
> > of the tree. You can see our code at 'tools/kvm/util/rbtree-interval.c',
> > basically all we need are the 2 augmentation functions I've mentioned
> > above.
> 
> Just a little question about Documentation/rbtree.txt:
> 
> I see that find_lowest_match(lo, hi, node) seems to use ">" and "<" to
> compare the lo value with the max_hi and node->lo. I think it would be
> more natural to do range comparison functions with inclusive ranges (>=
> and <=). Or maybe I am missing something about the way find_lowest_match
> works ?

Sorry for self-reply, I actually got my head around this detail: these
tests are excluding ranges. So to get the range with inclusive values,
we must take the negation of the opposite (which is a range without the
limit values).

The code for augmented RBtree search by range is now in the rbtree2
branch. I still need to find a good way to test the range search
functions though.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com