200507 - switch nsHTMLEntities to PLDHashTable

Status: RESOLVED WONTFIX

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

Description

[Alec Flett]

currently, nsHTMLEntities is using nsAVLTree in order to create 2 tables for
lookup, for string<->code conversion (matching entities to their numerical values)

this is silly becuase the tables are completely static, and thus there is no
need for a continually balanced tree. In addition, nsAVLTree is bloaty, because
it allocates a bunch of little nsAVLNode objects.

Instead, we should just use PLDHashTable, especially given that we know the
number of entities ahead of time. PLDHashTable will just allocate all the
objects in one sweep.

and yes, at some point we should use gperf for this.

the great thing about this is that this is the last consumer of nsAVLTree in the
tree, and we can remove nsAVLTree entirely with this.

Comment 1

[Alec Flett]

Attachment: switch to pldhash

And here's the patch.

Comment 2

[Alec Flett]

Comment on attachment 119304 [details] [diff] [review]
switch to pldhash

Jag/Harish - can I get a review here? this is pretty straight forward stuff...
also:
1) I'll remove nsAVLTree.* entirely from the tree
2) Since attaching this patch I've fixed all the odd/inconsistent indenting via
xemacs's indent-region

Comment 3

[harishd]

Comment on attachment 119304 [details] [diff] [review]
switch to pldhash

>+    return (nsCRT::strcmp(entry->node->mStr, str)==0);

Nit pick: Add whitespaces around ==.

>+PR_STATIC_CALLBACK(PRBool)
>+matchNodeUnicode(PLDHashTable*, const PLDHashEntryHdr* aHdr,
>+                const void* key)

Needs alignment.

Comment 4

[rbs]

Maybe this could be further simplified by using jkeiser's recent nsTHashTable.

Comment 5

[John Keiser (jkeiser)]

It's bsmedberg's, and I absolutely think it could :)  This uses standard key types.

Comment 6

[Benjamin Smedberg]

Yes, the basic idea is you have a table of type
nsDataHashtable<nsCStringHashKey,PRUint32>

then you can
Put(nsACString aEntity, PRUint32 aUnichar) and
Get(nsACString aEntity, PRUint32 *aUnichar)

Comment 7

[Alec Flett]

I'm not objecting to using nsDataHashtable or what have you, but I have a very
specific set of static data (a const array of EntityNodes) and I'd like to avoid
storing any more than a pointer to the structure.

is there a way to do that? otherwise I'll just stick to pldhash

Comment 8

[John Keiser (jkeiser)]

Ah, yes, in that case you just want to declare an entry struct that is a pointer
to that struct and declare nsTHashtable<MyEntryStruct>.  The entry struct would
look like this:

http://lxr.mozilla.org/seamonkey/source/xpcom/ds/nsTHashtable.h#59

You just store the pointer as the data member and grab the key and value out of
it when you need them.  Basically it's a simpler method of declaring the
functions you declared manually here (you get to declare class members instead
of first-level functions).

Comment 9

[Alec Flett]

Attachment: updated patch, with -bw

here's an updated patch with whitespace fixed

Comment 10

[Alec Flett]

Comment on attachment 119364 [details] [diff] [review]
updated patch, with -bw

transferring r=harishd, re-requesting jag's review.

Comment 11

[rbs]

alecf did nsCOMArray and has been making sure that people use it. 
Hope that if nsTHashTable is ok in this situation, would be nice to use it too.

Comment 12

[Benjamin Smedberg]

you can do do it with nsDataHashtable and const char* 
nsDataHashtable<nsConstCharHashKey, PRUint32>:

class nsConstCharHashKey : protected PLDHashEntryHdr
{
public:
  typedef const char* KeyType;
  typedef const char* KeyTypePointer;
 
  nsCStringHashKey(const char* aStr) : mStr(aStr) { }
  nsCStringHashKey(const nsConstCharHashKey& toCopy) : mStr(toCopy.mStr) { }
  ~nsCStringHashKey() { }

  KeyType GetKey() const { return mStr; }
  KeyTypePointer GetKeyPointer() const { return mStr; }

  PRBool KeyEquals(KeyTypePointer aKey) const
    { return !nsCRT::strcmp(mStr, aKey); }

  static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; }
  static PLDHashNumber HashKey(KeyTypePointer aKey)
  {
    return nsCRT::HashCode(aKey);
  }
  static PRBool AllowMemMove() { return PR_TRUE; }

private:
  const char* mStr;
};

Comment 13

[jag (Peter Annema)]

Comment on attachment 119364 [details] [diff] [review]
updated patch, with -bw

sr=jag

Comment 14

[Alec Flett]

I'm going to check this in but leave this open for me to do the final
conversion, since the big footprint win is from the dropping of nsAVLTree.. i.e.
probably 80% of the footprint win is done by this patch..I'll do the last 20% next.

Comment 15

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Comment on attachment 119364 [details] [diff] [review]
updated patch, with -bw

>+  if (!gEntityToUnicode.ops)
>+    PL_DHashTableInit(&gEntityToUnicode, &EntityToUnicodeOps,
>+                      nsnull, sizeof(EntityNodeEntry), NS_HTML_ENTITY_COUNT);
>+                         
>+  if (!gUnicodeToEntity.ops)
>+    PL_DHashTableInit(&gUnicodeToEntity, &UnicodeToEntityOps,
>+                      nsnull, sizeof(EntityNodeEntry), NS_HTML_ENTITY_COUNT);

Shouldn't you be using |PRUint32(float(NS_HTML_ENTITY_COUNT) / 0.75)|, since
the default maxAlphaFrac is 0.75?

Comment 16

[Eli Friedman]

Is this fixed?

Comment 17

[Henri Sivonen (:hsivonen)]

Got rid of this file for 57!