Make SkTLList prealloc its first block of nodes

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 21 matching lines @@
         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();
     }
 
     ~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) {
                 for (unsigned int i = 0; i < N; ++i) {
                     block->fNodes[i].~Node();
                 }
-                sk_free(block);
+                if (block != &fFirstBlock) {
+                    sk_free(block);
+                }
             }
         }
     }
 
     /** Adds a new element to the list at the head. */
     template <typename... Args> T* addToHead(Args&&... args) {
         this->validate();
         Node* node = this->createNode();
         fList.addToHead(node);
         this->validate();
@@ skipping 147 matching lines @@
         int fNodesInUse;
         Node fNodes[N];
     };
 
     Node* createNode() {
         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];
             new (node) Node;
             node->fBlock = block;
             block->fNodesInUse = 1;
             for (unsigned int i = 1; i < N; ++i) {
                 new (block->fNodes + i) Node;
                 fFreeList.addToHead(block->fNodes + i);
                 block->fNodes[i].fBlock = block;
             }
         }
         ++fCount;
         return node;
     }
 
     void removeNode(Node* node) {
         SkASSERT(node);
         fList.remove(node);
         SkTCast<T*>(node->fObj)->~T();
-        if (0 == --node->fBlock->fNodesInUse) {
-            Block* block = node->fBlock;
+        Block* block = node->fBlock;
+        // Don't ever elease the first block, just add its nodes to the free list
+        if (0 == --block->fNodesInUse && block != &fFirstBlock) {
             for (unsigned int i = 0; i < N; ++i) {
                 if (block->fNodes + i != node) {
                     fFreeList.remove(block->fNodes + i);
                 }
                 block->fNodes[i].~Node();
             }
             sk_free(block);
         } else {
             fFreeList.addToHead(node);
         }
         --fCount;
         this->validate();
     }
 
     void validate() const {
 #ifdef SK_DEBUG
         SkASSERT((0 == fCount) == fList.isEmpty());
-        SkASSERT((0 != fCount) || fFreeList.isEmpty());
-            
+        if (0 == fCount) {
+            // Should only have the nodes from the first block in the free list.
+            SkASSERT(fFreeList.countEntries() == N);
+        }
         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;
-            SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse < N);
-
+            // 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);
             int activeCnt = 0;
             int freeCnt = 0;
             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);
@@ skipping 19 matching lines @@
             }
             SkASSERT(activeCnt == block->fNodesInUse);
             activeNode = iter.next();
         }
         SkASSERT(count == fCount);
 #endif
     }
 
     NodeList fList;
     NodeList fFreeList;
+    Block    fFirstBlock;
     int fCount;
 };
 
 #endif