125396 2013-12-07 13:14:44 -0800 [CSS Grid Layout] Do log(n) search in the named line vectors when positioning named line spans 2014-05-27 07:38:02 -0700 1 1 1 Unclassified WebKit Layout and Rendering 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED BlinkMergeCandidate P2 Normal --- 133304 1 rniwa webkit-unassigned ap commit-queue dino esprehn+autocc glenn hyatt kling kondapallykalyan llango.u-szeged rego rniwa simon.fraser xan.lopez oldest_to_newest 957543 0 rniwa 2013-12-07 13:14:44 -0800 Consider merging https://chromium.googlesource.com/chromium/blink/+/9fc477af0be708c490a6b90e65e412b0c22b161f Implement the suggested FIXMEs and do a log search in the named line vectors. This maintains the previous (somewhat tricky) behavior by using std::lower_bound and std::upper_bound. No difference in existing performance tests, but should scale much better for big grids. 958285 1 218852 llango.u-szeged 2013-12-10 04:28:01 -0800 Created attachment 218852 Patch 974229 2 218852 kling 2014-01-30 23:35:48 -0800 Comment on attachment 218852 Patch OK 974240 3 218852 commit-queue 2014-01-31 00:05:30 -0800 Comment on attachment 218852 Patch Clearing flags on attachment: 218852 Committed r163166: <http://trac.webkit.org/changeset/163166> 974241 4 commit-queue 2014-01-31 00:05:34 -0800 All reviewed patches have been landed. Closing bug. 218852 2013-12-10 04:28:01 -0800 2014-01-31 00:05:30 -0800 Patch bug-125396-20131210042800.patch text/plain 4102 llango.u-szeged U3VidmVyc2lvbiBSZXZpc2lvbjogMTYwMzQ5CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggOWIwNzA2OTViNGMyNzhm NjExZWNiODAwMzZiNGQ2MTU4NGY3ZTk2OC4uMjZlMTk0MTc5MjZlYWFhMGU5MGM4NDQxZGI0YmUy ZjIxZmIzNWRmMCAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDI0IEBACisyMDEzLTEyLTEwICBMw6Fz emzDsyBMYW5nw7MgIDxsYW5nb0BpbmYudS1zemVnZWQuaHU+CisKKyAgICAgICAgW0NTUyBHcmlk IExheW91dF0gRG8gbG9nKG4pIHNlYXJjaCBpbiB0aGUgbmFtZWQgbGluZSB2ZWN0b3JzIHdoZW4g cG9zaXRpb25pbmcgbmFtZWQgbGluZSBzcGFucy4KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtp dC5vcmcvc2hvd19idWcuY2dpP2lkPTEyNTM5NgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9E WSAoT09QUyEpLgorCisgICAgICAgIEltcGxlbWVudCB0aGUgc3VnZ2VzdGVkIEZJWE1FcyBhbmQg ZG8gYSBsb2cgc2VhcmNoIGluIHRoZSBuYW1lZCBsaW5lCisgICAgICAgIHZlY3RvcnMuIFRoaXMg bWFpbnRhaW5zIHRoZSBwcmV2aW91cyAoc29tZXdoYXQgdHJpY2t5KSBiZWhhdmlvciBieQorICAg ICAgICB1c2luZyBzdGQ6Omxvd2VyX2JvdW5kIGFuZCBzdGQ6OnVwcGVyX2JvdW5kLiBObyBkaWZm ZXJlbmNlIGluIGV4aXN0aW5nCisgICAgICAgIHBlcmZvcm1hbmNlIHRlc3RzLCBidXQgc2hvdWxk IHNjYWxlIG11Y2ggYmV0dGVyIGZvciBiaWcgZ3JpZHMuCisKKyAgICAgICAgQmFja3BvcnRlZCBm cm9tIEJsaW5rOgorICAgICAgICBodHRwczovL2Nocm9taXVtLmdvb2dsZXNvdXJjZS5jb20vY2hy b21pdW0vYmxpbmsvKy85ZmM0NzdhZjBiZTcwOGM0OTBhNmI5MGU2NWU0MTJiMGMyMmIxNjFmCisK KyAgICAgICAgTm8gbmV3IHRlc3RzLCBubyBiZWhhdmlvciBjaGFuZ2UuCisKKyAgICAgICAgKiBy ZW5kZXJpbmcvUmVuZGVyR3JpZC5jcHA6CisgICAgICAgIChXZWJDb3JlOjpSZW5kZXJHcmlkOjpy ZXNvbHZlUm93U3RhcnRDb2x1bW5TdGFydE5hbWVkR3JpZExpbmVQb3NpdGlvbkFnYWluc3RPcHBv c2l0ZVBvc2l0aW9uKToKKyAgICAgICAgKFdlYkNvcmU6OlJlbmRlckdyaWQ6OnJlc29sdmVSb3dF bmRDb2x1bW5FbmROYW1lZEdyaWRMaW5lUG9zaXRpb25BZ2FpbnN0T3Bwb3NpdGVQb3NpdGlvbik6 CisKIDIwMTMtMTItMDkgIEFuZHJlYXMgS2xpbmcgIDxha2xpbmdAYXBwbGUuY29tPgogCiAgICAg ICAgIENsZWFyIG91dCBmb250IHdpZHRoIG1lYXN1cmVtZW50IGNhY2hlcyBvbiBtZW1vcnkgcHJl c3N1cmUuCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9yZW5kZXJpbmcvUmVuZGVyR3JpZC5j cHAgYi9Tb3VyY2UvV2ViQ29yZS9yZW5kZXJpbmcvUmVuZGVyR3JpZC5jcHAKaW5kZXggZjQwZmRh YzFiMjk2NjkyNmUwNjBjYjdmMWMwZjczYzEyZDFiNzM5Yy4uMzVkZGE3OTZlMGNlZDA4YjRkOTZm OGZkMjJjOTViYTQxZWVjYTAyYyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvcmVuZGVyaW5n L1JlbmRlckdyaWQuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJHcmlk LmNwcApAQCAtMTAwOSw5ICsxMDA5LDEwIEBAIFBhc3NPd25QdHI8R3JpZFNwYW4+IFJlbmRlckdy aWQ6OnJlc29sdmVSb3dTdGFydENvbHVtblN0YXJ0TmFtZWRHcmlkTGluZVBvc2l0aW9uCiB7CiAg ICAgLy8gVGhlIGdyaWQgbGluZSBpbmVxdWFsaXR5IG5lZWRzIHRvIGJlIHN0cmljdCAod2hpY2gg ZG9lc24ndCBtYXRjaCB0aGUgYWZ0ZXIgLyBlbmQgY2FzZSkgYmVjYXVzZSB8cmVzb2x2ZWRPcHBv c2l0ZVBvc2l0aW9ufAogICAgIC8vIGlzIGFscmVhZHkgY29udmVydGVkIHRvIGFuIGluZGV4IGlu IG91ciBncmlkIHJlcHJlc2VudGF0aW9uIChpZSBvbmUgd2FzIHJlbW92ZWQgZnJvbSB0aGUgZ3Jp ZCBsaW5lIHRvIGFjY291bnQgZm9yIHRoZSBzaWRlKS4KLSAgICAvLyBGSVhNRTogVGhpcyBjb3Vs ZCBiZSBhIGJpbmFyeSBzZWFyY2ggYXMgfGdyaWRMaW5lc3wgaXMgb3JkZXJlZC4KLSAgICBpbnQg Zmlyc3RMaW5lQmVmb3JlT3Bwb3NpdGVQb3NpdGlvbkluZGV4ID0gZ3JpZExpbmVzLnNpemUoKSAt IDE7Ci0gICAgZm9yICg7IGZpcnN0TGluZUJlZm9yZU9wcG9zaXRlUG9zaXRpb25JbmRleCA+PSAw ICYmIGdyaWRMaW5lc1tmaXJzdExpbmVCZWZvcmVPcHBvc2l0ZVBvc2l0aW9uSW5kZXhdID4gcmVz b2x2ZWRPcHBvc2l0ZVBvc2l0aW9uOyAtLWZpcnN0TGluZUJlZm9yZU9wcG9zaXRlUG9zaXRpb25J bmRleCkgeyB9CisgICAgc2l6ZV90IGZpcnN0TGluZUJlZm9yZU9wcG9zaXRlUG9zaXRpb25JbmRl eCA9IDA7CisgICAgY29uc3Qgc2l6ZV90KiBmaXJzdExpbmVCZWZvcmVPcHBvc2l0ZVBvc2l0aW9u ID0gc3RkOjpsb3dlcl9ib3VuZChncmlkTGluZXMuYmVnaW4oKSwgZ3JpZExpbmVzLmVuZCgpLCBy ZXNvbHZlZE9wcG9zaXRlUG9zaXRpb24pOworICAgIGlmIChmaXJzdExpbmVCZWZvcmVPcHBvc2l0 ZVBvc2l0aW9uICE9IGdyaWRMaW5lcy5lbmQoKSkKKyAgICAgICAgZmlyc3RMaW5lQmVmb3JlT3Bw b3NpdGVQb3NpdGlvbkluZGV4ID0gZmlyc3RMaW5lQmVmb3JlT3Bwb3NpdGVQb3NpdGlvbiAtIGdy aWRMaW5lcy5iZWdpbigpOwogCiAgICAgc2l6ZV90IGdyaWRMaW5lSW5kZXggPSBzdGQ6Om1heDxp bnQ+KDAsIGZpcnN0TGluZUJlZm9yZU9wcG9zaXRlUG9zaXRpb25JbmRleCAtIHBvc2l0aW9uLnNw YW5Qb3NpdGlvbigpICsgMSk7CiAgICAgc2l6ZV90IHJlc29sdmVkR3JpZExpbmVQb3NpdGlvbiA9 IGdyaWRMaW5lc1tncmlkTGluZUluZGV4XTsKQEAgLTEwMjIsOSArMTAyMywxMCBAQCBQYXNzT3du UHRyPEdyaWRTcGFuPiBSZW5kZXJHcmlkOjpyZXNvbHZlUm93U3RhcnRDb2x1bW5TdGFydE5hbWVk R3JpZExpbmVQb3NpdGlvbgogCiBQYXNzT3duUHRyPEdyaWRTcGFuPiBSZW5kZXJHcmlkOjpyZXNv bHZlUm93RW5kQ29sdW1uRW5kTmFtZWRHcmlkTGluZVBvc2l0aW9uQWdhaW5zdE9wcG9zaXRlUG9z aXRpb24oc2l6ZV90IHJlc29sdmVkT3Bwb3NpdGVQb3NpdGlvbiwgY29uc3QgR3JpZFBvc2l0aW9u JiBwb3NpdGlvbiwgY29uc3QgVmVjdG9yPHNpemVfdD4mIGdyaWRMaW5lcykgY29uc3QKIHsKLSAg ICAvLyBGSVhNRTogVGhpcyBjb3VsZCBiZSBhIGJpbmFyeSBzZWFyY2ggYXMgfGdyaWRMaW5lc3wg aXMgb3JkZXJlZC4KLSAgICBzaXplX3QgZmlyc3RMaW5lQWZ0ZXJPcHBvc2l0ZVBvc2l0aW9uSW5k ZXggPSAwOwotICAgIGZvciAoOyBmaXJzdExpbmVBZnRlck9wcG9zaXRlUG9zaXRpb25JbmRleCA8 IGdyaWRMaW5lcy5zaXplKCkgJiYgZ3JpZExpbmVzW2ZpcnN0TGluZUFmdGVyT3Bwb3NpdGVQb3Np dGlvbkluZGV4XSA8PSByZXNvbHZlZE9wcG9zaXRlUG9zaXRpb247ICsrZmlyc3RMaW5lQWZ0ZXJP cHBvc2l0ZVBvc2l0aW9uSW5kZXgpIHsgfQorICAgIHNpemVfdCBmaXJzdExpbmVBZnRlck9wcG9z aXRlUG9zaXRpb25JbmRleCA9IGdyaWRMaW5lcy5zaXplKCkgLSAxOworICAgIGNvbnN0IHNpemVf dCogZmlyc3RMaW5lQWZ0ZXJPcHBvc2l0ZVBvc2l0aW9uID0gc3RkOjp1cHBlcl9ib3VuZChncmlk TGluZXMuYmVnaW4oKSwgZ3JpZExpbmVzLmVuZCgpLCByZXNvbHZlZE9wcG9zaXRlUG9zaXRpb24p OworICAgIGlmIChmaXJzdExpbmVBZnRlck9wcG9zaXRlUG9zaXRpb24gIT0gZ3JpZExpbmVzLmVu ZCgpKQorICAgICAgICBmaXJzdExpbmVBZnRlck9wcG9zaXRlUG9zaXRpb25JbmRleCA9IGZpcnN0 TGluZUFmdGVyT3Bwb3NpdGVQb3NpdGlvbiAtIGdyaWRMaW5lcy5iZWdpbigpOwogCiAgICAgc2l6 ZV90IGdyaWRMaW5lSW5kZXggPSBzdGQ6Om1pbihncmlkTGluZXMuc2l6ZSgpIC0gMSwgZmlyc3RM aW5lQWZ0ZXJPcHBvc2l0ZVBvc2l0aW9uSW5kZXggKyBwb3NpdGlvbi5zcGFuUG9zaXRpb24oKSAt IDEpOwogICAgIHNpemVfdCByZXNvbHZlZEdyaWRMaW5lUG9zaXRpb24gPSBhZGp1c3RHcmlkUG9z aXRpb25Gb3JSb3dFbmRDb2x1bW5FbmRTaWRlKGdyaWRMaW5lc1tncmlkTGluZUluZGV4XSk7Cg==