Version: (using KDE KDE 3.1) Installed from: OpenBSD Packages OS: OpenBSD The nature of KCompTreeNode::remove() doing a recursive removal results in a huge amount of memory usage while trying to remove e.g. long URLs from the Konqueror completion history. This can be easily remedied by making the removal process non-recursive. --- kdecore/kcompletion.cpp.orig Thu Mar 7 11:38:57 2002 +++ kdecore/kcompletion.cpp Wed Apr 2 13:03:55 2003 @@ -704,26 +704,37 @@ return child; } - -// Recursively removes a string from the tree (untested :-) +// Iteratively removes a string from the tree void KCompTreeNode::remove( const QString& string ) { - KCompTreeNode *child = 0L; - - if ( string.isEmpty() ) { - child = find( 0x0 ); - delete myChildren.remove( child ); - return; - } + KCompTreeNode **children = new KCompTreeNode *[string.length() + 1]; + uint i; - QChar ch = string.at(0); - child = find( ch ); - if ( child ) { - child->remove( string.right( string.length() -1 ) ); - if ( child->myChildren.count() == 0 ) { - delete myChildren.remove( child ); + for ( i = 0; i <= string.length(); i++ ) { + QChar ch = string.at(i); + if ( i == 0 ) + children[i] = find( ch ); + else + children[i] = children[i - 1]->find( ch ); + if ( children[i] == NULL ) { + if ( i == 0 ) { + delete children; + return; + } + break; } } + do { + i--; + if ( i == 0 ) { + if ( children[i]->myChildren.count() == 0 ) + delete myChildren.remove(children[i]); + } else if ( i == string.length() || children[i + 1] == NULL || + children[i]->myChildren.count() == 0 ) { + delete children[i - 1]->myChildren.remove(children[i]); + } + } while ( i != 0 ); + delete children; } QStringList KCompletionMatchesWrapper::list() const {
Created attachment 1294 [details] proposed patch
Subject: kdelibs/kdecore CVS commit by pfeiffer: Iteratively remove strings from KCompletion to use less memory. Do you have a comparison for that, btw? Report and patch by Brian Feldman <bfeldman@fla.fujitsu.com> (modified for easier readability) CCMAIL: 56757-close@bugs.kde.org M +30 -15 kcompletion.cpp 1.51 --- kdelibs/kdecore/kcompletion.cpp #1.50:1.51 @@ -25,4 +25,6 @@ #include <kglobal.h> +#include <qptrvector.h> + #include "kcompletion.h" #include "kcompletion_private.h" @@ -706,22 +708,35 @@ KCompTreeNode * KCompTreeNode::insert( c -// Recursively removes a string from the tree (untested :-) -void KCompTreeNode::remove( const QString& string ) +// Iteratively removes a string from the tree. The nicer recursive +// version apparently was a little memory hungry (see #56757) +void KCompTreeNode::remove( const QString& str ) { + QString string = str; + string += QChar(0x0); + + QPtrVector<KCompTreeNode> deletables( string.length() + 1 ); + KCompTreeNode *child = 0L; + KCompTreeNode *parent = this; + deletables.insert( 0, parent ); - if ( string.isEmpty() ) { - child = find( 0x0 ); - delete myChildren.remove( child ); - return; - } + uint i = 0; + for ( ; i < string.length(); i++ ) + { + child = parent->find( string.at( i ) ); + if ( child ) + deletables.insert( i + 1, child ); + else + break; - QChar ch = string.at(0); - child = find( ch ); - if ( child ) { - child->remove( string.right( string.length() -1 ) ); - if ( child->myChildren.count() == 0 ) { - delete myChildren.remove( child ); + parent = child; } + + for ( ; i >= 1; i-- ) + { + parent = deletables.at( i - 1 ); + child = deletables.at( i ); + if ( child->myChildren.count() == 0 ) + delete parent->myChildren.remove( child ); } }
Subject: Re: KCompTreeNode::remove() uses excessive memory and crashes. Carsten Pfeiffer wrote:Iteratively remove strings from KCompletion to use less memory. Do you > have a comparison for that, btw? > > Report and patch by Brian Feldman <bfeldman@fla.fujitsu.com> > (modified for easier readability) > > CCMAIL: 56757-close@bugs.kde.org Sorry, I didn't develop any test scenario for it to see how much better it is than the pathological case; my verification was that a certain URL managed to crash konqueror by having it use so much memory freeing the completion tree that it was overwhelming my already large user limits (over 16MB of stack used!). -- Brian Fundakowski Feldman | http://www.fla.fujitsu.com/ Software Specialist | Fujitsu Laboratories of America