1209351 - Add to nsTHashTable the ability to remove an already-found entry

Status: RESOLVED FIXED

Description

[Nicholas Nethercote [:njn]]

This is a follow-up to bug 1202526, which did the same thing for PLDHashTable.

Here are two common nsTHashTable usage patterns:

> Entry* entry = table.GetEntry(key);
> if (!entry) {
>     return NS_ERROR_BLAH;
> }
> table.RemoveEntry(key);

> Entry* entry = table.GetEntry(key);
> if (foo(entry)) {
>     table.RemoveEntry(key);
> }

In both cases RemoveEntry() does an unnecessary re-lookup. You could instead use RawRemoveEntry(), but it does not subsequently shrink the table if its capacity gets too low.

This bug is about adding a new function that takes an already found entry (like RawRemoveEntry()) but also shrinks the table afterwards if appropriate (like RemoveEntry()).

Comment 1

[Nicholas Nethercote [:njn]]

Created attachment 8667026 [details] [diff] [review]
(part 1) - Add an overloading of nsTHashTable::RemoveEntry() that takes an already-found entry

Comment 2

[Nicholas Nethercote [:njn]]

Created attachment 8667027 [details] [diff] [review]
(part 2) - Optimize nsTHashTable::RemoveEntry() usage in dom/

Comment 3

[Nicholas Nethercote [:njn]]

Created attachment 8667028 [details] [diff] [review]
(part 3) - Optimize nsTHashTable::RemoveEntry() usage in gfx/

Comment 4

[Nicholas Nethercote [:njn]]

Created attachment 8667038 [details] [diff] [review]
(part 4) - Optimize nsTHashTable::RemoveEntry() usage in netwerk/

Comment 5

[Nicholas Nethercote [:njn]]

Created attachment 8667040 [details] [diff] [review]
(part 5) - Optimize nsTHashTable::RemoveEntry() usage in security/

Comment 6

[Nicholas Nethercote [:njn]]

Created attachment 8667041 [details] [diff] [review]
(part 6) - Optimize nsTHashTable::RemoveEntry() usage in toolkit/

Comment 7

[Nathan Froyd [:froydnj]]

When reviewing the toolkit/ patch, I realized one (small) problem is that people might do something like:

Entry* e = mTable.GetEntry(x);

if (e) {
  // ...
  mTable.RemoveEntry(e);
  ...
  // do something with e, which points to something completely different
}

It looks like e will have been destroyed, which may or may not leave it in a state that is sensible, but mTable could also have been resized, which means e may also point to a valid entry...just not the entry we thought it did.

WDYT about making RemoveEntry taking an |Entry*&|, so we can null out the pointer from the hashtable code?  (Maybe as a followup bug?)  That way, people mistakenly using Entry* after removing it would get a loud error about it (a null pointer dereference), rather than things happening to work and then not...  I guess RemoveEntry should also have documentation stating that you're not supposed to use the entry after it has been removed, too.

Comment 8

[Nicholas Nethercote [:njn]]

> WDYT about making RemoveEntry taking an |Entry*&|, so we can null out the
> pointer from the hashtable code? 

Not a bad idea...

Comment 9

[Boris Zbarsky [:bzbarsky, bz on IRC]]

Comment on attachment 8667027 [details] [diff] [review]
(part 2) - Optimize nsTHashTable::RemoveEntry() usage in dom/

r=me

Comment 10

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/114a04484e3b
https://hg.mozilla.org/integration/mozilla-inbound/rev/e645ae59fcec
https://hg.mozilla.org/integration/mozilla-inbound/rev/469b3a7acb0d
https://hg.mozilla.org/integration/mozilla-inbound/rev/43f1095ea9cd
https://hg.mozilla.org/integration/mozilla-inbound/rev/e33b7964a131
https://hg.mozilla.org/integration/mozilla-inbound/rev/6dff11f5236e

Comment 11

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/114a04484e3b
https://hg.mozilla.org/mozilla-central/rev/e645ae59fcec
https://hg.mozilla.org/mozilla-central/rev/469b3a7acb0d
https://hg.mozilla.org/mozilla-central/rev/43f1095ea9cd
https://hg.mozilla.org/mozilla-central/rev/e33b7964a131
https://hg.mozilla.org/mozilla-central/rev/6dff11f5236e