From mboxrd@z Thu Jan 1 00:00:00 1970 From: Dario Faggioli Subject: Re: [PATCH v2 08/20] rbtree: break out of rb_insert_color loop after tree rotation Date: Mon, 19 Jun 2017 19:10:58 +0200 Message-ID: <1497892258.7405.15.camel@citrix.com> References: <20170617093253.3990-1-kpraveen.lkml@gmail.com> <20170617093253.3990-9-kpraveen.lkml@gmail.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="===============8426226299769838579==" Return-path: In-Reply-To: <20170617093253.3990-9-kpraveen.lkml@gmail.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" To: Praveen Kumar , xen-devel@lists.xen.org Cc: sstabellini@kernel.org, wei.liu2@citrix.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, jbeulich@suse.com List-Id: xen-devel@lists.xenproject.org --===============8426226299769838579== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="=-0vgLktaVqL+EE3t+rSGh" --=-0vgLktaVqL+EE3t+rSGh Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Sat, 2017-06-17 at 15:02 +0530, Praveen Kumar wrote: > It is a well known property of rbtrees that insertion never requires > more > than two tree rotations.=C2=A0=C2=A0In our implementation, after one loop > iteration > identified one or two necessary tree rotations, we would iterate and > look > for more.=C2=A0=C2=A0However at that point the node's parent would always= be > black, > which would cause us to exit the loop. >=20 > We can make the code flow more obvious by just adding a break > statement > after the tree rotations, where we know we are done.=C2=A0=C2=A0Additiona= lly, > in the > cases where two tree rotations are necessary, we don't have to update > the > 'node' pointer as it wouldn't be used until the next loop iteration, > which > we now avoid due to this break statement. >=20 > Signed-off-by: Michel Lespinasse > Cc: Andrea Arcangeli > Acked-by: David Woodhouse > Cc: Rik van Riel > Cc: Peter Zijlstra > Cc: Daniel Santos > Cc: Jens Axboe > Cc: "Eric W. Biederman" > Signed-off-by: Andrew Morton > Signed-off-by: Linus Torvalds > [Linux commit 1f0528653e41ec230c60f5738820e8a544731399] >=20 > Ported to Xen. >=20 > Signed-off-by: Praveen Kumar > Now the patch has all the hunks. There's again some difference in '{' placement, though, between this patch and the Linux commit. More specifically, in the Linux commit, this: > --- a/xen/common/rbtree.c > +++ b/xen/common/rbtree.c > @@ -110,16 +110,14 @@ void rb_insert_color(struct rb_node *node, > struct rb_root *root) > =C2=A0 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0if (parent->rb_right =3D=3D node) > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0{ > Becomes: if (parent->rb_right =3D=3D node) { I appreciate that you may not be applying this specific modification because the Xen style is different. But I actually think you should, as this file is going to end up being mixed style anyway, so I'd prioritize staying identical to Linux's commit. Regards, Dario --=20 <> (Raistlin Majere) ----------------------------------------------------------------- Dario Faggioli, Ph.D, http://about.me/dario.faggioli Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK) --=-0vgLktaVqL+EE3t+rSGh Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAABCAAGBQJZSAWiAAoJEBZCeImluHPuHMwP/3ws+fzncHhWdLTQSg3Lu9ne D4SX3GP7CQLD2/OzAE1dCqE+eUKEwIIQDnYLA4D2pgyoIhAnb3LTl+pI2+1zdAB+ GhlJcPUVu66FBuQ/qCHVuWWa8n+8YsCMrOcdwLblM3iI7CXKLOWSPhaahg7acmxz LsZzlX6YsPMp4nT6A+RDsDdG9OOul3qPsMo6Oj3dxYg6yIFZpBPO6eLC5KPZFr9s Wu3v/+/S2aXiYbNuYSNdqw6Vy+3mzEPSCTTcQQnS9A7fGVwd9Pxpu+aOK51z3zrx 77D199VbsjPL0VLjneZfrLlcYlBvG0uPcxzAxBAFdDxlgjivP2q5Mkr1vzWFc7R7 7Pr6zAHWJzRTezTIaGsqrzH38zbZdRbi8hlT9Sid4LLAV8bUd8IY6nTIKzGIvGTf FDZJTIqGluYxdLE4AOAHSIgqQdtSnX7PobNxMZOkE1cT01R1O6p9+8T9WTFa/ko1 GbgLVyUJm9RvXdCdZyN+pd6DbptrxJD9nt1kQXVyQCrk8B98JcFQJpc7Z+K8S97H LIPZ3qk1Oxt0yqjtMetIxp3V7d10daF0AA+pCm6HKjW7jRgKu7wVNsQjMHKhhmmG CI/7n3OLul4y5qxKrfIT//R4bJ/W0Dw7VWPx0zVMuJ3iZKI/1smbx3sIcVEblT/v 67vJBhvxy+bCEtekEGNS =4ny6 -----END PGP SIGNATURE----- --=-0vgLktaVqL+EE3t+rSGh-- --===============8426226299769838579== Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: base64 Content-Disposition: inline X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KWGVuLWRldmVs IG1haWxpbmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9yZwpodHRwczovL2xpc3RzLnhlbi5v cmcveGVuLWRldmVsCg== --===============8426226299769838579==--