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 86201 a440008b594e7e04e30f6fa9047c1dfc4028a036
parent 86200 b6494c69be6b89f537db436f2b7ced371fcceaba
child 86202 5badb4b98315ed52b15aa6adec532fe6f11dfb57
child 86207 196733360636438da5fe0092089855b2e76356ba
push idunknown
push userunknown
push dateunknown
reviewerswaldo
bugs722581
milestone13.0a1
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. */