Bug 722581 - Update comments in mfbt/LinkedList.h. r=waldo
authorJustin Lebar <justin.lebar@gmail.com>
Sat, 04 Feb 2012 21:49:10 -0500
changeset 89471 a440008b594e7e04e30f6fa9047c1dfc4028a036
parent 89470 b6494c69be6b89f537db436f2b7ced371fcceaba
child 89472 5badb4b98315ed52b15aa6adec532fe6f11dfb57
child 89477 196733360636438da5fe0092089855b2e76356ba
push id136
push userlsblakk@mozilla.com
push dateFri, 01 Jun 2012 02:39:32 +0000
treeherdermozilla-release@7ebf7352c959 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs722581
milestone13.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 722581 - Update comments in mfbt/LinkedList.h. r=waldo
mfbt/LinkedList.h
--- a/mfbt/LinkedList.h
+++ b/mfbt/LinkedList.h
@@ -111,16 +111,35 @@ class LinkedListElement
      *
      * We could get rid of the extra word of storage by shoving the "is
      * sentinel" bit into one of the pointers, although this would, of course,
      * have performance implications of its own.
      *
      * But the goal here isn't to win an award for the fastest or slimmest
      * linked list; rather, we want a *convenient* linked list.  So we won't
      * waste time guessing which micro-optimization strategy is best.
+     *
+     *
+     * Speaking of unnecessary work, it's worth addressing here why we wrote
+     * mozilla::LinkedList in the first place, instead of using stl::list.
+     *
+     * The key difference between mozilla::LinkedList and stl::list is that
+     * mozilla::LinkedList stores the prev/next pointers in the object itself,
+     * while stl::list stores the prev/next pointers in a list element which
+     * itself points to the object being stored.
+     *
+     * mozilla::LinkedList's approach makes it harder to store an object in more
+     * than one list.  But the upside is that you can call next() / prev() /
+     * remove() directly on the object.  With stl::list, you'd need to store a
+     * pointer to its iterator in the object in order to accomplish this.  Not
+     * only would this waste space, but you'd have to remember to update that
+     * pointer every time you added or removed the object from a list.
+     *
+     * In-place, constant-time removal is a killer feature of doubly-linked
+     * lists, and supporting this painlessly was a key design criterion.
      */
 
 private:
     LinkedListElement* next;
     LinkedListElement* prev;
     const bool isSentinel;
 
 public:
@@ -195,24 +214,24 @@ public:
 
 private:
     LinkedListElement& operator=(const LinkedList<T>& other) MOZ_DELETE;
     LinkedListElement(const LinkedList<T>& other) MOZ_DELETE;
 
     friend class LinkedList<T>;
 
     enum NodeKind {
-        NODE_TYPE_NORMAL,
-        NODE_TYPE_SENTINEL
+        NODE_KIND_NORMAL,
+        NODE_KIND_SENTINEL
     };
 
-    LinkedListElement(NodeKind nodeType)
+    LinkedListElement(NodeKind nodeKind)
         : next(this)
         , prev(this)
-        , isSentinel(nodeType == NODE_TYPE_SENTINEL)
+        , isSentinel(nodeKind == NODE_KIND_SENTINEL)
     {
     }
 
     /*
      * Return |this| cast to T* if we're a normal node, or return NULL if we're
      * a sentinel node.
      */
     T* asT()
@@ -260,17 +279,17 @@ class LinkedList
 private:
     LinkedListElement<T> sentinel;
 
 public:
     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
 
     LinkedList()
-        : sentinel(LinkedListElement<T>::NODE_TYPE_SENTINEL)
+        : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL)
     {
     }
 
     /*
      * Add elem to the front of the list.
      */
     void insertFront(T* elem)
     {
@@ -367,17 +386,20 @@ public:
              slow = slow->prev,
              fast1 = fast2->prev,
              fast2 = fast1->prev) {
 
             MOZ_ASSERT(slow != fast1);
             MOZ_ASSERT(slow != fast2);
         }
 
-        /* Check that |sentinel| is the only root in the list. */
+        /*
+         * Check that |sentinel| is the only node in the list with
+         * isSentinel == true.
+         */
         for (LinkedListElement<T>* elem = sentinel.next;
              elem != sentinel;
              elem = elem->next) {
 
           MOZ_ASSERT(!elem->isSentinel);
         }
 
         /* Check that the next/prev pointers match up. */