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

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

* 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.

Given we have to update the parent nodes when the interval values
change, we need to work on a copy of these parent nodes to ensure that
their information about the children min/max corresponds to the
children's left/right pointers they contain. Any discrepancy between
their left/right pointers and the children min/max value they store
would be invalid from a reader's POV.

I'll see if I can embed this in my tree. It should be doable with the
"decay" approach I am using. We'll need a way to test this though:
possibly by walking the tree with range-aware lookups that also make
sure that the ranges that were promised by the upper nodes are contained
within their children at all times.

Thanks,

Mathieu


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