Closed Bug 1277725 Opened 8 years ago Closed 7 years ago

Implement a linked list primitive supporting singly linked lists and flexible link storage

Categories

(Core :: MFBT, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox49 --- affected
firefox55 --- fixed

People

(Reporter: terrence, Assigned: erahm)

Details

Attachments

(1 file, 4 obsolete files)

Attached patch implement_list-v0.diff (obsolete) — Splinter Review
I can think of at least half a dozen places off the top of my head that we could use this List that we cannot use LinkedList because of the overhead or lack of pointer placement options. I specifically have in mind Rooted, NativeIterators, Chunks, Arenas, NonEscapingWrapperRoots, and GCList at the moment. I'm sure there are others. I've taken the conceit of implementing this in mfbt in the assumption that it will be broadly useful in Gecko as well.
Attachment #8759428 - Flags: review?(jwalden+bmo)
Comment on attachment 8759428 [details] [diff] [review]
implement_list-v0.diff

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

::: mfbt/List.h
@@ +4,5 @@
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +#ifndef ds_ForwardList_h
> +#define ds_ForwardList_h

You're not in ds/ anymore.

@@ +31,5 @@
> +//
> +//   class ObserverContainer
> +//   {
> +//   private:
> +//     LinkedList<Observer> list;

Seems like this should probably be using gecko style, shouldn't it? mList here, and obviously lots of changes elsewhere too.

@@ +34,5 @@
> +//   private:
> +//     LinkedList<Observer> list;
> +//
> +//   public:
> +//     void addObserver(Observer* aObserver)

Heh. *Especially* if you're going to be doing the aParameter thing anyway!

@@ +59,5 @@
> +namespace mozilla {
> +
> +// Provides access to a next and previous element pointer named |next| and
> +// |prev| respectively. This class is the default and will work if the list
> +// element derives from FowradListElement or ListElement.

*ForwardListElement

@@ +61,5 @@
> +// Provides access to a next and previous element pointer named |next| and
> +// |prev| respectively. This class is the default and will work if the list
> +// element derives from FowradListElement or ListElement.
> +template <typename T>
> +struct NextPrevMemberHelper {

There must be a better name here than SomethingHelper. What do you think of ListLinkAccessor or ListLinkAccessors?

Might also want to say what the requirements are when using this only for a ForwardList (as in, SetPrev and GetPrev can exist but will be ignored, or something?)

@@ +104,5 @@
> +
> +    T* operator *() const { return mCurrent; }
> +    T* operator ->() const { return mCurrent; }
> +
> +    const Iterator& operator++() {

Should there be an operator++(int) defined too? Or deleted? I'm not sure if some defaulting comes into play here.

@@ +109,5 @@
> +      mCurrent = LinkHelper::GetNext(mCurrent);
> +      return *this;
> +    }
> +
> +    bool operator!=(Iterator& aOther) const {

seems like this should be const Iterator&

@@ +147,5 @@
> +    return result;
> +  }
> +};
> +
> +// As for ForwardListElement. Deriving from this will allow T to be inserted

"As for ForwardListElement" -> "Doubly-linked version of ForwardListElement", maybe?

@@ +221,5 @@
> +  // be in a list.
> +  void pushFront(T* elmt) {
> +    MOZ_ASSERT(elmt);
> +    MOZ_ASSERT(!LinkHelper::GetNext(elmt));
> +    MOZ_ASSERT(!LinkHelper::GetPrev(elmt));

This seems to be a bit of a hidden constraint on GetNext/GetPrev that should perhaps be documented up with the LinkHelper stuff -- your elements must be initialized in a way that GetNext and GetPrev return nullptr.

@@ +224,5 @@
> +    MOZ_ASSERT(!LinkHelper::GetNext(elmt));
> +    MOZ_ASSERT(!LinkHelper::GetPrev(elmt));
> +    MOZ_ASSERT((head_ != nullptr) == (tail_ != nullptr));
> +    LinkHelper::SetPrev(elmt, nullptr);
> +    LinkHelper::SetNext(elmt, head_);

I know it can be argued both ways, but would it be better to make these circular doubly-linked lists? That preserves constant time pushBack/popBack without changing much else, but removes the need for a tail_ pointer. It does complicate things a little, though.

@@ +338,5 @@
> +  }
> +
> +  // Returns an iterator referencing the first found element whose value matches
> +  // the given element.
> +  Iterator find(T* elmt) {

This is a bit of a strange operation. I kind of wonder if it would make more sense the other way around -- to have a |bool contains(elt)| that iterates the list, and either make find(elt) be

  return contains(elt) ? Iterator(elt) : Iterator();

or rename 'find' to 'iterator' or 'at' or 'Iterator::from' or something.
Attachment #8759428 - Flags: feedback+
Comment on attachment 8759428 [details] [diff] [review]
implement_list-v0.diff

Cancelling review while I address the Steve's feedback.
Attachment #8759428 - Flags: review?(jwalden+bmo)
Comment on attachment 8759428 [details] [diff] [review]
implement_list-v0.diff

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

I've been staring at this too long, should just post what I have and leave alone/wait for more conversation to happen.

::: mfbt/List.h
@@ +7,5 @@
> +#ifndef ds_ForwardList_h
> +#define ds_ForwardList_h
> +
> +// Where mozilla::LinkedList strives for ease of use above all other
> +// considerations, mozilla::List strives for flexibility. The following are

Looking at this header, it really seems to me that it's doing two distinct things.  It's offering a SinglyLinkedList, and it's offering a DoublyLinkedList (no way are you squatting "List" for this :-) -- and also it's too generic a name, doesn't communicate what sort of list it is).  The only real thing shared between the two is NextPrevMemberHelper, but that's so minimal it doesn't seem necessary, or all that useful.  Please split this header into {Singly,Doubly}LinkedList.h.

@@ +59,5 @@
> +namespace mozilla {
> +
> +// Provides access to a next and previous element pointer named |next| and
> +// |prev| respectively. This class is the default and will work if the list
> +// element derives from FowradListElement or ListElement.

Name the element base-classes {Singly,Doubly}LinkedListElement.

Also, please explicitly state that users *should* specialize the sibling trait-access class if all {Singly,Doubly}LinkedList of T will use the same algorithm for element access, and otherwise users should specify custom sibling access *at each instance*.  That is: if all lists of T use the same sibling access algorithms, they *should* specialize this and specify it once.  And if they don't all use the same algorithm, *every instance* should individually specify custom access.  No mixing and matching, for user sanity.  (Unfortunately I don't think there's any way for us to enforce this.)

@@ +61,5 @@
> +// Provides access to a next and previous element pointer named |next| and
> +// |prev| respectively. This class is the default and will work if the list
> +// element derives from FowradListElement or ListElement.
> +template <typename T>
> +struct NextPrevMemberHelper {

Please name this struct {Singly,Doubly}LinkedSiblingAccess.

@@ +81,5 @@
> +public:
> +  ForwardListElement() : next(nullptr) {}
> +};
> +
> +// A singly linked list. |T| is the type of element contained in the list.  |T|

Having to specify singly-linked or doubly-linked as the very first sentence of docs, seems like a tell to me that the name should be saying that already.  :-)

@@ +87,5 @@
> +// argument |LinkHelper| provides code to tell this list how to get and set the
> +// next pointer. The actual storage of the next link may reside anywhere and be
> +// encoded in any way.
> +template <typename T, typename LinkHelper = NextPrevMemberHelper<T>>
> +class ForwardList

LinkHelper can be SiblingAccess, for both classes.

@@ +94,5 @@
> +
> +public:
> +  ForwardList() : head_(nullptr) {}
> +
> +  class Iterator {

Make the list and iterator classes final -- data structure classes should be used in has-a configuration, not is-a.

@@ +104,5 @@
> +
> +    T* operator *() const { return mCurrent; }
> +    T* operator ->() const { return mCurrent; }
> +
> +    const Iterator& operator++() {

Yeah, operator++(int) should be defined.  And for the doubly-linked version, the decrement operators.

@@ +184,5 @@
> +
> +    T* operator *() const { return mCurrent; }
> +    T* operator ->() const { return mCurrent; }
> +
> +    const Iterator& operator++() {

Seems like operator++(int), operator--(), and operator--(int) are worth adding, too.

@@ +212,5 @@
> +  const Iterator cend() const { return Iterator(); }
> +
> +  // Returns true if the list contains no elements.
> +  bool isEmpty() const {
> +    MOZ_ASSERT((head_ != nullptr) == (tail_ != nullptr));

I'd add a reason-string here for developer readability if the assertion's ever hit.

@@ +224,5 @@
> +    MOZ_ASSERT(!LinkHelper::GetNext(elmt));
> +    MOZ_ASSERT(!LinkHelper::GetPrev(elmt));
> +    MOZ_ASSERT((head_ != nullptr) == (tail_ != nullptr));
> +    LinkHelper::SetPrev(elmt, nullptr);
> +    LinkHelper::SetNext(elmt, head_);

I think I mildly agree with just having explicit head/tail, even if it's spacier.

@@ +236,5 @@
> +    }
> +  }
> +
> +  // Remove the head of the list and return it. Calling this on an empty list
> +  // will return nullptr.

jlebar and I had an argument over this interface years ago, and I still think it's wrong.  A mutating operation shouldn't have the ability to not-mutate, as this one has if the list is empty.  This function should assert non-empty, and it should always pop the first element.  (I should resurrect the patch I had years ago to fix popFront in LinkedList, for consistency.  Note that this operation is currently *inconsistent* with ForwardList, and ForwardList does it the right way.)

@@ +238,5 @@
> +
> +  // Remove the head of the list and return it. Calling this on an empty list
> +  // will return nullptr.
> +  T* popFront() {
> +    MOZ_ASSERT((head_ != nullptr) == (tail_ != nullptr));

Reason-string again for these sorts of asserts.

@@ +254,5 @@
> +    }
> +    return result;
> +  }
> +
> +  // Inserts elmt into the list at the tail position. |elmt| must not already

"Append elmt to the list."

@@ +259,5 @@
> +  // be in a list.
> +  void pushBack(T* elmt) {
> +    MOZ_ASSERT(elmt);
> +    MOZ_ASSERT(!LinkHelper::GetNext(elmt));
> +    MOZ_ASSERT(!LinkHelper::GetPrev(elmt));

The !prev, !next assertion pair probably should be a detail::IsInList(T*) that combines the two -- seems clearer than two separate assertions.

@@ +274,5 @@
> +    }
> +  }
> +
> +  // Remove the tail of the list and return it. Calling this on an empty list
> +  // will return nullptr.

As with popFront, this should assert non-empty.

@@ +293,5 @@
> +    return result;
> +  }
> +
> +  // Insert the given |elmt| *before* |iter|.
> +  void insert(const Iterator& iter, T* elmt) {

Hmmmmmmmm.  It feels...somewhat strange...that you'd have to have a reference to the containing list to insert.  I guess it's necessary, tho, to keep head_/tail_ synced.  Feh.

Also, seems like it might be arbitrary to support only before-insertion and not after-insertion.  Probably we would want both?

Worth asserting the list contains *iter?  Makes the method O(n), so I dunno exactly.  I guess we could have *two* methods, one that asserts contains, and let users decide if the hit is bearable.  Or maybe not(?).

@@ +338,5 @@
> +  }
> +
> +  // Returns an iterator referencing the first found element whose value matches
> +  // the given element.
> +  Iterator find(T* elmt) {

Hmm.  I'm not horribly opposed to the name/signature as they exist now, but not horribly happy with 'em.  I guess I'd leave it alone, with weak confidence of feeling.

@@ +349,5 @@
> +  }
> +
> +  // Returns whether the given element is in the list. Note that this uses
> +  // T::operator=, not pointer comparison.
> +  bool contains(T* elmt) {

It probably doesn't make sense to have two methods, one doing element-equality, one doing pointer-equality.  At least, not unless you have use cases for both that we can evaluate.
Hey Jeff, this is an update of the work Terrence started. I just went with a
doubly-linked list because that's all I need right now.

I'm open to changing things around, I think I addressed most of your previous
feedback.
Attachment #8858177 - Flags: feedback?(jwalden+bmo)
Attachment #8759428 - Attachment is obsolete: true
Assignee: terrence.d.cole → erahm
MozReview-Commit-ID: JnhnomQwSja
Attachment #8858358 - Flags: review?(jwalden+bmo)
Attachment #8858358 - Flags: feedback?(sphink)
Attachment #8858177 - Attachment is obsolete: true
Attachment #8858177 - Flags: feedback?(jwalden+bmo)
Sorry for the churn. I fixed some typos, cleaned up the iterator a bit, actually ran the custom accessor tests, and made popFront/popBack release assert the list is not empty.
Comment on attachment 8858358 [details] [diff] [review]
Implement a list class that is both usable and efficient

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

::: mfbt/DoublyLinkedList.h
@@ +12,5 @@
> +
> +// Where mozilla::LinkedList strives for ease of use above all other
> +// considerations, mozilla::DoublyLinkedList strives for flexibility. The
> +// following are things that can be done with mozilla::DoublyLinkedList and
> +// mozilla::ForwardList that cannot be done with mozilla::LinkedList:

There's no mozilla::ForwardList (for now).

@@ +60,5 @@
> +namespace mozilla {
> +
> +// Provides access to a next and previous element pointer named |mNext| and
> +// |mPrev| respectively. This class is the default and will work if the list
> +// element derives from DoublyLinkedListElement.

I wonder if it's also worth mentioning that this will work for anything that has mNext and mPrev fields. (And if so, hopefully this is what they're meant to be used for!)

@@ +69,5 @@
> +  static void SetPrev(T* aElm, T* aPrev) { aElm->mPrev = aPrev; }
> +  static T* GetPrev(T* aElm) { return aElm->mPrev; }
> +};
> +
> +// Deriving from this will allow T to be inserted into and removed from a List.

s/List/DoublyLinkedList/

@@ +123,5 @@
> +    T* operator ->() const { return mCurrent; }
> +
> +    const Iterator& operator++() {
> +      mCurrent = SiblingAccess::GetNext(mCurrent);
> +      return *this;

I would expect a non-const Iterator& here. Why prevent the return value from being incremented and things?

@@ +129,5 @@
> +
> +    Iterator& operator++(int) {
> +      Iterator result = *this;
> +      ++(*this);
> +      return result;

This does not look right. You're returning a reference to a temporary. I believe this should be returning an Iterator (copy), not an Iterator&.

@@ +130,5 @@
> +    Iterator& operator++(int) {
> +      Iterator result = *this;
> +      ++(*this);
> +      return result;
> +    }

How about operator--() and operator--(int)?

@@ +205,5 @@
> +  }
> +
> +  // Inserts aElm into the list at the tail position. |aElm| must not already
> +  // be in a list.
> +  void pushBack(T* aElm) {

I do wonder whether it's necessary to use both front/back and head/tail terminology. If the desired API is front/back, maybe mHead -> mFront and mTail -> mBack?

@@ +270,5 @@
> +    SiblingAccess::SetPrev(after, aElm);
> +  }
> +
> +  // Removes the given element from the list. The element must be in this list.
> +  void remove(T* aElm) {

maybe MOZ_ASSERT(aElm) here. Otherwise, it'll make it through everything until it seg faults in SiblingAccess::GetNext.

@@ +272,5 @@
> +
> +  // Removes the given element from the list. The element must be in this list.
> +  void remove(T* aElm) {
> +    MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
> +               (aElm == mHead && aElm == mTail));

MOZ_ASSERT(..., "attempted to remove element not in this list") or something

@@ +293,5 @@
> +    SiblingAccess::SetPrev(aElm, nullptr);
> +  }
> +
> +  // Returns an iterator referencing the first found element whose value matches
> +  // the given element.

"matches" according to operator==, right?

@@ +299,5 @@
> +    return std::find(begin(), end(), aElm);
> +  }
> +
> +  // Returns whether the given element is in the list. Note that this uses
> +  // T::operator=, not pointer comparison.

operator==, I assume
Attachment #8858358 - Flags: feedback?(sphink) → feedback+
Updated per sfink's feedback. Didn't change |mHead| and |mTail| as I don't
think the internal member should matter in the external interface, but am happy
to change them pending an r+.
Attachment #8858979 - Flags: review?(jwalden+bmo)
Attachment #8858358 - Attachment is obsolete: true
Attachment #8858358 - Flags: review?(jwalden+bmo)
Comment on attachment 8858979 [details] [diff] [review]
Implement a list class that is both usable and efficient

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

Mostly style nitpicks, but the actual bugs I should look at the fixes as a double-check on them.

::: mfbt/DoublyLinkedList.h
@@ +2,5 @@
> +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +

Add a single-line /** */-style overview comment here.

@@ +9,5 @@
> +
> +#include <algorithm>
> +#include <iterator>
> +
> +// Where mozilla::LinkedList strives for ease of use above all other

Use /** */-style comments for this, this is SpiderMonkey style right now.

@@ +114,5 @@
> +  class Iterator final {
> +    T* mCurrent;
> +
> +  public:
> +    typedef std::forward_iterator_tag iterator_category;

Make these |using| now.

@@ +182,5 @@
> +    MOZ_ASSERT(aElm);
> +    MOZ_ASSERT(ElementNotInList(aElm));
> +    MOZ_ASSERT(isStateValid());
> +
> +    SiblingAccess::SetPrev(aElm, nullptr);

I don't get why this line is necessary.  Doesn't the not-in-list assertion guarantee this is already the case?

@@ +192,5 @@
> +
> +    mHead = aElm;
> +    if (!mTail) {
> +      mTail = aElm;
> +    }

Notwithstanding what comment 0 says about this being usable to implement Rooted, I'm not sure we'd want to.  This implementation seems to have a lot of null-checks and (in particular, control flow) operations in it, that aren't in Rooted's current implementation.  The idea abstractly sounds nice, but if we want to not have to fully implement Rooted for some reason, seems like js/src/ds/Nestable.h would be closer to the right foundation.

@@ +198,5 @@
> +
> +  // Remove the head of the list and return it. Calling this on an empty list
> +  // will assert.
> +  T* popFront() {
> +    MOZ_RELEASE_ASSERT(!isEmpty());

A release-assert for this seems overkill generally.  The typical result of misuse would be a safe near-null write and is not worth extra overhead/special caring.

@@ +292,5 @@
> +    MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
> +               (aElm == mHead && aElm == mTail),
> +               "Attempted to remove element not in this list");
> +
> +    if (SiblingAccess::GetPrev(aElm)) {

if (T* prev = SiblingAccess::GetPrev(aElm))

and then use |prev| directly in the call just below.

@@ +299,5 @@
> +      MOZ_ASSERT(mHead == aElm);
> +      mHead = SiblingAccess::GetNext(aElm);
> +    }
> +
> +    if (SiblingAccess::GetNext(aElm)) {

Same local thing as above.

@@ +311,5 @@
> +    SiblingAccess::SetPrev(aElm, nullptr);
> +  }
> +
> +  // Returns an iterator referencing the first found element whose value matches
> +  // the given element accourding to operator==.

according

Also -- all these function comments should be /** */-style doc comments.

::: mfbt/tests/TestDoublyLinkedList.cpp
@@ +39,5 @@
> +  MOZ_RELEASE_ASSERT(list.isEmpty());
> +  MOZ_RELEASE_ASSERT(!list.begin());
> +  MOZ_RELEASE_ASSERT(!list.end());
> +  MOZ_RELEASE_ASSERT(!list.popFront());
> +  MOZ_RELEASE_ASSERT(!list.popBack());

...these popFront/popBack items seem like they assert, don't they?  First statement in those functions asserts the list is non-empty, but |list| clearly is here.

@@ +43,5 @@
> +  MOZ_RELEASE_ASSERT(!list.popBack());
> +
> +  for (SomeClass& x : list) {
> +    MOZ_RELEASE_ASSERT(x.mValue);
> +    MOZ_RELEASE_ASSERT(false);

Shouldn't this just be |MOZ_ASSERT_NOT_REACHED(...)|?

@@ +113,5 @@
> +  for (SomeClass& x : list) {
> +    x.incr();
> +  }
> +
> +  MOZ_RELEASE_ASSERT(*list.begin() == two);

...am I misreading, or should this be |== three|?  Used to be 2, then we incremented, no?

@@ +117,5 @@
> +  MOZ_RELEASE_ASSERT(*list.begin() == two);
> +  MOZ_RELEASE_ASSERT(*++list.begin() == three);
> +
> +  SomeClass four(4);
> +  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));

Hmm?  Doesn't look right to me -- the list is [3, 3] now with no four in sight.

@@ +120,5 @@
> +  SomeClass four(4);
> +  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
> +}
> +
> +void

static on the subtest.
Attachment #8858979 - Flags: review?(jwalden+bmo) → review-
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #9)
> Comment on attachment 8858979 [details] [diff] [review]
> Implement a list class that is both usable and efficient
> 
> Review of attachment 8858979 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Mostly style nitpicks, but the actual bugs I should look at the fixes as a
> double-check on them.
> 
> ::: mfbt/DoublyLinkedList.h
> @@ +2,5 @@
> > +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
> > +/* This Source Code Form is subject to the terms of the Mozilla Public
> > + * License, v. 2.0. If a copy of the MPL was not distributed with this
> > + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> > +
> 
> Add a single-line /** */-style overview comment here.

OK.

> @@ +9,5 @@
> > +
> > +#include <algorithm>
> > +#include <iterator>
> > +
> > +// Where mozilla::LinkedList strives for ease of use above all other
> 
> Use /** */-style comments for this, this is SpiderMonkey style right now.

Will update.

> @@ +114,5 @@
> > +  class Iterator final {
> > +    T* mCurrent;
> > +
> > +  public:
> > +    typedef std::forward_iterator_tag iterator_category;
> 
> Make these |using| now.

Will update, is this official style now? We should update the coding style doc if so.

> @@ +182,5 @@
> > +    MOZ_ASSERT(aElm);
> > +    MOZ_ASSERT(ElementNotInList(aElm));
> > +    MOZ_ASSERT(isStateValid());
> > +
> > +    SiblingAccess::SetPrev(aElm, nullptr);
> 
> I don't get why this line is necessary.  Doesn't the not-in-list assertion
> guarantee this is already the case?

Yeah it can be removed.

> @@ +192,5 @@
> > +
> > +    mHead = aElm;
> > +    if (!mTail) {
> > +      mTail = aElm;
> > +    }
> 
> Notwithstanding what comment 0 says about this being usable to implement
> Rooted, I'm not sure we'd want to.  This implementation seems to have a lot
> of null-checks and (in particular, control flow) operations in it, that
> aren't in Rooted's current implementation.  The idea abstractly sounds nice,
> but if we want to not have to fully implement Rooted for some reason, seems
> like js/src/ds/Nestable.h would be closer to the right foundation.

Yeah, I have no intent to make this work for Rooted. If someone wants to follow up on that more power to them.

> @@ +198,5 @@
> > +
> > +  // Remove the head of the list and return it. Calling this on an empty list
> > +  // will assert.
> > +  T* popFront() {
> > +    MOZ_RELEASE_ASSERT(!isEmpty());
> 
> A release-assert for this seems overkill generally.  The typical result of
> misuse would be a safe near-null write and is not worth extra
> overhead/special caring.

OK.

> @@ +292,5 @@
> > +    MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
> > +               (aElm == mHead && aElm == mTail),
> > +               "Attempted to remove element not in this list");
> > +
> > +    if (SiblingAccess::GetPrev(aElm)) {
> 
> if (T* prev = SiblingAccess::GetPrev(aElm))
> 
> and then use |prev| directly in the call just below.

OK.

> @@ +299,5 @@
> > +      MOZ_ASSERT(mHead == aElm);
> > +      mHead = SiblingAccess::GetNext(aElm);
> > +    }
> > +
> > +    if (SiblingAccess::GetNext(aElm)) {
> 
> Same local thing as above.

OK.

> @@ +311,5 @@
> > +    SiblingAccess::SetPrev(aElm, nullptr);
> > +  }
> > +
> > +  // Returns an iterator referencing the first found element whose value matches
> > +  // the given element accourding to operator==.
> 
> according

Will update.

> Also -- all these function comments should be /** */-style doc comments.

Will update.

> ::: mfbt/tests/TestDoublyLinkedList.cpp
> @@ +39,5 @@
> > +  MOZ_RELEASE_ASSERT(list.isEmpty());
> > +  MOZ_RELEASE_ASSERT(!list.begin());
> > +  MOZ_RELEASE_ASSERT(!list.end());
> > +  MOZ_RELEASE_ASSERT(!list.popFront());
> > +  MOZ_RELEASE_ASSERT(!list.popBack());
> 
> ...these popFront/popBack items seem like they assert, don't they?  First
> statement in those functions asserts the list is non-empty, but |list|
> clearly is here.

Ah right, that was a recent change from your previous review. I'll remove them.

> @@ +43,5 @@
> > +  MOZ_RELEASE_ASSERT(!list.popBack());
> > +
> > +  for (SomeClass& x : list) {
> > +    MOZ_RELEASE_ASSERT(x.mValue);
> > +    MOZ_RELEASE_ASSERT(false);
> 
> Shouldn't this just be |MOZ_ASSERT_NOT_REACHED(...)|?

OK, but I need keep the x.mValue assert to shut up a warning about x being unused.

> @@ +113,5 @@
> > +  for (SomeClass& x : list) {
> > +    x.incr();
> > +  }
> > +
> > +  MOZ_RELEASE_ASSERT(*list.begin() == two);
> 
> ...am I misreading, or should this be |== three|?  Used to be 2, then we
> incremented, no?

We are comparing objects using their operator==. In this case |two.mValue == two.mValue|.

> @@ +117,5 @@
> > +  MOZ_RELEASE_ASSERT(*list.begin() == two);
> > +  MOZ_RELEASE_ASSERT(*++list.begin() == three);
> > +
> > +  SomeClass four(4);
> > +  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
> 
> Hmm?  Doesn't look right to me -- the list is [3, 3] now with no four in
> sight.

Again this is comparing objects using their operator==. In this case |three.mValue == four.mValue| b/c we incr'd it.

> @@ +120,5 @@
> > +  SomeClass four(4);
> > +  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
> > +}
> > +
> > +void
> 
> static on the subtest.

OK.
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #9)
> Shouldn't this just be |MOZ_ASSERT_NOT_REACHED(...)|?

Looks like MOZ_ASSERT_UNREACHABLE (I assume that's what you meant) is debug only so a no-go.
Updated per review.
Attachment #8859689 - Flags: review?(jwalden+bmo)
Attachment #8858979 - Attachment is obsolete: true
(In reply to Eric Rahm [:erahm] from comment #10)
> (In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #9)
> > @@ +192,5 @@
> > > +
> > > +    mHead = aElm;
> > > +    if (!mTail) {
> > > +      mTail = aElm;
> > > +    }
> > 
> > Notwithstanding what comment 0 says about this being usable to implement
> > Rooted, I'm not sure we'd want to.  This implementation seems to have a lot
> > of null-checks and (in particular, control flow) operations in it, that
> > aren't in Rooted's current implementation.  The idea abstractly sounds nice,
> > but if we want to not have to fully implement Rooted for some reason, seems
> > like js/src/ds/Nestable.h would be closer to the right foundation.
> 
> Yeah, I have no intent to make this work for Rooted. If someone wants to
> follow up on that more power to them.

Nestable.h? Is that a hypothetical thing?

I'm not sure I see a lot of non-DEBUG unnecessary null-checks and control flow goop? But it's tough to compare, because Rooted would be using SinglyLinkedList, not this. I guess we could use this for PersistentRooted.
sfink, Nestable.h is totally a real thing, and I'm very upset you didn't look in my tree to read it.  (Ahem.)  (Although actually, it's just Nestable moved out of frontend/Something.h right now, so it does actually exist for current perusal.)

Reading the code for Rooted/~Rooted, it seemed to have straight-line control flow without any ifs in it.  If I read it correctly.  Unfortunately, it didn't really have the usual series of pointer-assignments you'd hope for in linked-list code, so I'm not 100% sure it's exactly the same approach.  But it's definitely closer to it.
Comment on attachment 8859689 [details] [diff] [review]
Implement a list class that is both usable and efficient

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

JS at least has more or less switched over to |using| in everything but fact, and the muscle memory of people who haven't quite picked it up yet.  We probably could stand to institutionalize it in our style rules, yeah.

I would totally be in favor of putting it in Mozilla's style rules as well, but I don't interact with them enough to know if other people feel at all similarly or not.  Feel free to push it upstream if you want, but I don't have the time to do much active pushing, myself.

::: mfbt/DoublyLinkedList.h
@@ +262,5 @@
> +   * Remove the tail of the list and return it. Calling this on an empty list
> +   * will assert.
> +   */
> +  T* popBack() {
> +    MOZ_RELEASE_ASSERT(!isEmpty());

Also downgrade this to a simple assert, as in popFront.

::: mfbt/tests/TestDoublyLinkedList.cpp
@@ +112,5 @@
> +    x.incr();
> +  }
> +
> +  MOZ_RELEASE_ASSERT(*list.begin() == two);
> +  MOZ_RELEASE_ASSERT(*++list.begin() == three);

Oh, right, this is after pushing *addresses* of objects.  So |two| is 3, and |three| is really 4.  Maybe add a comment in the loop above that because |two| and |three| were added and stored in the list by pointer, their values are actively modified?  Just something to make the reader not double-take at these like I was.
Attachment #8859689 - Flags: review?(jwalden+bmo) → review+
Thanks for the quick review!

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #15)
> Comment on attachment 8859689 [details] [diff] [review]
> Implement a list class that is both usable and efficient
> 
> Review of attachment 8859689 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> JS at least has more or less switched over to |using| in everything but
> fact, and the muscle memory of people who haven't quite picked it up yet. 
> We probably could stand to institutionalize it in our style rules, yeah.
> 
> I would totally be in favor of putting it in Mozilla's style rules as well,
> but I don't interact with them enough to know if other people feel at all
> similarly or not.  Feel free to push it upstream if you want, but I don't
> have the time to do much active pushing, myself.

I'd pursue it but I don't fully understand the rationale. Generally speaking I think it's a bit clearer than typedef, but that's all I've got.

> ::: mfbt/DoublyLinkedList.h
> @@ +262,5 @@
> > +   * Remove the tail of the list and return it. Calling this on an empty list
> > +   * will assert.
> > +   */
> > +  T* popBack() {
> > +    MOZ_RELEASE_ASSERT(!isEmpty());
> 
> Also downgrade this to a simple assert, as in popFront.

Will do.

> ::: mfbt/tests/TestDoublyLinkedList.cpp
> @@ +112,5 @@
> > +    x.incr();
> > +  }
> > +
> > +  MOZ_RELEASE_ASSERT(*list.begin() == two);
> > +  MOZ_RELEASE_ASSERT(*++list.begin() == three);
> 
> Oh, right, this is after pushing *addresses* of objects.  So |two| is 3, and
> |three| is really 4.  Maybe add a comment in the loop above that because
> |two| and |three| were added and stored in the list by pointer, their values
> are actively modified?  Just something to make the reader not double-take at
> these like I was.

I'll add a comment.
https://hg.mozilla.org/integration/mozilla-inbound/rev/feb9622d58ab943909b06461da6c5fa8658186e4
Bug 1277725 - Implement a list class that is both usable and efficient. r=waldo
https://hg.mozilla.org/mozilla-central/rev/feb9622d58ab
Status: ASSIGNED → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
(In reply to Eric Rahm [:erahm] from comment #16)
> I'd pursue it but I don't fully understand the rationale. Generally speaking
> I think it's a bit clearer than typedef, but that's all I've got.

That's all I've got, too.  :-)  Seems like that's all you really need.  And when it comes to certain typedef forms (function pointers, array types) that's actually pretty huge, IMO.  Anyway, this remains in your capable hands.
You need to log in before you can comment on or make changes to this bug.