• rniwa@webkit.org's avatar
    Accessing the last item in children should be a constant time operation · 03fce206
    rniwa@webkit.org authored
    https://bugs.webkit.org/show_bug.cgi?id=91320
    
    Reviewed by Ojan Vafai.
    
    Source/WebCore: 
    
    Traverse nodes from the last item when the target offset we're looking for is closer to the last item
    than to the cached item. e.g. if the cached item was at offset 0 in the collection and length was 100,
    we should not be looking for the item at offset 95 from the cached item.
    
    Note that this trick can be only used in HTML collection that supports itemBefore and when the length
    cache is available.
    
    Also broke shouldSearchFromFirstItem into smaller logical pieces to clarify the intents.
    
    Test: perf/htmlcollection-last-item.html
    
    * html/HTMLCollection.cpp:
    (WebCore):
    (WebCore::HTMLCollection::isLastItemCloserThanLastOrCachedItem):
    (WebCore::HTMLCollection::isFirstItemCloserThanCachedItem):
    (WebCore::HTMLCollection::item):
    * html/HTMLCollection.h:
    (HTMLCollection):
    
    LayoutTests: 
    
    Added an asymptotic time complexity test.
    
    * perf/htmlcollection-last-item-expected.txt: Added.
    * perf/htmlcollection-last-item.html: Added.
    
    
    git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122672 268f45cc-cd09-0410-ab3c-d52691b4dbfc
    03fce206
htmlcollection-last-item-expected.txt 98 Bytes