45507 2010-09-09 17:53:48 -0700 Improve the local{SharedStyle,CousinList} algorithm 2011-02-21 22:48:48 -0800 1 1 1 Unclassified WebKit CSS 528+ (Nightly build) All All RESOLVED FIXED P2 Normal --- 1 jchaffraix jchaffraix commit-queue eric koivisto sam webkit.review.bot oldest_to_newest 276889 0 jchaffraix 2010-09-09 17:53:48 -0700 Currently the algorithm in the CSSStyleSelector to look for cousins iterates twice to avoid a bad runtime complexity. This is arbitrary and will miss some cousin. The idea is to change this algorithm to one that guarantees a number of visited nodes while limiting the exponential complexity (locateCousin is called in a for loop and calls itself recursively). 276951 1 67142 jchaffraix 2010-09-09 19:29:27 -0700 Created attachment 67142 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off 276953 2 webkit.review.bot 2010-09-09 19:30:29 -0700 Attachment 67142 did not pass style-queue: Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1 WebCore/css/CSSStyleSelector.cpp:965: Extra space before ) in if [whitespace/parens] [5] WebCore/css/CSSStyleSelector.cpp:966: This { should be at the end of the previous line [whitespace/braces] [4] WebCore/css/CSSStyleSelector.cpp:975: Extra space before last semicolon. If this should be an empty statement, use { } instead. [whitespace/semicolon] [5] Total errors found: 3 in 3 files If any of these errors are false positives, please file a bug against check-webkit-style. 277594 3 67282 jchaffraix 2010-09-10 18:45:26 -0700 Created attachment 67282 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues) 277898 4 67282 hyatt 2010-09-12 13:07:40 -0700 Comment on attachment 67282 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues) I like it! 293875 5 67282 darin 2010-10-13 18:02:05 -0700 Comment on attachment 67282 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues) View in context: https://bugs.webkit.org/attachment.cgi?id=67282&action=review > WebCore/css/CSSStyleSelector.cpp:949 > +Node* CSSStyleSelector::locateCousinList(Element* parent, unsigned &visitedNodesCount) The "&" goes next to the type rather than next to the variable name. > WebCore/css/CSSStyleSelector.cpp:951 > + if (visitedNodesCount >= (cStyleSearchThreshold * cStyleSearchLevelThreshold)) The parentheses here are not helpful. Please remove them. > WebCore/css/CSSStyleSelector.cpp:1076 > + unsigned visitedNodesCount = 0; The phrase “visited nodes count” is not good grammar, but “visited node count” would be. > WebCore/css/CSSStyleSelector.cpp:1079 > + // FIXME: We should use the ElementTraversal API instead of this for-loop but we need to test the performance implication of this change. I’m glad that you would test performance before making the change, but I don’t agree with the FIXME. Just because element traversal is a public DOM API doesn’t mean it’s a good idea to use it inside the engine. With both previousSibling and isElementNode implemented as efficient inline functions, it’s almost certainly better to call code that can do this inline. If you’d like to come back here and deploy some kind of fast implementation of element traversal, that’s OK, but I do not think it deserves a FIXME comment. > WebCore/css/CSSStyleSelector.h:113 > + Node* locateCousinList(Element* parent, unsigned &visitedNodes); Please move the & next to the type. The name visitedNodes is not good. This variable does not hold nodes, so it should not be named “visited nodes”. I think visitedNodeCount is an acceptable name. 321824 6 eric 2010-12-14 01:51:47 -0800 What's the next step here, Julien? Are you going to post an updated patch? 353311 7 82888 jchaffraix 2011-02-17 18:42:28 -0800 Created attachment 82888 Rebased patch - Also addressed Darin's comments Finally got around to update this patch. Re-applied the logic on top of ToT. 354296 8 koivisto 2011-02-20 11:06:34 -0800 Looks good. Did you measure performance? I would be interested in hearing the sharing percentage on some major web sites with this vs. the old code. It should be easy to find out with some debugging code thrown in. 354913 9 jchaffraix 2011-02-21 17:03:33 -0800 (In reply to comment #8) > Looks good. Did you measure performance? I would be interested in hearing the sharing percentage on some major web sites with this vs. the old code. It should be easy to find out with some debugging code thrown in. We did some sharing measurements on major websites. Most websites were showing small benefits (less than 5%) but on at least 2 (amazon & rakuten.co.jp) we found out that much sharing was missed by the current algorithm. In those 2 cases, the new algorithm would improve the sharing by resp. 33% (amazon) and 16% (rakuten). 355049 10 82888 koivisto 2011-02-21 22:10:38 -0800 Comment on attachment 82888 Rebased patch - Also addressed Darin's comments Nice. r=me assuming layout tests pass. 355073 11 82888 commit-queue 2011-02-21 22:48:42 -0800 Comment on attachment 82888 Rebased patch - Also addressed Darin's comments Clearing flags on attachment: 82888 Committed r79293: <http://trac.webkit.org/changeset/79293> 355074 12 commit-queue 2011-02-21 22:48:48 -0800 All reviewed patches have been landed. Closing bug. 67142 2010-09-09 19:29:27 -0700 2010-09-10 18:45:26 -0700 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off improve-local-SharedStyle-CousinList-algorithm.diff text/plain 7195 jchaffraix ZGlmZiAtLWdpdCBhL1dlYkNvcmUvQ2hhbmdlTG9nIGIvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXgg NDZmMTMzZC4uMDFkZjQwMiAxMDA2NDQKLS0tIGEvV2ViQ29yZS9DaGFuZ2VMb2cKKysrIGIvV2Vi Q29yZS9DaGFuZ2VMb2cKQEAgLTEsMyArMSwyOCBAQAorMjAxMC0wOS0wOSAgSnVsaWVuIENoYWZm cmFpeCA8amNoYWZmcmFpeEBjb2RlYXVyb3JhLm9yZz4KKworICAgICAgICBSZXZpZXdlZCBieSBO T0JPRFkgKE9PUFMhKS4KKworICAgICAgICBJbXByb3ZlIHRoZSBsb2NhbHtTaGFyZWRTdHlsZSxD b3VzaW5MaXN0fSBhbGdvcml0aG0KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hv d19idWcuY2dpP2lkPTQ1NTA3CisKKyAgICAgICAgVGhpcyBjaGFuZ2UgaW1wcm92ZXMgdGhlIGFs Z29yaXRobSB0byBmaW5kIHNoYXJlZCBzdHlsZXM6ICBUaGUgb2xkCisgICAgICAgIGFsZ29yaXRo bSB3b3VsZCBzdG9wIHRoZSBzZWFyY2ggYWZ0ZXIgdGhlIGZpcnN0IGNvdXNpbiwgZXZlbiBpZgor ICAgICAgICB0aGUgc2VhcmNoIHRocmVzaG9sZCBpcyBub3QgbWV0LiBBcyBzdWNoLCB0aGUgYWxn b3JpdGhtIHdvdWxkCisgICAgICAgIHN5c3RlbWF0aWNhbGx5IG1pc3Mgc2hhcmluZ3MgYWNyb3Nz IHNlY29uZCBjb3VzaW5zIGFuZCBiZXlvbmQuCisgICAgICAgIFRoZSBuZXcgYWxnb3JpdGhtIGNv bnRpbnVlcyB0aGUgc2VhcmNoLCBhcyBsb25nIGFzIHRocmVzaG9sZCBpcworICAgICAgICBub3Qg bWV0LiBJdCBhbHNvIHNlcGFyYXRlcyB0aGUgdGhyZXNob2xkIGZvciBzaWJsaW5nL2NvdXNpbnMK KyAgICAgICAgc2VhcmNoLCBmcm9tIHRoYXQgb24gdGhlIGxldmVscyBvZiBzZWFyY2gsIHdoaWNo IGlzIGVhc2llciB0bworICAgICAgICBvcHRpbWl6ZS4KKyAgICAgICAgVGhlIG5ldyBhbGdvcml0 aG0gZmluZHMgdXAgdG8gMzAlIG1vcmUgc2hhcmluZ3Mgb24gc29tZSBzaXRlcworICAgICAgICAo ZS5nLiBhbWF6b24uY29tIGFuZCByYWt1dGVuLmNvLmpwKSB3aXRoIG5vIG5vdGljZWFibGUgc2xv d2Rvd24uCisKKyAgICAgICAgTm8gbmV3IHRlc3QsIHJlZmFjdG9yaW5nIG9ubHkuCisKKyAgICAg ICAgKiBjc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHA6CisgICAgICAgIChXZWJDb3JlOjpDU1NTdHls ZVNlbGVjdG9yOjpsb2NhdGVDb3VzaW5MaXN0KToKKyAgICAgICAgKFdlYkNvcmU6OkNTU1N0eWxl U2VsZWN0b3I6OmxvY2F0ZVNoYXJlZFN0eWxlKToKKyAgICAgICAgKiBjc3MvQ1NTU3R5bGVTZWxl Y3Rvci5oOgorCiAyMDEwLTA5LTA5ICBLZW5uZXRoIFJ1c3NlbGwgIDxrYnJAZ29vZ2xlLmNvbT4K IAogICAgICAgICBSZXZpZXdlZCBieSBKYW1lcyBSb2JpbnNvbi4KZGlmZiAtLWdpdCBhL1dlYkNv cmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuY3BwIGIvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rv ci5jcHAKaW5kZXggNDdkMDFlOC4uYmJlYjMzYSAxMDA2NDQKLS0tIGEvV2ViQ29yZS9jc3MvQ1NT U3R5bGVTZWxlY3Rvci5jcHAKKysrIGIvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAK QEAgLTYsNiArNiw3IEBACiAgKiBDb3B5cmlnaHQgKEMpIDIwMDcgQWxleGV5IFByb3NrdXJ5YWtv diA8YXBAd2Via2l0Lm9yZz4KICAqIENvcHlyaWdodCAoQykgMjAwNywgMjAwOCBFcmljIFNlaWRl bCA8ZXJpY0B3ZWJraXQub3JnPgogICogQ29weXJpZ2h0IChDKSAyMDA4LCAyMDA5IFRvcmNoIE1v YmlsZSBJbmMuIEFsbCByaWdodHMgcmVzZXJ2ZWQuIChodHRwOi8vd3d3LnRvcmNobW9iaWxlLmNv bS8pCisgKiBDb3B5cmlnaHQgKGMpIDIwMTAsIENvZGUgQXVyb3JhIEZvcnVtLiBBbGwgcmlnaHRz IHJlc2VydmVkLgogICoKICAqIFRoaXMgbGlicmFyeSBpcyBmcmVlIHNvZnR3YXJlOyB5b3UgY2Fu IHJlZGlzdHJpYnV0ZSBpdCBhbmQvb3IKICAqIG1vZGlmeSBpdCB1bmRlciB0aGUgdGVybXMgb2Yg dGhlIEdOVSBMaWJyYXJ5IEdlbmVyYWwgUHVibGljCkBAIC05NDMsMzEgKzk0NCwzNiBAQCBib29s IENTU1N0eWxlU2VsZWN0b3I6OlNlbGVjdG9yQ2hlY2tlcjo6Y2hlY2tTZWxlY3RvcihDU1NTZWxl Y3Rvciogc2VsLCBFbGVtZW50KgogfQogCiBzdGF0aWMgY29uc3QgdW5zaWduZWQgY1N0eWxlU2Vh cmNoVGhyZXNob2xkID0gMTA7CitzdGF0aWMgY29uc3QgdW5zaWduZWQgY1N0eWxlU2VhcmNoTGV2 ZWxUaHJlc2hvbGQgPSAxMDsKIAotTm9kZSogQ1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlQ291c2lu TGlzdChFbGVtZW50KiBwYXJlbnQsIHVuc2lnbmVkIGRlcHRoKQorTm9kZSogQ1NTU3R5bGVTZWxl Y3Rvcjo6bG9jYXRlQ291c2luTGlzdChFbGVtZW50KiBwYXJlbnQsIHVuc2lnbmVkICZ2aXNpdGVk Tm9kZXNDb3VudCkKIHsKLSAgICBpZiAocGFyZW50ICYmIHBhcmVudC0+aXNTdHlsZWRFbGVtZW50 KCkpIHsKKyAgICBpZiAodmlzaXRlZE5vZGVzQ291bnQgPCAoY1N0eWxlU2VhcmNoVGhyZXNob2xk ICogY1N0eWxlU2VhcmNoTGV2ZWxUaHJlc2hvbGQpICYmIHBhcmVudCAmJiBwYXJlbnQtPmlzU3R5 bGVkRWxlbWVudCgpKSB7CiAgICAgICAgIFN0eWxlZEVsZW1lbnQqIHAgPSBzdGF0aWNfY2FzdDxT dHlsZWRFbGVtZW50Kj4ocGFyZW50KTsKICAgICAgICAgaWYgKCFwLT5pbmxpbmVTdHlsZURlY2wo KSAmJiAhcC0+aGFzSUQoKSkgewotICAgICAgICAgICAgTm9kZSogciA9IHAtPnByZXZpb3VzU2li bGluZygpOwotICAgICAgICAgICAgdW5zaWduZWQgc3ViY291bnQgPSAwOwogICAgICAgICAgICAg UmVuZGVyU3R5bGUqIHN0ID0gcC0+cmVuZGVyU3R5bGUoKTsKLSAgICAgICAgICAgIHdoaWxlIChy KSB7Ci0gICAgICAgICAgICAgICAgaWYgKHItPnJlbmRlclN0eWxlKCkgPT0gc3QpCi0gICAgICAg ICAgICAgICAgICAgIHJldHVybiByLT5sYXN0Q2hpbGQoKTsKLSAgICAgICAgICAgICAgICBpZiAo c3ViY291bnQrKyA9PSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQpCi0gICAgICAgICAgICAgICAgICAg IHJldHVybiAwOwotICAgICAgICAgICAgICAgIHIgPSByLT5wcmV2aW91c1NpYmxpbmcoKTsKLSAg ICAgICAgICAgIH0KLSAgICAgICAgICAgIGlmICghciAmJiBkZXB0aCA8IGNTdHlsZVNlYXJjaFRo cmVzaG9sZCkKLSAgICAgICAgICAgICAgICByID0gbG9jYXRlQ291c2luTGlzdChwYXJlbnQtPnBh cmVudEVsZW1lbnQoKSwgZGVwdGggKyAxKTsKLSAgICAgICAgICAgIHdoaWxlIChyKSB7Ci0gICAg ICAgICAgICAgICAgaWYgKHItPnJlbmRlclN0eWxlKCkgPT0gc3QpCi0gICAgICAgICAgICAgICAg ICAgIHJldHVybiByLT5sYXN0Q2hpbGQoKTsKLSAgICAgICAgICAgICAgICBpZiAoc3ViY291bnQr KyA9PSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQpCi0gICAgICAgICAgICAgICAgICAgIHJldHVybiAw OwotICAgICAgICAgICAgICAgIHIgPSByLT5wcmV2aW91c1NpYmxpbmcoKTsKLSAgICAgICAgICAg IH0KKyAgICAgICAgICAgIHVuc2lnbmVkIHN1YmNvdW50ID0gMDsKKyAgICAgICAgICAgIE5vZGUq IHRoaXNDb3VzaW4gPSBwOworICAgICAgICAgICAgTm9kZSogciA9IHAtPnByZXZpb3VzU2libGlu ZygpOworCisgICAgICAgICAgICAvLyBSZXNlcnZlIHRoZSB0cmllcyBmb3IgdGhpcyBsZXZlbC4g VGhpcyBlZmZlY3RpdmVseSBtYWtlcyBzdXJlIHRoYXQgdGhlIGFsZ29yaXRobQorICAgICAgICAg ICAgLy8gd2lsbCBuZXZlciBnbyBkZWVwZXIgdGhhbiBjU3R5bGVTZWFyY2hMZXZlbFRocmVzaG9s ZCBsZXZlbHMgaW50byByZWN1cnNpb24uCisgICAgICAgICAgICB2aXNpdGVkTm9kZXNDb3VudCAr PSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQ7CisgICAgICAgICAgICBkbyB7CisgICAgICAgICAgICAg ICAgd2hpbGUgKHIpIHsKKyAgICAgICAgICAgICAgICAgICAgKytzdWJjb3VudDsKKyAgICAgICAg ICAgICAgICAgICAgaWYgKHItPnJlbmRlclN0eWxlKCkgPT0gc3QgJiYgci0+bGFzdENoaWxkKCkg KQorICAgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgICAgICAvLyBBZGp1 c3QgZm9yIHVudXNlZCByZXNlcnZlZCB0cmllcy4KKyAgICAgICAgICAgICAgICAgICAgICAgIHZp c2l0ZWROb2Rlc0NvdW50IC09IGNTdHlsZVNlYXJjaFRocmVzaG9sZCAtIHN1YmNvdW50OworICAg ICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHItPmxhc3RDaGlsZCgpOworICAgICAgICAgICAg ICAgICAgICB9CisgICAgICAgICAgICAgICAgICAgIGlmIChzdWJjb3VudCA+PSBjU3R5bGVTZWFy Y2hUaHJlc2hvbGQpCisgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gMDsKKyAgICAgICAg ICAgICAgICAgICAgciA9IHItPnByZXZpb3VzU2libGluZygpOworICAgICAgICAgICAgICAgIH0K KyAgICAgICAgICAgICAgICByID0gdGhpc0NvdXNpbiA9IGxvY2F0ZUNvdXNpbkxpc3QodGhpc0Nv dXNpbi0+cGFyZW50RWxlbWVudCgpLCB2aXNpdGVkTm9kZXNDb3VudCkgOworICAgICAgICAgICAg fSB3aGlsZSAodGhpc0NvdXNpbik7CiAgICAgICAgIH0KICAgICB9CiAgICAgcmV0dXJuIDA7CkBA IC0xMDU0LDI2ICsxMDYwLDIzIEBAIGJvb2wgQ1NTU3R5bGVTZWxlY3Rvcjo6Y2FuU2hhcmVTdHls ZVdpdGhFbGVtZW50KE5vZGUqIG4pCiBBTFdBWVNfSU5MSU5FIFJlbmRlclN0eWxlKiBDU1NTdHls ZVNlbGVjdG9yOjpsb2NhdGVTaGFyZWRTdHlsZSgpCiB7CiAgICAgaWYgKG1fc3R5bGVkRWxlbWVu dCAmJiAhbV9zdHlsZWRFbGVtZW50LT5pbmxpbmVTdHlsZURlY2woKSAmJiAhbV9zdHlsZWRFbGVt ZW50LT5oYXNJRCgpICYmICFtX3N0eWxlZEVsZW1lbnQtPmRvY3VtZW50KCktPnVzZXNTaWJsaW5n UnVsZXMoKSkgewotICAgICAgICAvLyBDaGVjayBwcmV2aW91cyBzaWJsaW5ncy4KKyAgICAgICAg Ly8gQ2hlY2sgcHJldmlvdXMgc2libGluZ3MgYW5kIHRoZW4gY291c2lucy4KICAgICAgICAgdW5z aWduZWQgY291bnQgPSAwOworICAgICAgICB1bnNpZ25lZCB2aXNpdGVkTm9kZXNDb3VudCA9IDA7 CisgICAgICAgIE5vZGUqIHRoaXNFbGVtZW50ID0gbV9lbGVtZW50OwogICAgICAgICBOb2RlKiBu OwotICAgICAgICBmb3IgKG4gPSBtX2VsZW1lbnQtPnByZXZpb3VzU2libGluZygpOyBuICYmICFu LT5pc0VsZW1lbnROb2RlKCk7IG4gPSBuLT5wcmV2aW91c1NpYmxpbmcoKSkgeyB9Ci0gICAgICAg IHdoaWxlIChuKSB7Ci0gICAgICAgICAgICBpZiAoY2FuU2hhcmVTdHlsZVdpdGhFbGVtZW50KG4p KQotICAgICAgICAgICAgICAgIHJldHVybiBuLT5yZW5kZXJTdHlsZSgpOwotICAgICAgICAgICAg aWYgKGNvdW50KysgPT0gY1N0eWxlU2VhcmNoVGhyZXNob2xkKQotICAgICAgICAgICAgICAgIHJl dHVybiAwOwotICAgICAgICAgICAgZm9yIChuID0gbi0+cHJldmlvdXNTaWJsaW5nKCk7IG4gJiYg IW4tPmlzRWxlbWVudE5vZGUoKTsgbiA9IG4tPnByZXZpb3VzU2libGluZygpKSB7IH0KLSAgICAg ICAgfQotICAgICAgICBpZiAoIW4pIAotICAgICAgICAgICAgbiA9IGxvY2F0ZUNvdXNpbkxpc3Qo bV9lbGVtZW50LT5wYXJlbnRFbGVtZW50KCkpOwotICAgICAgICB3aGlsZSAobikgewotICAgICAg ICAgICAgaWYgKGNhblNoYXJlU3R5bGVXaXRoRWxlbWVudChuKSkKLSAgICAgICAgICAgICAgICBy ZXR1cm4gbi0+cmVuZGVyU3R5bGUoKTsKLSAgICAgICAgICAgIGlmIChjb3VudCsrID09IGNTdHls ZVNlYXJjaFRocmVzaG9sZCkKLSAgICAgICAgICAgICAgICByZXR1cm4gMDsKLSAgICAgICAgICAg IGZvciAobiA9IG4tPnByZXZpb3VzU2libGluZygpOyBuICYmICFuLT5pc0VsZW1lbnROb2RlKCk7 IG4gPSBuLT5wcmV2aW91c1NpYmxpbmcoKSkgeyB9Ci0gICAgICAgIH0gICAgICAgIAorICAgICAg ICAvLyBGSVhNRTogV2Ugc2hvdWxkIHVzZSB0aGUgRWxlbWVudFRyYXZlcnNhbCBBUEkgaW5zdGVh ZCBvZiB0aGlzIGZvci1sb29wIGJ1dCB3ZSBuZWVkIHRvIHRlc3QgdGhlIHBlcmZvcm1hbmNlIGlt cGxpY2F0aW9uIG9mIHRoaXMgY2hhbmdlLgorICAgICAgICBmb3IgKG4gPSB0aGlzRWxlbWVudC0+ cHJldmlvdXNTaWJsaW5nKCk7IG4gJiYgIW4tPmlzRWxlbWVudE5vZGUoKTsgbiA9IG4tPnByZXZp b3VzU2libGluZygpKSB7IH0KKyAgICAgICAgZG8geworICAgICAgICAgICAgd2hpbGUgKG4pIHsK KyAgICAgICAgICAgICAgICBpZiAoY2FuU2hhcmVTdHlsZVdpdGhFbGVtZW50KG4pKQorICAgICAg ICAgICAgICAgICAgICByZXR1cm4gbi0+cmVuZGVyU3R5bGUoKTsKKyAgICAgICAgICAgICAgICBp ZiAoY291bnQrKyA9PSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQpCisgICAgICAgICAgICAgICAgICAg IHJldHVybiAwOworICAgICAgICAgICAgICAgIGZvciAobiA9IG4tPnByZXZpb3VzU2libGluZygp OyBuICYmICFuLT5pc0VsZW1lbnROb2RlKCk7IG4gPSBuLT5wcmV2aW91c1NpYmxpbmcoKSkgeyB9 CisgICAgICAgICAgICB9CisgICAgICAgICAgICBuID0gdGhpc0VsZW1lbnQgPSBsb2NhdGVDb3Vz aW5MaXN0KHRoaXNFbGVtZW50LT5wYXJlbnRFbGVtZW50KCksIHZpc2l0ZWROb2Rlc0NvdW50KTsK KyAgICAgICAgfSB3aGlsZSAodGhpc0VsZW1lbnQpOwogICAgIH0KICAgICByZXR1cm4gMDsKIH0K ZGlmZiAtLWdpdCBhL1dlYkNvcmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuaCBiL1dlYkNvcmUvY3Nz L0NTU1N0eWxlU2VsZWN0b3IuaAppbmRleCAyOGQ0NDg4Li5mZjQ0YzlmIDEwMDY0NAotLS0gYS9X ZWJDb3JlL2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmgKKysrIGIvV2ViQ29yZS9jc3MvQ1NTU3R5bGVT ZWxlY3Rvci5oCkBAIC0xMTAsNyArMTEwLDcgQEAgcHVibGljOgogICAgICAgICB2b2lkIGluaXRG b3JTdHlsZVJlc29sdmUoRWxlbWVudCosIFJlbmRlclN0eWxlKiBwYXJlbnRTdHlsZSA9IDAsIFBz ZXVkb0lkID0gTk9QU0VVRE8pOwogICAgICAgICB2b2lkIGluaXRFbGVtZW50KEVsZW1lbnQqKTsK ICAgICAgICAgUmVuZGVyU3R5bGUqIGxvY2F0ZVNoYXJlZFN0eWxlKCk7Ci0gICAgICAgIE5vZGUq IGxvY2F0ZUNvdXNpbkxpc3QoRWxlbWVudCogcGFyZW50LCB1bnNpZ25lZCBkZXB0aCA9IDEpOwor ICAgICAgICBOb2RlKiBsb2NhdGVDb3VzaW5MaXN0KEVsZW1lbnQqIHBhcmVudCwgdW5zaWduZWQg JnZpc2l0ZWROb2Rlcyk7CiAgICAgICAgIGJvb2wgY2FuU2hhcmVTdHlsZVdpdGhFbGVtZW50KE5v ZGUqKTsKIAogICAgICAgICBSZW5kZXJTdHlsZSogc3R5bGUoKSBjb25zdCB7IHJldHVybiBtX3N0 eWxlLmdldCgpOyB9Cg== 67282 2010-09-10 18:45:26 -0700 2011-02-17 18:42:28 -0800 Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues) improve-local-SharedStyle-CousinList-algorithm-improved.diff text/plain 7671 jchaffraix ZGlmZiAtLWdpdCBhL1dlYkNvcmUvQ2hhbmdlTG9nIGIvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXgg MTM5OTZmMThmM2VmY2UzY2ZmNGYzYzBmZTE5NzgzNGQxNDI0NzIzNi4uYjQ2NjIxMzZlMWYzNzZm OTE4NTc3MTQ3YmI5ZWM0NmY4NmExNTY0YyAxMDA2NDQKLS0tIGEvV2ViQ29yZS9DaGFuZ2VMb2cK KysrIGIvV2ViQ29yZS9DaGFuZ2VMb2cKQEAgLTEsMyArMSwzMSBAQAorMjAxMC0wOS0xMCAgSnVs aWVuIENoYWZmcmFpeCA8amNoYWZmcmFpeEBjb2RlYXVyb3JhLm9yZz4KKworICAgICAgICBSZXZp ZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBJbXByb3ZlIHRoZSBsb2NhbHtTaGFy ZWRTdHlsZSxDb3VzaW5MaXN0fSBhbGdvcml0aG0KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtp dC5vcmcvc2hvd19idWcuY2dpP2lkPTQ1NTA3CisKKyAgICAgICAgVGhpcyBjaGFuZ2UgaW1wcm92 ZXMgdGhlIGFsZ29yaXRobSB0byBmaW5kIHNoYXJlZCBzdHlsZXM6ICBUaGUgb2xkCisgICAgICAg IGFsZ29yaXRobSB3b3VsZCBzdG9wIHRoZSBzZWFyY2ggYWZ0ZXIgdGhlIGZpcnN0IGNvdXNpbiwg ZXZlbiBpZgorICAgICAgICB0aGUgc2VhcmNoIHRocmVzaG9sZCBpcyBub3QgbWV0LiBBcyBzdWNo LCB0aGUgYWxnb3JpdGhtIHdvdWxkCisgICAgICAgIHN5c3RlbWF0aWNhbGx5IG1pc3Mgc2hhcmlu Z3MgYWNyb3NzIHNlY29uZCBjb3VzaW5zIGFuZCBiZXlvbmQuCisgICAgICAgIFRoZSBuZXcgYWxn b3JpdGhtIGNvbnRpbnVlcyB0aGUgc2VhcmNoLCBhcyBsb25nIGFzIHRocmVzaG9sZCBpcworICAg ICAgICBub3QgbWV0LiBJdCBhbHNvIHNlcGFyYXRlcyB0aGUgdGhyZXNob2xkIGZvciBzaWJsaW5n L2NvdXNpbnMKKyAgICAgICAgc2VhcmNoLCBmcm9tIHRoYXQgb24gdGhlIGxldmVscyBvZiBzZWFy Y2gsIHdoaWNoIGlzIGVhc2llciB0bworICAgICAgICBvcHRpbWl6ZS4KKyAgICAgICAgVGhlIG5l dyBhbGdvcml0aG0gZmluZHMgdXAgdG8gMzAlIG1vcmUgc2hhcmluZ3Mgb24gc29tZSBzaXRlcwor ICAgICAgICAoZS5nLiBhbWF6b24uY29tIGFuZCByYWt1dGVuLmNvLmpwKSB3aXRoIG5vIG5vdGlj ZWFibGUgc2xvd2Rvd24uCisKKyAgICAgICAgTm8gbmV3IHRlc3QsIHJlZmFjdG9yaW5nIG9ubHku CisKKyAgICAgICAgKiBjc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHA6CisgICAgICAgIChXZWJDb3Jl OjpDU1NTdHlsZVNlbGVjdG9yOjpsb2NhdGVDb3VzaW5MaXN0KToKKyAgICAgICAgKFdlYkNvcmU6 OkNTU1N0eWxlU2VsZWN0b3I6OmxvY2F0ZVNoYXJlZFN0eWxlKToKKyAgICAgICAgV2hpbGUgY2hh bmdpbmcgdGhlIGFsZ29yaXRobSwgY2xlYW5lZCB1cCB0aGUgc3R5bGUgb2YgdGhvc2UgMiBtZXRo b2RzCisgICAgICAgICh1c2UgZWFybHkgcmV0dXJuLCByZW5hbWVkIHNvbWUgdmFyaWFibGVzKS4K KworICAgICAgICAqIGNzcy9DU1NTdHlsZVNlbGVjdG9yLmg6CisKIDIwMTAtMDktMTAgIEFkYW0g QmFydGggIDxhYmFydGhAd2Via2l0Lm9yZz4KIAogICAgICAgICBSZXZpZXdlZCBieSBFcmljIFNl aWRlbC4KZGlmZiAtLWdpdCBhL1dlYkNvcmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuY3BwIGIvV2Vi Q29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAKaW5kZXggNWRjZDc3NDdiMjYxYWE1ZWQwODlh MGNiOTcwY2U5ZTFhMDE1NzAzZC4uMzU3YjAzZWE0YzVhNzdjZDM2MDgwOWMwOWFiYzI2NzM3ZTY2 NDczYyAxMDA2NDQKLS0tIGEvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAKKysrIGIv V2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAKQEAgLTYsNiArNiw3IEBACiAgKiBDb3B5 cmlnaHQgKEMpIDIwMDcgQWxleGV5IFByb3NrdXJ5YWtvdiA8YXBAd2Via2l0Lm9yZz4KICAqIENv cHlyaWdodCAoQykgMjAwNywgMjAwOCBFcmljIFNlaWRlbCA8ZXJpY0B3ZWJraXQub3JnPgogICog Q29weXJpZ2h0IChDKSAyMDA4LCAyMDA5IFRvcmNoIE1vYmlsZSBJbmMuIEFsbCByaWdodHMgcmVz ZXJ2ZWQuIChodHRwOi8vd3d3LnRvcmNobW9iaWxlLmNvbS8pCisgKiBDb3B5cmlnaHQgKGMpIDIw MTAsIENvZGUgQXVyb3JhIEZvcnVtLiBBbGwgcmlnaHRzIHJlc2VydmVkLgogICoKICAqIFRoaXMg bGlicmFyeSBpcyBmcmVlIHNvZnR3YXJlOyB5b3UgY2FuIHJlZGlzdHJpYnV0ZSBpdCBhbmQvb3IK ICAqIG1vZGlmeSBpdCB1bmRlciB0aGUgdGVybXMgb2YgdGhlIEdOVSBMaWJyYXJ5IEdlbmVyYWwg UHVibGljCkBAIC05NDMsMzMgKzk0NCw0NCBAQCBib29sIENTU1N0eWxlU2VsZWN0b3I6OlNlbGVj dG9yQ2hlY2tlcjo6Y2hlY2tTZWxlY3RvcihDU1NTZWxlY3Rvciogc2VsLCBFbGVtZW50KgogfQog CiBzdGF0aWMgY29uc3QgdW5zaWduZWQgY1N0eWxlU2VhcmNoVGhyZXNob2xkID0gMTA7CitzdGF0 aWMgY29uc3QgdW5zaWduZWQgY1N0eWxlU2VhcmNoTGV2ZWxUaHJlc2hvbGQgPSAxMDsKIAotTm9k ZSogQ1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlQ291c2luTGlzdChFbGVtZW50KiBwYXJlbnQsIHVu c2lnbmVkIGRlcHRoKQorTm9kZSogQ1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlQ291c2luTGlzdChF bGVtZW50KiBwYXJlbnQsIHVuc2lnbmVkICZ2aXNpdGVkTm9kZXNDb3VudCkKIHsKLSAgICBpZiAo cGFyZW50ICYmIHBhcmVudC0+aXNTdHlsZWRFbGVtZW50KCkpIHsKLSAgICAgICAgU3R5bGVkRWxl bWVudCogcCA9IHN0YXRpY19jYXN0PFN0eWxlZEVsZW1lbnQqPihwYXJlbnQpOwotICAgICAgICBp ZiAoIXAtPmlubGluZVN0eWxlRGVjbCgpICYmICFwLT5oYXNJRCgpKSB7Ci0gICAgICAgICAgICBO b2RlKiByID0gcC0+cHJldmlvdXNTaWJsaW5nKCk7Ci0gICAgICAgICAgICB1bnNpZ25lZCBzdWJj b3VudCA9IDA7Ci0gICAgICAgICAgICBSZW5kZXJTdHlsZSogc3QgPSBwLT5yZW5kZXJTdHlsZSgp OwotICAgICAgICAgICAgd2hpbGUgKHIpIHsKLSAgICAgICAgICAgICAgICBpZiAoci0+cmVuZGVy U3R5bGUoKSA9PSBzdCkKLSAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHItPmxhc3RDaGlsZCgp OwotICAgICAgICAgICAgICAgIGlmIChzdWJjb3VudCsrID09IGNTdHlsZVNlYXJjaFRocmVzaG9s ZCkKLSAgICAgICAgICAgICAgICAgICAgcmV0dXJuIDA7Ci0gICAgICAgICAgICAgICAgciA9IHIt PnByZXZpb3VzU2libGluZygpOwotICAgICAgICAgICAgfQotICAgICAgICAgICAgaWYgKCFyICYm IGRlcHRoIDwgY1N0eWxlU2VhcmNoVGhyZXNob2xkKQotICAgICAgICAgICAgICAgIHIgPSBsb2Nh dGVDb3VzaW5MaXN0KHBhcmVudC0+cGFyZW50RWxlbWVudCgpLCBkZXB0aCArIDEpOwotICAgICAg ICAgICAgd2hpbGUgKHIpIHsKLSAgICAgICAgICAgICAgICBpZiAoci0+cmVuZGVyU3R5bGUoKSA9 PSBzdCkKLSAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHItPmxhc3RDaGlsZCgpOwotICAgICAg ICAgICAgICAgIGlmIChzdWJjb3VudCsrID09IGNTdHlsZVNlYXJjaFRocmVzaG9sZCkKLSAgICAg ICAgICAgICAgICAgICAgcmV0dXJuIDA7Ci0gICAgICAgICAgICAgICAgciA9IHItPnByZXZpb3Vz U2libGluZygpOworICAgIGlmICh2aXNpdGVkTm9kZXNDb3VudCA+PSAoY1N0eWxlU2VhcmNoVGhy ZXNob2xkICogY1N0eWxlU2VhcmNoTGV2ZWxUaHJlc2hvbGQpKQorICAgICAgICByZXR1cm4gMDsK KworICAgIGlmICghcGFyZW50IHx8ICFwYXJlbnQtPmlzU3R5bGVkRWxlbWVudCgpKQorICAgICAg ICByZXR1cm4gMDsKKworICAgIFN0eWxlZEVsZW1lbnQqIHBhcmVudFN0eWxlZEVsZW1lbnQgPSBz dGF0aWNfY2FzdDxTdHlsZWRFbGVtZW50Kj4ocGFyZW50KTsKKyAgICBpZiAocGFyZW50U3R5bGVk RWxlbWVudC0+aW5saW5lU3R5bGVEZWNsKCkgfHwgcGFyZW50U3R5bGVkRWxlbWVudC0+aGFzSUQo KSkKKyAgICAgICAgcmV0dXJuIDA7CisKKyAgICBSZW5kZXJTdHlsZSogcGFyZW50U3R5bGUgPSBw YXJlbnRTdHlsZWRFbGVtZW50LT5yZW5kZXJTdHlsZSgpOworICAgIHVuc2lnbmVkIHN1YmNvdW50 ID0gMDsKKyAgICBOb2RlKiB0aGlzQ291c2luID0gcGFyZW50U3R5bGVkRWxlbWVudDsKKyAgICBO b2RlKiBjdXJyZW50Tm9kZSA9IHBhcmVudFN0eWxlZEVsZW1lbnQtPnByZXZpb3VzU2libGluZygp OworCisgICAgLy8gUmVzZXJ2ZSB0aGUgdHJpZXMgZm9yIHRoaXMgbGV2ZWwuIFRoaXMgZWZmZWN0 aXZlbHkgbWFrZXMgc3VyZSB0aGF0IHRoZSBhbGdvcml0aG0KKyAgICAvLyB3aWxsIG5ldmVyIGdv IGRlZXBlciB0aGFuIGNTdHlsZVNlYXJjaExldmVsVGhyZXNob2xkIGxldmVscyBpbnRvIHJlY3Vy c2lvbi4KKyAgICB2aXNpdGVkTm9kZXNDb3VudCArPSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQ7Cisg ICAgd2hpbGUgKHRoaXNDb3VzaW4pIHsKKyAgICAgICAgd2hpbGUgKGN1cnJlbnROb2RlKSB7Cisg ICAgICAgICAgICArK3N1YmNvdW50OworICAgICAgICAgICAgaWYgKGN1cnJlbnROb2RlLT5yZW5k ZXJTdHlsZSgpID09IHBhcmVudFN0eWxlICYmIGN1cnJlbnROb2RlLT5sYXN0Q2hpbGQoKSkgewor ICAgICAgICAgICAgICAgIC8vIEFkanVzdCBmb3IgdW51c2VkIHJlc2VydmVkIHRyaWVzLgorICAg ICAgICAgICAgICAgIHZpc2l0ZWROb2Rlc0NvdW50IC09IGNTdHlsZVNlYXJjaFRocmVzaG9sZCAt IHN1YmNvdW50OworICAgICAgICAgICAgICAgIHJldHVybiBjdXJyZW50Tm9kZS0+bGFzdENoaWxk KCk7CiAgICAgICAgICAgICB9CisgICAgICAgICAgICBpZiAoc3ViY291bnQgPj0gY1N0eWxlU2Vh cmNoVGhyZXNob2xkKQorICAgICAgICAgICAgICAgIHJldHVybiAwOworICAgICAgICAgICAgY3Vy cmVudE5vZGUgPSBjdXJyZW50Tm9kZS0+cHJldmlvdXNTaWJsaW5nKCk7CiAgICAgICAgIH0KKyAg ICAgICAgY3VycmVudE5vZGUgPSBsb2NhdGVDb3VzaW5MaXN0KHRoaXNDb3VzaW4tPnBhcmVudEVs ZW1lbnQoKSwgdmlzaXRlZE5vZGVzQ291bnQpOworICAgICAgICB0aGlzQ291c2luID0gY3VycmVu dE5vZGU7CiAgICAgfQorCiAgICAgcmV0dXJuIDA7CiB9CiAKQEAgLTEwNTMsMTEgKzEwNjUsMjAg QEAgYm9vbCBDU1NTdHlsZVNlbGVjdG9yOjpjYW5TaGFyZVN0eWxlV2l0aEVsZW1lbnQoTm9kZSog bikKIAogQUxXQVlTX0lOTElORSBSZW5kZXJTdHlsZSogQ1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRl U2hhcmVkU3R5bGUoKQogewotICAgIGlmIChtX3N0eWxlZEVsZW1lbnQgJiYgIW1fc3R5bGVkRWxl bWVudC0+aW5saW5lU3R5bGVEZWNsKCkgJiYgIW1fc3R5bGVkRWxlbWVudC0+aGFzSUQoKSAmJiAh bV9zdHlsZWRFbGVtZW50LT5kb2N1bWVudCgpLT51c2VzU2libGluZ1J1bGVzKCkpIHsKLSAgICAg ICAgLy8gQ2hlY2sgcHJldmlvdXMgc2libGluZ3MuCi0gICAgICAgIHVuc2lnbmVkIGNvdW50ID0g MDsKLSAgICAgICAgTm9kZSogbjsKLSAgICAgICAgZm9yIChuID0gbV9lbGVtZW50LT5wcmV2aW91 c1NpYmxpbmcoKTsgbiAmJiAhbi0+aXNFbGVtZW50Tm9kZSgpOyBuID0gbi0+cHJldmlvdXNTaWJs aW5nKCkpIHsgfQorICAgIGlmICghbV9zdHlsZWRFbGVtZW50KQorICAgICAgICByZXR1cm4gMDsK KworICAgIGlmIChtX3N0eWxlZEVsZW1lbnQtPmlubGluZVN0eWxlRGVjbCgpIHx8IG1fc3R5bGVk RWxlbWVudC0+aGFzSUQoKSB8fCBtX3N0eWxlZEVsZW1lbnQtPmRvY3VtZW50KCktPnVzZXNTaWJs aW5nUnVsZXMoKSkKKyAgICAgICAgcmV0dXJuIDA7CisKKyAgICAvLyBDaGVjayBwcmV2aW91cyBz aWJsaW5ncyBhbmQgdGhlaXIgY291c2lucy4KKyAgICB1bnNpZ25lZCBjb3VudCA9IDA7CisgICAg dW5zaWduZWQgdmlzaXRlZE5vZGVzQ291bnQgPSAwOworICAgIE5vZGUqIHRoaXNFbGVtZW50ID0g bV9lbGVtZW50OworICAgIE5vZGUqIG47CisgICAgLy8gRklYTUU6IFdlIHNob3VsZCB1c2UgdGhl IEVsZW1lbnRUcmF2ZXJzYWwgQVBJIGluc3RlYWQgb2YgdGhpcyBmb3ItbG9vcCBidXQgd2UgbmVl ZCB0byB0ZXN0IHRoZSBwZXJmb3JtYW5jZSBpbXBsaWNhdGlvbiBvZiB0aGlzIGNoYW5nZS4KKyAg ICBmb3IgKG4gPSB0aGlzRWxlbWVudC0+cHJldmlvdXNTaWJsaW5nKCk7IG4gJiYgIW4tPmlzRWxl bWVudE5vZGUoKTsgbiA9IG4tPnByZXZpb3VzU2libGluZygpKSB7IH0KKyAgICB3aGlsZSAodGhp c0VsZW1lbnQpIHsKICAgICAgICAgd2hpbGUgKG4pIHsKICAgICAgICAgICAgIGlmIChjYW5TaGFy ZVN0eWxlV2l0aEVsZW1lbnQobikpCiAgICAgICAgICAgICAgICAgcmV0dXJuIG4tPnJlbmRlclN0 eWxlKCk7CkBAIC0xMDY1LDE1ICsxMDg2LDggQEAgQUxXQVlTX0lOTElORSBSZW5kZXJTdHlsZSog Q1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlU2hhcmVkU3R5bGUoKQogICAgICAgICAgICAgICAgIHJl dHVybiAwOwogICAgICAgICAgICAgZm9yIChuID0gbi0+cHJldmlvdXNTaWJsaW5nKCk7IG4gJiYg IW4tPmlzRWxlbWVudE5vZGUoKTsgbiA9IG4tPnByZXZpb3VzU2libGluZygpKSB7IH0KICAgICAg ICAgfQotICAgICAgICBpZiAoIW4pIAotICAgICAgICAgICAgbiA9IGxvY2F0ZUNvdXNpbkxpc3Qo bV9lbGVtZW50LT5wYXJlbnRFbGVtZW50KCkpOwotICAgICAgICB3aGlsZSAobikgewotICAgICAg ICAgICAgaWYgKGNhblNoYXJlU3R5bGVXaXRoRWxlbWVudChuKSkKLSAgICAgICAgICAgICAgICBy ZXR1cm4gbi0+cmVuZGVyU3R5bGUoKTsKLSAgICAgICAgICAgIGlmIChjb3VudCsrID09IGNTdHls ZVNlYXJjaFRocmVzaG9sZCkKLSAgICAgICAgICAgICAgICByZXR1cm4gMDsKLSAgICAgICAgICAg IGZvciAobiA9IG4tPnByZXZpb3VzU2libGluZygpOyBuICYmICFuLT5pc0VsZW1lbnROb2RlKCk7 IG4gPSBuLT5wcmV2aW91c1NpYmxpbmcoKSkgeyB9Ci0gICAgICAgIH0gICAgICAgIAorICAgICAg ICBuID0gbG9jYXRlQ291c2luTGlzdCh0aGlzRWxlbWVudC0+cGFyZW50RWxlbWVudCgpLCB2aXNp dGVkTm9kZXNDb3VudCk7CisgICAgICAgIHRoaXNFbGVtZW50ID0gbjsKICAgICB9CiAgICAgcmV0 dXJuIDA7CiB9CmRpZmYgLS1naXQgYS9XZWJDb3JlL2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmggYi9X ZWJDb3JlL2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmgKaW5kZXggNGE0NTY1ZGYzNmI5NzQ2YWE3MDdi NTJhMDU5ZDliZGE3ZDRjYmE3NC4uZTE4ZDc3ODExN2ZiMzAwZGQ3OGNlN2YzNDgzYWZkYmM0ODQ0 MWJjZSAxMDA2NDQKLS0tIGEvV2ViQ29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5oCisrKyBiL1dl YkNvcmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuaApAQCAtMTEwLDcgKzExMCw3IEBAIHB1YmxpYzoK ICAgICAgICAgdm9pZCBpbml0Rm9yU3R5bGVSZXNvbHZlKEVsZW1lbnQqLCBSZW5kZXJTdHlsZSog cGFyZW50U3R5bGUgPSAwLCBQc2V1ZG9JZCA9IE5PUFNFVURPKTsKICAgICAgICAgdm9pZCBpbml0 RWxlbWVudChFbGVtZW50Kik7CiAgICAgICAgIFJlbmRlclN0eWxlKiBsb2NhdGVTaGFyZWRTdHls ZSgpOwotICAgICAgICBOb2RlKiBsb2NhdGVDb3VzaW5MaXN0KEVsZW1lbnQqIHBhcmVudCwgdW5z aWduZWQgZGVwdGggPSAxKTsKKyAgICAgICAgTm9kZSogbG9jYXRlQ291c2luTGlzdChFbGVtZW50 KiBwYXJlbnQsIHVuc2lnbmVkICZ2aXNpdGVkTm9kZXMpOwogICAgICAgICBib29sIGNhblNoYXJl U3R5bGVXaXRoRWxlbWVudChOb2RlKik7CiAKICAgICAgICAgUmVuZGVyU3R5bGUqIHN0eWxlKCkg Y29uc3QgeyByZXR1cm4gbV9zdHlsZS5nZXQoKTsgfQoK 82888 2011-02-17 18:42:28 -0800 2011-02-21 22:48:42 -0800 Rebased patch - Also addressed Darin's comments improve-local-SharedStyle-CousinList-algorithm-rebased-02172011.diff text/plain 6496 jchaffraix ZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZyBiL1NvdXJjZS9XZWJDb3JlL0No YW5nZUxvZwppbmRleCBmMDI2ZGM0Li4wN2ViOWM1IDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29y ZS9DaGFuZ2VMb2cKKysrIGIvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCkBAIC0xLDMgKzEsMzEg QEAKKzIwMTEtMDItMTcgIEp1bGllbiBDaGFmZnJhaXggIDxqY2hhZmZyYWl4QGNvZGVhdXJvcmEu b3JnPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIElt cHJvdmUgdGhlIGxvY2Fse1NoYXJlZFN0eWxlLENvdXNpbkxpc3R9IGFsZ29yaXRobQorICAgICAg ICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9NDU1MDcKKworICAgICAg ICBUaGlzIGNoYW5nZSBpbXByb3ZlcyB0aGUgYWxnb3JpdGhtIHRvIGZpbmQgc2hhcmVkIHN0eWxl czogdGhlIG9sZAorICAgICAgICBhbGdvcml0aG0gd291bGQgc3RvcCB0aGUgc2VhcmNoIGFmdGVy IHRoZSBmaXJzdCBjb3VzaW4sIGV2ZW4gaWYKKyAgICAgICAgdGhlIHNlYXJjaCB0aHJlc2hvbGQg aXMgbm90IG1ldC4gQXMgc3VjaCwgdGhlIGFsZ29yaXRobSB3b3VsZAorICAgICAgICBzeXN0ZW1h dGljYWxseSBtaXNzIHNoYXJpbmdzIGFjcm9zcyBzZWNvbmQgY291c2lucyBhbmQgYmV5b25kLgor ICAgICAgICBUaGUgbmV3IGFsZ29yaXRobSBjb250aW51ZXMgdGhlIHNlYXJjaCwgYXMgbG9uZyBh cyB0aHJlc2hvbGQgaXMKKyAgICAgICAgbm90IG1ldC4gSXQgYWxzbyBzZXBhcmF0ZXMgdGhlIHRo cmVzaG9sZCBmb3Igc2libGluZy9jb3VzaW5zCisgICAgICAgIHNlYXJjaCwgZnJvbSB0aGF0IG9u IHRoZSBsZXZlbHMgb2Ygc2VhcmNoLCB3aGljaCBpcyBlYXNpZXIgdG8KKyAgICAgICAgb3B0aW1p emUuCisgICAgICAgIFRoZSBuZXcgYWxnb3JpdGhtIGZpbmRzIHVwIHRvIDMwJSBtb3JlIHNoYXJp bmdzIG9uIHNvbWUgc2l0ZXMKKyAgICAgICAgKGUuZy4gYW1hem9uLmNvbSBhbmQgcmFrdXRlbi5j by5qcCkgd2l0aCBubyBub3RpY2VhYmxlIHNsb3dkb3duLgorCisgICAgICAgIE5vIG5ldyB0ZXN0 LCByZWZhY3RvcmluZyBvbmx5LgorCisgICAgICAgICogY3NzL0NTU1N0eWxlU2VsZWN0b3IuY3Bw OgorICAgICAgICAoV2ViQ29yZTo6Q1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlQ291c2luTGlzdCk6 CisgICAgICAgIChXZWJDb3JlOjpDU1NTdHlsZVNlbGVjdG9yOjpsb2NhdGVTaGFyZWRTdHlsZSk6 CisgICAgICAgIFdoaWxlIGNoYW5naW5nIHRoZSBhbGdvcml0aG0sIGNsZWFuZWQgdXAgdGhlIHN0 eWxlIG9mIHRob3NlIDIgbWV0aG9kcworICAgICAgICAodXNlIGVhcmx5IHJldHVybiwgcmVuYW1l ZCBzb21lIHZhcmlhYmxlcykuCisKKyAgICAgICAgKiBjc3MvQ1NTU3R5bGVTZWxlY3Rvci5oOgor CiAyMDExLTAyLTE3ICBLZW5uZXRoIFJ1c3NlbGwgIDxrYnJAZ29vZ2xlLmNvbT4KIAogICAgICAg ICBSZXZpZXdlZCBieSBKYW1lcyBSb2JpbnNvbi4KZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3Jl L2Nzcy9DU1NTdHlsZVNlbGVjdG9yLmNwcCBiL1NvdXJjZS9XZWJDb3JlL2Nzcy9DU1NTdHlsZVNl bGVjdG9yLmNwcAppbmRleCBjMDJlOGVmLi5kYmUxODg2IDEwMDY0NAotLS0gYS9Tb3VyY2UvV2Vi Q29yZS9jc3MvQ1NTU3R5bGVTZWxlY3Rvci5jcHAKKysrIGIvU291cmNlL1dlYkNvcmUvY3NzL0NT U1N0eWxlU2VsZWN0b3IuY3BwCkBAIC02LDYgKzYsNyBAQAogICogQ29weXJpZ2h0IChDKSAyMDA3 IEFsZXhleSBQcm9za3VyeWFrb3YgPGFwQHdlYmtpdC5vcmc+CiAgKiBDb3B5cmlnaHQgKEMpIDIw MDcsIDIwMDggRXJpYyBTZWlkZWwgPGVyaWNAd2Via2l0Lm9yZz4KICAqIENvcHlyaWdodCAoQykg MjAwOCwgMjAwOSBUb3JjaCBNb2JpbGUgSW5jLiBBbGwgcmlnaHRzIHJlc2VydmVkLiAoaHR0cDov L3d3dy50b3JjaG1vYmlsZS5jb20vKQorICogQ29weXJpZ2h0IChjKSAyMDExLCBDb2RlIEF1cm9y YSBGb3J1bS4gQWxsIHJpZ2h0cyByZXNlcnZlZC4KICAqCiAgKiBUaGlzIGxpYnJhcnkgaXMgZnJl ZSBzb2Z0d2FyZTsgeW91IGNhbiByZWRpc3RyaWJ1dGUgaXQgYW5kL29yCiAgKiBtb2RpZnkgaXQg dW5kZXIgdGhlIHRlcm1zIG9mIHRoZSBHTlUgTGlicmFyeSBHZW5lcmFsIFB1YmxpYwpAQCAtOTky LDkgKzk5MywxMiBAQCBib29sIENTU1N0eWxlU2VsZWN0b3I6OlNlbGVjdG9yQ2hlY2tlcjo6Y2hl Y2tTZWxlY3RvcihDU1NTZWxlY3Rvciogc2VsLCBFbGVtZW50KgogfQogCiBzdGF0aWMgY29uc3Qg dW5zaWduZWQgY1N0eWxlU2VhcmNoVGhyZXNob2xkID0gMTA7CitzdGF0aWMgY29uc3QgdW5zaWdu ZWQgY1N0eWxlU2VhcmNoTGV2ZWxUaHJlc2hvbGQgPSAxMDsKIAotTm9kZSogQ1NTU3R5bGVTZWxl Y3Rvcjo6bG9jYXRlQ291c2luTGlzdChFbGVtZW50KiBwYXJlbnQsIHVuc2lnbmVkIGRlcHRoKSBj b25zdAorTm9kZSogQ1NTU3R5bGVTZWxlY3Rvcjo6bG9jYXRlQ291c2luTGlzdChFbGVtZW50KiBw YXJlbnQsIHVuc2lnbmVkJiB2aXNpdGVkTm9kZUNvdW50KSBjb25zdAogeworICAgIGlmICh2aXNp dGVkTm9kZUNvdW50ID49IGNTdHlsZVNlYXJjaFRocmVzaG9sZCAqIGNTdHlsZVNlYXJjaExldmVs VGhyZXNob2xkKQorICAgICAgICByZXR1cm4gMDsKICAgICBpZiAoIXBhcmVudCB8fCAhcGFyZW50 LT5pc1N0eWxlZEVsZW1lbnQoKSkKICAgICAgICAgcmV0dXJuIDA7CiAgICAgU3R5bGVkRWxlbWVu dCogcCA9IHN0YXRpY19jYXN0PFN0eWxlZEVsZW1lbnQqPihwYXJlbnQpOwpAQCAtMTAwMiwyNSAr MTAwNiwzMSBAQCBOb2RlKiBDU1NTdHlsZVNlbGVjdG9yOjpsb2NhdGVDb3VzaW5MaXN0KEVsZW1l bnQqIHBhcmVudCwgdW5zaWduZWQgZGVwdGgpIGNvbnN0CiAgICAgICAgIHJldHVybiAwOwogICAg IGlmIChwLT5oYXNJRCgpICYmIG1faWRzSW5SdWxlcy5jb250YWlucyhwLT5pZEZvclN0eWxlUmVz b2x1dGlvbigpLmltcGwoKSkpCiAgICAgICAgIHJldHVybiAwOwotICAgIE5vZGUqIHIgPSBwLT5w cmV2aW91c1NpYmxpbmcoKTsKKworICAgIFJlbmRlclN0eWxlKiBwYXJlbnRTdHlsZSA9IHAtPnJl bmRlclN0eWxlKCk7CiAgICAgdW5zaWduZWQgc3ViY291bnQgPSAwOwotICAgIFJlbmRlclN0eWxl KiBzdCA9IHAtPnJlbmRlclN0eWxlKCk7Ci0gICAgd2hpbGUgKHIpIHsKLSAgICAgICAgaWYgKHIt PnJlbmRlclN0eWxlKCkgPT0gc3QpCi0gICAgICAgICAgICByZXR1cm4gci0+bGFzdENoaWxkKCk7 Ci0gICAgICAgIGlmIChzdWJjb3VudCsrID09IGNTdHlsZVNlYXJjaFRocmVzaG9sZCkKLSAgICAg ICAgICAgIHJldHVybiAwOwotICAgICAgICByID0gci0+cHJldmlvdXNTaWJsaW5nKCk7Ci0gICAg fQotICAgIGlmICghciAmJiBkZXB0aCA8IGNTdHlsZVNlYXJjaFRocmVzaG9sZCkKLSAgICAgICAg ciA9IGxvY2F0ZUNvdXNpbkxpc3QocGFyZW50LT5wYXJlbnRFbGVtZW50KCksIGRlcHRoICsgMSk7 Ci0gICAgd2hpbGUgKHIpIHsKLSAgICAgICAgaWYgKHItPnJlbmRlclN0eWxlKCkgPT0gc3QpCi0g ICAgICAgICAgICByZXR1cm4gci0+bGFzdENoaWxkKCk7Ci0gICAgICAgIGlmIChzdWJjb3VudCsr ID09IGNTdHlsZVNlYXJjaFRocmVzaG9sZCkKLSAgICAgICAgICAgIHJldHVybiAwOwotICAgICAg ICByID0gci0+cHJldmlvdXNTaWJsaW5nKCk7CisgICAgTm9kZSogdGhpc0NvdXNpbiA9IHA7Cisg ICAgTm9kZSogY3VycmVudE5vZGUgPSBwLT5wcmV2aW91c1NpYmxpbmcoKTsKKworICAgIC8vIFJl c2VydmUgdGhlIHRyaWVzIGZvciB0aGlzIGxldmVsLiBUaGlzIGVmZmVjdGl2ZWx5IG1ha2VzIHN1 cmUgdGhhdCB0aGUgYWxnb3JpdGhtCisgICAgLy8gd2lsbCBuZXZlciBnbyBkZWVwZXIgdGhhbiBj U3R5bGVTZWFyY2hMZXZlbFRocmVzaG9sZCBsZXZlbHMgaW50byByZWN1cnNpb24uCisgICAgdmlz aXRlZE5vZGVDb3VudCArPSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQ7CisgICAgd2hpbGUgKHRoaXND b3VzaW4pIHsKKyAgICAgICAgd2hpbGUgKGN1cnJlbnROb2RlKSB7CisgICAgICAgICAgICArK3N1 YmNvdW50OworICAgICAgICAgICAgaWYgKGN1cnJlbnROb2RlLT5yZW5kZXJTdHlsZSgpID09IHBh cmVudFN0eWxlICYmIGN1cnJlbnROb2RlLT5sYXN0Q2hpbGQoKSkgeworICAgICAgICAgICAgICAg IC8vIEFkanVzdCBmb3IgdW51c2VkIHJlc2VydmVkIHRyaWVzLgorICAgICAgICAgICAgICAgIHZp c2l0ZWROb2RlQ291bnQgLT0gY1N0eWxlU2VhcmNoVGhyZXNob2xkIC0gc3ViY291bnQ7CisgICAg ICAgICAgICAgICAgcmV0dXJuIGN1cnJlbnROb2RlLT5sYXN0Q2hpbGQoKTsKKyAgICAgICAgICAg IH0KKyAgICAgICAgICAgIGlmIChzdWJjb3VudCA+PSBjU3R5bGVTZWFyY2hUaHJlc2hvbGQpCisg ICAgICAgICAgICAgICAgcmV0dXJuIDA7CisgICAgICAgICAgICBjdXJyZW50Tm9kZSA9IGN1cnJl bnROb2RlLT5wcmV2aW91c1NpYmxpbmcoKTsKKyAgICAgICAgfQorICAgICAgICBjdXJyZW50Tm9k ZSA9IGxvY2F0ZUNvdXNpbkxpc3QodGhpc0NvdXNpbi0+cGFyZW50RWxlbWVudCgpLCB2aXNpdGVk Tm9kZUNvdW50KTsKKyAgICAgICAgdGhpc0NvdXNpbiA9IGN1cnJlbnROb2RlOwogICAgIH0KKwog ICAgIHJldHVybiAwOwogfQogCkBAIC0xMTYzLDE1ICsxMTczLDIzIEBAIEFMV0FZU19JTkxJTkUg UmVuZGVyU3R5bGUqIENTU1N0eWxlU2VsZWN0b3I6OmxvY2F0ZVNoYXJlZFN0eWxlKCkKICAgICAg ICAgcmV0dXJuIDA7CiAgICAgaWYgKHBhcmVudFN0eWxlUHJldmVudHNTaGFyaW5nKG1fcGFyZW50 U3R5bGUpKQogICAgICAgICByZXR1cm4gMDsKLSAgICAvLyBDaGVjayBwcmV2aW91cyBzaWJsaW5n cy4KKworICAgIC8vIENoZWNrIHByZXZpb3VzIHNpYmxpbmdzIGFuZCB0aGVpciBjb3VzaW5zLgog ICAgIHVuc2lnbmVkIGNvdW50ID0gMDsKLSAgICBOb2RlKiBzaGFyZU5vZGUgPSBmaW5kU2libGlu Z0ZvclN0eWxlU2hhcmluZyhtX3N0eWxlZEVsZW1lbnQtPnByZXZpb3VzU2libGluZygpLCBjb3Vu dCk7Ci0gICAgaWYgKCFzaGFyZU5vZGUpIHsKLSAgICAgICAgTm9kZSogY291c2luTGlzdCA9IGxv Y2F0ZUNvdXNpbkxpc3QobV9zdHlsZWRFbGVtZW50LT5wYXJlbnRFbGVtZW50KCkpOwotICAgICAg ICBzaGFyZU5vZGUgPSBmaW5kU2libGluZ0ZvclN0eWxlU2hhcmluZyhjb3VzaW5MaXN0LCBjb3Vu dCk7IAotICAgICAgICBpZiAoIXNoYXJlTm9kZSkKLSAgICAgICAgICAgIHJldHVybiAwOworICAg IHVuc2lnbmVkIHZpc2l0ZWROb2RlQ291bnQgPSAwOworICAgIE5vZGUqIHNoYXJlTm9kZSA9IDA7 CisgICAgTm9kZSogY291c2luTGlzdCA9IG1fc3R5bGVkRWxlbWVudC0+cHJldmlvdXNTaWJsaW5n KCk7CisgICAgd2hpbGUgKGNvdXNpbkxpc3QpIHsKKyAgICAgICAgc2hhcmVOb2RlID0gZmluZFNp YmxpbmdGb3JTdHlsZVNoYXJpbmcoY291c2luTGlzdCwgY291bnQpOworICAgICAgICBpZiAoc2hh cmVOb2RlKQorICAgICAgICAgICAgYnJlYWs7CisgICAgICAgIGNvdXNpbkxpc3QgPSBsb2NhdGVD b3VzaW5MaXN0KGNvdXNpbkxpc3QtPnBhcmVudEVsZW1lbnQoKSwgdmlzaXRlZE5vZGVDb3VudCk7 CiAgICAgfQorCisgICAgLy8gSWYgd2UgaGF2ZSBleGhhdXN0ZWQgYWxsIG91ciBidWRnZXQgb3Ig b3VyIGNvdXNpbnMuCisgICAgaWYgKCFzaGFyZU5vZGUpCisgICAgICAgIHJldHVybiAwOworCiAg ICAgLy8gQ2FuJ3Qgc2hhcmUgaWYgc2libGluZyBydWxlcyBhcHBseS4gVGhpcyBpcyBjaGVja2Vk IGF0IHRoZSBlbmQgYXMgaXQgc2hvdWxkIHJhcmVseSBmYWlsLgogICAgIGlmIChtYXRjaGVzU2li bGluZ1J1bGVzKCkpCiAgICAgICAgIHJldHVybiAwOwpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNv cmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuaCBiL1NvdXJjZS9XZWJDb3JlL2Nzcy9DU1NTdHlsZVNl bGVjdG9yLmgKaW5kZXggNTc4ZjRhOC4uN2MxNDhmMSAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNv cmUvY3NzL0NTU1N0eWxlU2VsZWN0b3IuaAorKysgYi9Tb3VyY2UvV2ViQ29yZS9jc3MvQ1NTU3R5 bGVTZWxlY3Rvci5oCkBAIC0xMTYsNyArMTE2LDcgQEAgcHVibGljOgogICAgICAgICB2b2lkIGlu aXRFbGVtZW50KEVsZW1lbnQqKTsKICAgICAgICAgUmVuZGVyU3R5bGUqIGxvY2F0ZVNoYXJlZFN0 eWxlKCk7CiAgICAgICAgIGJvb2wgbWF0Y2hlc1NpYmxpbmdSdWxlcygpOwotICAgICAgICBOb2Rl KiBsb2NhdGVDb3VzaW5MaXN0KEVsZW1lbnQqIHBhcmVudCwgdW5zaWduZWQgZGVwdGggPSAxKSBj b25zdDsKKyAgICAgICAgTm9kZSogbG9jYXRlQ291c2luTGlzdChFbGVtZW50KiBwYXJlbnQsIHVu c2lnbmVkJiB2aXNpdGVkTm9kZUNvdW50KSBjb25zdDsKICAgICAgICAgTm9kZSogZmluZFNpYmxp bmdGb3JTdHlsZVNoYXJpbmcoTm9kZSosIHVuc2lnbmVkJiBjb3VudCkgY29uc3Q7CiAgICAgICAg IGJvb2wgY2FuU2hhcmVTdHlsZVdpdGhFbGVtZW50KE5vZGUqKSBjb25zdDsKICAgICAgICAgCg==