This is a preparation work for bug 40197, which is about extending the current hit testing system to also support rectangular hit area, instead of only points. As discussed by hyatt in https://bugs.webkit.org/show_bug.cgi?id=40197#c19 , a ListHashSet structure is to be used to store the hit-tested nodes. In order to expose this rect-based hit test functionality to the DOM, a nodesFromRect method will be added to Document class, and it will return a NodeList wrapping this ListHashSet. This bug intends to provide this wrapper class.
Created attachment 59533 [details] patch v1 I have not added LayoutTests for this new NodeList at the moment, because it is only going to be used by patch to be submitted in bug 40197 - RefPrt<NodeList> Document::nodesFromRect const will use it/expose it.
Attachment 59533 [details] did not pass style-queue: Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1 WebCore/dom/StaticHashSetNodeList.h:40: Code inside a namespace should not be indented. [whitespace/indent] [4] WebCore/dom/StaticHashSetNodeList.cpp:46: Semicolon defining empty statement for this loop. Use { } instead. [whitespace/semicolon] [5] Total errors found: 2 in 9 files If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 59539 [details] patch v1.1 - fixed style issues
Created attachment 59608 [details] (commit r61818, r=dhyatt) patch v1.2 Removed an unnecessery FIXME in the code (due to accidental copy & paste) pointed out by dhyatt on IRC
Comment on attachment 59608 [details] (commit r61818, r=dhyatt) patch v1.2 r=me
Comment on attachment 59608 [details] (commit r61818, r=dhyatt) patch v1.2 Clearing flags on attachment: 59608 Committed r61818: <http://trac.webkit.org/changeset/61818>
Why a ListHashSet and not a Vector?
Once the hit test is done, it would be best to copy the contents of the ListHashSet into a Vector.
(In reply to comment #8) > Once the hit test is done, it would be best to copy the contents of the ListHashSet into a Vector. We were using Vector in previous versions of the rect-based HitTest patch, but it was suggested to use ListHashSet. see: https://bugs.webkit.org/show_bug.cgi?id=40197#c11 https://bugs.webkit.org/show_bug.cgi?id=40197#c15 https://bugs.webkit.org/show_bug.cgi?id=40197#c21 I understand your concern, though. It is probably because every NodeList::item(int n) operation has to iterate over the ListHashSet, which is O(n). With a Vector it'd be O(1) , since we can just do Vector::at(int n). Is that the case, Darin?
It’s fine to use ListHashSet to build up the list; a good efficient way to check for duplicates and membership while creating it. Once the list is created, though, moving to a Vector makes sense to me.
(In reply to comment #9) > I understand your concern, though. It is probably because every NodeList::item(int n) operation has to iterate over the ListHashSet, which is O(n). With a Vector it'd be O(1) , since we can just do Vector::at(int n). Is that the case, Darin? That’s one of my concerns. The other is that a ListHashSet uses a lot of extra memory.
(In reply to comment #11) > (In reply to comment #9) > > I understand your concern, though. It is probably because every NodeList::item(int n) operation has to iterate over the ListHashSet, which is O(n). With a Vector it'd be O(1) , since we can just do Vector::at(int n). Is that the case, Darin? > > That’s one of my concerns. The other is that a ListHashSet uses a lot of extra memory. Darin, I am really open to make it as you suggested: copy the listhashset over a vector after hittest is ready, and expose it as a StaticNodeList instead of as the added StaticHashSetNodeList. In this case, we can also discuss and decide if we need this StaticHashSetListNode at all, or just remove it. If we decide to keep it, I will templatize StaticListNode to either work with a Vector or a ListHashSet, as talked to Dyatt on irc, merging StaticHashSetListNode into StaticListNode anyways. I will try to get the core patch (in bug 40197) in a better shape first, then get back to this.
Revision r61818 cherry-picked into qtwebkit-2.1 with commit 8a8a28d007539792bf63f36817cfc3abdf994555