Remove use of wtf/ListHashSet from CCPrioritizedTextureManager.

cc/prioritized_texture_manager.cc

Index: cc/prioritized_texture_manager.cc
diff --git a/cc/prioritized_texture_manager.cc b/cc/prioritized_texture_manager.cc
index 06d6c8e8fced4eded97301a9bcc5e57c372ca4ff..56c898e781f2eb46bbc494ab1fbc4c9e2bb3b0fd 100644
--- a/cc/prioritized_texture_manager.cc
+++ b/cc/prioritized_texture_manager.cc
@@ -35,7 +35,7 @@ CCPrioritizedTextureManager::~CCPrioritizedTextureManager()
     ASSERT(m_evictedBackings.isEmpty());
 
     // Each remaining backing is a leaked opengl texture. There should be none.
-    ASSERT(m_backings.isEmpty());
+    ASSERT(m_backings.empty());
 }
 
 void CCPrioritizedTextureManager::prioritizeTextures()
@@ -103,10 +103,11 @@ void CCPrioritizedTextureManager::pushTexturePrioritiesToBackings()
     TRACE_EVENT0("cc", "CCPrioritizedTextureManager::pushTexturePrioritiesToBackings");
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
 
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it)
+    assertInvariants();
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it)
         (*it)->updatePriority();
-
     sortBackings();
+    assertInvariants();
 }
 
 void CCPrioritizedTextureManager::updateBackingsInDrawingImplTree()
@@ -114,35 +115,22 @@ void CCPrioritizedTextureManager::updateBackingsInDrawingImplTree()
     TRACE_EVENT0("cc", "CCPrioritizedTextureManager::updateBackingsInDrawingImplTree");
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
 
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
+    assertInvariants();
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         CCPrioritizedTexture::Backing* backing = (*it);
         backing->updateInDrawingImplTree();
     }
-
     sortBackings();
+    assertInvariants();
 }
 
 void CCPrioritizedTextureManager::sortBackings()
 {
-    TRACE_EVENT0("cc", "CCPrioritizedTextureManager::updateBackingsPriorities");
-    ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
-
-    // Update backings' priorities and put backings in eviction/recycling order.
-    BackingVector& sortedBackings = m_tempBackingVector;

[jamesr, 2012/10/17 01:31:11]

can we get rid of the m_tempBackingVector member completely now?

[ccameron, 2012/10/17 02:13:58]

Yeah, it's gone now.

-    sortedBackings.clear();
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it)
-        sortedBackings.append(*it);
-    std::sort(sortedBackings.begin(), sortedBackings.end(), compareBackings);
-
-    for (BackingVector::iterator it = sortedBackings.begin(); it != sortedBackings.end(); ++it) {
-        m_backings.remove(*it);
-        m_backings.add(*it);
-    }
-    sortedBackings.clear();
+    TRACE_EVENT0("cc", "CCPrioritizedTextureManager::sortBackings");
+    ASSERT(CCProxy::isImplThread());
 
-#if !ASSERT_DISABLED
-    assertInvariants();
-#endif
+    // Put backings in eviction/recycling order.
+    m_backings.sort(compareBackings);

[jamesr, 2012/10/17 01:31:11]

cool, I didn't know std::list had a O(n log(n)) sort. Any idea how it works?

[ccameron, 2012/10/17 02:13:58]

I didn't know it before today. I'd guess it uses std::list::merge().

 }
 
 void CCPrioritizedTextureManager::clearPriorities()
@@ -189,11 +177,12 @@ void CCPrioritizedTextureManager::acquireBackingTextureIfNeeded(CCPrioritizedTex
     CCPrioritizedTexture::Backing* backing = 0;
 
     // First try to recycle
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if (!(*it)->canBeRecycled())
             break;
         if ((*it)->size() == texture->size() && (*it)->format() == texture->format()) {
             backing = (*it);
+            m_backings.erase(it);
             break;
         }
     }
@@ -202,14 +191,15 @@ void CCPrioritizedTextureManager::acquireBackingTextureIfNeeded(CCPrioritizedTex
     if (!backing) {
         evictBackingsToReduceMemory(m_memoryAvailableBytes - texture->bytes(), RespectManagerPriorityCutoff, resourceProvider);
         backing = createBacking(texture->size(), texture->format(), resourceProvider);
+        ASSERT(backing == m_backings.front());
+        m_backings.pop_front();
     }
 
     // Move the used backing texture to the end of the eviction list.
     if (backing->owner())
         backing->owner()->unlink();
     texture->link(backing);
-    m_backings.remove(backing);
-    m_backings.add(backing);
+    m_backings.push_back(backing);
 
     // Update the backing's priority from its new owner.
     backing->updatePriority();
@@ -224,11 +214,11 @@ void CCPrioritizedTextureManager::evictBackingsToReduceMemory(size_t limitBytes,
     // Destroy backings until we are below the limit,
     // or until all backings remaining are above the cutoff.
     while (memoryUseBytes() > limitBytes && m_backings.size() > 0) {
-        CCPrioritizedTexture::Backing* backing = *m_backings.begin();
+        CCPrioritizedTexture::Backing* backing = m_backings.front();
         if (evictionPolicy == RespectManagerPriorityCutoff)
             if (backing->wasAbovePriorityCutoffAtLastPriorityUpdate())
                 break;
-        evictBackingResource(backing, resourceProvider);
+        evictFirstBackingResource(backing, resourceProvider);
     }
 }
 
@@ -245,7 +235,7 @@ void CCPrioritizedTextureManager::reduceMemory(CCResourceProvider* resourceProvi
     // limit externally, but until then this just does some "clean up" of unused
     // backing textures (any more than 10%).
     size_t wastedMemory = 0;
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if ((*it)->owner())
             break;
         wastedMemory += (*it)->bytes();
@@ -275,6 +265,9 @@ void CCPrioritizedTextureManager::reduceMemoryOnImplThread(size_t limitBytes, CC
 {
     ASSERT(CCProxy::isImplThread());
     ASSERT(resourceProvider);
+    // If we are in the process of uploading a new frame then the backings at the very end of
+    // the list are not sorted by priority. Sort them before doing the eviction.
+    sortBackings();
     evictBackingsToReduceMemory(limitBytes, DoNotRespectManagerPriorityCutoff, resourceProvider);
 }
 
@@ -357,17 +350,16 @@ CCPrioritizedTexture::Backing* CCPrioritizedTextureManager::createBacking(IntSiz
     CCResourceProvider::ResourceId resourceId = resourceProvider->createResource(m_pool, size, format, CCResourceProvider::TextureUsageAny);
     CCPrioritizedTexture::Backing* backing = new CCPrioritizedTexture::Backing(resourceId, resourceProvider, size, format);
     m_memoryUseBytes += backing->bytes();
-    // Put backing texture at the front for eviction, since it isn't in use yet.
-    m_backings.insertBefore(m_backings.begin(), backing);
+    m_backings.push_front(backing);

[ccameron, 2012/10/17 01:10:52]

There was some controversy about doing this "add to the front of the list, then
remove from the front of the list and put at the back of the list". The reason
for this is that on some platforms we will want to be able to call createBacking
when not paired with tying it to a backing, in order to avoid driver overhead of
creating resources

[jamesr, 2012/10/17 01:31:11]

Writing code now because we will need it later isn't a great way to do things -
let's write the code we need now now and write stuff we need later later. 
createBacking() is private so we only have to worry about local invariants here
and the only caller to createBacking() puts the return value in the list itself.

[ccameron, 2012/10/17 02:13:58]

Removed.

     return backing;
 }
 
-void CCPrioritizedTextureManager::evictBackingResource(CCPrioritizedTexture::Backing* backing, CCResourceProvider* resourceProvider)
+void CCPrioritizedTextureManager::evictFirstBackingResource(CCPrioritizedTexture::Backing* backing, CCResourceProvider* resourceProvider)

[jamesr, 2012/10/17 01:31:11]

why does this take a backing* if it's only operating on the first in the list? 
I would just leave the parameter out

[ccameron, 2012/10/17 02:13:58]

Yeah, this just made me feel warm and fuzzy.  Deleted.

 {
     ASSERT(CCProxy::isImplThread());
     ASSERT(backing);
     ASSERT(resourceProvider);
-    ASSERT(m_backings.find(backing) != m_backings.end());
+    ASSERT(m_backings.front() == backing);
 
     // Note that we create a backing and its resource at the same time, but we
     // delete the backing structure and its resource in two steps. This is because
@@ -375,13 +367,13 @@ void CCPrioritizedTextureManager::evictBackingResource(CCPrioritizedTexture::Bac
     // unlink backings while the main thread is running.
     backing->deleteResource(resourceProvider);
     m_memoryUseBytes -= backing->bytes();
-    m_backings.remove(backing);
+    m_backings.pop_front();
     m_evictedBackings.append(backing);
 }
 
-#if !ASSERT_DISABLED
 void CCPrioritizedTextureManager::assertInvariants()
 {
+#if !ASSERT_DISABLED
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
 
     // If we hit any of these asserts, there is a bug in this class. To see
@@ -389,7 +381,7 @@ void CCPrioritizedTextureManager::assertInvariants()
     // every public function.
 
     // Backings/textures must be doubly-linked and only to other backings/textures in this manager.
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if ((*it)->owner()) {
             ASSERT(ContainsKey(m_textures, (*it)->owner()));
             ASSERT((*it)->owner()->backing() == (*it));
@@ -400,10 +392,10 @@ void CCPrioritizedTextureManager::assertInvariants()
         CCPrioritizedTexture::Backing* backing = texture->backing();
         if (backing) {
             if (backing->resourceHasBeenDeleted()) {
-                ASSERT(m_backings.find(backing) == m_backings.end());
+                ASSERT(std::find(m_backings.begin(), m_backings.end(), backing) == m_backings.end());
                 ASSERT(m_evictedBackings.contains(backing));
             } else {
-                ASSERT(m_backings.find(backing) != m_backings.end());
+                ASSERT(std::find(m_backings.begin(), m_backings.end(), backing) != m_backings.end());
                 ASSERT(!m_evictedBackings.contains(backing));
             }
             ASSERT(backing->owner() == texture);
@@ -414,7 +406,7 @@ void CCPrioritizedTextureManager::assertInvariants()
     // backings that can't be evicted in the backing texture list (otherwise
     // reduceMemory will not find all textures available for eviction/recycling).
     bool reachedUnrecyclable = false;
-    for (BackingSet::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
+    for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if (!(*it)->canBeRecycled())
             reachedUnrecyclable = true;
         if (reachedUnrecyclable)
@@ -422,8 +414,7 @@ void CCPrioritizedTextureManager::assertInvariants()
         else
             ASSERT((*it)->canBeRecycled());
     }
-}
 #endif
-
+}
 
 } // namespace cc