Bug 91320

Summary: Accessing the last item in children should be a constant time operation
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: DOMAssignee: Ryosuke Niwa <rniwa>
Status: RESOLVED FIXED    
Severity: Normal CC: andersca, darin, haraken, kling, koivisto, ojan, sam
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 91306    
Bug Blocks: 89919    
Attachments:
Description Flags
Fixes the bug ojan: review+

Ryosuke Niwa
Reported 2012-07-14 03:38:57 PDT
element.children[element.children.length - 1] should be a constant time operation with respect to the number of child nodes element has.
Attachments
Fixes the bug (6.71 KB, patch)
2012-07-14 03:47 PDT, Ryosuke Niwa 		ojan: review+
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Ryosuke Niwa
Comment 1 2012-07-14 03:47:56 PDT
Created attachment 152418 [details] Fixes the bug
Ryosuke Niwa
Comment 2 2012-07-14 03:48:55 PDT
(provided that the length cache is available).
Ryosuke Niwa
Comment 3 2012-07-14 04:13:44 PDT
Once this patch is landed, I'll post the final unification patch that merges DynamicNodeList::item and HTMLCollection::item.
Ojan Vafai
Comment 4 2012-07-14 09:41:50 PDT
Comment on attachment 152418 [details] Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review > Source/WebCore/html/HTMLCollection.cpp:336 > + if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) { > + // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection > + unsigned unusedOffsetInArray = 0; > + Node* lastItem = itemBefore(unusedOffsetInArray, 0); > + ASSERT(!unusedOffsetInArray); > + ASSERT(lastItem); > + setItemCache(lastItem, cachedLength() - 1, 0); > + } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) { This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions.
Ryosuke Niwa
Comment 5 2012-07-14 11:18:29 PDT
Comment on attachment 152418 [details] Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review >> Source/WebCore/html/HTMLCollection.cpp:336 >> + } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) { > > This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions. I did that initially but then realized that the fact such as length is cached, and itemBefore is supported, etc... isn't obvious in the first if statement. Also, if I did add those two functions then I have to assume that either shouldSearchFromFirstItem or shouldSearchFromLastItem is called first since conditions in the function becomes way too complicated otherwise and making such call order assumption seemed error prone.
Ryosuke Niwa
Comment 6 2012-07-14 14:38:44 PDT
Committed r122672: <http://trac.webkit.org/changeset/122672>
Note You need to log in before you can comment on or make changes to this bug.