Changeset 166981 in webkit
- Timestamp:
- Apr 8, 2014 5:06:09 PM (10 years ago)
- Location:
- trunk/Source/WebCore
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WebCore/ChangeLog
r166980 r166981 1 2014-04-08 Ryosuke Niwa <rniwa@webkit.org> 2 3 HTMLConverter::aggregatedAttributesForAncestors should cache intermediate results 4 https://bugs.webkit.org/show_bug.cgi?id=131400 5 6 Reviewed by Sam Weinig. 7 8 Instead of accumulating attributes from a character node to the highest ancestor, 9 recursively call aggregatedAttributesForElementAndItsAncestors so that aggregated 10 attributes are cached on each ancestor to eliminate the old O(n^2) behavior. 11 12 * editing/cocoa/HTMLConverter.mm: 13 (HTMLConverter::aggregatedAttributesForAncestors): 14 (HTMLConverter::aggregatedAttributesForElementAndItsAncestors): Extracted from aggregatedAttributesForAncestors. 15 1 16 2014-04-08 Jinwoo Song <jinwoo7.song@samsung.com> 2 17 -
trunk/Source/WebCore/editing/cocoa/HTMLConverter.mm
r166464 r166981 450 450 HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_attributesForElements; 451 451 HashMap<RetainPtr<NSTextTable>, RefPtr<Element>> m_textTableFooters; 452 HashMap<RefPtr<Element>, RetainPtr<NS MutableDictionary>> m_aggregatedAttributesForElements;452 HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_aggregatedAttributesForElements; 453 453 454 454 NSMutableAttributedString *_attrStr; … … 488 488 NSDictionary *attributesForElement(Element&); 489 489 NSDictionary *aggregatedAttributesForAncestors(CharacterData&); 490 490 NSDictionary* aggregatedAttributesForElementAndItsAncestors(Element&); 491 491 492 Element* _blockLevelElementForNode(Node*); 492 493 … … 1358 1359 if (!ancestor) 1359 1360 return nullptr; 1360 1361 auto& attributes = m_aggregatedAttributesForElements.add(toElement(ancestor), nullptr).iterator->value; 1362 if (!attributes) { 1363 Vector<Element*, 16> ancestorElements; 1364 ancestorElements.append(toElement(ancestor)); 1365 for (; ancestor; ancestor = ancestor->parentNode()) { 1366 if (ancestor->isElementNode()) 1367 ancestorElements.append(toElement(ancestor)); 1368 } 1369 1370 attributes = [NSMutableDictionary dictionary]; 1371 // Fill attrs dictionary with attributes from the highest to the lowest, not overwriting ones deeper in the tree 1372 for (unsigned index = ancestorElements.size(); index;) { 1373 index--; 1374 [attributes addEntriesFromDictionary:attributesForElement(*ancestorElements[index])]; 1375 } 1376 } 1377 1378 return attributes.get(); 1361 return aggregatedAttributesForElementAndItsAncestors(*toElement(ancestor)); 1362 } 1363 1364 NSDictionary* HTMLConverter::aggregatedAttributesForElementAndItsAncestors(Element& element) 1365 { 1366 auto& cachedAttributes = m_aggregatedAttributesForElements.add(&element, nullptr).iterator->value; 1367 if (cachedAttributes) 1368 return cachedAttributes.get(); 1369 1370 NSDictionary* attributesForCurrentElement = attributesForElement(element); 1371 ASSERT(attributesForCurrentElement); 1372 1373 Node* ancestor = element.parentNode(); 1374 while (ancestor && !ancestor->isElementNode()) 1375 ancestor = ancestor->parentNode(); 1376 1377 if (!ancestor) { 1378 cachedAttributes = attributesForCurrentElement; 1379 return attributesForCurrentElement; 1380 } 1381 1382 RetainPtr<NSMutableDictionary> attributesForAncestors = adoptNS([aggregatedAttributesForElementAndItsAncestors(*toElement(ancestor)) mutableCopy]); 1383 [attributesForAncestors addEntriesFromDictionary:attributesForCurrentElement]; 1384 m_aggregatedAttributesForElements.set(&element, attributesForAncestors); 1385 1386 return attributesForAncestors.get(); 1379 1387 } 1380 1388
Note: See TracChangeset
for help on using the changeset viewer.