The only consumer of nsAVLTree is the htmlparser - we would probably speed up the loading of both libraries if we were to move the class into the htmlparser library, and stop exporting it.
no time for this now, -> mozilla1.1 but its an easy win if anyone feels like doing the platform drudgery. One of the advantages of moving this is that the linker would cull out the parts of nsAVLTree/nsAVLNode/etc that nobody is using (it looks like htmlparser is only using a few of the routines) so it would probably be an overall footprint win, if small.
woah, 1.1 came up quick. Throwing these bugs over to 1.2.. little or no work has been done and there is no way that these bugs can be fixed in 1.1.
Created attachment 98641 [details] [diff] [review] move nsAVLTree into htmlparser ok, I had leaf copy the files over, so you'll see this patch has just one minor change to nsAVLTree, and that is to stop exporting stuff from the DLL. I also included the changes to remove nsAVLTree from xpcom, and I will remove the files themselves as a part of my checkin. Looking for reviews.
Comment on attachment 98641 [details] [diff] [review] move nsAVLTree into htmlparser sr=jst, and you're doing all the makefile changes too, right?
Comment on attachment 98641 [details] [diff] [review] move nsAVLTree into htmlparser r=harishd
Comment on attachment 98641 [details] [diff] [review] move nsAVLTree into htmlparser Why aren't we using an O(1) data structure like a hash table (non-minimal perfect hash, generated, was used by MozillaClassic, for fixed tag vocabularies such as HTML)? I still see xpcom/ds/*AVL* in my tree after updating. Aren't those files going away? Did leaf do a "cvs move" (copy/remove) or are we giving up the log history (no big deal)? See http://www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html for an extremely compact implementation of AVL trees, if you really need AVL trees. I use the minimal pieces of this necessary for the problem in http://lxr.mozilla.org/mozilla/source/js/src/jsemit.c#321 and thereabouts. /be
fixed! thanks for the reviews.
brendan: hey slow down there I hadn't landed yet when you posted :) If AVL Trees are not the appropriate solution, file a new bug against the HTML parser. my only goal here was to reduce our overall footprint...
This patch didn't include the mac build change to remove nsAVLTree.cpp from the xpcom project file. I went ahead and did that to fix the bustage.
My question about hashing was for harishd -- I'll let him bug himself and cite the # here, if he agrees. /be
>Why aren't we using an O(1) data structure like a hash table (non-minimal >perfect hash, generated, was used by MozillaClassic, for fixed tag vocabularies >such as HTML)? We do use has table for tags, however, we don't use it for entities if that's what you're refering to.
this broke the mozdev spellchecker (you can browse the source using bonsai, it's something like this: http://bonsai.mozilla.org/rview.cgi?cvsroot=/cvsroot&dir=mozilla/extensions/spellcheck/src/Attic&module=default&rev=BEONEX_0_9_BRANCH note that it's in the attic because it isn't on HEAD. The fact that bonsai doesn't make it easy for you to walk around on a branch is probably a bug that i should probably fix...) also note that i'm not claiming that spellchecker should be using avltree, just that it was using an xpcom datastructure which seemed like a reasonable choice, and I suspect we didn't post to npm.xpcom announcing its execution.