124182 - move nsAVLTree into htmlparser

Status: RESOLVED FIXED

(Core :: DOM: HTML Parser, defect, P3)

Description

[Alec Flett]

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.

Comment 1

[Alec Flett]

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.

Comment 2

[Alec Flett]

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.

Comment 3

[Alec Flett]

Attachment: 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 4

[Johnny Stenback (:jst)]

Comment on attachment 98641 [details] [diff] [review]
move nsAVLTree into htmlparser

sr=jst, and you're doing all the makefile changes too, right?

Comment 5

[harishd]

Comment on attachment 98641 [details] [diff] [review]
move nsAVLTree into htmlparser

r=harishd

Comment 6

[Brendan Eich [:brendan]]

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

Comment 7

[Alec Flett]

fixed! thanks for the reviews.

Comment 8

[Alec Flett]

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...

Comment 9

[Brian Ryner (not reading)]

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.

Comment 10

[Brendan Eich [:brendan]]

My question about hashing was for harishd -- I'll let him bug himself and cite
the # here, if he agrees.

/be

Comment 11

[harishd]

>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.

Comment 12

[timeless]

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.