On Tue, 2010-06-01 at 19:19 +0200, Peter Zijlstra wrote: > On Tue, 2010-06-01 at 10:00 -0700, Venkatesh Pallipadi wrote: > > I am not seeing how this can cover all the callbacks we will need to > > maintain the augmented tree property. May be I am missing something. > > Yes, indeed, how about the below delta, which my eevdf code did do but I > overlooked on the conversion to the PAT code. > > That removes the break as you said, but also adds code to update the > child nodes when walking up the path. > > So in your rotation case: > > G P > / \ --> / \ > P U N G > / <-- \ > N U > > Say we take the right rotation, then the traversal up from N to P will > find that since N was the left child of P and it has a right child (G) > it will also update G. Hmm, that looks like it could well be folded in to the generic code.. let me spin a new patch. -- To unsubscribe from this list: send the line "unsubscribe linux-tip-commits" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
|