Note: There are a few cases of duplicates in user autocompletion which are being worked on.

move nsAVLTree into htmlparser

RESOLVED FIXED in mozilla1.2beta



HTML: Parser
16 years ago
15 years ago


(Reporter: Alec Flett, Assigned: Alec Flett)


Windows 2000
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)



(1 attachment)



16 years ago
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

16 years ago
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.
Priority: -- → P3
Target Milestone: --- → mozilla1.1

Comment 2

15 years ago
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.
Target Milestone: mozilla1.1alpha → mozilla1.2alpha


15 years ago
Target Milestone: mozilla1.2alpha → mozilla1.2beta


15 years ago
Depends on: 166874

Comment 3

15 years ago
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?
Attachment #98641 - Flags: superreview+

Comment 5

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

Attachment #98641 - Flags: review+
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 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 and thereabouts.


Comment 7

15 years ago
fixed! thanks for the reviews.
Last Resolved: 15 years ago
Resolution: --- → FIXED

Comment 8

15 years ago
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.


Comment 11

15 years ago
>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

15 years ago
this broke the mozdev spellchecker (you can browse the source using bonsai, it's
something like this:
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.
Blocks: 56301
You need to log in before you can comment on or make changes to this bug.