From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v5 12/17] rbtree: optimize fetching of sibling node Date: Fri, 14 Jul 2017 13:56:31 +0530 Message-ID: <20170714082636.29511-13-kpraveen.lkml@gmail.com> References: <20170714082636.29511-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: <20170714082636.29511-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, kpraveen.lkml@gmail.com, jbeulich@suse.com List-Id: xen-devel@lists.xenproject.org RnJvbTogTWljaGVsIExlc3BpbmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgoKV2hlbiBsb29raW5n IHRvIGZldGNoIGEgbm9kZSdzIHNpYmxpbmcsIHdlIHdlbnQgdGhyb3VnaCBhIHNlcXVlbmNlIG9m OgotIGNoZWNrIGlmIG5vZGUgaXMgdGhlIHBhcmVudCdzIGxlZnQgY2hpbGQKLSBpZiBpdCBpcywg dGhlbiBmZXRjaCB0aGUgcGFyZW50J3MgcmlnaHQgY2hpbGQKClRoaXMgY2FuIGJlIHJlcGxhY2Vk IHdpdGg6Ci0gZmV0Y2ggdGhlIHBhcmVudCdzIHJpZ2h0IGNoaWxkIGFzIGFuIGFzc3VtZWQgc2li bGluZwotIGNoZWNrIHRoYXQgbm9kZSBpcyBOT1QgdGhlIGZldGNoZWQgY2hpbGQKClRoaXMgYXZv aWRzIGZldGNoaW5nIHRoZSBwYXJlbnQncyBsZWZ0IGNoaWxkIHdoZW4gbm9kZSBpcyBhY3R1YWxs eQp0aGF0IGNoaWxkLiBTYXZlcyBhIGJpdCBvbiBjb2RlIHNpemUsIHRob3VnaCBpdCBkb2Vzbid0 IHNlZW0gdG8gbWFrZQphIGxhcmdlIGRpZmZlcmVuY2UgaW4gc3BlZWQuCgpTaWduZWQtb2ZmLWJ5 OiBNaWNoZWwgTGVzcGluYXNzZSA8d2Fsa2VuQGdvb2dsZS5jb20+CkNjOiBBbmRyZWEgQXJjYW5n ZWxpIDxhYXJjYW5nZUByZWRoYXQuY29tPgpDYzogRGF2aWQgV29vZGhvdXNlIDxEYXZpZC5Xb29k aG91c2VAaW50ZWwuY29tPgpBY2tlZC1ieTogUmlrIHZhbiBSaWVsIDxyaWVsQHJlZGhhdC5jb20+ CkNjOiBQZXRlciBaaWpsc3RyYSA8YS5wLnppamxzdHJhQGNoZWxsby5ubD4KQ2M6IERhbmllbCBT YW50b3MgPGRhbmllbC5zYW50b3NAcG9ib3guY29tPgpDYzogSmVucyBBeGJvZSA8YXhib2VAa2Vy bmVsLmRrPgpDYzogIkVyaWMgVy4gQmllZGVybWFuIiA8ZWJpZWRlcm1AeG1pc3Npb24uY29tPgpT aWduZWQtb2ZmLWJ5OiBBbmRyZXcgTW9ydG9uIDxha3BtQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpT aWduZWQtb2ZmLWJ5OiBMaW51cyBUb3J2YWxkcyA8dG9ydmFsZHNAbGludXgtZm91bmRhdGlvbi5v cmc+CltMaW51eCBjb21taXQgNTk2MzNhYmYzNGUyZjQ0YjhlNzcyYTJjMTJhOTIxMzJhYTdjMjIy MF0KClBvcnRlZCB0byBYZW4uCgpTaWduZWQtb2ZmLWJ5OiBQcmF2ZWVuIEt1bWFyIDxrcHJhdmVl bi5sa21sQGdtYWlsLmNvbT4KLS0tCiB4ZW4vY29tbW9uL3JidHJlZS5jIHwgMjEgKysrKysrKysr KysrKy0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTMgaW5zZXJ0aW9ucygrKSwgOCBkZWxldGlv bnMoLSkKCmRpZmYgLS1naXQgYS94ZW4vY29tbW9uL3JidHJlZS5jIGIveGVuL2NvbW1vbi9yYnRy ZWUuYwppbmRleCAyMTVkNGYzNjEzLi5kOGYxMTk0ZTIwIDEwMDY0NAotLS0gYS94ZW4vY29tbW9u L3JidHJlZS5jCisrKyBiL3hlbi9jb21tb24vcmJ0cmVlLmMKQEAgLTEwNyw4ICsxMDcsOCBAQCB2 b2lkIHJiX2luc2VydF9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3Qg KnJvb3QpCiAKIAkJZ3BhcmVudCA9IHJiX3JlZF9wYXJlbnQocGFyZW50KTsKIAotCQlpZiAocGFy ZW50ID09IGdwYXJlbnQtPnJiX2xlZnQpIHsKLQkJCXRtcCA9IGdwYXJlbnQtPnJiX3JpZ2h0Owor CQl0bXAgPSBncGFyZW50LT5yYl9yaWdodDsKKwkJaWYgKHBhcmVudCAhPSB0bXApIHsgICAgLyog cGFyZW50ID09IGdwYXJlbnQtPnJiX2xlZnQgKi8KIAkJCWlmICh0bXAgJiYgcmJfaXNfcmVkKHRt cCkpIHsKIAkJCQkvKgogCQkJCSAqIENhc2UgMSAtIGNvbG9yIGZsaXBzCkBAIC0xMzEsNyArMTMx LDggQEAgdm9pZCByYl9pbnNlcnRfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCBy Yl9yb290ICpyb290KQogCQkJCWNvbnRpbnVlOwogCQkJfQogCi0JCQlpZiAocGFyZW50LT5yYl9y aWdodCA9PSBub2RlKSB7CisJCQl0bXAgPSBwYXJlbnQtPnJiX3JpZ2h0OworCQkJaWYgKG5vZGUg PT0gdG1wKSB7CiAJCQkJLyoKIAkJCQkgKiBDYXNlIDIgLSBsZWZ0IHJvdGF0ZSBhdCBwYXJlbnQK IAkJCQkgKgpAQCAtMTUxLDYgKzE1Miw3IEBAIHZvaWQgcmJfaW5zZXJ0X2NvbG9yKHN0cnVjdCBy Yl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIAkJCQkJCQkgICAgUkJfQkxBQ0sp OwogCQkJCXJiX3NldF9wYXJlbnRfY29sb3IocGFyZW50LCBub2RlLCBSQl9SRUQpOwogCQkJCXBh cmVudCA9IG5vZGU7CisJCQkJdG1wID0gbm9kZS0+cmJfcmlnaHQ7CiAJCQl9CiAKIAkJCS8qCkBA IC0xNjIsNyArMTY0LDcgQEAgdm9pZCByYl9pbnNlcnRfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5v ZGUsIHN0cnVjdCByYl9yb290ICpyb290KQogCQkJICogICAgIC8gICAgICAgICAgICAgICAgIFwK IAkJCSAqICAgIG4gICAgICAgICAgICAgICAgICAgVQogCQkJICovCi0JCQlncGFyZW50LT5yYl9s ZWZ0ID0gdG1wID0gcGFyZW50LT5yYl9yaWdodDsKKwkJCWdwYXJlbnQtPnJiX2xlZnQgPSB0bXA7 ICAvKiA9PSBwYXJlbnQtPnJiX3JpZ2h0ICovCiAJCQlwYXJlbnQtPnJiX3JpZ2h0ID0gZ3BhcmVu dDsKIAkJCWlmICh0bXApCiAJCQkJcmJfc2V0X3BhcmVudF9jb2xvcih0bXAsIGdwYXJlbnQsIFJC X0JMQUNLKTsKQEAgLTE4MCw3ICsxODIsOCBAQCB2b2lkIHJiX2luc2VydF9jb2xvcihzdHJ1Y3Qg cmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiAJCQkJY29udGludWU7CiAJCQl9 CiAKLQkJCWlmIChwYXJlbnQtPnJiX2xlZnQgPT0gbm9kZSkgeworCQkJdG1wID0gcGFyZW50LT5y Yl9sZWZ0OworCQkJaWYgKG5vZGUgPT0gdG1wKSB7CiAJCQkJLyogQ2FzZSAyIC0gcmlnaHQgcm90 YXRlIGF0IHBhcmVudCAqLwogCQkJCXBhcmVudC0+cmJfbGVmdCA9IHRtcCA9IG5vZGUtPnJiX3Jp Z2h0OwogCQkJCW5vZGUtPnJiX3JpZ2h0ID0gcGFyZW50OwpAQCAtMTg5LDEwICsxOTIsMTEgQEAg dm9pZCByYl9pbnNlcnRfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9yb290 ICpyb290KQogCQkJCQkJCSAgICBSQl9CTEFDSyk7CiAJCQkJcmJfc2V0X3BhcmVudF9jb2xvcihw YXJlbnQsIG5vZGUsIFJCX1JFRCk7CiAJCQkJcGFyZW50ID0gbm9kZTsKKwkJCQl0bXAgPSBub2Rl LT5yYl9sZWZ0OwogCQkJfQogCiAJCQkvKiBDYXNlIDMgLSBsZWZ0IHJvdGF0ZSBhdCBncGFyZW50 ICovCi0JCQlncGFyZW50LT5yYl9yaWdodCA9IHRtcCA9IHBhcmVudC0+cmJfbGVmdDsKKwkJCWdw YXJlbnQtPnJiX3JpZ2h0ID0gdG1wOyAgLyogPT0gcGFyZW50LT5yYl9sZWZ0ICovCiAJCQlwYXJl bnQtPnJiX2xlZnQgPSBncGFyZW50OwogCQkJaWYgKHRtcCkKIAkJCQlyYl9zZXRfcGFyZW50X2Nv bG9yKHRtcCwgZ3BhcmVudCwgUkJfQkxBQ0spOwpAQCAtMjIzLDggKzIyNyw5IEBAIHN0YXRpYyB2 b2lkIF9fcmJfZXJhc2VfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9ub2Rl ICpwYXJlbnQsCiAJCQlicmVhazsKIAkJfSBlbHNlIGlmICghcGFyZW50KSB7CiAJCQlicmVhazsK LQkJfSBlbHNlIGlmIChwYXJlbnQtPnJiX2xlZnQgPT0gbm9kZSkgewotCQkJc2libGluZyA9IHBh cmVudC0+cmJfcmlnaHQ7CisJCX0KKwkJc2libGluZyA9IHBhcmVudC0+cmJfcmlnaHQ7CisJCWlm IChub2RlICE9IHNpYmxpbmcpIHsgIC8qIG5vZGUgPT0gcGFyZW50LT5yYl9sZWZ0ICovCiAJCQlp ZiAocmJfaXNfcmVkKHNpYmxpbmcpKSB7CiAJCQkJLyoKIAkJCQkgKiBDYXNlIDEgLSBsZWZ0IHJv dGF0ZSBhdCBwYXJlbnQKLS0gCjIuMTIuMAoKCl9fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fClhlbi1kZXZlbCBtYWlsaW5nIGxpc3QKWGVuLWRldmVsQGxpc3Rz Lnhlbi5vcmcKaHR0cHM6Ly9saXN0cy54ZW4ub3JnL3hlbi1kZXZlbAo=