1059550 - Add an iterator to PLDHashtable

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Joshua Cranmer [:jcranmer]]

I'm keeping this small in scope since it's needed to reopen the Thunderbird tree... extensions can be done in other bugs.

Comment 1

[Joshua Cranmer [:jcranmer]]

Attachment: Iterator support for pldhashtable

I'm using the use in Thunderbird as the correctness test for this patch.

Comment 2

[Nathan Froyd [:froydnj]]

Comment on attachment 8480230 [details] [diff] [review]
Iterator support for pldhashtable

Points for supporting ChaosMode.

I'd really rather not add this API that exists solely for Thunderbird's usage.  It'd be better if ::Enumerate was built on top of this, but I don't think this iterator even deals well with removals (or if it does, it's too late at night to think about it).

Can you just eagerly grab all the entries out of the hashtable, stuff them in an array, and iterate through those instead in Thunderbird?

Feel free to yell at me tomorrow morning.

Comment 3

[Joshua Cranmer [:jcranmer]]

So this is modeled partially after std::iterator, and I see this as a launching pad for using range-based for once we can claim min gcc 4.6. The iterator is intentionally invalid if the hashtable is modified in the middle (both addition and removal)--hence why the recursion count is incremented when the constructor is called and decremented when it is released.

As far as why I didn't just arrays... I felt that the hashtable was large enough to make the business of creating and filling arrays slightly risky in terms of mem/time profile. Since I knew that iterator style is also desired by some people instead of pesky Enumerate functions, I saw this as a starting point. I used Java-style iterators since that's more common in our codebase, I hate coding STL iterators (more work), and I already had an implementation of a Java-style iterator I could crib off of (although I ended up not using it).

I don't think of this as solely for Thunderbird but rather a launching pad for future usage.

Comment 4

[Nathan Froyd [:froydnj]]

Comment on attachment 8480230 [details] [diff] [review]
Iterator support for pldhashtable

Review of attachment 8480230 [details] [diff] [review]:
-----------------------------------------------------------------

OK, I take back my comments.  I guess this could start being useful for things inside Gecko, too.  I don't think it's worth going all the way to an STL iterator until we can use range-based |for| across all platforms...and we have a dev-platform discussion or similar about using range-based |for|.

What does need to be added are some comments.

Comment 5

[Joshua Cranmer [:jcranmer]]

Attachment: Iterator support for pldhashtable

Now with more comments.

Comment 6

[Nathan Froyd [:froydnj]]

Comment on attachment 8480607 [details] [diff] [review]
Iterator support for pldhashtable

Review of attachment 8480607 [details] [diff] [review]:
-----------------------------------------------------------------

Hooray for comments.

::: xpcom/glue/pldhash.cpp
@@ +857,5 @@
> +
> +  // The following code is taken from, and should be kept in sync with, the
> +  // PLDHashTable::Enumerate method above. The variables i and entryAddr (which
> +  // vary over the course of the for loop) are converted into mEntryOffset and
> +  // mEntryAddr, respectively.

Maybe add a comment in the equivalent place in ::Enumerate?

@@ +904,5 @@
> +
> +  // The following code is taken from, and should be kept in sync with, the
> +  // PLDHashTable::Enumerate method above. The variables i and entryAddr (which
> +  // vary over the course of the for loop) are converted into mEntryOffset and
> +  // mEntryAddr, respectively.

Likewise here.

::: xpcom/glue/pldhash.h
@@ +328,5 @@
>  
> +  /**
> +   * This is an iterator that works over the elements of PLDHashtable. It is not
> +   * safe to modify the hashtable while it is being iterated over; on debug
> +   * builds, attempting to do so will result in an assertion failure.

You may want to say something about PL_DHashRawRemove being legitimate?

Comment 7

[Joshua Cranmer [:jcranmer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6f9a154cab40

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/6f9a154cab40