From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH 09/17] rbtree: adjust node color in __rb_erase_color() only when necessary Date: Thu, 1 Jun 2017 02:17:00 +0530 Message-ID: <20170531204708.10470-10-kpraveen.lkml@gmail.com> References: <20170531204708.10470-1-kpraveen.lkml@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: In-Reply-To: <20170531204708.10470-1-kpraveen.lkml@gmail.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" To: xen-devel@lists.xen.org Cc: Andrea Arcangeli , Jens Axboe , Rik van Riel , sstabellini@kernel.org, wei.liu2@citrix.com, Peter Zijlstra , George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, Adrian Hunter , tim@xen.org, Daniel Santos , Praveen Kumar , "Eric W. Biederman" , jbeulich@suse.com, Alexander Shishkin , Andrew Morton , Michel Lespinasse , Linus Torvalds List-Id: xen-devel@lists.xenproject.org SW4gX19yYl9lcmFzZV9jb2xvcigpLCB3ZSB3ZXJlIGFsd2F5cyBzZXR0aW5nIGEgbm9kZSB0byBi bGFjayBhZnRlcgpleGl0aW5nIHRoZSBtYWluIGxvb3AuICBBbmQgaW4gb25lIGNhc2UsIGFmdGVy IGZpeGluZyB1cCB0aGUgdHJlZSB0bwpzYXRpc2Z5IGFsbCByYnRyZWUgaW52YXJpYW50cywgd2Ug d2VyZSBzZXR0aW5nIHRoZSBjdXJyZW50IG5vZGUgdG8gcm9vdApqdXN0IHRvIGd1YXJhbnRlZSBh IGxvb3AgZXhpdCwgYXQgd2hpY2ggcG9pbnQgdGhlIHJvb3Qgd291bGQgYmUgc2V0IHRvCmJsYWNr LiAgSG93ZXZlciB0aGlzIGlzIG5vdCBuZWNlc3NhcnksIGFzIHRoZSByb290IG9mIGFuIHJidHJl ZSBpcyBhbHJlYWR5Cmtub3duIHRvIGJlIGJsYWNrLiAgVGhlIG9ubHkgY2FzZSB3aGVyZSB0aGUg Y29sb3IgZmxpcCBpcyByZXF1aXJlZCBpcyB3aGVuCndlIGV4aXQgdGhlIGxvb3AgZHVlIHRvIHRo ZSBjdXJyZW50IG5vZGUgYmVpbmcgcmVkLCBhbmQgaXQncyBlYXNpZXN0IHRvCmp1c3QgZG8gdGhl IGZsaXAgYXQgdGhhdCBwb2ludCBpbnN0ZWFkIG9mIGRvaW5nIGl0IGFmdGVyIHRoZSBsb29wLgoK Y29tbWl0IGQ2ZmYxMjczOTI4ZWJmMTU0NjZhODViN2UxODEwY2QwMGU3Mjk5OGIgZnJvbSBsaW51 eCB0cmVlCgpbYWRyaWFuLmh1bnRlckBpbnRlbC5jb206IHBlcmYgdG9vbHM6IGZpeCBidWlsZCBm b3IgYW5vdGhlciByYnRyZWUuYyBjaGFuZ2VdClNpZ25lZC1vZmYtYnk6IE1pY2hlbCBMZXNwaW5h c3NlIDx3YWxrZW5AZ29vZ2xlLmNvbT4KQ2M6IEFuZHJlYSBBcmNhbmdlbGkgPGFhcmNhbmdlQHJl ZGhhdC5jb20+CkFja2VkLWJ5OiBEYXZpZCBXb29kaG91c2UgPERhdmlkLldvb2Rob3VzZUBpbnRl bC5jb20+CkNjOiBSaWsgdmFuIFJpZWwgPHJpZWxAcmVkaGF0LmNvbT4KQ2M6IFBldGVyIFppamxz dHJhIDxhLnAuemlqbHN0cmFAY2hlbGxvLm5sPgpDYzogRGFuaWVsIFNhbnRvcyA8ZGFuaWVsLnNh bnRvc0Bwb2JveC5jb20+CkNjOiBKZW5zIEF4Ym9lIDxheGJvZUBrZXJuZWwuZGs+CkNjOiAiRXJp YyBXLiBCaWVkZXJtYW4iIDxlYmllZGVybUB4bWlzc2lvbi5jb20+ClNpZ25lZC1vZmYtYnk6IEFk cmlhbiBIdW50ZXIgPGFkcmlhbi5odW50ZXJAaW50ZWwuY29tPgpDYzogQWxleGFuZGVyIFNoaXNo a2luIDxhbGV4YW5kZXIuc2hpc2hraW5AaW50ZWwuY29tPgpTaWduZWQtb2ZmLWJ5OiBBbmRyZXcg TW9ydG9uIDxha3BtQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpTaWduZWQtb2ZmLWJ5OiBMaW51cyBU b3J2YWxkcyA8dG9ydmFsZHNAbGludXgtZm91bmRhdGlvbi5vcmc+Ci0tLQogeGVuL2NvbW1vbi9y YnRyZWUuYyB8IDIyICsrKysrKysrKysrKysrKystLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCAxNiBp bnNlcnRpb25zKCspLCA2IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3hlbi9jb21tb24vcmJ0 cmVlLmMgYi94ZW4vY29tbW9uL3JidHJlZS5jCmluZGV4IDhkYjdhNWI0Y2EuLjczNmUyYTU1YWEg MTAwNjQ0Ci0tLSBhL3hlbi9jb21tb24vcmJ0cmVlLmMKKysrIGIveGVuL2NvbW1vbi9yYnRyZWUu YwpAQCAtMjYyLDEwICsyNjIsMjQgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1 Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKIHsKICAgICBzdHJ1Y3Qg cmJfbm9kZSAqb3RoZXI7CiAKLSAgICB3aGlsZSAoKCFub2RlIHx8IHJiX2lzX2JsYWNrKG5vZGUp KSAmJiBub2RlICE9IHJvb3QtPnJiX25vZGUpCisgICAgd2hpbGUgKHRydWUpCiAgICAgewotICAg ICAgICBpZiAocGFyZW50LT5yYl9sZWZ0ID09IG5vZGUpCisgICAgICAgIC8qCisgICAgICAgICAq IExvb3AgaW52YXJpYW50OiBhbGwgbGVhZiBwYXRocyBnb2luZyB0aHJvdWdoIG5vZGUgaGF2ZSBh CisgICAgICAgICAqIGJsYWNrIG5vZGUgY291bnQgdGhhdCBpcyAxIGxvd2VyIHRoYW4gb3RoZXIg bGVhZiBwYXRocy4KKyAgICAgICAgICoKKyAgICAgICAgICogSWYgbm9kZSBpcyByZWQsIHdlIGNh biBmbGlwIGl0IHRvIGJsYWNrIHRvIGFkanVzdC4KKyAgICAgICAgICogSWYgbm9kZSBpcyB0aGUg cm9vdCwgYWxsIGxlYWYgcGF0aHMgZ28gdGhyb3VnaCBpdC4KKyAgICAgICAgICogT3RoZXJ3aXNl LCB3ZSBuZWVkIHRvIGFkanVzdCB0aGUgdHJlZSB0aHJvdWdoIGNvbG9yIGZsaXBzCisgICAgICAg ICAqIGFuZCB0cmVlIHJvdGF0aW9ucyBhcyBwZXIgb25lIG9mIHRoZSA0IGNhc2VzIGJlbG93Lgor ICAgICAgICAgKi8KKyAgICAgICAgaWYgKG5vZGUgJiYgcmJfaXNfcmVkKG5vZGUpKQogICAgICAg ICB7CisgICAgICAgICAgICByYl9zZXRfYmxhY2sobm9kZSk7CisgICAgICAgICAgICBicmVhazsK KyAgICAgICAgfSBlbHNlIGlmICghcGFyZW50KSB7CisgICAgICAgICAgICBicmVhazsKKyAgICAg ICAgfSBlbHNlIGlmIChwYXJlbnQtPnJiX2xlZnQgPT0gbm9kZSkgewogICAgICAgICAgICAgb3Ro ZXIgPSBwYXJlbnQtPnJiX3JpZ2h0OwogICAgICAgICAgICAgaWYgKHJiX2lzX3JlZChvdGhlcikp CiAgICAgICAgICAgICB7CkBAIC0yOTcsNyArMzExLDYgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFz ZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKICAg ICAgICAgICAgICAgICBpZiAob3RoZXItPnJiX3JpZ2h0KQogICAgICAgICAgICAgICAgICAgICBy Yl9zZXRfYmxhY2sob3RoZXItPnJiX3JpZ2h0KTsKICAgICAgICAgICAgICAgICBfX3JiX3JvdGF0 ZV9sZWZ0KHBhcmVudCwgcm9vdCk7Ci0gICAgICAgICAgICAgICAgbm9kZSA9IHJvb3QtPnJiX25v ZGU7CiAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICB9CiAgICAgICAgIH0KQEAg LTMzNCwxMyArMzQ3LDEwIEBAIHN0YXRpYyB2b2lkIF9fcmJfZXJhc2VfY29sb3Ioc3RydWN0IHJi X25vZGUgKm5vZGUsIHN0cnVjdCByYl9ub2RlICpwYXJlbnQsCiAgICAgICAgICAgICAgICAgaWYg KG90aGVyLT5yYl9sZWZ0KQogICAgICAgICAgICAgICAgICAgICByYl9zZXRfYmxhY2sob3RoZXIt PnJiX2xlZnQpOwogICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX3JpZ2h0KHBhcmVudCwgcm9v dCk7Ci0gICAgICAgICAgICAgICAgbm9kZSA9IHJvb3QtPnJiX25vZGU7CiAgICAgICAgICAgICAg ICAgYnJlYWs7CiAgICAgICAgICAgICB9CiAgICAgICAgIH0KICAgICB9Ci0gICAgaWYgKG5vZGUp Ci0gICAgICAgIHJiX3NldF9ibGFjayhub2RlKTsKIH0KIAogdm9pZCByYl9lcmFzZShzdHJ1Y3Qg cmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCi0tIAoyLjEyLjAKCgpfX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwpYZW4tZGV2ZWwgbWFpbGlu ZyBsaXN0Clhlbi1kZXZlbEBsaXN0cy54ZW4ub3JnCmh0dHBzOi8vbGlzdHMueGVuLm9yZy94ZW4t ZGV2ZWwK