commit a7c41c5217da2f091ae78d002c9b92c20360ab87
author bsalomon <bsalomon@google.com> Wed Nov 18 19:48:50 2015 -0800
committer Commit bot <commit-bot@chromium.org> Wed Nov 18 19:48:50 2015 -0800
tree fc60973e8dcfa251d16889249da9358724bdba80
parent f045d600fc5c17f8a3537401baf45043e7617368

Make SkTLList prealloc its first block of nodes

Review URL: https://codereview.chromium.org/1458703005

src/core/SkTLList.h

diff --git a/src/core/SkTLList.h b/src/core/SkTLList.h
index 1a8c54c..48e81bd 100644
--- a/src/core/SkTLList.h
+++ b/src/core/SkTLList.h
@@ -39,6 +39,11 @@
     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();
     }
 
@@ -54,7 +59,9 @@
                 for (unsigned int i = 0; i < N; ++i) {
                     block->fNodes[i].~Node();
                 }
-                sk_free(block);
+                if (block != &fFirstBlock) {
+                    sk_free(block);
+                }
             }
         }
     }
@@ -222,6 +229,9 @@
             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;
@@ -241,8 +251,9 @@
         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);
@@ -260,8 +271,10 @@
     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;
@@ -269,8 +282,9 @@
         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) {
@@ -310,6 +324,7 @@
 
     NodeList fList;
     NodeList fFreeList;
+    Block    fFirstBlock;
     int fCount;
 };