rbtree: undo augmented damage -v2
in [Kernel]
|
Prev: sched: adjust when cpu_active and cpuset configurations are updated during cpu on/offlining
Next: [PATCH][1/1] fs: wrong type for 'magic' argument in 'simple_fill_super()', fs/libfs.c
From: Venkatesh Pallipadi on 1 Jun 2010 14:10 On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: >> >> Yes. This will cover all the cases on insert. But on erase, there is >> still a case where a rotate of sibling node is done during the >> re-coloration process. There we have a child change on sibling's >> child. I am not able to think of any easy way to handle that case. > > Let me go draw some figures with pen and paper to match up the erase > path with the rb_augment_erase_begin() code, because I can't quite spot > the case we're missing. > > If you have it handy, ascii art might help.. It is this case P / \ N S / \ SL SR changing to P / \ N SL \ S \ SR This can happen in __rb_erase_color, where 'other' points to sibling node. Thanks, Venki -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on 1 Jun 2010 14:50 On Tue, 2010-06-01 at 11:09 -0700, Venkatesh Pallipadi wrote: > On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: > > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: > >> > >> Yes. This will cover all the cases on insert. But on erase, there is > >> still a case where a rotate of sibling node is done during the > >> re-coloration process. There we have a child change on sibling's > >> child. I am not able to think of any easy way to handle that case. > > > > Let me go draw some figures with pen and paper to match up the erase > > path with the rb_augment_erase_begin() code, because I can't quite spot > > the case we're missing. > > > > If you have it handy, ascii art might help.. > > It is this case > > P > / \ > N S > / \ > SL SR > > changing to > > P > / \ > N SL > \ > S > \ > SR Right, but see: http://en.wikipedia.org/wiki/Red-black_tree That is delete_case5, however then we fall into delete_case6 and perform a left rotation. So suppose we start with the tree: P P P SL / \ / \ / \ / \ D S --> N S --> N SL --> P S \ / \ / \ \ / \ N SL SR SL* SR S* N SR \ SR and then remove D, delete case 5 and finally delete case 6, * marks red. rb_augment_erase_begin(D) will return N, and then rb_augment_path(N) will re-augment: N, P, SL and S. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Venkatesh Pallipadi on 1 Jun 2010 16:40 On Tue, Jun 1, 2010 at 11:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: > On Tue, 2010-06-01 at 11:09 -0700, Venkatesh Pallipadi wrote: >> On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: >> > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: >> >> >> >> Yes. This will cover all the cases on insert. But on erase, there is >> >> still a case where a rotate of sibling node is done during the >> >> re-coloration process. There we have a child change on sibling's >> >> child. I am not able to think of any easy way to handle that case. >> > >> > Let me go draw some figures with pen and paper to match up the erase >> > path with the rb_augment_erase_begin() code, because I can't quite spot >> > the case we're missing. >> > >> > If you have it handy, ascii art might help.. >> >> It is this case >> >> � � P >> � �/ \ >> � N � S >> � � �/ \ >> � � SL SR >> >> changing to >> >> � � P >> � �/ \ >> � N �SL >> � � � \ >> � � � �S >> � � � � \ >> � � � � SR > > Right, but see: http://en.wikipedia.org/wiki/Red-black_tree > That is delete_case5, however then we fall into delete_case6 and perform > a left rotation. > > So suppose we start with the tree: > > � �P � � � � � � � � �P � � � � � � � P � � � � � � � �SL > �/ � \ � � � � � � � / \ � � � � � � / \ � � � � � � � / \ > �D � � S � � �--> � �N �S � � �--> � N � SL � � --> � �P � S > �\ � / \ � � � � � � �/ \ � � � � � � � �\ � � � � � / � � \ > � N SL �SR � � � � �SL* SR � � � � � � � �S* � � � �N � � �SR > � � � � � � � � � � � � � � � � � � � � � �\ > � � � � � � � � � � � � � � � � � � � � � � SR > > and then remove D, delete case 5 and finally delete case 6, * marks red. > > rb_augment_erase_begin(D) will return N, and then rb_augment_path(N) > will re-augment: N, P, SL and S. > Yes. I had missed that rotate_right of parent following the rotate_left of sibling (or vice-versa). Thanks for fixing this. The latest patch looks good. Acked-by: Venkatesh Pallipadi <venki(a)google.com> -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Suresh Siddha on 2 Jun 2010 17:20 On Tue, 2010-06-01 at 11:42 -0700, Peter Zijlstra wrote: > On Tue, 2010-06-01 at 11:09 -0700, Venkatesh Pallipadi wrote: > > On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: > > > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: > > >> > > >> Yes. This will cover all the cases on insert. But on erase, there is > > >> still a case where a rotate of sibling node is done during the > > >> re-coloration process. There we have a child change on sibling's > > >> child. I am not able to think of any easy way to handle that case. > > > > > > Let me go draw some figures with pen and paper to match up the erase > > > path with the rb_augment_erase_begin() code, because I can't quite spot > > > the case we're missing. > > > > > > If you have it handy, ascii art might help.. > > > > It is this case > > > > P > > / \ > > N S > > / \ > > SL SR > > > > changing to > > > > P > > / \ > > N SL > > \ > > S > > \ > > SR > > Right, but see: http://en.wikipedia.org/wiki/Red-black_tree > That is delete_case5, however then we fall into delete_case6 and perform > a left rotation. > > So suppose we start with the tree: > > P P P SL > / \ / \ / \ / \ > D S --> N S --> N SL --> P S > \ / \ / \ \ / \ > N SL SR SL* SR S* N SR > \ > SR > > and then remove D, delete case 5 and finally delete case 6, * marks red. > > rb_augment_erase_begin(D) will return N, and then rb_augment_path(N) > will re-augment: N, P, SL and S. P SL / \ / \ N S ---> N S / / \ / \ C SL SR C SR If P needs to be removed, we need to re-augment S also in this case, right? It looks like we are not handling this case. thanks, suresh -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Venkatesh Pallipadi on 2 Jun 2010 21:20
On Wed, Jun 2, 2010 at 2:11 PM, Suresh Siddha <suresh.b.siddha(a)intel.com> wrote: > On Tue, 2010-06-01 at 11:42 -0700, Peter Zijlstra wrote: >> On Tue, 2010-06-01 at 11:09 -0700, Venkatesh Pallipadi wrote: >> > On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz(a)infradead.org> wrote: >> > > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: >> > >> >> > >> Yes. This will cover all the cases on insert. But on erase, there is >> > >> still a case where a rotate of sibling node is done during the >> > >> re-coloration process. There we have a child change on sibling's >> > >> child. I am not able to think of any easy way to handle that case. >> > > >> > > Let me go draw some figures with pen and paper to match up the erase >> > > path with the rb_augment_erase_begin() code, because I can't quite spot >> > > the case we're missing. >> > > >> > > If you have it handy, ascii art might help.. >> > >> > It is this case >> > >> > � � P >> > � �/ \ >> > � N � S >> > � � �/ \ >> > � � SL SR >> > >> > changing to >> > >> > � � P >> > � �/ \ >> > � N �SL >> > � � � \ >> > � � � �S >> > � � � � \ >> > � � � � SR >> >> Right, but see: http://en.wikipedia.org/wiki/Red-black_tree >> That is delete_case5, however then we fall into delete_case6 and perform >> a left rotation. >> >> So suppose we start with the tree: >> >> � � P � � � � � � � � �P � � � � � � � P � � � � � � � �SL >> � / � \ � � � � � � � / \ � � � � � � / \ � � � � � � � / \ >> �D � � S � � �--> � �N �S � � �--> � N � SL � � --> � �P � S >> � \ � / \ � � � � � � �/ \ � � � � � � � �\ � � � � � / � � \ >> � �N SL �SR � � � � �SL* SR � � � � � � � �S* � � � �N � � �SR >> � � � � � � � � � � � � � � � � � � � � � � \ >> � � � � � � � � � � � � � � � � � � � � � � �SR >> >> and then remove D, delete case 5 and finally delete case 6, * marks red. >> >> rb_augment_erase_begin(D) will return N, and then rb_augment_path(N) >> will re-augment: N, P, SL and S. > > > � � �P � � � � � � � � � � � SL > � �/ �\ � � � � � � � � � � / �\ > � N � �S � � � ---> � � � �N � �S > �/ � / �\ � � � � � � � � / � � �\ > �C � SL �SR � � � � � � � C � � � �SR > > If P needs to be removed, we need to re-augment S also in this case, > right? It looks like we are not handling this case. > rb_augment_erase_begin() should take care of that. In this case, it will return S as the deepest node and we start the walk-back-to-root from there. Thanks, Venki -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |