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. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
