From mboxrd@z Thu Jan 1 00:00:00 1970 From: Praveen Kumar Subject: [Resend][PATCH 15/17] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() Date: Thu, 1 Jun 2017 02:50:54 +0530 Message-ID: <20170531212056.10583-16-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 QW4gaW50ZXJlc3Rpbmcgb2JzZXJ2YXRpb24gZm9yIHJiX2VyYXNlKCkgaXMgdGhhdCB3aGVuIGEg bm9kZSBoYXMKZXhhY3RseSBvbmUgY2hpbGQsIHRoZSBub2RlIG11c3QgYmUgYmxhY2sgYW5kIHRo ZSBjaGlsZCBtdXN0IGJlIHJlZC4KQW4gaW50ZXJlc3RpbmcgY29uc2VxdWVuY2UgaXMgdGhhdCBy ZW1vdmluZyBzdWNoIGEgbm9kZSBjYW4gYmUgZG9uZSBieQpzaW1wbHkgcmVwbGFjaW5nIGl0IHdp dGggaXRzIGNoaWxkIGFuZCBtYWtpbmcgdGhlIGNoaWxkIGJsYWNrLAp3aGljaCB3ZSBjYW4gZG8g ZWZmaWNpZW50bHkgaW4gcmJfZXJhc2UoKS4gX19yYl9lcmFzZV9jb2xvcigpIHRoZW4Kb25seSBu ZWVkcyB0byBoYW5kbGUgdGhlIG5vLWNoaWxkcyBjYXNlIGFuZCBjYW4gYmUgbW9kaWZpZWQgYWNj b3JkaW5nbHkuCgpjb21taXQgNDZiNjEzNWE3NDAyYWMyM2M1YjI1ZjJiZDc5YjAzYmFiOGY5ODI3 OCBmcm9tIExpbnV4IHRyZWUKClNpZ25lZC1vZmYtYnk6IFByYXZlZW4gS3VtYXIgPGtwcmF2ZWVu LmxrbWxAZ21haWwuY29tPgotLS0KIHhlbi9jb21tb24vcmJ0cmVlLmMgfCAxMTAgKysrKysrKysr KysrKysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLS0tLS0tLQogMSBmaWxlIGNoYW5n ZWQsIDY2IGluc2VydGlvbnMoKyksIDQ0IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3hlbi9j b21tb24vcmJ0cmVlLmMgYi94ZW4vY29tbW9uL3JidHJlZS5jCmluZGV4IDY5Yzc0OTZjNjUuLjZl MzdlOTYwYWIgMTAwNjQ0Ci0tLSBhL3hlbi9jb21tb24vcmJ0cmVlLmMKKysrIGIveGVuL2NvbW1v bi9yYnRyZWUuYwpAQCAtMiw2ICsyLDcgQEAKICAgUmVkIEJsYWNrIFRyZWVzCiAgIChDKSAxOTk5 ICBBbmRyZWEgQXJjYW5nZWxpIDxhbmRyZWFAc3VzZS5kZT4KICAgKEMpIDIwMDIgIERhdmlkIFdv b2Rob3VzZSA8ZHdtdzJAaW5mcmFkZWFkLm9yZz4KKyAgKEMpIDIwMTIgIE1pY2hlbCBMZXNwaW5h c3NlIDx3YWxrZW5AZ29vZ2xlLmNvbT4KICAgCiAgIFRoaXMgcHJvZ3JhbSBpcyBmcmVlIHNvZnR3 YXJlOyB5b3UgY2FuIHJlZGlzdHJpYnV0ZSBpdCBhbmQvb3IgbW9kaWZ5CiAgIGl0IHVuZGVyIHRo ZSB0ZXJtcyBvZiB0aGUgR05VIEdlbmVyYWwgUHVibGljIExpY2Vuc2UgYXMgcHVibGlzaGVkIGJ5 CkBAIC00OSw2ICs1MCwxMiBAQAogI2RlZmluZSByYl9pc19yZWQocikgICAgKCFyYl9jb2xvcihy KSkKICNkZWZpbmUgcmJfaXNfYmxhY2socikgIHJiX2NvbG9yKHIpCiAKK3N0YXRpYyBpbmxpbmUg dm9pZCByYl9zZXRfYmxhY2soc3RydWN0IHJiX25vZGUgKnJiKQoreworICAgIHJiLT5fX3JiX3Bh cmVudF9jb2xvciB8PSBSQl9CTEFDSzsKK30KKworCiBzdGF0aWMgaW5saW5lIHZvaWQgcmJfc2V0 X3BhcmVudChzdHJ1Y3QgcmJfbm9kZSAqcmIsIHN0cnVjdCByYl9ub2RlICpwKQogewogICAgIHJi LT5fX3JiX3BhcmVudF9jb2xvciA9IHJiX2NvbG9yKHJiKSB8ICh1bnNpZ25lZCBsb25nKXA7CkBA IC0yMTksMjkgKzIyNiwxOSBAQCB2b2lkIHJiX2luc2VydF9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAq bm9kZSwgc3RydWN0IHJiX3Jvb3QgKnJvb3QpCiB9CiBFWFBPUlRfU1lNQk9MKHJiX2luc2VydF9j b2xvcik7CiAKLXN0YXRpYyB2b2lkIF9fcmJfZXJhc2VfY29sb3Ioc3RydWN0IHJiX25vZGUgKm5v ZGUsIHN0cnVjdCByYl9ub2RlICpwYXJlbnQsCi0gICAgICAgICAgICAgICAgICAgICAgICAgICAg IHN0cnVjdCByYl9yb290ICpyb290KQorc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1 Y3QgcmJfbm9kZSAqcGFyZW50LCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIHsKLSAgICBzdHJ1Y3Qg cmJfbm9kZSAqc2libGluZywgKnRtcDEsICp0bXAyOworICAgIHN0cnVjdCByYl9ub2RlICpub2Rl ID0gTlVMTCwgKnNpYmxpbmcsICp0bXAxLCAqdG1wMjsKIAogICAgIHdoaWxlICh0cnVlKQogICAg IHsKICAgICAgICAgLyoKLSAgICAgICAgICogTG9vcCBpbnZhcmlhbnQ6IGFsbCBsZWFmIHBhdGhz IGdvaW5nIHRocm91Z2ggbm9kZSBoYXZlIGEKLSAgICAgICAgICogYmxhY2sgbm9kZSBjb3VudCB0 aGF0IGlzIDEgbG93ZXIgdGhhbiBvdGhlciBsZWFmIHBhdGhzLgotICAgICAgICAgKgotICAgICAg ICAgKiBJZiBub2RlIGlzIHJlZCwgd2UgY2FuIGZsaXAgaXQgdG8gYmxhY2sgdG8gYWRqdXN0Lgot ICAgICAgICAgKiBJZiBub2RlIGlzIHRoZSByb290LCBhbGwgbGVhZiBwYXRocyBnbyB0aHJvdWdo IGl0LgotICAgICAgICAgKiBPdGhlcndpc2UsIHdlIG5lZWQgdG8gYWRqdXN0IHRoZSB0cmVlIHRo cm91Z2ggY29sb3IgZmxpcHMKLSAgICAgICAgICogYW5kIHRyZWUgcm90YXRpb25zIGFzIHBlciBv bmUgb2YgdGhlIDQgY2FzZXMgYmVsb3cuCisgICAgICAgICAqIExvb3AgaW52YXJpYW50czoKKyAg ICAgICAgICogLSBub2RlIGlzIGJsYWNrIChvciBOVUxMIG9uIGZpcnN0IGl0ZXJhdGlvbikKKyAg ICAgICAgICogLSBub2RlIGlzIG5vdCB0aGUgcm9vdCAocGFyZW50IGlzIG5vdCBOVUxMKQorICAg ICAgICAgKiAtIEFsbCBsZWFmIHBhdGhzIGdvaW5nIHRocm91Z2ggcGFyZW50IGFuZCBub2RlIGhh dmUgYQorICAgICAgICAgKiAgIGJsYWNrIG5vZGUgY291bnQgdGhhdCBpcyAxIGxvd2VyIHRoYW4g b3RoZXIgbGVhZiBwYXRocy4KICAgICAgICAgICovCi0gICAgICAgIGlmIChub2RlICYmIHJiX2lz X3JlZChub2RlKSkKLSAgICAgICAgewotICAgICAgICAgICAgcmJfc2V0X3BhcmVudF9jb2xvcihu b2RlLCBwYXJlbnQsIFJCX0JMQUNLKTsKLSAgICAgICAgICAgIGJyZWFrOwotICAgICAgICB9IGVs c2UgaWYgKCFwYXJlbnQpIHsKLSAgICAgICAgICAgIGJyZWFrOwotICAgICAgICB9CiAgICAgICAg IHNpYmxpbmcgPSBwYXJlbnQtPnJiX3JpZ2h0OwogICAgICAgICBpZiAoIG5vZGUgIT0gc2libGlu ZykgICAgLyogbm9kZSA9PSBwYXJlbnQtPnJiX2xlZnQgKi8KICAgICAgICAgewpAQCAtMjc3LDE3 ICsyNzQsMjIgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xvcihzdHJ1Y3QgcmJfbm9kZSAq bm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKICAgICAgICAgICAgICAgICAgICAgICogICAg ICAvIFwgICAgICAgICAgIC8gXAogICAgICAgICAgICAgICAgICAgICAgKiAgICAgU2wgIFNyICAg ICAgICBTbCAgU3IKICAgICAgICAgICAgICAgICAgICAgICoKLSAgICAgICAgICAgICAgICAgICAg ICogVGhpcyBsZWF2ZXMgdXMgdmlvbGF0aW5nIDUpLCBzbwotICAgICAgICAgICAgICAgICAgICAg KiByZWN1cnNlIGF0IHAuIElmIHAgaXMgcmVkLCB0aGUKLSAgICAgICAgICAgICAgICAgICAgICog cmVjdXJzaW9uIHdpbGwganVzdCBmbGlwIGl0IHRvIGJsYWNrCi0gICAgICAgICAgICAgICAgICAg ICAqIGFuZCBleGl0LiBJZiBjb21pbmcgZnJvbSBDYXNlIDEsCi0gICAgICAgICAgICAgICAgICAg ICAqIHAgaXMga25vd24gdG8gYmUgcmVkLgorICAgICAgICAgICAgICAgICAgICAgKiBUaGlzIGxl YXZlcyB1cyB2aW9sYXRpbmcgNSkgd2hpY2gKKyAgICAgICAgICAgICAgICAgICAgICogY2FuIGJl IGZpeGVkIGJ5IGZsaXBwaW5nIHAgdG8gYmxhY2sKKyAgICAgICAgICAgICAgICAgICAgICogaWYg aXQgd2FzIHJlZCwgb3IgYnkgcmVjdXJzaW5nIGF0IHAuCisgICAgICAgICAgICAgICAgICAgICAq IHAgaXMgcmVkIHdoZW4gY29taW5nIGZyb20gQ2FzZSAxLgogICAgICAgICAgICAgICAgICAgICAg Ki8KICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X3BhcmVudF9jb2xvcihzaWJsaW5nLCBwYXJl bnQsIFJCX1JFRCk7Ci0gICAgICAgICAgICAgICAgICAgIG5vZGUgPSBwYXJlbnQ7Ci0gICAgICAg ICAgICAgICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKLSAgICAgICAgICAgICAgICAg ICAgY29udGludWU7Ci0KKyAgICAgICAgICAgICAgICAgICAgaWYgKHJiX2lzX3JlZChwYXJlbnQp KQorICAgICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKHBhcmVudCk7CisgICAgICAg ICAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAg ICAgICAgICAgbm9kZSA9IHBhcmVudDsKKyAgICAgICAgICAgICAgICAgICAgICAgIHBhcmVudCA9 IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChwYXJlbnQpCisg ICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CisgICAgICAgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgfQogICAgICAg ICAgICAgICAgIC8qCiAgICAgICAgICAgICAgICAgICogQ2FzZSAzIC0gcmlnaHQgcm90YXRlIGF0 IHNpYmxpbmcKQEAgLTM0OSw5ICszNTEsMTYgQEAgc3RhdGljIHZvaWQgX19yYl9lcmFzZV9jb2xv cihzdHJ1Y3QgcmJfbm9kZSAqbm9kZSwgc3RydWN0IHJiX25vZGUgKnBhcmVudCwKICAgICAgICAg ICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgIC8qIENhc2UgMiAtIHNpYmxpbmcgY29sb3Ig ZmxpcCAqLwogICAgICAgICAgICAgICAgICAgICByYl9zZXRfcGFyZW50X2NvbG9yKHNpYmxpbmcs IHBhcmVudCwgUkJfUkVEKTsKLSAgICAgICAgICAgICAgICAgICAgbm9kZSA9IHBhcmVudDsKLSAg ICAgICAgICAgICAgICAgICAgcGFyZW50ID0gcmJfcGFyZW50KG5vZGUpOwotICAgICAgICAgICAg ICAgICAgICBjb250aW51ZTsKKyAgICAgICAgICAgICAgICAgICAgaWYgKHJiX2lzX3JlZChwYXJl bnQpKQorICAgICAgICAgICAgICAgICAgICAgICAgcmJfc2V0X2JsYWNrKHBhcmVudCk7CisgICAg ICAgICAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAg ICAgICAgICAgICAgbm9kZSA9IHBhcmVudDsKKyAgICAgICAgICAgICAgICAgICAgICAgIHBhcmVu dCA9IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChwYXJlbnQp CisgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CisgICAgICAgICAgICAgICAg ICAgIH0KKyAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgfQogICAg ICAgICAgICAgICAgIC8qIENhc2UgMyAtIHJpZ2h0IHJvdGF0ZSBhdCBzaWJsaW5nICovCiAgICAg ICAgICAgICAgICAgc2libGluZy0+cmJfcmlnaHQgPSB0bXAxID0gdG1wMi0+cmJfbGVmdDsKQEAg LTM3NywyNCArMzg2LDMzIEBAIHN0YXRpYyB2b2lkIF9fcmJfZXJhc2VfY29sb3Ioc3RydWN0IHJi X25vZGUgKm5vZGUsIHN0cnVjdCByYl9ub2RlICpwYXJlbnQsCiB2b2lkIHJiX2VyYXNlKHN0cnVj dCByYl9ub2RlICpub2RlLCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIHsKICAgICBzdHJ1Y3QgcmJf bm9kZSAqY2hpbGQgPSBub2RlLT5yYl9yaWdodCwgKnRtcCA9IG5vZGUtPnJiX2xlZnQ7Ci0gICAg c3RydWN0IHJiX25vZGUgKnBhcmVudDsKLSAgICBpbnQgY29sb3I7CisgICAgc3RydWN0IHJiX25v ZGUgKnBhcmVudCwgKnJlYmFsYW5jZTsKIAogICAgIGlmICghdG1wKQogICAgIHsKLSAgICBjYXNl MToKLSAgICAgICAgLyogQ2FzZSAxOiBub2RlIHRvIGVyYXNlIGhhcyBubyBtb3JlIHRoYW4gMSBj aGlsZCAoZWFzeSEpICovCisgICAgICAgIC8qCisgICAgICAgICAqIENhc2UgMTogbm9kZSB0byBl cmFzZSBoYXMgbm8gbW9yZSB0aGFuIDEgY2hpbGQgKGVhc3khKQorICAgICAgICAgKgorICAgICAg ICAgKiBOb3RlIHRoYXQgaWYgdGhlcmUgaXMgb25lIGNoaWxkIGl0IG11c3QgYmUgcmVkIGR1ZSB0 byA1KQorICAgICAgICAgKiBhbmQgbm9kZSBtdXN0IGJlIGJsYWNrIGR1ZSB0byA0KS4gV2UgYWRq dXN0IGNvbG9ycyBsb2NhbGx5CisgICAgICAgICAqIHNvIGFzIHRvIGJ5cGFzcyBfX3JiX2VyYXNl X2NvbG9yKCkgbGF0ZXIgb24uCisgICAgICAgICAqLwogCiAgICAgICAgIHBhcmVudCA9IHJiX3Bh cmVudChub2RlKTsKLSAgICAgICAgY29sb3IgPSByYl9jb2xvcihub2RlKTsKLQotICAgICAgICBp ZiAoY2hpbGQpCi0gICAgICAgICAgICByYl9zZXRfcGFyZW50KGNoaWxkLCBwYXJlbnQpOwogICAg ICAgICBfX3JiX2NoYW5nZV9jaGlsZChub2RlLCBjaGlsZCwgcGFyZW50LCByb290KTsKKyAgICAg ICAgaWYgKGNoaWxkKQorICAgICAgICB7CisgICAgICAgICAgICByYl9zZXRfcGFyZW50X2NvbG9y KGNoaWxkLCBwYXJlbnQsIFJCX0JMQUNLKTsKKyAgICAgICAgICAgIHJlYmFsYW5jZSA9IE5VTEw7 CisgICAgICAgIH0gZWxzZSB7CisgICAgICAgICAgICByZWJhbGFuY2UgPSByYl9pc19ibGFjayhu b2RlKSA/IHBhcmVudCA6IE5VTEw7CisgICAgICAgIH0KICAgICB9IGVsc2UgaWYgKCFjaGlsZCkg ewogICAgICAgICAvKiBTdGlsbCBjYXNlIDEsIGJ1dCB0aGlzIHRpbWUgdGhlIGNoaWxkIGlzIG5v ZGUtPnJiX2xlZnQgKi8KLSAgICAgICAgY2hpbGQgPSB0bXA7Ci0gICAgICAgIGdvdG8gY2FzZTE7 CisgICAgICAgIHBhcmVudCA9IHJiX3BhcmVudChub2RlKTsKKyAgICAgICAgX19yYl9jaGFuZ2Vf Y2hpbGQobm9kZSwgdG1wLCBwYXJlbnQsIHJvb3QpOworICAgICAgICByYl9zZXRfcGFyZW50X2Nv bG9yKHRtcCwgcGFyZW50LCBSQl9CTEFDSyk7CisgICAgICAgIHJlYmFsYW5jZSA9IE5VTEw7CiAg ICAgfSBlbHNlIHsKICAgICAgICAgc3RydWN0IHJiX25vZGUgKm9sZCA9IG5vZGUsICpsZWZ0Owog CkBAIC00MDYsMjcgKzQyNCwzMSBAQCB2b2lkIHJiX2VyYXNlKHN0cnVjdCByYl9ub2RlICpub2Rl LCBzdHJ1Y3QgcmJfcm9vdCAqcm9vdCkKIAogICAgICAgICBjaGlsZCA9IG5vZGUtPnJiX3JpZ2h0 OwogICAgICAgICBwYXJlbnQgPSByYl9wYXJlbnQobm9kZSk7Ci0gICAgICAgIGNvbG9yID0gcmJf Y29sb3Iobm9kZSk7CiAKICAgICAgICAgaWYgKHBhcmVudCA9PSBvbGQpIHsKICAgICAgICAgICAg IHBhcmVudCA9IG5vZGU7CiAgICAgICAgIH0gZWxzZSB7Ci0gICAgICAgICAgICBpZiAoY2hpbGQp Ci0gICAgICAgICAgICAgICAgcmJfc2V0X3BhcmVudChjaGlsZCwgcGFyZW50KTsKICAgICAgICAg ICAgIHBhcmVudC0+cmJfbGVmdCA9IGNoaWxkOwogCiAgICAgICAgICAgICBub2RlLT5yYl9yaWdo dCA9IG9sZC0+cmJfcmlnaHQ7CiAgICAgICAgICAgICByYl9zZXRfcGFyZW50KG9sZC0+cmJfcmln aHQsIG5vZGUpOwogICAgICAgICB9CiAKKyAgICAgICAgaWYgKGNoaWxkKSB7CisgICAgICAgICAg ICByYl9zZXRfcGFyZW50X2NvbG9yKGNoaWxkLCBwYXJlbnQsIFJCX0JMQUNLKTsKKyAgICAgICAg ICAgIHJlYmFsYW5jZSA9IE5VTEw7CisgICAgICAgIH0gZWxzZSB7CisgICAgICAgICAgICByZWJh bGFuY2UgPSByYl9pc19ibGFjayhub2RlKSA/IHBhcmVudCA6IE5VTEw7CisgICAgICAgIH0KKwog ICAgICAgICBub2RlLT5fX3JiX3BhcmVudF9jb2xvciA9IG9sZC0+X19yYl9wYXJlbnRfY29sb3I7 CiAgICAgICAgIG5vZGUtPnJiX2xlZnQgPSBvbGQtPnJiX2xlZnQ7CiAKICAgICAgICAgcmJfc2V0 X3BhcmVudChvbGQtPnJiX2xlZnQsIG5vZGUpOwogICAgIH0KIAotICAgIGlmIChjb2xvciA9PSBS Ql9CTEFDSykKLSAgICAgICAgX19yYl9lcmFzZV9jb2xvcihjaGlsZCwgcGFyZW50LCByb290KTsK KyAgICBpZiAocmViYWxhbmNlKQorICAgICAgICBfX3JiX2VyYXNlX2NvbG9yKHJlYmFsYW5jZSwg cm9vdCk7CiB9CiBFWFBPUlRfU1lNQk9MKHJiX2VyYXNlKTsKIAotLSAKMi4xMi4wCgoKX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KWGVuLWRldmVsIG1haWxp bmcgbGlzdApYZW4tZGV2ZWxAbGlzdHMueGVuLm9yZwpodHRwczovL2xpc3RzLnhlbi5vcmcveGVu LWRldmVsCg==