Closed
Bug 1310547
Opened 8 years ago
Closed 8 years ago
Allow LinkedList to hold RefPtr elements
Categories
(Core :: MFBT, defect)
Core
MFBT
Tracking
()
RESOLVED
FIXED
mozilla52
Tracking | Status | |
---|---|---|
firefox52 | --- | fixed |
People
(Reporter: billm, Assigned: billm)
References
Details
Attachments
(2 files, 2 obsolete files)
12.54 KB,
patch
|
froydnj
:
review+
|
Details | Diff | Splinter Review |
2.59 KB,
patch
|
froydnj
:
review+
|
Details | Diff | Splinter Review |
The usefulness of LinkedList is somewhat diminished by the fact that it can't be used to hold refcounted elements. I don't think there's a specific reason for this. I wrote a little adapter class that makes it work. With this patch, you can use LinkedList<RefPtr<T>> for a linked list that holds strong references to T elements (where T must be a subclass of LinkedListElement<RefPtr<T>>). This would probably make more sense if in all other places we used LinkedList<Foo*> instead of LinkedList<Foo>. I'm not sure what to do about that. Maybe instead of writing LinkedList<RefPtr<T>> we should use LinkedList<T, something>? Somehow LinkedList<RefPtr<T>> seems very natural though. Anyway, I'm open to ideas.
Attachment #8801613 -
Flags: review?(nfroyd)
Comment 1•8 years ago
|
||
Comment on attachment 8801613 [details] [diff] [review] patch Review of attachment 8801613 [details] [diff] [review]: ----------------------------------------------------------------- This is great. I was just reviewing a patch the other day that had LinkedList<T*> where T* was refcounted, and the logic was...awkward. The only real concern I have is about efficiency, see below. I'm not really sure how to solve this, though...I'd like to at least have some sort of discussion before r+'ing this. ::: mfbt/LinkedList.h @@ +79,5 @@ > + > +/** > + * LinkedList supports refcounted elements using this adapter class. Clients > + * using LinkedList<RefPtr<T>> will get a data structure that holds a strong > + * reference to T as long as T is in the list. I think we should put these adapters in mozilla::detail. @@ +212,5 @@ > * Get the next element in the list, or nullptr if this is the last element > * in the list. > */ > + ClientType getNext() { return ClientType(mNext->asT()); } > + ConstClientType getNext() const { return ConstClientType(mNext->asT()); } This part requires you to add a reference every time you call this method; particularly when you're traversing a linked list, we're going to incur a lot of refcounting traffic for very little gain. I guess the problem here is that if the list holds the only reference to the element, you can't have this method return T*, because then when you remove the element from the list, you are going to release the element, which leaves you holding a bogus pointer. Right? (I guess in some ways this is an argument for encouraging people to use for_each or equivalent, so we could do the efficient thing in that case, and then if somebody really needed manual traversal, they would have to accept a tiny amount of inefficiency. But even then, you could still call .remove() and blow things up, so that's not a total solution...) ::: mfbt/tests/TestLinkedList.cpp @@ +169,5 @@ > + while (ptr) { > + MOZ_RELEASE_ASSERT(ptr->mCount == 2); > + RefPtr<CountedClass> next = ptr->getNext(); > + ptr->remove(); > + ptr = next; Might as well do |ptr = Move(next);|.
Attachment #8801613 -
Flags: review?(nfroyd) → feedback+
Assignee | ||
Comment 2•8 years ago
|
||
For the efficiency issue, the only thing I can think of is to make getNext/getPrevious return raw pointers. That's a little less safe but it's not really any different than what we would get for nsTArray. What do you think Nathan? That also raises the issue of what to do about the other ClientType stuff: - setNext/setPrevious - Iterator - insertFront/insertBack - getFirst/getLast - popFirst/popLast popFirst/popLast pretty much have to return ClientType since they remove the element. But all the others could be raw pointers.
Flags: needinfo?(nfroyd)
Comment 3•8 years ago
|
||
(In reply to Bill McCloskey (:billm) from comment #2) > For the efficiency issue, the only thing I can think of is to make > getNext/getPrevious return raw pointers. That's a little less safe but it's > not really any different than what we would get for nsTArray. What do you > think Nathan? Yeah, I think that's what we're going to have to do. Returning RefPtr<T>&, as nsTArray would do, doesn't make sense here, AFAICT. > That also raises the issue of what to do about the other ClientType stuff: > - setNext/setPrevious > - Iterator > - insertFront/insertBack > - getFirst/getLast > - popFirst/popLast > > popFirst/popLast pretty much have to return ClientType since they remove the > element. But all the others could be raw pointers. Sounds good to me.
Flags: needinfo?(nfroyd)
Assignee | ||
Comment 4•8 years ago
|
||
Attachment #8801613 -
Attachment is obsolete: true
Attachment #8804508 -
Flags: review?(nfroyd)
Assignee | ||
Comment 5•8 years ago
|
||
I'm going to throw this in here since I found it useful. I have a couple of loops where I need to iterate over the list and conditionally remove elements. It's kind of annoying to have to do: for (RefPtr<T> p = list.getFirst(); p; ) { if (...) { RefPtr<T> next = p->getNext(); p->remove(); p = next; continue } ... p = p->getNext(); } This patch allows you instead to do: for (RefPtr<T> p = list.getFirst(); p; ) { if (...) { p = p->removeAndGetNext(); continue } ... p = p->getNext(); } which is a little nicer. I feel like this could be improved more, but I don't have any ideas.
Attachment #8804550 -
Flags: review?(nfroyd)
Comment 6•8 years ago
|
||
Comment on attachment 8804508 [details] [diff] [review] patch v2 Review of attachment 8804508 [details] [diff] [review]: ----------------------------------------------------------------- Looks good, r=me with changes below. ::: mfbt/LinkedList.h @@ +84,5 @@ > + * using LinkedList<RefPtr<T>> will get a data structure that holds a strong > + * reference to T as long as T is in the list. > + */ > +template<typename T> > +struct LinkedListAdapter Nit: we should call this LinkedListElementTraits. @@ +92,5 @@ > + typedef T* ClientType; > + typedef const T* ConstClientType; > + > + static void enterList(LinkedListElement<T>* elt) {} > + static void exitList(LinkedListElement<T>* elt) {} Documentation on these two functions would be good. @@ +118,5 @@ > { > + typedef typename detail::LinkedListAdapter<T>::RawType RawType; > + typedef typename detail::LinkedListAdapter<T>::ConstRawType ConstRawType; > + typedef typename detail::LinkedListAdapter<T>::ClientType ClientType; > + typedef typename detail::LinkedListAdapter<T>::ConstClientType ConstClientType; Maybe we should do something like: typedef typename detail::LinkedListElementTraits<T> Traits; typedef Traits::RawType RawType; ... ? That would enable shortening of calls to enterList and exitList below as well. @@ +355,5 @@ > private: > + typedef typename detail::LinkedListAdapter<T>::RawType RawType; > + typedef typename detail::LinkedListAdapter<T>::ConstRawType ConstRawType; > + typedef typename detail::LinkedListAdapter<T>::ClientType ClientType; > + typedef typename detail::LinkedListAdapter<T>::ConstClientType ConstClientType; Same typedef dance as we did in LinkedListElement would be helpful here. @@ +433,2 @@ > if (ret) { > + static_cast<LinkedListElement<T>*>(RawType(ret))->remove(); It would be great it we could implement this without the extra refcounting, something like: RawType ret = sentinel.getNext(); if (ret) { static_cast<LinkedListElement<T>*>(ret)->unlink(); } // dont_AddRef isn't available in MFBT. :( return already_AddRefed(ret); unlink() is a new, private function that implements the guts of remove(), but without the exitList() call. But that'd require another traits typedef or two, and I'm not sure if it generalizes nicely to other kinds of elements. =/ I guess file a followup bug for that, unless you think the above scheme is reasonable.
Attachment #8804508 -
Flags: review?(nfroyd) → review+
Comment 7•8 years ago
|
||
Comment on attachment 8804550 [details] [diff] [review] removeAndGetNext/Previous We'd need tests for this, along with documentation, but I think this is reasonable. Same comments about avoiding extra refcounting apply here.
Attachment #8804550 -
Flags: review?(nfroyd) → feedback+
Assignee | ||
Comment 8•8 years ago
|
||
With docs and tests. I'll file a new bug for getting rid of the refcounting in popFirst and such.
Attachment #8804550 -
Attachment is obsolete: true
Attachment #8805316 -
Flags: review?(nfroyd)
Comment 9•8 years ago
|
||
Comment on attachment 8805316 [details] [diff] [review] removeAndGetNext/Previous v2 Review of attachment 8805316 [details] [diff] [review]: ----------------------------------------------------------------- Thank you!
Attachment #8805316 -
Flags: review?(nfroyd) → review+
Comment 10•8 years ago
|
||
Pushed by wmccloskey@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/c41a71b1c24e Allow LinkedList to hold RefPtr elements (r=froydnj) https://hg.mozilla.org/integration/mozilla-inbound/rev/721e3171510d Add removeAndGetNext/Previous methods to LinkedList (r=froydnj) https://hg.mozilla.org/integration/mozilla-inbound/rev/aeeb739b7ba7 Use CancelableRunnable for mOnChannelConnectedTask (r=dvander) https://hg.mozilla.org/integration/mozilla-inbound/rev/eccaf394924f Remove FlushPendingInterruptQueue (r=dvander) https://hg.mozilla.org/integration/mozilla-inbound/rev/73e04e795ec3 Associate each message in IPC queue with the runnable that will run it (r=dvander)
Comment 11•8 years ago
|
||
Pushed by wmccloskey@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/b119fb8bc703 Revert "Bug 1310547 - Associate each message in IPC queue with the runnable that will run it (r=dvander)" https://hg.mozilla.org/integration/mozilla-inbound/rev/767af6517e3e Revert "Bug 1310547 - Remove FlushPendingInterruptQueue (r=dvander)" https://hg.mozilla.org/integration/mozilla-inbound/rev/cdcde3282769 Revert "Bug 1310547 - Use CancelableRunnable for mOnChannelConnectedTask (r=dvander)"
Assignee | ||
Comment 12•8 years ago
|
||
Landed some stuff here with the wrong bug number. I backed it out and re-landed.
Comment 13•8 years ago
|
||
Pushed by wmccloskey@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/b15d4e773bdd LinkedList compiler fixes
Comment 14•8 years ago
|
||
Backed bug 1312960 and bug 1310547 out for failing splitText-normalize.html in reftests on Windows 7 VM debug: Bug 1312960: https://hg.mozilla.org/integration/mozilla-inbound/rev/be5f087a2c4e3fcfd64a56921429f2a5b76dc02f https://hg.mozilla.org/integration/mozilla-inbound/rev/07f30746ec45034db4a2d6da54796e6742ab7dfb https://hg.mozilla.org/integration/mozilla-inbound/rev/4b390287fd434a9256a424a88f59d37cf1073362 https://hg.mozilla.org/integration/mozilla-inbound/rev/4c5b55684c21a261a1f4187b290d6ac7b4d5891c https://hg.mozilla.org/integration/mozilla-inbound/rev/c4f2be33044f293bba6518622bbf4043b48e57bb Bug 1310547: https://hg.mozilla.org/integration/mozilla-inbound/rev/b38d9a1cd7995c1cf79d7fc9e5351839a1a2d95c https://hg.mozilla.org/integration/mozilla-inbound/rev/0e4c28cbee9c44b1e1a97846212f03f95f4b11fb https://hg.mozilla.org/integration/mozilla-inbound/rev/ac349d1b3c10546da0193046d6ce4b7f065eb070 https://hg.mozilla.org/integration/mozilla-inbound/rev/d9c679129b669805d737c09c97a4768a8e6f7e6f https://hg.mozilla.org/integration/mozilla-inbound/rev/7e9f99645168e37e0f7298faebeba3e263491bbc https://hg.mozilla.org/integration/mozilla-inbound/rev/c5a67edeb6239cc576be71fc8ec4955e544a4ca4 https://hg.mozilla.org/integration/mozilla-inbound/rev/e419e663860780657e7825bd7a0108e414c1a134 https://hg.mozilla.org/integration/mozilla-inbound/rev/e0730d3f61026ed2d45b4f339b7a1082199bcedb https://hg.mozilla.org/integration/mozilla-inbound/rev/ebd1c1823d617cabfc57d3d9325f2be4a28330ec First not busted push which exposes the failure: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=a171aae3ae491dd52e184735c51924c7a467a0bf Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=38420599&repo=mozilla-inbound 01:36:25 INFO - REFTEST TEST-UNEXPECTED-FAIL | file:///C:/slave/test/build/tests/reftest/tests/layout/reftests/selection/splitText-normalize.html | load failed: timed out waiting for pending paint count to reach zero (waiting for MozAfterPaint)
Flags: needinfo?(wmccloskey)
Comment 15•8 years ago
|
||
Pushed by wmccloskey@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/815e8f226bb9 Allow LinkedList to hold RefPtr elements (r=froydnj) https://hg.mozilla.org/integration/mozilla-inbound/rev/b30dfbf5fe2a Add removeAndGetNext/Previous methods to LinkedList (r=froydnj)
Comment 16•8 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/815e8f226bb9 https://hg.mozilla.org/mozilla-central/rev/b30dfbf5fe2a
Status: NEW → RESOLVED
Closed: 8 years ago
status-firefox52:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla52
Assignee | ||
Updated•8 years ago
|
Flags: needinfo?(wmccloskey)
You need to log in
before you can comment on or make changes to this bug.
Description
•