From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH 02/20] lib/rbtree.c: optimize rb_erase() Date: Sat, 17 Jun 2017 15:02:35 +0530 Message-ID: <20170617093253.3990-3-kpraveen.lkml@gmail.com> References: <20170617093253.3990-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: <20170617093253.3990-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 VGZvdXIgNCByZWR1bmRhbnQgaWYtY29uZGl0aW9ucyBpbiBmdW5jdGlvbiBfX3JiX2VyYXNlX2Nv bG9yKCkgaW4KbGliL3JidHJlZS5jIGFyZSByZW1vdmVkLgoKSW4gcHNldWRvLXNvdXJjZS1jb2Rl LCB0aGUgc3RydWN0dXJlIG9mIHRoZSBjb2RlIGlzIGFzIGZvbGxvd3M6CgppZiAoKCFBIHx8IEIp ICYmICghQyB8fCBEKSkgewouCi4KLgp9IGVsc2UgewoJCWlmICghQyB8fCBEKSB7Ly9pZiB0aGlz IGlzIHRydWUsIGl0IGltcGxpZXM6IChBID09IHRydWUpICYmIChCID09IGZhbHNlKQoJCQkJaWYg KEEpIHsvL2hlbmNlIHRoaXMgYWx3YXlzIGV2YWx1YXRlcyB0byAndHJ1ZScuLi4KCQkJCQkJLgoJ CQkJfQoJCQkJLgoJCQkJLy9hdCB0aGlzIHBvaW50LCBDIGFsd2F5cyBiZWNvbWVzIHRydWUsIGJl Y2F1c2Ugb2Y6CgkJCQlfX3JiX3JvdGF0ZV9yaWdodC9sZWZ0KCk7CgkJCQkvL2FuZDoKCQkJCW90 aGVyID0gcGFyZW50LT5yYl9yaWdodC9sZWZ0OwoJCX0KCQkuCgkJLgoJCWlmIChDKSB7Ly8uLi5h bmQgdGhpcyB0b28gIQoJCQkJLgoJCX0KfQoKU2lnbmVkLW9mZi1ieTogV29sZnJhbSBTdHJlcHAg PHdzdHJlcHBAZ214LmRlPgpBY2tlZC1ieTogUGV0ZXIgWmlqbHN0cmEgPGEucC56aWpsc3RyYUBj aGVsbG8ubmw+CkNjOiBBbmRyZWEgQXJjYW5nZWxpIDxhbmRyZWFAcXVtcmFuZXQuY29tPgpTaWdu ZWQtb2ZmLWJ5OiBBbmRyZXcgTW9ydG9uIDxha3BtQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpTaWdu ZWQtb2ZmLWJ5OiBMaW51cyBUb3J2YWxkcyA8dG9ydmFsZHNAbGludXgtZm91bmRhdGlvbi5vcmc+ CltMaW51eCBjb21taXQgNTVhNjM5OThiODk2NzYxNWExNWUyMjExYmEwZmYzYTg0YTU2NTgyNF0K ClBvcnRlZCB0byBYZW4uCgpTaWduZWQtb2ZmLWJ5OiBQcmF2ZWVuIEt1bWFyIDxrcHJhdmVlbi5s a21sQGdtYWlsLmNvbT4KLS0tCiB4ZW4vY29tbW9uL3JidHJlZS5jIHwgMTQgKysrKy0tLS0tLS0t LS0KIDEgZmlsZSBjaGFuZ2VkLCA0IGluc2VydGlvbnMoKyksIDEwIGRlbGV0aW9ucygtKQoKZGlm ZiAtLWdpdCBhL3hlbi9jb21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9uL3JidHJlZS5jCmluZGV4 IGQ4NmI1ZjI1YzAuLjcwY2IxNWYxZmUgMTAwNjQ0Ci0tLSBhL3hlbi9jb21tb24vcmJ0cmVlLmMK KysrIGIveGVuL2NvbW1vbi9yYnRyZWUuYwpAQCAtMTYyLDE3ICsxNjIsMTQgQEAgc3RhdGljIHZv aWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUg KnBhcmVudCwKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBpZiAoIW90aGVyLT5yYl9y aWdodCB8fCByYl9pc19ibGFjayhvdGhlci0+cmJfcmlnaHQpKQogICAgICAgICAgICAgICAgIHsK LSAgICAgICAgICAgICAgICAgICAgc3RydWN0IHJiX25vZGUgKm9fbGVmdDsKLSAgICAgICAgICAg ICAgICAgICAgaWYgKChvX2xlZnQgPSBvdGhlci0+cmJfbGVmdCkpCi0gICAgICAgICAgICAgICAg ICAgICAgICByYl9zZXRfYmxhY2sob19sZWZ0KTsKKyAgICAgICAgICAgICAgICAgICAgcmJfc2V0 X2JsYWNrKG90aGVyLT5yYl9sZWZ0KTsKICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X3JlZChv dGhlcik7CiAgICAgICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX3JpZ2h0KG90aGVyLCByb290 KTsKICAgICAgICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQtPnJiX3JpZ2h0OwogICAgICAg ICAgICAgICAgIH0KICAgICAgICAgICAgICAgICByYl9zZXRfY29sb3Iob3RoZXIsIHJiX2NvbG9y KHBhcmVudCkpOwogICAgICAgICAgICAgICAgIHJiX3NldF9ibGFjayhwYXJlbnQpOwotICAgICAg ICAgICAgICAgIGlmIChvdGhlci0+cmJfcmlnaHQpCi0gICAgICAgICAgICAgICAgICAgIHJiX3Nl dF9ibGFjayhvdGhlci0+cmJfcmlnaHQpOworICAgICAgICAgICAgICAgIHJiX3NldF9ibGFjayhv dGhlci0+cmJfcmlnaHQpOwogICAgICAgICAgICAgICAgIF9fcmJfcm90YXRlX2xlZnQocGFyZW50 LCByb290KTsKICAgICAgICAgICAgICAgICBub2RlID0gcm9vdC0+cmJfbm9kZTsKICAgICAgICAg ICAgICAgICBicmVhazsKQEAgLTE5OSwxNyArMTk2LDE0IEBAIHN0YXRpYyB2b2lkIF9fcmJfZXJh c2VfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9ub2RlICpwYXJlbnQsCiAg ICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgaWYgKCFvdGhlci0+cmJfbGVmdCB8fCByYl9p c19ibGFjayhvdGhlci0+cmJfbGVmdCkpCiAgICAgICAgICAgICAgICAgewotICAgICAgICAgICAg ICAgICAgICByZWdpc3RlciBzdHJ1Y3QgcmJfbm9kZSAqb19yaWdodDsKLSAgICAgICAgICAgICAg ICAgICAgaWYgKChvX3JpZ2h0ID0gb3RoZXItPnJiX3JpZ2h0KSkKLSAgICAgICAgICAgICAgICAg ICAgICAgIHJiX3NldF9ibGFjayhvX3JpZ2h0KTsKKyAgICAgICAgICAgICAgICAgICAgcmJfc2V0 X2JsYWNrKG90aGVyLT5yYl9yaWdodCk7CiAgICAgICAgICAgICAgICAgICAgIHJiX3NldF9yZWQo b3RoZXIpOwogICAgICAgICAgICAgICAgICAgICBfX3JiX3JvdGF0ZV9sZWZ0KG90aGVyLCByb290 KTsKICAgICAgICAgICAgICAgICAgICAgb3RoZXIgPSBwYXJlbnQtPnJiX2xlZnQ7CiAgICAgICAg ICAgICAgICAgfQogICAgICAgICAgICAgICAgIHJiX3NldF9jb2xvcihvdGhlciwgcmJfY29sb3Io cGFyZW50KSk7CiAgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKHBhcmVudCk7Ci0gICAgICAg ICAgICAgICAgaWYgKG90aGVyLT5yYl9sZWZ0KQotICAgICAgICAgICAgICAgICAgICByYl9zZXRf YmxhY2sob3RoZXItPnJiX2xlZnQpOworICAgICAgICAgICAgICAgIHJiX3NldF9ibGFjayhvdGhl ci0+cmJfbGVmdCk7CiAgICAgICAgICAgICAgICAgX19yYl9yb3RhdGVfcmlnaHQocGFyZW50LCBy b290KTsKICAgICAgICAgICAgICAgICBub2RlID0gcm9vdC0+cmJfbm9kZTsKICAgICAgICAgICAg ICAgICBicmVhazsKLS0gCjIuMTIuMAoKCl9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fClhlbi1kZXZlbCBtYWlsaW5nIGxpc3QKWGVuLWRldmVsQGxpc3RzLnhl bi5vcmcKaHR0cHM6Ly9saXN0cy54ZW4ub3JnL3hlbi1kZXZlbAo=