Closed Bug 1173600 Opened 4 years ago Closed 4 years ago

Add PLDHashTable::RemovingIterator


(Core :: XPCOM, defect)

Not set



Tracking Status
firefox41 --- fixed


(Reporter: njn, Assigned: njn)




(4 files)

We already have PLDHashTable::Iterator which is good for read-only iterations. But plenty of our existing PL_DHashTableEnumerate() calls use PL_DHASH_REMOVE to remove entries. So we need to be able to do removals during iteration.

We could extend Iterator to allow that but I prefer to add a new iterator type, for the following reasons.

- It makes it more obvious whether the iteration is read-only or not.

- It will eventually allow the sanity checker to do a better job; currently its checking of PL_DHashTableEnumerate() is weak because it doesn't know up front whether it's a read-only enumeration.

- js::HashTable has two different iterators, and it's a good precedent.
Depends on: 1174625
Things to note.

- Unlike Iterator, we don't allow RemovingIterator to be copied, because
  concurrent modifying accesses are a recipe for disaster.

- Both iterators now have tests.
Attachment #8622317 - Flags: review?(nfroyd)
Attachment #8622315 - Flags: review?(nfroyd) → review+
Comment on attachment 8622316 [details] [diff] [review]
(part 2) - Move post-enumeration shrinking code into its own function

Review of attachment 8622316 [details] [diff] [review]:

::: xpcom/glue/pldhash.cpp
@@ +767,5 @@
> +void
> +PLDHashTable::ShrinkIfAppropriate()
> +{
> +  uint32_t capacity = Capacity();
> +  if (mRemovedCount >= capacity >> 2 ||

This feels like a bogus check, comparing something accumulated over the entire lifetime of the table to a static snapshot of the table's current behavior.  If we could nuke it, then we could have Remove() call ShrinkIfAppropriate, which seems like a nice cleanup.  (Obviously a followup bug.)
Attachment #8622316 - Flags: review?(nfroyd) → review+
Comment on attachment 8622317 [details] [diff] [review]
(part 3) - Add PLDHashTable::RemovingIterator

Review of attachment 8622317 [details] [diff] [review]:

+1 for tests.

r=me, but let's get the naming thing figured out before you commit this.  I note that your commit message continues to refer to RemovingIterator. :p

::: xpcom/glue/pldhash.h
@@ +323,5 @@
>    Iter Iterate() const { return Iter(this); }
> +  // This is an iterator that allows elements to be removed during iteration.
> +  // If any elements are removed, the table may be resized once iteration ends.
> +  class RIter : public Iter

I don't like this name; I would argue that given the concept of "iterator", one would probably think that "R" means "reverse".  I made comments over in for this.

That proposal requires a move constructor, I think, but that doesn't seem so bad.  The proposal is also slightly more STL-y.

@@ +330,5 @@
> +    explicit RIter(PLDHashTable* aTable);
> +    ~RIter();
> +
> +    // Remove the current entry. Must only be called once per entry, and Get()
> +    // must not be called on that entry afterwards.

I was going to suggest RIter::Get() that calls Iter::Get() and asserts liveness, but I noticed that Iter::Get() already asserts liveness.  Maybe not a bad idea to add a comment to Iter::Get() about the multiple purposes (verifying we didn't program the iteration code wrong, and that the user of the iterator is following the contract(s)...) that assert serves?
Attachment #8622317 - Flags: review?(nfroyd) → review+
New version.
Attachment #8622955 - Flags: review?(nfroyd)
Comment on attachment 8622955 [details] [diff] [review]
(part 3) - Add PLDHashTable::RemovingIterator

Review of attachment 8622955 [details] [diff] [review]:

r=me with the same solution we agree on from bug 1174625 applied here, too.

::: xpcom/glue/pldhash.h
@@ +370,5 @@
> +  };
> +
> +  RemovingIterator RemovingIter() const
> +  {
> +    return mozilla::Move(RemovingIterator(const_cast<PLDHashTable*>(this)));

bug 1174625 comment 10 applies here, too.
Attachment #8622955 - Flags: review?(nfroyd) → review+
Blocks: 1174631
You need to log in before you can comment on or make changes to this bug.