* Sasha Levin (levinsasha928@xxxxxxxxx) wrote: > On Mon, 2011-05-30 at 13:38 -0400, Mathieu Desnoyers 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 ? > > It's just an implementation of an interval search() function. Since > kernel rbtree users implement their own search() and insert() functions > (look in our util/rbtree-interval.c) it shouldn't be a consideration in > designing the tree - we (the users of urcu/rbtree) want to control the > search code anyway. The reason why I provide this facility as part of the RCU rbtree is because, unlike the kernel rbtree where every user is free to use "inheritance" to put their object in the same cache-line as the rbtree node, the RCU implementation needs to do copies of its inner nodes, so the rbtree user cannot expect the node pointer to stay valid. Therefore, I use a more usual scheme where the pointer to the user-provided data structure is kept as a "void *key" in the node. So basically, the rbtree user don't have to provide the search, next and prev functions: this is all done within the rbtree code, especially because these have to be RCU-aware, and because the code that augments the rbtree with ranges needs to be RCU-aware too. Finally, my tests showed up that the "<= and >=" need to have the equal for the ranges to be inclusive. I tested this by using the same test-case as the search, duplicating the key value as both lower and upper bound of the range searched for. (see updated rbtree2 branch for tested range search). My stress-test now tests the range lookups, and it passes fine so far: e.g. test_urcu_rbtree 6 2 200 -g 40 (on a 8-core machine) 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
