121185 2013-09-11 15:09:10 -0700 Avoid copying a hash table bucket when inserting causes a rehash 2013-09-11 15:26:30 -0700 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 andersca andersca benjamin cmarcelo commit-queue oldest_to_newest 928002 0 andersca 2013-09-11 15:09:10 -0700 Avoid copying a hash table bucket when inserting causes a rehash 928003 1 211358 andersca 2013-09-11 15:11:21 -0700 Created attachment 211358 Patch 928006 2 211358 darin 2013-09-11 15:13:36 -0700 Comment on attachment 211358 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=211358&action=review > Source/WTF/ChangeLog:8 > + Allow rehahsing to track a hash bucket and return the new pointer to it, thus avoiding typo: rehashing > Source/WTF/wtf/HashTable.h:-940 > - // FIXME: This makes an extra copy on expand. Probably not that bad since > - // expand is rare, but would be better to have a version of expand that can > - // follow a pivot entry and return the new position. You fixed this FIXME! 928015 3 andersca 2013-09-11 15:26:30 -0700 Committed r155571: <http://trac.webkit.org/changeset/155571> 211358 2013-09-11 15:11:21 -0700 2013-09-11 15:13:36 -0700 Patch bug-121185-20130911151121.patch text/plain 6818 andersca U3VidmVyc2lvbiBSZXZpc2lvbjogMTU1NTUyCmRpZmYgLS1naXQgYS9Tb3VyY2UvV1RGL0NoYW5n ZUxvZyBiL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCmluZGV4IDM0MTQxMmRhNDlmNjgxYmRmZjI1YmIx NDM0ZmI0NjI1ZTA5M2Y0YTMuLjJiZmQ1MjEzYThmMmMxMmE3NTkzYTA4ZGQ2MTRlMjRkYWM3ZTM0 MzcgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCisrKyBiL1NvdXJjZS9XVEYvQ2hh bmdlTG9nCkBAIC0xLDUgKzEsMTcgQEAKIDIwMTMtMDktMTEgIEFuZGVycyBDYXJsc3NvbiAgPGFu ZGVyc2NhQGFwcGxlLmNvbT4KIAorICAgICAgICBBdm9pZCBjb3B5aW5nIGEgaGFzaCB0YWJsZSBi dWNrZXQgd2hlbiBpbnNlcnRpbmcgY2F1c2VzIGEgcmVoYXNoCisgICAgICAgIGh0dHBzOi8vYnVn cy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMjExODUKKworICAgICAgICBSZXZpZXdlZCBi eSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBBbGxvdyByZWhhaHNpbmcgdG8gdHJhY2sgYSBo YXNoIGJ1Y2tldCBhbmQgcmV0dXJuIHRoZSBuZXcgcG9pbnRlciB0byBpdCwgdGh1cyBhdm9pZGlu ZworICAgICAgICBoYXZpbmcgdG8gZG8gYSBjb3B5IG9mIGEgaGFzaCB0YWJsZSBidWNrZXQgYXMg d2VsbCBhcyBhbiBleHRyYSBoYXNoIGxvb2t1cC4KKworICAgICAgICAqIHd0Zi9IYXNoVGFibGUu aDoKKworMjAxMy0wOS0xMSAgQW5kZXJzIENhcmxzc29uICA8YW5kZXJzY2FAYXBwbGUuY29tPgor CiAgICAgICAgIFZlY3Rvcjo6YXBwZW5kIGRvZXNuJ3Qgd29yayBpZiBlbGVtZW50IHR5cGUgaGFz IG92ZXJsb2FkZWQgb3BlcmF0b3ImCiAgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3No b3dfYnVnLmNnaT9pZD0xMjExNzUKIApkaWZmIC0tZ2l0IGEvU291cmNlL1dURi93dGYvSGFzaFRh YmxlLmggYi9Tb3VyY2UvV1RGL3d0Zi9IYXNoVGFibGUuaAppbmRleCBjY2U5ODE4NjUzZDU3NmEy MTRkY2RjOWFiZmQ0ODg0MmRkMTkzOTA0Li4wMDYxNGY1M2E4MWZmZWQzNWQyYzEyNDVhZWY0M2Zi YTllN2RlNTMzIDEwMDY0NAotLS0gYS9Tb3VyY2UvV1RGL3d0Zi9IYXNoVGFibGUuaAorKysgYi9T b3VyY2UvV1RGL3d0Zi9IYXNoVGFibGUuaApAQCAtNDU3LDExICs0NTcsMTEgQEAgbmFtZXNwYWNl IFdURiB7CiAgICAgICAgIGJvb2wgc2hvdWxkRXhwYW5kKCkgY29uc3QgeyByZXR1cm4gKG1fa2V5 Q291bnQgKyBtX2RlbGV0ZWRDb3VudCkgKiBtX21heExvYWQgPj0gbV90YWJsZVNpemU7IH0KICAg ICAgICAgYm9vbCBtdXN0UmVoYXNoSW5QbGFjZSgpIGNvbnN0IHsgcmV0dXJuIG1fa2V5Q291bnQg KiBtX21pbkxvYWQgPCBtX3RhYmxlU2l6ZSAqIDI7IH0KICAgICAgICAgYm9vbCBzaG91bGRTaHJp bmsoKSBjb25zdCB7IHJldHVybiBtX2tleUNvdW50ICogbV9taW5Mb2FkIDwgbV90YWJsZVNpemUg JiYgbV90YWJsZVNpemUgPiBLZXlUcmFpdHM6Om1pbmltdW1UYWJsZVNpemU7IH0KLSAgICAgICAg dm9pZCBleHBhbmQoKTsKLSAgICAgICAgdm9pZCBzaHJpbmsoKSB7IHJlaGFzaChtX3RhYmxlU2l6 ZSAvIDIpOyB9CisgICAgICAgIFZhbHVlVHlwZSogZXhwYW5kKFZhbHVlVHlwZSogZW50cnkgPSBu dWxscHRyKTsKKyAgICAgICAgdm9pZCBzaHJpbmsoKSB7IHJlaGFzaChtX3RhYmxlU2l6ZSAvIDIs IG51bGxwdHIpOyB9CiAKLSAgICAgICAgdm9pZCByZWhhc2goaW50IG5ld1RhYmxlU2l6ZSk7Ci0g ICAgICAgIHZvaWQgcmVpbnNlcnQoVmFsdWVUeXBlJik7CisgICAgICAgIFZhbHVlVHlwZSogcmVo YXNoKGludCBuZXdUYWJsZVNpemUsIFZhbHVlVHlwZSogZW50cnkpOworICAgICAgICBWYWx1ZVR5 cGUqIHJlaW5zZXJ0KFZhbHVlVHlwZSYpOwogCiAgICAgICAgIHN0YXRpYyB2b2lkIGluaXRpYWxp emVCdWNrZXQoVmFsdWVUeXBlJiBidWNrZXQpOwogICAgICAgICBzdGF0aWMgdm9pZCBkZWxldGVC dWNrZXQoVmFsdWVUeXBlJiBidWNrZXQpIHsgYnVja2V0Ln5WYWx1ZVR5cGUoKTsgVHJhaXRzOjpj b25zdHJ1Y3REZWxldGVkVmFsdWUoYnVja2V0KTsgfQpAQCAtODE4LDcgKzgxOCw3IEBAIG5hbWVz cGFjZSBXVEYgewogICAgICAgICBpbnZhbGlkYXRlSXRlcmF0b3JzKCk7CiAKICAgICAgICAgaWYg KCFtX3RhYmxlKQotICAgICAgICAgICAgZXhwYW5kKCk7CisgICAgICAgICAgICBleHBhbmQobnVs bHB0cik7CiAKICAgICAgICAgaW50ZXJuYWxDaGVja1RhYmxlQ29uc2lzdGVuY3koKTsKIApAQCAt ODg2LDIwICs4ODYsMTEgQEAgbmFtZXNwYWNlIFdURiB7CiAgICAgICAgIH0KIAogICAgICAgICBI YXNoVHJhbnNsYXRvcjo6dHJhbnNsYXRlKCplbnRyeSwga2V5LCBleHRyYSk7Ci0KICAgICAgICAg KyttX2tleUNvdW50OwogICAgICAgICAKLSAgICAgICAgaWYgKHNob3VsZEV4cGFuZCgpKSB7Ci0g ICAgICAgICAgICAvLyBGSVhNRTogVGhpcyBtYWtlcyBhbiBleHRyYSBjb3B5IG9uIGV4cGFuZC4g UHJvYmFibHkgbm90IHRoYXQgYmFkIHNpbmNlCi0gICAgICAgICAgICAvLyBleHBhbmQgaXMgcmFy ZSwgYnV0IHdvdWxkIGJlIGJldHRlciB0byBoYXZlIGEgdmVyc2lvbiBvZiBleHBhbmQgdGhhdCBj YW4KLSAgICAgICAgICAgIC8vIGZvbGxvdyBhIHBpdm90IGVudHJ5IGFuZCByZXR1cm4gdGhlIG5l dyBwb3NpdGlvbi4KLSAgICAgICAgICAgIEtleVR5cGUgZW50ZXJlZEtleSA9IEV4dHJhY3Rvcjo6 ZXh0cmFjdCgqZW50cnkpOwotICAgICAgICAgICAgZXhwYW5kKCk7Ci0gICAgICAgICAgICBBZGRS ZXN1bHQgcmVzdWx0KGZpbmQoZW50ZXJlZEtleSksIHRydWUpOwotICAgICAgICAgICAgQVNTRVJU KHJlc3VsdC5pdGVyYXRvciAhPSBlbmQoKSk7Ci0gICAgICAgICAgICByZXR1cm4gcmVzdWx0Owot ICAgICAgICB9Ci0gICAgICAgIAorICAgICAgICBpZiAoc2hvdWxkRXhwYW5kKCkpCisgICAgICAg ICAgICBlbnRyeSA9IGV4cGFuZChlbnRyeSk7CisKICAgICAgICAgaW50ZXJuYWxDaGVja1RhYmxl Q29uc2lzdGVuY3koKTsKICAgICAgICAgCiAgICAgICAgIHJldHVybiBBZGRSZXN1bHQobWFrZUtu b3duR29vZEl0ZXJhdG9yKGVudHJ5KSwgdHJ1ZSk7CkBAIC05MzQsMTYgKzkyNSw5IEBAIG5hbWVz cGFjZSBXVEYgewogICAgICAgICAKICAgICAgICAgSGFzaFRyYW5zbGF0b3I6OnRyYW5zbGF0ZSgq ZW50cnksIGtleSwgZXh0cmEsIGgpOwogICAgICAgICArK21fa2V5Q291bnQ7Ci0gICAgICAgIGlm IChzaG91bGRFeHBhbmQoKSkgewotICAgICAgICAgICAgLy8gRklYTUU6IFRoaXMgbWFrZXMgYW4g ZXh0cmEgY29weSBvbiBleHBhbmQuIFByb2JhYmx5IG5vdCB0aGF0IGJhZCBzaW5jZQotICAgICAg ICAgICAgLy8gZXhwYW5kIGlzIHJhcmUsIGJ1dCB3b3VsZCBiZSBiZXR0ZXIgdG8gaGF2ZSBhIHZl cnNpb24gb2YgZXhwYW5kIHRoYXQgY2FuCi0gICAgICAgICAgICAvLyBmb2xsb3cgYSBwaXZvdCBl bnRyeSBhbmQgcmV0dXJuIHRoZSBuZXcgcG9zaXRpb24uCi0gICAgICAgICAgICBLZXlUeXBlIGVu dGVyZWRLZXkgPSBFeHRyYWN0b3I6OmV4dHJhY3QoKmVudHJ5KTsKLSAgICAgICAgICAgIGV4cGFu ZCgpOwotICAgICAgICAgICAgQWRkUmVzdWx0IHJlc3VsdChmaW5kKGVudGVyZWRLZXkpLCB0cnVl KTsKLSAgICAgICAgICAgIEFTU0VSVChyZXN1bHQuaXRlcmF0b3IgIT0gZW5kKCkpOwotICAgICAg ICAgICAgcmV0dXJuIHJlc3VsdDsKLSAgICAgICAgfQorCisgICAgICAgIGlmIChzaG91bGRFeHBh bmQoKSkKKyAgICAgICAgICAgIGVudHJ5ID0gZXhwYW5kKGVudHJ5KTsKIAogICAgICAgICBpbnRl cm5hbENoZWNrVGFibGVDb25zaXN0ZW5jeSgpOwogCkBAIC05NTEsNyArOTM1LDcgQEAgbmFtZXNw YWNlIFdURiB7CiAgICAgfQogCiAgICAgdGVtcGxhdGU8dHlwZW5hbWUgS2V5LCB0eXBlbmFtZSBW YWx1ZSwgdHlwZW5hbWUgRXh0cmFjdG9yLCB0eXBlbmFtZSBIYXNoRnVuY3Rpb25zLCB0eXBlbmFt ZSBUcmFpdHMsIHR5cGVuYW1lIEtleVRyYWl0cz4KLSAgICBpbmxpbmUgdm9pZCBIYXNoVGFibGU8 S2V5LCBWYWx1ZSwgRXh0cmFjdG9yLCBIYXNoRnVuY3Rpb25zLCBUcmFpdHMsIEtleVRyYWl0cz46 OnJlaW5zZXJ0KFZhbHVlVHlwZSYgZW50cnkpCisgICAgaW5saW5lIFZhbHVlKiBIYXNoVGFibGU8 S2V5LCBWYWx1ZSwgRXh0cmFjdG9yLCBIYXNoRnVuY3Rpb25zLCBUcmFpdHMsIEtleVRyYWl0cz46 OnJlaW5zZXJ0KFZhbHVlVHlwZSYgZW50cnkpCiAgICAgewogICAgICAgICBBU1NFUlQobV90YWJs ZSk7CiAgICAgICAgIEFTU0VSVCghbG9va3VwRm9yV3JpdGluZyhFeHRyYWN0b3I6OmV4dHJhY3Qo ZW50cnkpKS5zZWNvbmQpOwpAQCAtOTYzLDcgKzk0NywxMCBAQCBuYW1lc3BhY2UgV1RGIHsKICAg ICAgICAgKyttX3N0YXRzLT5udW1SZWluc2VydHM7CiAjZW5kaWYKIAotICAgICAgICBNb3ZlcjxW YWx1ZVR5cGUsIFRyYWl0czo6bmVlZHNEZXN0cnVjdGlvbj46Om1vdmUoZW50cnksICpsb29rdXBG b3JXcml0aW5nKEV4dHJhY3Rvcjo6ZXh0cmFjdChlbnRyeSkpLmZpcnN0KTsKKyAgICAgICAgVmFs dWUqIG5ld0VudHJ5ID0gbG9va3VwRm9yV3JpdGluZyhFeHRyYWN0b3I6OmV4dHJhY3QoZW50cnkp KS5maXJzdDsKKyAgICAgICAgTW92ZXI8VmFsdWVUeXBlLCBUcmFpdHM6Om5lZWRzRGVzdHJ1Y3Rp b24+Ojptb3ZlKGVudHJ5LCAqbmV3RW50cnkpOworCisgICAgICAgIHJldHVybiBuZXdFbnRyeTsK ICAgICB9CiAKICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBLZXksIHR5cGVuYW1lIFZhbHVlLCB0eXBl bmFtZSBFeHRyYWN0b3IsIHR5cGVuYW1lIEhhc2hGdW5jdGlvbnMsIHR5cGVuYW1lIFRyYWl0cywg dHlwZW5hbWUgS2V5VHJhaXRzPgpAQCAtMTA5OCw3ICsxMDg1LDcgQEAgbmFtZXNwYWNlIFdURiB7 CiAgICAgfQogCiAgICAgdGVtcGxhdGU8dHlwZW5hbWUgS2V5LCB0eXBlbmFtZSBWYWx1ZSwgdHlw ZW5hbWUgRXh0cmFjdG9yLCB0eXBlbmFtZSBIYXNoRnVuY3Rpb25zLCB0eXBlbmFtZSBUcmFpdHMs IHR5cGVuYW1lIEtleVRyYWl0cz4KLSAgICB2b2lkIEhhc2hUYWJsZTxLZXksIFZhbHVlLCBFeHRy YWN0b3IsIEhhc2hGdW5jdGlvbnMsIFRyYWl0cywgS2V5VHJhaXRzPjo6ZXhwYW5kKCkKKyAgICBW YWx1ZSogSGFzaFRhYmxlPEtleSwgVmFsdWUsIEV4dHJhY3RvciwgSGFzaEZ1bmN0aW9ucywgVHJh aXRzLCBLZXlUcmFpdHM+OjpleHBhbmQoVmFsdWUqIGVudHJ5KQogICAgIHsKICAgICAgICAgaW50 IG5ld1NpemU7CiAgICAgICAgIGlmIChtX3RhYmxlU2l6ZSA9PSAwKQpAQCAtMTEwOCwxMSArMTA5 NSwxMSBAQCBuYW1lc3BhY2UgV1RGIHsKICAgICAgICAgZWxzZQogICAgICAgICAgICAgbmV3U2l6 ZSA9IG1fdGFibGVTaXplICogMjsKIAotICAgICAgICByZWhhc2gobmV3U2l6ZSk7CisgICAgICAg IHJldHVybiByZWhhc2gobmV3U2l6ZSwgZW50cnkpOwogICAgIH0KIAogICAgIHRlbXBsYXRlPHR5 cGVuYW1lIEtleSwgdHlwZW5hbWUgVmFsdWUsIHR5cGVuYW1lIEV4dHJhY3RvciwgdHlwZW5hbWUg SGFzaEZ1bmN0aW9ucywgdHlwZW5hbWUgVHJhaXRzLCB0eXBlbmFtZSBLZXlUcmFpdHM+Ci0gICAg dm9pZCBIYXNoVGFibGU8S2V5LCBWYWx1ZSwgRXh0cmFjdG9yLCBIYXNoRnVuY3Rpb25zLCBUcmFp dHMsIEtleVRyYWl0cz46OnJlaGFzaChpbnQgbmV3VGFibGVTaXplKQorICAgIFZhbHVlKiBIYXNo VGFibGU8S2V5LCBWYWx1ZSwgRXh0cmFjdG9yLCBIYXNoRnVuY3Rpb25zLCBUcmFpdHMsIEtleVRy YWl0cz46OnJlaGFzaChpbnQgbmV3VGFibGVTaXplLCBWYWx1ZSAqZW50cnkpCiAgICAgewogICAg ICAgICBpbnRlcm5hbENoZWNrVGFibGVDb25zaXN0ZW5jeUV4Y2VwdFNpemUoKTsKIApAQCAtMTEz MywxNSArMTEyMCwyNiBAQCBuYW1lc3BhY2UgV1RGIHsKICAgICAgICAgbV90YWJsZVNpemVNYXNr ID0gbmV3VGFibGVTaXplIC0gMTsKICAgICAgICAgbV90YWJsZSA9IGFsbG9jYXRlVGFibGUobmV3 VGFibGVTaXplKTsKIAotICAgICAgICBmb3IgKGludCBpID0gMDsgaSAhPSBvbGRUYWJsZVNpemU7 ICsraSkKLSAgICAgICAgICAgIGlmICghaXNFbXB0eU9yRGVsZXRlZEJ1Y2tldChvbGRUYWJsZVtp XSkpCi0gICAgICAgICAgICAgICAgcmVpbnNlcnQob2xkVGFibGVbaV0pOworICAgICAgICBWYWx1 ZSogbmV3RW50cnkgPSBudWxscHRyOworICAgICAgICBmb3IgKGludCBpID0gMDsgaSAhPSBvbGRU YWJsZVNpemU7ICsraSkgeworICAgICAgICAgICAgaWYgKGlzRW1wdHlPckRlbGV0ZWRCdWNrZXQo b2xkVGFibGVbaV0pKSB7CisgICAgICAgICAgICAgICAgQVNTRVJUKCZvbGRUYWJsZVtpXSAhPSBl bnRyeSk7CisgICAgICAgICAgICAgICAgY29udGludWU7CisgICAgICAgICAgICB9CisKKyAgICAg ICAgICAgIFZhbHVlKiByZWluc2VydGVkRW50cnkgPSByZWluc2VydChvbGRUYWJsZVtpXSk7Cisg ICAgICAgICAgICBpZiAoJm9sZFRhYmxlW2ldID09IGVudHJ5KSB7CisgICAgICAgICAgICAgICAg QVNTRVJUKCFuZXdFbnRyeSk7CisgICAgICAgICAgICAgICAgbmV3RW50cnkgPSByZWluc2VydGVk RW50cnk7CisgICAgICAgICAgICB9CisgICAgICAgIH0KIAogICAgICAgICBtX2RlbGV0ZWRDb3Vu dCA9IDA7CiAKICAgICAgICAgZGVhbGxvY2F0ZVRhYmxlKG9sZFRhYmxlLCBvbGRUYWJsZVNpemUp OwogCiAgICAgICAgIGludGVybmFsQ2hlY2tUYWJsZUNvbnNpc3RlbmN5KCk7CisgICAgICAgIHJl dHVybiBuZXdFbnRyeTsKICAgICB9CiAKICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBLZXksIHR5cGVu YW1lIFZhbHVlLCB0eXBlbmFtZSBFeHRyYWN0b3IsIHR5cGVuYW1lIEhhc2hGdW5jdGlvbnMsIHR5 cGVuYW1lIFRyYWl0cywgdHlwZW5hbWUgS2V5VHJhaXRzPgo=