From mboxrd@z Thu Jan  1 00:00:00 1970
From: Andre Przywara <andre.przywara@linaro.org>
Subject: [PATCH v2 17/45] Add list_sort() routine from Linux
Date: Thu, 15 Mar 2018 20:30:22 +0000
Message-ID: <20180315203050.19791-18-andre.przywara@linaro.org>
References: <20180315203050.19791-1-andre.przywara@linaro.org>
Mime-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
Return-path: <xen-devel-bounces@lists.xenproject.org>
Received: from us1-rack-dfw2.inumbo.com ([104.130.134.6])
 by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from
 <srs0=jxrf=gf=linaro.org=andre.przywara@srs-us1.protection.inumbo.net>)
 id 1ewZX4-0003P6-Rl
 for xen-devel@lists.xenproject.org; Thu, 15 Mar 2018 20:31:26 +0000
Received: by mail-wm0-x241.google.com with SMTP id s206so24730985wme.0
 for <xen-devel@lists.xenproject.org>; Thu, 15 Mar 2018 13:31:24 -0700 (PDT)
In-Reply-To: <20180315203050.19791-1-andre.przywara@linaro.org>
List-Unsubscribe: <https://lists.xenproject.org/mailman/options/xen-devel>,
 <mailto:xen-devel-request@lists.xenproject.org?subject=unsubscribe>
List-Post: <mailto:xen-devel@lists.xenproject.org>
List-Help: <mailto:xen-devel-request@lists.xenproject.org?subject=help>
List-Subscribe: <https://lists.xenproject.org/mailman/listinfo/xen-devel>,
 <mailto:xen-devel-request@lists.xenproject.org?subject=subscribe>
Errors-To: xen-devel-bounces@lists.xenproject.org
Sender: "Xen-devel" <xen-devel-bounces@lists.xenproject.org>
To: Stefano Stabellini <sstabellini@kernel.org>, Julien Grall <julien.grall@arm.com>
Cc: Wei Liu <wei.liu2@citrix.com>, George Dunlap <George.Dunlap@eu.citrix.com>, Andrew Cooper <andrew.cooper3@citrix.com>, Ian Jackson <ian.jackson@eu.citrix.com>, Tim Deegan <tim@xen.org>, Jan Beulich <jbeulich@suse.com>, xen-devel@lists.xenproject.org
List-Id: xen-devel@lists.xenproject.org

VGhpcyBwdWxscyBpbiBMaW51eCcgbGlzdF9zb3J0LmMsIHdoaWNoIGlzIGEgbWVyZ2Ugc29ydCBp
bXBsZW1lbnRhdGlvbgpmb3IgbGlua2VkIGxpc3RzLiBBcGFydCBmcm9tIGFkZGluZyBhIGZ1bGwg
ZmVhdHVyZWQgbGljZW5zZSBoZWFkZXIgYW5kCmFkanVzdGluZyB0aGUgI2luY2x1ZGUgZmlsZSwg
bm90aGluZyBoYXMgYmVlbiBjaGFuZ2VkIGluIHRoaXMgY29kZS4KClNpZ25lZC1vZmYtYnk6IEFu
ZHJlIFByenl3YXJhIDxhbmRyZS5wcnp5d2FyYUBsaW5hcm8ub3JnPgotLS0KQ2hhbmdlbG9nIHYx
IC4uLiB2MjoKLSBzcGxpdCBvdXQgdG8ganVzdCBjb250YWluIExpbnV4IGNvZGUgZHVtcAoKIHhl
bi9jb21tb24vbGlzdF9zb3J0LmMgICAgICB8IDE1NyArKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKysrKysrKwogeGVuL2luY2x1ZGUveGVuL2xpc3Rfc29ydC5oIHwgIDExICsr
KysKIDIgZmlsZXMgY2hhbmdlZCwgMTY4IGluc2VydGlvbnMoKykKIGNyZWF0ZSBtb2RlIDEwMDY0
NCB4ZW4vY29tbW9uL2xpc3Rfc29ydC5jCiBjcmVhdGUgbW9kZSAxMDA2NDQgeGVuL2luY2x1ZGUv
eGVuL2xpc3Rfc29ydC5oCgpkaWZmIC0tZ2l0IGEveGVuL2NvbW1vbi9saXN0X3NvcnQuYyBiL3hl
bi9jb21tb24vbGlzdF9zb3J0LmMKbmV3IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAw
MC4uYWYyYjJmNjUxOQotLS0gL2Rldi9udWxsCisrKyBiL3hlbi9jb21tb24vbGlzdF9zb3J0LmMK
QEAgLTAsMCArMSwxNTcgQEAKKy8qCisgKiBsaXN0X3NvcnQuYzogbWVyZ2Ugc29ydCBpbXBsZW1l
bnRhdGlvbiBmb3IgbGlua2VkIGxpc3RzCisgKiBDb3BpZWQgZnJvbSB0aGUgTGludXgga2VybmVs
IChsaWIvbGlzdF9zb3J0LmMpCisgKgorICogVGhpcyBwcm9ncmFtIGlzIGZyZWUgc29mdHdhcmU7
IHlvdSBjYW4gcmVkaXN0cmlidXRlIGl0IGFuZC9vciBtb2RpZnkgaXQKKyAqIHVuZGVyIHRoZSB0
ZXJtcyBhbmQgY29uZGl0aW9ucyBvZiB0aGUgR05VIEdlbmVyYWwgUHVibGljIExpY2Vuc2UsCisg
KiB2ZXJzaW9uIDIsIGFzIHB1Ymxpc2hlZCBieSB0aGUgRnJlZSBTb2Z0d2FyZSBGb3VuZGF0aW9u
LgorICoKKyAqIFRoaXMgcHJvZ3JhbSBpcyBkaXN0cmlidXRlZCBpbiB0aGUgaG9wZSBpdCB3aWxs
IGJlIHVzZWZ1bCwgYnV0IFdJVEhPVVQKKyAqIEFOWSBXQVJSQU5UWTsgd2l0aG91dCBldmVuIHRo
ZSBpbXBsaWVkIHdhcnJhbnR5IG9mIE1FUkNIQU5UQUJJTElUWSBvcgorICogRklUTkVTUyBGT1Ig
QSBQQVJUSUNVTEFSIFBVUlBPU0UuICBTZWUgdGhlIEdOVSBHZW5lcmFsIFB1YmxpYyBMaWNlbnNl
IGZvcgorICogbW9yZSBkZXRhaWxzLgorICoKKyAqIFlvdSBzaG91bGQgaGF2ZSByZWNlaXZlZCBh
IGNvcHkgb2YgdGhlIEdOVSBHZW5lcmFsIFB1YmxpYyBMaWNlbnNlIGFsb25nIHdpdGgKKyAqIHRo
aXMgcHJvZ3JhbTsgSWYgbm90LCBzZWUgPGh0dHA6Ly93d3cuZ251Lm9yZy9saWNlbnNlcy8+Lgor
ICovCisKKyNpbmNsdWRlIDx4ZW4vbGliLmg+CisjaW5jbHVkZSA8eGVuL2xpc3QuaD4KKworI2Rl
ZmluZSBNQVhfTElTVF9MRU5HVEhfQklUUyAyMAorCisvKgorICogUmV0dXJucyBhIGxpc3Qgb3Jn
YW5pemVkIGluIGFuIGludGVybWVkaWF0ZSBmb3JtYXQgc3VpdGVkCisgKiB0byBjaGFpbmluZyBv
ZiBtZXJnZSgpIGNhbGxzOiBudWxsLXRlcm1pbmF0ZWQsIG5vIHJlc2VydmVkIG9yCisgKiBzZW50
aW5lbCBoZWFkIG5vZGUsICJwcmV2IiBsaW5rcyBub3QgbWFpbnRhaW5lZC4KKyAqLworc3RhdGlj
IHN0cnVjdCBsaXN0X2hlYWQgKm1lcmdlKHZvaWQgKnByaXYsCisJCQkJaW50ICgqY21wKSh2b2lk
ICpwcml2LCBzdHJ1Y3QgbGlzdF9oZWFkICphLAorCQkJCQlzdHJ1Y3QgbGlzdF9oZWFkICpiKSwK
KwkJCQlzdHJ1Y3QgbGlzdF9oZWFkICphLCBzdHJ1Y3QgbGlzdF9oZWFkICpiKQoreworCXN0cnVj
dCBsaXN0X2hlYWQgaGVhZCwgKnRhaWwgPSAmaGVhZDsKKworCXdoaWxlIChhICYmIGIpIHsKKwkJ
LyogaWYgZXF1YWwsIHRha2UgJ2EnIC0tIGltcG9ydGFudCBmb3Igc29ydCBzdGFiaWxpdHkgKi8K
KwkJaWYgKCgqY21wKShwcml2LCBhLCBiKSA8PSAwKSB7CisJCQl0YWlsLT5uZXh0ID0gYTsKKwkJ
CWEgPSBhLT5uZXh0OworCQl9IGVsc2UgeworCQkJdGFpbC0+bmV4dCA9IGI7CisJCQliID0gYi0+
bmV4dDsKKwkJfQorCQl0YWlsID0gdGFpbC0+bmV4dDsKKwl9CisJdGFpbC0+bmV4dCA9IGE/OmI7
CisJcmV0dXJuIGhlYWQubmV4dDsKK30KKworLyoKKyAqIENvbWJpbmUgZmluYWwgbGlzdCBtZXJn
ZSB3aXRoIHJlc3RvcmF0aW9uIG9mIHN0YW5kYXJkIGRvdWJseS1saW5rZWQKKyAqIGxpc3Qgc3Ry
dWN0dXJlLiAgVGhpcyBhcHByb2FjaCBkdXBsaWNhdGVzIGNvZGUgZnJvbSBtZXJnZSgpLCBidXQK
KyAqIHJ1bnMgZmFzdGVyIHRoYW4gdGhlIHRpZGllciBhbHRlcm5hdGl2ZXMgb2YgZWl0aGVyIGEg
c2VwYXJhdGUgZmluYWwKKyAqIHByZXYtbGluayByZXN0b3JhdGlvbiBwYXNzLCBvciBtYWludGFp
bmluZyB0aGUgcHJldiBsaW5rcworICogdGhyb3VnaG91dC4KKyAqLworc3RhdGljIHZvaWQgbWVy
Z2VfYW5kX3Jlc3RvcmVfYmFja19saW5rcyh2b2lkICpwcml2LAorCQkJCWludCAoKmNtcCkodm9p
ZCAqcHJpdiwgc3RydWN0IGxpc3RfaGVhZCAqYSwKKwkJCQkJc3RydWN0IGxpc3RfaGVhZCAqYiks
CisJCQkJc3RydWN0IGxpc3RfaGVhZCAqaGVhZCwKKwkJCQlzdHJ1Y3QgbGlzdF9oZWFkICphLCBz
dHJ1Y3QgbGlzdF9oZWFkICpiKQoreworCXN0cnVjdCBsaXN0X2hlYWQgKnRhaWwgPSBoZWFkOwor
CXU4IGNvdW50ID0gMDsKKworCXdoaWxlIChhICYmIGIpIHsKKwkJLyogaWYgZXF1YWwsIHRha2Ug
J2EnIC0tIGltcG9ydGFudCBmb3Igc29ydCBzdGFiaWxpdHkgKi8KKwkJaWYgKCgqY21wKShwcml2
LCBhLCBiKSA8PSAwKSB7CisJCQl0YWlsLT5uZXh0ID0gYTsKKwkJCWEtPnByZXYgPSB0YWlsOwor
CQkJYSA9IGEtPm5leHQ7CisJCX0gZWxzZSB7CisJCQl0YWlsLT5uZXh0ID0gYjsKKwkJCWItPnBy
ZXYgPSB0YWlsOworCQkJYiA9IGItPm5leHQ7CisJCX0KKwkJdGFpbCA9IHRhaWwtPm5leHQ7CisJ
fQorCXRhaWwtPm5leHQgPSBhID8gOiBiOworCisJZG8geworCQkvKgorCQkgKiBJbiB3b3JzdCBj
YXNlcyB0aGlzIGxvb3AgbWF5IHJ1biBtYW55IGl0ZXJhdGlvbnMuCisJCSAqIENvbnRpbnVlIGNh
bGxiYWNrcyB0byB0aGUgY2xpZW50IGV2ZW4gdGhvdWdoIG5vCisJCSAqIGVsZW1lbnQgY29tcGFy
aXNvbiBpcyBuZWVkZWQsIHNvIHRoZSBjbGllbnQncyBjbXAoKQorCQkgKiByb3V0aW5lIGNhbiBp
bnZva2UgY29uZF9yZXNjaGVkKCkgcGVyaW9kaWNhbGx5LgorCQkgKi8KKwkJaWYgKHVubGlrZWx5
KCEoKytjb3VudCkpKQorCQkJKCpjbXApKHByaXYsIHRhaWwtPm5leHQsIHRhaWwtPm5leHQpOwor
CisJCXRhaWwtPm5leHQtPnByZXYgPSB0YWlsOworCQl0YWlsID0gdGFpbC0+bmV4dDsKKwl9IHdo
aWxlICh0YWlsLT5uZXh0KTsKKworCXRhaWwtPm5leHQgPSBoZWFkOworCWhlYWQtPnByZXYgPSB0
YWlsOworfQorCisvKioKKyAqIGxpc3Rfc29ydCAtIHNvcnQgYSBsaXN0CisgKiBAcHJpdjogcHJp
dmF0ZSBkYXRhLCBvcGFxdWUgdG8gbGlzdF9zb3J0KCksIHBhc3NlZCB0byBAY21wCisgKiBAaGVh
ZDogdGhlIGxpc3QgdG8gc29ydAorICogQGNtcDogdGhlIGVsZW1lbnRzIGNvbXBhcmlzb24gZnVu
Y3Rpb24KKyAqCisgKiBUaGlzIGZ1bmN0aW9uIGltcGxlbWVudHMgIm1lcmdlIHNvcnQiLCB3aGlj
aCBoYXMgTyhubG9nKG4pKQorICogY29tcGxleGl0eS4KKyAqCisgKiBUaGUgY29tcGFyaXNvbiBm
dW5jdGlvbiBAY21wIG11c3QgcmV0dXJuIGEgbmVnYXRpdmUgdmFsdWUgaWYgQGEKKyAqIHNob3Vs
ZCBzb3J0IGJlZm9yZSBAYiwgYW5kIGEgcG9zaXRpdmUgdmFsdWUgaWYgQGEgc2hvdWxkIHNvcnQg
YWZ0ZXIKKyAqIEBiLiBJZiBAYSBhbmQgQGIgYXJlIGVxdWl2YWxlbnQsIGFuZCB0aGVpciBvcmln
aW5hbCByZWxhdGl2ZQorICogb3JkZXJpbmcgaXMgdG8gYmUgcHJlc2VydmVkLCBAY21wIG11c3Qg
cmV0dXJuIDAuCisgKi8KK3ZvaWQgbGlzdF9zb3J0KHZvaWQgKnByaXYsIHN0cnVjdCBsaXN0X2hl
YWQgKmhlYWQsCisJCWludCAoKmNtcCkodm9pZCAqcHJpdiwgc3RydWN0IGxpc3RfaGVhZCAqYSwK
KwkJCXN0cnVjdCBsaXN0X2hlYWQgKmIpKQoreworCXN0cnVjdCBsaXN0X2hlYWQgKnBhcnRbTUFY
X0xJU1RfTEVOR1RIX0JJVFMrMV07IC8qIHNvcnRlZCBwYXJ0aWFsIGxpc3RzCisJCQkJCQktLSBs
YXN0IHNsb3QgaXMgYSBzZW50aW5lbCAqLworCWludCBsZXY7ICAvKiBpbmRleCBpbnRvIHBhcnRb
XSAqLworCWludCBtYXhfbGV2ID0gMDsKKwlzdHJ1Y3QgbGlzdF9oZWFkICpsaXN0OworCisJaWYg
KGxpc3RfZW1wdHkoaGVhZCkpCisJCXJldHVybjsKKworCW1lbXNldChwYXJ0LCAwLCBzaXplb2Yo
cGFydCkpOworCisJaGVhZC0+cHJldi0+bmV4dCA9IE5VTEw7CisJbGlzdCA9IGhlYWQtPm5leHQ7
CisKKwl3aGlsZSAobGlzdCkgeworCQlzdHJ1Y3QgbGlzdF9oZWFkICpjdXIgPSBsaXN0OworCQls
aXN0ID0gbGlzdC0+bmV4dDsKKwkJY3VyLT5uZXh0ID0gTlVMTDsKKworCQlmb3IgKGxldiA9IDA7
IHBhcnRbbGV2XTsgbGV2KyspIHsKKwkJCWN1ciA9IG1lcmdlKHByaXYsIGNtcCwgcGFydFtsZXZd
LCBjdXIpOworCQkJcGFydFtsZXZdID0gTlVMTDsKKwkJfQorCQlpZiAobGV2ID4gbWF4X2xldikg
eworCQkJaWYgKHVubGlrZWx5KGxldiA+PSBBUlJBWV9TSVpFKHBhcnQpLTEpKSB7CisJCQkJZHBy
aW50ayhYRU5MT0dfREVCVUcsCisJCQkJCSJsaXN0IHRvbyBsb25nIGZvciBlZmZpY2llbmN5XG4i
KTsKKwkJCQlsZXYtLTsKKwkJCX0KKwkJCW1heF9sZXYgPSBsZXY7CisJCX0KKwkJcGFydFtsZXZd
ID0gY3VyOworCX0KKworCWZvciAobGV2ID0gMDsgbGV2IDwgbWF4X2xldjsgbGV2KyspCisJCWlm
IChwYXJ0W2xldl0pCisJCQlsaXN0ID0gbWVyZ2UocHJpdiwgY21wLCBwYXJ0W2xldl0sIGxpc3Qp
OworCisJbWVyZ2VfYW5kX3Jlc3RvcmVfYmFja19saW5rcyhwcml2LCBjbXAsIGhlYWQsIHBhcnRb
bWF4X2xldl0sIGxpc3QpOworfQorRVhQT1JUX1NZTUJPTChsaXN0X3NvcnQpOwpkaWZmIC0tZ2l0
IGEveGVuL2luY2x1ZGUveGVuL2xpc3Rfc29ydC5oIGIveGVuL2luY2x1ZGUveGVuL2xpc3Rfc29y
dC5oCm5ldyBmaWxlIG1vZGUgMTAwNjQ0CmluZGV4IDAwMDAwMDAwMDAuLjEzY2UwYTU1ZWMKLS0t
IC9kZXYvbnVsbAorKysgYi94ZW4vaW5jbHVkZS94ZW4vbGlzdF9zb3J0LmgKQEAgLTAsMCArMSwx
MSBAQAorI2lmbmRlZiBfTElOVVhfTElTVF9TT1JUX0gKKyNkZWZpbmUgX0xJTlVYX0xJU1RfU09S
VF9ICisKKyNpbmNsdWRlIDx4ZW4vdHlwZXMuaD4KKworc3RydWN0IGxpc3RfaGVhZDsKKwordm9p
ZCBsaXN0X3NvcnQodm9pZCAqcHJpdiwgc3RydWN0IGxpc3RfaGVhZCAqaGVhZCwKKwkgICAgICAg
aW50ICgqY21wKSh2b2lkICpwcml2LCBzdHJ1Y3QgbGlzdF9oZWFkICphLAorCQkJICBzdHJ1Y3Qg
bGlzdF9oZWFkICpiKSk7CisjZW5kaWYKLS0gCjIuMTQuMQoKCl9fX19fX19fX19fX19fX19fX19f
X19fX19fX19fX19fX19fX19fX19fX19fX19fClhlbi1kZXZlbCBtYWlsaW5nIGxpc3QKWGVuLWRl
dmVsQGxpc3RzLnhlbnByb2plY3Qub3JnCmh0dHBzOi8vbGlzdHMueGVucHJvamVjdC5vcmcvbWFp
bG1hbi9saXN0aW5mby94ZW4tZGV2ZWw=