Reviewed by Harrison.

	Fixed: <rdar://problem/3228878> potential performance problem in finding in large framesets

	Got rid of O(N^2) conditions in _nextSibling and _previousSibling of where we were looking up self in the parent array of frames.

        * WebView.subproj/WebFrame.h: Added two new pointers, one for the previous kid and one for the next kid
        * WebView.subproj/WebFrame.m:
        (-[WebFrame _addChild:]): Updates the previous frame and the next frame after this child
        (-[WebFrame _removeChild:]): ditto
        (-[WebFrame _nextSibling]): just return the pointer now
        (-[WebFrame _previousSibling]): ditto

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@8095 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/WebKit/ChangeLog b/WebKit/ChangeLog
index 488b5ba133fa11339e4705cfcfc254a58bc1c19c..c5feb0f946845535c1bbce99793449e1266e595a 100644 (file)
--- a/WebKit/ChangeLog
+++ b/WebKit/ChangeLog
@@ -1,3 +1,18 @@
+2004-12-01  Kevin Decker  <kdecker@apple.com>
+
+        Reviewed by Harrison.
+
+       Fixed: <rdar://problem/3228878> potential performance problem in finding in large framesets
+
+       Got rid of O(N^2) conditions in _nextSibling and _previousSibling of where we were looking up self in the parent array of frames.
+
+        * WebView.subproj/WebFrame.h: Added two new pointers, one for the previous kid and one for the next kid
+        * WebView.subproj/WebFrame.m: 
+        (-[WebFrame _addChild:]): Updates the previous frame and the next frame after this child
+        (-[WebFrame _removeChild:]): ditto
+        (-[WebFrame _nextSibling]): just return the pointer now
+        (-[WebFrame _previousSibling]): ditto
+
 2004-11-30  Chris Blumenberg  <cblu@apple.com>
 
        Fixed:

diff --git a/WebKit/WebView.subproj/WebFrame.h b/WebKit/WebView.subproj/WebFrame.h
index af04150b49de6e0a8217c1629d8fd089d62703e3..cf91b2206eb25eead3ccd058702fc2cddc8e4faf 100644 (file)
--- a/WebKit/WebView.subproj/WebFrame.h
+++ b/WebKit/WebView.subproj/WebFrame.h
@@ -25,6 +25,8 @@
 {
 @private
     WebFramePrivate *_private;
+    WebFrame *_nextSibling;
+    WebFrame *_previousSibling;
 }
 
 /*!

diff --git a/WebKit/WebView.subproj/WebFrame.m b/WebKit/WebView.subproj/WebFrame.m
index f975b163d950cd90ddc83d55c02df6a83b23341f..52a1e476ffe44182073e292b36400e861afe7a3f 100644 (file)
--- a/WebKit/WebView.subproj/WebFrame.m
+++ b/WebKit/WebView.subproj/WebFrame.m
@@ -2086,14 +2086,35 @@ static CFAbsoluteTime _timeOfLastCompletedLoad;
     if (_private->children == nil)
         _private->children = [[NSMutableArray alloc] init];
     [_private->children addObject:child];
-
+       
     child->_private->parent = self;
     [[child _bridge] setParent:_private->bridge];
-    [[child dataSource] _setOverrideEncoding:[[self dataSource] _overrideEncoding]];   
+    [[child dataSource] _setOverrideEncoding:[[self dataSource] _overrideEncoding]];  
+        
+    unsigned currentIndex = [_private->children count] - 1;
+    // we keep track of sibling pointers to avoid the overhead of a lookup in the children array
+    
+    if (currentIndex > 0) {
+        WebFrame *previousFrame = [[self childFrames] objectAtIndex: currentIndex - 1];
+        previousFrame->_nextSibling = child;
+        child->_previousSibling = previousFrame;
+        ASSERT(child->_nextSibling == nil);
+    }
+    
 }
 
 - (void)_removeChild:(WebFrame *)child
 {
+       // move corresponding previous and next WebFrame sibling pointers to their new positions
+       // when we remove a child we may have to reattach the previous frame's next frame and visa versa
+       if (child->_previousSibling) {
+            child->_previousSibling->_nextSibling = child->_nextSibling;
+       }
+       
+       if (child->_nextSibling) { 
+            child->_nextSibling->_previousSibling = child->_previousSibling; 
+       }
+       
     [_private->children removeObject:child];
     child->_private->parent = nil;
 }
@@ -2336,32 +2357,16 @@ static CFAbsoluteTime _timeOfLastCompletedLoad;
     [self _checkNewWindowPolicyForRequest:request action:(NSDictionary *)action frameName:frameName formState:nil andCall:self withSelector:@selector(_continueLoadRequestAfterNewWindowPolicy:frameName:formState:)];
 }
 
-// Returns the next frame in our parent's children array, or nil
+// Returns the next frame in our parent's children array
 - (WebFrame *)_nextSibling
 {
-    if (_private->parent) {
-        NSArray *parentsKids = _private->parent->_private->children;
-        unsigned selfIndex = [parentsKids indexOfObjectIdenticalTo:self];
-        ASSERT(selfIndex != NSNotFound);
-        if (selfIndex < [parentsKids count]-1) {
-            return [parentsKids objectAtIndex:selfIndex+1];
-        }
-    }
-    return nil;                // no parent, or no more later siblings
+    return _nextSibling;
 }
 
 // Returns the previous frame in our parent's children array, or nil
 - (WebFrame *)_previousSibling
 {
-    if (_private->parent) {
-        NSArray *parentsKids = _private->parent->_private->children;
-        unsigned selfIndex = [parentsKids indexOfObjectIdenticalTo:self];
-        ASSERT(selfIndex != NSNotFound);
-        if (selfIndex > 0) {
-            return [parentsKids objectAtIndex:selfIndex-1];
-        }
-    }
-    return nil;                // no parent, or no more earlier siblings
+    return _previousSibling;
 }
 
 // Returns the last child of us and any children, or nil