Messages in this thread | | | Subject | Re: [PATCH] rbtree: undo augmented damage -v2 | From | Peter Zijlstra <> | Date | Tue, 01 Jun 2010 19:34:10 +0200 |
| |
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.
| |