From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [PATCH v6 14/16] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() Date: Tue, 21 Nov 2017 20:50:07 +0530 Message-ID: <20171121152009.15591-15-kpraveen.lkml@gmail.com> References: <20171121152009.15591-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: <20171121152009.15591-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, konrad.wilk@oracle.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 RnJvbTogTWljaGVsIExlc3BpbmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgoKQW4gaW50ZXJlc3Rp bmcgb2JzZXJ2YXRpb24gZm9yIHJiX2VyYXNlKCkgaXMgdGhhdCB3aGVuIGEgbm9kZSBoYXMKZXhh Y3RseSBvbmUgY2hpbGQsIHRoZSBub2RlIG11c3QgYmUgYmxhY2sgYW5kIHRoZSBjaGlsZCBtdXN0 IGJlIHJlZC4KQW4gaW50ZXJlc3RpbmcgY29uc2VxdWVuY2UgaXMgdGhhdCByZW1vdmluZyBzdWNo IGEgbm9kZSBjYW4gYmUgZG9uZSBieQpzaW1wbHkgcmVwbGFjaW5nIGl0IHdpdGggaXRzIGNoaWxk IGFuZCBtYWtpbmcgdGhlIGNoaWxkIGJsYWNrLAp3aGljaCB3ZSBjYW4gZG8gZWZmaWNpZW50bHkg aW4gcmJfZXJhc2UoKS4gX19yYl9lcmFzZV9jb2xvcigpIHRoZW4Kb25seSBuZWVkcyB0byBoYW5k bGUgdGhlIG5vLWNoaWxkcyBjYXNlIGFuZCBjYW4gYmUgbW9kaWZpZWQgYWNjb3JkaW5nbHkuCgpT aWduZWQtb2ZmLWJ5OiBNaWNoZWwgTGVzcGluYXNzZSA8d2Fsa2VuQGdvb2dsZS5jb20+CkFja2Vk LWJ5OiBSaWsgdmFuIFJpZWwgPHJpZWxAcmVkaGF0LmNvbT4KQ2M6IFBldGVyIFppamxzdHJhIDxh LnAuemlqbHN0cmFAY2hlbGxvLm5sPgpDYzogQW5kcmVhIEFyY2FuZ2VsaSA8YWFyY2FuZ2VAcmVk aGF0LmNvbT4KQ2M6IERhdmlkIFdvb2Rob3VzZSA8ZHdtdzJAaW5mcmFkZWFkLm9yZz4KU2lnbmVk LW9mZi1ieTogQW5kcmV3IE1vcnRvbiA8YWtwbUBsaW51eC1mb3VuZGF0aW9uLm9yZz4KU2lnbmVk LW9mZi1ieTogTGludXMgVG9ydmFsZHMgPHRvcnZhbGRzQGxpbnV4LWZvdW5kYXRpb24ub3JnPgpb TGludXggY29tbWl0IDQ2YjYxMzVhNzQwMmFjMjNjNWIyNWYyYmQ3OWIwM2JhYjhmOTgyNzhdCgpQ b3J0ZWQgdG8gWGVuLgoKU2lnbmVkLW9mZi1ieTogUHJhdmVlbiBLdW1hciA8a3ByYXZlZW4ubGtt bEBnbWFpbC5jb20+Ci0tLQpSZW1vdmVkIG5ldyBsaW5lIGZyb20gcHJldmlvdXMgcGF0Y2ggdG8g bWFrZSBpbmxpbmUgd2l0aCBMaW51eCBjb2RlIGJhc2UKLS0tCiB4ZW4vY29tbW9uL3JidHJlZS5j IHwgMTA1ICsrKysrKysrKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0tLS0t LS0KIDEgZmlsZSBjaGFuZ2VkLCA2MiBpbnNlcnRpb25zKCspLCA0MyBkZWxldGlvbnMoLSkKCmRp ZmYgLS1naXQgYS94ZW4vY29tbW9uL3JidHJlZS5jIGIveGVuL2NvbW1vbi9yYnRyZWUuYwppbmRl eCAxM2E2MjIzMjZkLi5lN2RmMjczODAwIDEwMDY0NAotLS0gYS94ZW4vY29tbW9uL3JidHJlZS5j CisrKyBiL3hlbi9jb21tb24vcmJ0cmVlLmMKQEAgLTIsNyArMiw4IEBACiAgIFJlZCBCbGFjayBU cmVlcwogICAoQykgMTk5OSAgQW5kcmVhIEFyY2FuZ2VsaSA8YW5kcmVhQHN1c2UuZGU+CiAgIChD KSAyMDAyICBEYXZpZCBXb29kaG91c2UgPGR3bXcyQGluZnJhZGVhZC5vcmc+Ci0gIAorICAoQykg MjAxMiAgTWljaGVsIExlc3BpbmFzc2UgPHdhbGtlbkBnb29nbGUuY29tPgorCiAgIFRoaXMgcHJv Z3JhbSBpcyBmcmVlIHNvZnR3YXJlOyB5b3UgY2FuIHJlZGlzdHJpYnV0ZSBpdCBhbmQvb3IgbW9k aWZ5CiAgIGl0IHVuZGVyIHRoZSB0ZXJtcyBvZiB0aGUgR05VIEdlbmVyYWwgUHVibGljIExpY2Vu c2UgYXMgcHVibGlzaGVkIGJ5CiAgIHRoZSBGcmVlIFNvZnR3YXJlIEZvdW5kYXRpb247IGVpdGhl ciB2ZXJzaW9uIDIgb2YgdGhlIExpY2Vuc2UsIG9yCkBAIC01MCw2ICs1MSwxMSBAQAogI2RlZmlu ZSByYl9pc19yZWQocikgICAoIXJiX2NvbG9yKHIpKQogI2RlZmluZSByYl9pc19ibGFjayhyKSBy Yl9jb2xvcihyKQogCitzdGF0aWMgaW5saW5lIHZvaWQgcmJfc2V0X2JsYWNrKHN0cnVjdCByYl9u b2RlICpyYikKK3sKKwlyYi0+X19yYl9wYXJlbnRfY29sb3IgfD0gUkJfQkxBQ0s7Cit9CisKIHN0 YXRpYyBpbmxpbmUgdm9pZCByYl9zZXRfcGFyZW50KHN0cnVjdCByYl9ub2RlICpyYiwgc3RydWN0 IHJiX25vZGUgKnApCiB7CiAJcmItPl9fcmJfcGFyZW50X2NvbG9yID0gcmJfY29sb3IocmIpIHwg KHVuc2lnbmVkIGxvbmcpcDsKQEAgLTIxNCwyNyArMjIwLDE4IEBAIHZvaWQgcmJfaW5zZXJ0X2Nv bG9yKHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIH0KIEVYUE9S VF9TWU1CT0wocmJfaW5zZXJ0X2NvbG9yKTsKIAotc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xv cihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKLQkJCSAgICAg c3RydWN0IHJiX3Jvb3QgKnJvb3QpCitzdGF0aWMgdm9pZCBfX3JiX2VyYXNlX2NvbG9yKHN0cnVj dCByYl9ub2RlICpwYXJlbnQsIHN0cnVjdCByYl9yb290ICpyb290KQogewotCXN0cnVjdCByYl9u b2RlICpzaWJsaW5nLCAqdG1wMSwgKnRtcDI7CisJc3RydWN0IHJiX25vZGUgKm5vZGUgPSBOVUxM LCAqc2libGluZywgKnRtcDEsICp0bXAyOwogCiAJd2hpbGUgKHRydWUpIHsKIAkJLyoKLQkJICog TG9vcCBpbnZhcmlhbnQ6IGFsbCBsZWFmIHBhdGhzIGdvaW5nIHRocm91Z2ggbm9kZSBoYXZlIGEK LQkJICogYmxhY2sgbm9kZSBjb3VudCB0aGF0IGlzIDEgbG93ZXIgdGhhbiBvdGhlciBsZWFmIHBh dGhzLgotCQkgKgotCQkgKiBJZiBub2RlIGlzIHJlZCwgd2UgY2FuIGZsaXAgaXQgdG8gYmxhY2sg dG8gYWRqdXN0LgotCQkgKiBJZiBub2RlIGlzIHRoZSByb290LCBhbGwgbGVhZiBwYXRocyBnbyB0 aHJvdWdoIGl0LgotCQkgKiBPdGhlcndpc2UsIHdlIG5lZWQgdG8gYWRqdXN0IHRoZSB0cmVlIHRo cm91Z2ggY29sb3IgZmxpcHMKLQkJICogYW5kIHRyZWUgcm90YXRpb25zIGFzIHBlciBvbmUgb2Yg dGhlIDQgY2FzZXMgYmVsb3cuCisJCSAqIExvb3AgaW52YXJpYW50czoKKwkJICogLSBub2RlIGlz IGJsYWNrIChvciBOVUxMIG9uIGZpcnN0IGl0ZXJhdGlvbikKKwkJICogLSBub2RlIGlzIG5vdCB0 aGUgcm9vdCAocGFyZW50IGlzIG5vdCBOVUxMKQorCQkgKiAtIEFsbCBsZWFmIHBhdGhzIGdvaW5n IHRocm91Z2ggcGFyZW50IGFuZCBub2RlIGhhdmUgYQorCQkgKiAgIGJsYWNrIG5vZGUgY291bnQg dGhhdCBpcyAxIGxvd2VyIHRoYW4gb3RoZXIgbGVhZiBwYXRocy4KIAkJICovCi0JCWlmIChub2Rl ICYmIHJiX2lzX3JlZChub2RlKSkgewotCQkJcmJfc2V0X3BhcmVudF9jb2xvcihub2RlLCBwYXJl bnQsIFJCX0JMQUNLKTsKLQkJCWJyZWFrOwotCQl9IGVsc2UgaWYgKCFwYXJlbnQpIHsKLQkJCWJy ZWFrOwotCQl9CiAJCXNpYmxpbmcgPSBwYXJlbnQtPnJiX3JpZ2h0OwogCQlpZiAobm9kZSAhPSBz aWJsaW5nKSB7ICAvKiBub2RlID09IHBhcmVudC0+cmJfbGVmdCAqLwogCQkJaWYgKHJiX2lzX3Jl ZChzaWJsaW5nKSkgewpAQCAtMjY4LDE3ICsyNjUsMjIgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFz ZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKIAkJ CQkJKiAgICAgIC8gXCAgICAgICAgICAgLyBcCiAJCQkJCSogICAgIFNsICBTciAgICAgICAgU2wg IFNyCiAJCQkJCSoKLQkJCQkJKiBUaGlzIGxlYXZlcyB1cyB2aW9sYXRpbmcgNSksIHNvCi0JCQkJ CSogcmVjdXJzZSBhdCBwLiBJZiBwIGlzIHJlZCwgdGhlCi0JCQkJCSogcmVjdXJzaW9uIHdpbGwg anVzdCBmbGlwIGl0IHRvIGJsYWNrCi0JCQkJCSogYW5kIGV4aXQuIElmIGNvbWluZyBmcm9tIENh c2UgMSwKLQkJCQkJKiBwIGlzIGtub3duIHRvIGJlIHJlZC4KKwkJCQkJKiBUaGlzIGxlYXZlcyB1 cyB2aW9sYXRpbmcgNSkgd2hpY2gKKwkJCQkJKiBjYW4gYmUgZml4ZWQgYnkgZmxpcHBpbmcgcCB0 byBibGFjaworCQkJCQkqIGlmIGl0IHdhcyByZWQsIG9yIGJ5IHJlY3Vyc2luZyBhdCBwLgorCQkJ CQkqIHAgaXMgcmVkIHdoZW4gY29taW5nIGZyb20gQ2FzZSAxLgogCQkJCQkqLwogCQkJCQlyYl9z ZXRfcGFyZW50X2NvbG9yKHNpYmxpbmcsIHBhcmVudCwKIAkJCQkJCQkgICAgUkJfUkVEKTsKLQkJ CQkJbm9kZSA9IHBhcmVudDsKLQkJCQkJcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOwotCQkJCQlj b250aW51ZTsKKwkJCQkJaWYgKHJiX2lzX3JlZChwYXJlbnQpKQorCQkJCQkJcmJfc2V0X2JsYWNr KHBhcmVudCk7CisJCQkJCWVsc2UgeworCQkJCQkJbm9kZSA9IHBhcmVudDsKKwkJCQkJCXBhcmVu dCA9IHJiX3BhcmVudChub2RlKTsKKwkJCQkJCWlmIChwYXJlbnQpCisJCQkJCQkJY29udGludWU7 CisJCQkJCX0KKwkJCQkJYnJlYWs7CiAJCQkJfQogCQkJCS8qCiAJCQkJICogQ2FzZSAzIC0gcmln aHQgcm90YXRlIGF0IHNpYmxpbmcKQEAgLTMzOSw5ICszNDEsMTUgQEAgc3RhdGljIHZvaWQgX19y Yl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVu dCwKIAkJCQkJLyogQ2FzZSAyIC0gc2libGluZyBjb2xvciBmbGlwICovCiAJCQkJCXJiX3NldF9w YXJlbnRfY29sb3Ioc2libGluZywgcGFyZW50LAogCQkJCQkJCSAgICBSQl9SRUQpOwotCQkJCQlu b2RlID0gcGFyZW50OwotCQkJCQlwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0JCQkJCWNvbnRp bnVlOworCQkJCQlpZiAocmJfaXNfcmVkKHBhcmVudCkpCisJCQkJCQlyYl9zZXRfYmxhY2socGFy ZW50KTsKKwkJCQkJZWxzZSB7CisJCQkJCQlub2RlID0gcGFyZW50OworCQkJCQkJcGFyZW50ID0g cmJfcGFyZW50KG5vZGUpOworCQkJCQkJaWYgKHBhcmVudCkKKwkJCQkJCQljb250aW51ZTsKKwkJ CQkJfQorCQkJCQlicmVhazsKIAkJCQl9CiAJCQkJLyogQ2FzZSAzIC0gcmlnaHQgcm90YXRlIGF0 IHNpYmxpbmcgKi8KIAkJCQlzaWJsaW5nLT5yYl9yaWdodCA9IHRtcDEgPSB0bXAyLT5yYl9sZWZ0 OwpAQCAtMzY5LDIzICszNzcsMzEgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1 Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKIHZvaWQgcmJfZXJhc2Uo c3RydWN0IHJiX25vZGUgKm5vZGUsIHN0cnVjdCByYl9yb290ICpyb290KQogewogCXN0cnVjdCBy Yl9ub2RlICpjaGlsZCA9IG5vZGUtPnJiX3JpZ2h0LCAqdG1wID0gbm9kZS0+cmJfbGVmdDsKLQlz dHJ1Y3QgcmJfbm9kZSAqcGFyZW50OwotCWludCBjb2xvcjsKKwlzdHJ1Y3QgcmJfbm9kZSAqcGFy ZW50LCAqcmViYWxhbmNlOwogCiAJaWYgKCF0bXApIHsKLQljYXNlMToKLQkJLyogQ2FzZSAxOiBu b2RlIHRvIGVyYXNlIGhhcyBubyBtb3JlIHRoYW4gMSBjaGlsZCAoZWFzeSEpICovCisJCS8qCisJ CSAqIENhc2UgMTogbm9kZSB0byBlcmFzZSBoYXMgbm8gbW9yZSB0aGFuIDEgY2hpbGQgKGVhc3kh KQorCQkgKgorCQkgKiBOb3RlIHRoYXQgaWYgdGhlcmUgaXMgb25lIGNoaWxkIGl0IG11c3QgYmUg cmVkIGR1ZSB0byA1KQorCQkgKiBhbmQgbm9kZSBtdXN0IGJlIGJsYWNrIGR1ZSB0byA0KS4gV2Ug YWRqdXN0IGNvbG9ycyBsb2NhbGx5CisJCSAqIHNvIGFzIHRvIGJ5cGFzcyBfX3JiX2VyYXNlX2Nv bG9yKCkgbGF0ZXIgb24uCisJCSAqLwogCiAJCXBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKLQkJ Y29sb3IgPSByYl9jb2xvcihub2RlKTsKLQotCQlpZiAoY2hpbGQpCi0JCQlyYl9zZXRfcGFyZW50 KGNoaWxkLCBwYXJlbnQpOwogCQlfX3JiX2NoYW5nZV9jaGlsZChub2RlLCBjaGlsZCwgcGFyZW50 LCByb290KTsKKwkJaWYgKGNoaWxkKSB7CisJCQlyYl9zZXRfcGFyZW50X2NvbG9yKGNoaWxkLCBw YXJlbnQsIFJCX0JMQUNLKTsKKwkJCXJlYmFsYW5jZSA9IE5VTEw7CisJCX0gZWxzZSB7CisJCQly ZWJhbGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7CisJCX0KIAl9IGVs c2UgaWYgKCFjaGlsZCkgewogCQkvKiBTdGlsbCBjYXNlIDEsIGJ1dCB0aGlzIHRpbWUgdGhlIGNo aWxkIGlzIG5vZGUtPnJiX2xlZnQgKi8KLQkJY2hpbGQgPSB0bXA7Ci0JCWdvdG8gY2FzZTE7CisJ CXBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKKwkJX19yYl9jaGFuZ2VfY2hpbGQobm9kZSwgdG1w LCBwYXJlbnQsIHJvb3QpOworCQlyYl9zZXRfcGFyZW50X2NvbG9yKHRtcCwgcGFyZW50LCBSQl9C TEFDSyk7CisJCXJlYmFsYW5jZSA9IE5VTEw7CiAJfSBlbHNlIHsKIAkJc3RydWN0IHJiX25vZGUg Km9sZCA9IG5vZGUsICpsZWZ0OwogCkBAIC0zOTcsMjYgKzQxMywyOSBAQCB2b2lkIHJiX2VyYXNl KHN0cnVjdCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIAogCQljaGlsZCA9 IG5vZGUtPnJiX3JpZ2h0OwogCQlwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0JCWNvbG9yID0g cmJfY29sb3Iobm9kZSk7CiAKIAkJaWYgKHBhcmVudCA9PSBvbGQpIHsKIAkJCXBhcmVudCA9IG5v ZGU7CiAJCX0gZWxzZSB7Ci0JCQlpZiAoY2hpbGQpCi0JCQkJcmJfc2V0X3BhcmVudChjaGlsZCwg cGFyZW50KTsKIAkJCXBhcmVudC0+cmJfbGVmdCA9IGNoaWxkOwogCiAJCQlub2RlLT5yYl9yaWdo dCA9IG9sZC0+cmJfcmlnaHQ7CiAJCQlyYl9zZXRfcGFyZW50KG9sZC0+cmJfcmlnaHQsIG5vZGUp OwogCQl9CiAKKwkJaWYgKGNoaWxkKSB7CisJCQlyYl9zZXRfcGFyZW50X2NvbG9yKGNoaWxkLCBw YXJlbnQsIFJCX0JMQUNLKTsKKwkJCXJlYmFsYW5jZSA9IE5VTEw7CisJCX0gZWxzZSB7CisJCQly ZWJhbGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7CisJCX0KIAkJbm9k ZS0+X19yYl9wYXJlbnRfY29sb3IgPSBvbGQtPl9fcmJfcGFyZW50X2NvbG9yOwogCQlub2RlLT5y Yl9sZWZ0ID0gb2xkLT5yYl9sZWZ0OwogCQlyYl9zZXRfcGFyZW50KG9sZC0+cmJfbGVmdCwgbm9k ZSk7CiAJfQogCi0JaWYgKGNvbG9yID09IFJCX0JMQUNLKQotCQlfX3JiX2VyYXNlX2NvbG9yKGNo aWxkLCBwYXJlbnQsIHJvb3QpOworCWlmIChyZWJhbGFuY2UpCisJCV9fcmJfZXJhc2VfY29sb3Io cmViYWxhbmNlLCByb290KTsKIH0KIEVYUE9SVF9TWU1CT0wocmJfZXJhc2UpOwogCi0tIAoyLjEz LjEKCgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwpYZW4t ZGV2ZWwgbWFpbGluZyBsaXN0Clhlbi1kZXZlbEBsaXN0cy54ZW4ub3JnCmh0dHBzOi8vbGlzdHMu eGVuLm9yZy94ZW4tZGV2ZWwK