From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [Resend][PATCH 12/17] rbtree: optimize fetching of sibling node Date: Thu, 1 Jun 2017 02:50:51 +0530 Message-ID: <20170531212056.10583-13-kpraveen.lkml@gmail.com> References: <20170531212056.10583-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: <20170531212056.10583-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: sstabellini@kernel.org, wei.liu2@citrix.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, Praveen Kumar , jbeulich@suse.com List-Id: xen-devel@lists.xenproject.org V2hlbiBsb29raW5nIHRvIGZldGNoIGEgbm9kZSdzIHNpYmxpbmcsIHdlIHdlbnQgdGhyb3VnaCBh IHNlcXVlbmNlIG9mOgotIGNoZWNrIGlmIG5vZGUgaXMgdGhlIHBhcmVudCdzIGxlZnQgY2hpbGQK LSBpZiBpdCBpcywgdGhlbiBmZXRjaCB0aGUgcGFyZW50J3MgcmlnaHQgY2hpbGQKClRoaXMgY2Fu IGJlIHJlcGxhY2VkIHdpdGg6Ci0gZmV0Y2ggdGhlIHBhcmVudCdzIHJpZ2h0IGNoaWxkIGFzIGFu IGFzc3VtZWQgc2libGluZwotIGNoZWNrIHRoYXQgbm9kZSBpcyBOT1QgdGhlIGZldGNoZWQgY2hp bGQKClRoaXMgYXZvaWRzIGZldGNoaW5nIHRoZSBwYXJlbnQncyBsZWZ0IGNoaWxkIHdoZW4gbm9k ZSBpcyBhY3R1YWxseQp0aGF0IGNoaWxkLiBTYXZlcyBhIGJpdCBvbiBjb2RlIHNpemUsIHRob3Vn aCBpdCBkb2Vzbid0IHNlZW0gdG8gbWFrZQphIGxhcmdlIGRpZmZlcmVuY2UgaW4gc3BlZWQuCgpj b21taXQgNTk2MzNhYmYzNGUyZjQ0YjhlNzcyYTJjMTJhOTIxMzJhYTdjMjIyMCBmcm9tIExpbnV4 IHRyZWUKClNpZ25lZC1vZmYtYnk6IFByYXZlZW4gS3VtYXIgPGtwcmF2ZWVuLmxrbWxAZ21haWwu Y29tPgotLS0KIHhlbi9jb21tb24vcmJ0cmVlLmMgfCAyMSArKysrKysrKysrKysrLS0tLS0tLS0K IDEgZmlsZSBjaGFuZ2VkLCAxMyBpbnNlcnRpb25zKCspLCA4IGRlbGV0aW9ucygtKQoKZGlmZiAt LWdpdCBhL3hlbi9jb21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9uL3JidHJlZS5jCmluZGV4IDI1 Mzg2MWQ4ODkuLmI2NWYwMGNhMWYgMTAwNjQ0Ci0tLSBhL3hlbi9jb21tb24vcmJ0cmVlLmMKKysr IGIveGVuL2NvbW1vbi9yYnRyZWUuYwpAQCAtMTA4LDkgKzEwOCw5IEBAIHZvaWQgcmJfaW5zZXJ0 X2NvbG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIAogICAg ICAgICBncGFyZW50ID0gcmJfcmVkX3BhcmVudChwYXJlbnQpOwogCi0gICAgICAgIGlmIChwYXJl bnQgPT0gZ3BhcmVudC0+cmJfbGVmdCkKKyAgICAgICAgdG1wID0gZ3BhcmVudC0+cmJfcmlnaHQ7 CisgICAgICAgIGlmIChwYXJlbnQgIT0gdG1wKSAgICAvKiBwYXJlbnQgPT0gZ3BhcmVudC0+cmJf bGVmdCAqLwogICAgICAgICB7Ci0gICAgICAgICAgICB0bXAgPSBncGFyZW50LT5yYl9yaWdodDsK ICAgICAgICAgICAgIGlmICh0bXAgJiYgcmJfaXNfcmVkKHRtcCkpCiAgICAgICAgICAgICB7CiAg ICAgICAgICAgICAgICAgLyoKQEAgLTEzNCw3ICsxMzQsOCBAQCB2b2lkIHJiX2luc2VydF9jb2xv cihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiAgICAgICAgICAg ICAgICAgY29udGludWU7CiAgICAgICAgICAgICB9CiAKLSAgICAgICAgICAgIGlmIChwYXJlbnQt PnJiX3JpZ2h0ID09IG5vZGUpCisgICAgICAgICAgICB0bXAgPSBwYXJlbnQtPnJiX3JpZ2h0Owor ICAgICAgICAgICAgaWYgKG5vZGUgPT0gdG1wKQogICAgICAgICAgICAgewogICAgICAgICAgICAg ICAgIC8qCiAgICAgICAgICAgICAgICAgICogQ2FzZSAyIC0gbGVmdCByb3RhdGUgYXQgcGFyZW50 CkBAIC0xNjQsNyArMTY1LDcgQEAgdm9pZCByYl9pbnNlcnRfY29sb3Ioc3RydWN0IHJiX25vZGUg Km5vZGUsIHN0cnVjdCByYl9yb290ICpyb290KQogICAgICAgICAgICAgICogICAgIC8gICAgICAg ICAgICAgICAgIFwKICAgICAgICAgICAgICAqICAgIG4gICAgICAgICAgICAgICAgICAgVQogICAg ICAgICAgICAgICovCi0gICAgICAgICAgICBncGFyZW50LT5yYl9sZWZ0ID0gdG1wID0gcGFyZW50 LT5yYl9yaWdodDsKKyAgICAgICAgICAgIGdwYXJlbnQtPnJiX2xlZnQgPSB0bXA7ICAgIC8qID09 IHBhcmVudC0+cmJfcmlnaHQgKi8KICAgICAgICAgICAgIHBhcmVudC0+cmJfcmlnaHQgPSBncGFy ZW50OwogICAgICAgICAgICAgaWYgKHRtcCkKICAgICAgICAgICAgICAgICByYl9zZXRfcGFyZW50 X2NvbG9yKHRtcCwgZ3BhcmVudCwgUkJfQkxBQ0spOwpAQCAtMTgzLDcgKzE4NCw4IEBAIHZvaWQg cmJfaW5zZXJ0X2NvbG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9v dCkKICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgIH0KIAotICAgICAgICAg ICAgaWYgKHBhcmVudC0+cmJfbGVmdCA9PSBub2RlKQorICAgICAgICAgICAgdG1wID0gcGFyZW50 LT5yYl9sZWZ0OworICAgICAgICAgICAgaWYgKG5vZGUgPT0gdG1wKQogICAgICAgICAgICAgewog ICAgICAgICAgICAgICAgIC8qIENhc2UgMiAtIHJpZ2h0IHJvdGF0ZSBhdCBwYXJlbnQgKi8KICAg ICAgICAgICAgICAgICBwYXJlbnQtPnJiX2xlZnQgPSB0bXAgPSBub2RlLT5yYl9yaWdodDsKQEAg LTE5MiwxMCArMTk0LDExIEBAIHZvaWQgcmJfaW5zZXJ0X2NvbG9yKHN0cnVjdCByYl9ub2RlICpu b2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X3Bh cmVudF9jb2xvcih0bXAsIHBhcmVudCwgUkJfQkxBQ0spOwogICAgICAgICAgICAgICAgIHJiX3Nl dF9wYXJlbnRfY29sb3IocGFyZW50LCBub2RlLCBSQl9SRUQpOwogICAgICAgICAgICAgICAgIHBh cmVudCA9IG5vZGU7CisgICAgICAgICAgICAgICAgdG1wID0gbm9kZS0+cmJfbGVmdDsKICAgICAg ICAgICAgIH0KIAogICAgICAgICAgICAgLyogQ2FzZSAzIC0gbGVmdCByb3RhdGUgYXQgZ3BhcmVu dCAqLwotICAgICAgICAgICAgZ3BhcmVudC0+cmJfcmlnaHQgPSB0bXAgPSBwYXJlbnQtPnJiX2xl ZnQ7CisgICAgICAgICAgICBncGFyZW50LT5yYl9yaWdodCA9IHRtcDsgICAgLyogPT0gcGFyZW50 LT5yYl9sZWZ0ICovCiAgICAgICAgICAgICBwYXJlbnQtPnJiX2xlZnQgPSBncGFyZW50OwogICAg ICAgICAgICAgaWYgKHRtcCkKICAgICAgICAgICAgICAgICByYl9zZXRfcGFyZW50X2NvbG9yKHRt cCwgZ3BhcmVudCwgUkJfQkxBQ0spOwpAQCAtMjI4LDggKzIzMSwxMCBAQCBzdGF0aWMgdm9pZCBf X3JiX2VyYXNlX2NvbG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfbm9kZSAqcGFy ZW50LAogICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIH0gZWxzZSBpZiAoIXBhcmVudCkgewog ICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgIH0gZWxzZSBpZiAocGFyZW50LT5yYl9sZWZ0ID09 IG5vZGUpIHsKLSAgICAgICAgICAgIHNpYmxpbmcgPSBwYXJlbnQtPnJiX3JpZ2h0OworICAgICAg ICB9CisgICAgICAgIHNpYmxpbmcgPSBwYXJlbnQtPnJiX3JpZ2h0OworICAgICAgICBpZiAoIG5v ZGUgIT0gc2libGluZykgICAgLyogbm9kZSA9PSBwYXJlbnQtPnJiX2xlZnQgKi8KKyAgICAgICAg ewogICAgICAgICAgICAgaWYgKHJiX2lzX3JlZChzaWJsaW5nKSkgewogICAgICAgICAgICAgICAg IC8qCiAgICAgICAgICAgICAgICAgICogQ2FzZSAxIC0gbGVmdCByb3RhdGUgYXQgcGFyZW50Ci0t IAoyLjEyLjAKCgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f XwpYZW4tZGV2ZWwgbWFpbGluZyBsaXN0Clhlbi1kZXZlbEBsaXN0cy54ZW4ub3JnCmh0dHBzOi8v bGlzdHMueGVuLm9yZy94ZW4tZGV2ZWwK