* Mathieu Desnoyers (mathieu.desnoyers@xxxxxxxxxxxx) wrote: > * Sasha Levin (levinsasha928@xxxxxxxxx) 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 -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
