Changeset 166981 in webkit


Ignore:
Timestamp:
Apr 8, 2014 5:06:09 PM (10 years ago)
Author:
rniwa@webkit.org
Message:

HTMLConverter::aggregatedAttributesForAncestors should cache intermediate results
https://bugs.webkit.org/show_bug.cgi?id=131400

Reviewed by Sam Weinig.

Instead of accumulating attributes from a character node to the highest ancestor,
recursively call aggregatedAttributesForElementAndItsAncestors so that aggregated
attributes are cached on each ancestor to eliminate the old O(n2) behavior.

  • editing/cocoa/HTMLConverter.mm:

(HTMLConverter::aggregatedAttributesForAncestors):
(HTMLConverter::aggregatedAttributesForElementAndItsAncestors): Extracted from aggregatedAttributesForAncestors.

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r166980 r166981  
     12014-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
    1162014-04-08  Jinwoo Song  <jinwoo7.song@samsung.com>
    217
  • trunk/Source/WebCore/editing/cocoa/HTMLConverter.mm

    r166464 r166981  
    450450    HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_attributesForElements;
    451451    HashMap<RetainPtr<NSTextTable>, RefPtr<Element>> m_textTableFooters;
    452     HashMap<RefPtr<Element>, RetainPtr<NSMutableDictionary>> m_aggregatedAttributesForElements;
     452    HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_aggregatedAttributesForElements;
    453453
    454454    NSMutableAttributedString *_attrStr;
     
    488488    NSDictionary *attributesForElement(Element&);
    489489    NSDictionary *aggregatedAttributesForAncestors(CharacterData&);
    490    
     490    NSDictionary* aggregatedAttributesForElementAndItsAncestors(Element&);
     491
    491492    Element* _blockLevelElementForNode(Node*);
    492493   
     
    13581359    if (!ancestor)
    13591360        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
     1364NSDictionary* 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();
    13791387}
    13801388
Note: See TracChangeset for help on using the changeset viewer.