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

Sasha Levin
2011-05-30T06:07:41Z

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.

--

Sasha.