Delay initialization of free list in SkTLList until first use of list

src/core/SkTLList.h

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTLList_DEFINED
 #define SkTLList_DEFINED
 
@@ skipping 20 matching lines @@
     struct Node {
         char fObj[sizeof(T)];
         SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
         Block* fBlock; // owning block.
     };
     typedef SkTInternalLList<Node> NodeList;
 
 public:
     class Iter;
 
-    SkTLList() : fCount(0) {
-        fFirstBlock.fNodesInUse = 0;
-        for (unsigned int i = 0; i < N; ++i) {
-            fFreeList.addToHead(fFirstBlock.fNodes + i);
-            fFirstBlock.fNodes[i].fBlock = &fFirstBlock;
-        }
-        this->validate();
-    }
+    // Having fCount initialized to -1 indicates that the first time we attempt to grab a free node
+    // all the nodes in the pre-allocated first block need to be inserted into the free list. This
+    // allows us to skip that loop in instances when the list is never populated.
+    SkTLList() : fCount(-1) {}
 
     ~SkTLList() {
         this->validate();
         typename NodeList::Iter iter;
         Node* node = iter.init(fList, Iter::kHead_IterStart);
         while (node) {
             SkTCast<T*>(node->fObj)->~T();
             Block* block = node->fBlock;
             node = iter.next();
             if (0 == --block->fNodesInUse) {
@@ skipping 82 matching lines @@
 
     void reset() {
         this->validate();
         Iter iter(*this, Iter::kHead_IterStart);
         while (iter.get()) {
             Iter next = iter;
             next.next();
             this->remove(iter.get());
             iter = next;
         }
-        SkASSERT(0 == fCount);
+        SkASSERT(0 == fCount || -1 == fCount);
         this->validate();
     }
 
-    int count() const { return fCount; }
-    bool isEmpty() const { this->validate(); return 0 == fCount; }
+    int count() const { return SkTMax(fCount ,0); }
+    bool isEmpty() const { this->validate(); return 0 == fCount || -1 == fCount; }
 
     bool operator== (const SkTLList& list) const {
         if (this == &list) {
             return true;
         }
-        if (fCount != list.fCount) {
+        // Call count() rather than use fCount because an empty list may have fCount = 0 or -1.
+        if (this->count() != list.count()) {
             return false;
         }
         for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
              a.get();
              a.next(), b.next()) {
             SkASSERT(b.get()); // already checked that counts match.
             if (!(*a.get() == *b.get())) {
                 return false;
             }
         }
@@ skipping 43 matching lines @@
             }
         }
     };
 
 private:
     struct Block {
         int fNodesInUse;
         Node fNodes[N];
     };
 
+    void delayedInit() {
+        SkASSERT(-1 == fCount);
+        fFirstBlock.fNodesInUse = 0;
+        for (unsigned int i = 0; i < N; ++i) {
+            fFreeList.addToHead(fFirstBlock.fNodes + i);
+            fFirstBlock.fNodes[i].fBlock = &fFirstBlock;
+        }
+        fCount = 0;
+        this->validate();
+    }
+
     Node* createNode() {
+        if (-1 == fCount) {
+            this->delayedInit();
+        }
         Node* node = fFreeList.head();
         if (node) {
             fFreeList.remove(node);
             ++node->fBlock->fNodesInUse;
         } else {
             // Should not get here when count == 0 because we always have the preallocated first
             // block.
             SkASSERT(fCount > 0);
             Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block)));
             node = &block->fNodes[0];
@@ skipping 26 matching lines @@
             sk_free(block);
         } else {
             fFreeList.addToHead(node);
         }
         --fCount;
         this->validate();
     }
 
     void validate() const {
 #ifdef SK_DEBUG
-        SkASSERT((0 == fCount) == fList.isEmpty());
-        if (0 == fCount) {
+        bool isEmpty = false;
+        if (-1 == fCount) {
+            // We should not yet have initialized the free list.
+            SkASSERT(fFreeList.isEmpty());
+            isEmpty = true;
+        } else if (0 == fCount) {
             // Should only have the nodes from the first block in the free list.
             SkASSERT(fFreeList.countEntries() == N);
+            isEmpty = true;
         }
+        SkASSERT(isEmpty == fList.isEmpty());
         fList.validate();
         fFreeList.validate();
         typename NodeList::Iter iter;
         Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
         while (freeNode) {
             SkASSERT(fFreeList.isInList(freeNode));
             Block* block = freeNode->fBlock;
             // Only the first block is allowed to have all its nodes in the free list.
             SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock);
             SkASSERT((unsigned)block->fNodesInUse < N);
@@ skipping 23 matching lines @@
             for (unsigned int i = 0; i < N; ++i) {
                 bool free = fFreeList.isInList(block->fNodes + i);
                 bool active = fList.isInList(block->fNodes + i);
                 SkASSERT(free != active);
                 activeCnt += active;
                 freeCnt += free;
             }
             SkASSERT(activeCnt == block->fNodesInUse);
             activeNode = iter.next();
         }
-        SkASSERT(count == fCount);
+        SkASSERT(count == fCount || (0 == count && -1 == fCount));
 #endif
     }
 
     NodeList fList;
     NodeList fFreeList;
     Block    fFirstBlock;
     int fCount;
 };
 
 #endif