Remove use of wtf/ListHashSet from CCPrioritizedTextureManager.

cc/prioritized_texture_manager.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 
 #include "CCPrioritizedTextureManager.h"
 
 #include "base/stl_util.h"
 #include "CCPrioritizedTexture.h"
@@ skipping 17 matching lines @@
 
 CCPrioritizedTextureManager::~CCPrioritizedTextureManager()
 {
     while (m_textures.size() > 0)
         unregisterTexture(*m_textures.begin());
 
     deleteUnlinkedEvictedBackings();
     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()
 {
     TRACE_EVENT0("cc", "CCPrioritizedTextureManager::prioritizeTextures");
     ASSERT(CCProxy::isMainThread());
 
     // Sorting textures in this function could be replaced by a slightly
     // modified O(n) quick-select to partition textures rather than
     // sort them (if performance of the sort becomes an issue).
@@ skipping 47 matching lines @@
 
     ASSERT(m_memoryAboveCutoffBytes <= m_memoryAvailableBytes);
     ASSERT(memoryAboveCutoffBytes() <= maxMemoryLimitBytes());
 }
 
 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()
 {
     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());
+    TRACE_EVENT0("cc", "CCPrioritizedTextureManager::sortBackings");
+    ASSERT(CCProxy::isImplThread());
 
-    // 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();
-
-#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()
 {
     ASSERT(CCProxy::isMainThread());
     for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
         // FIXME: We should remove this and just set all priorities to
         //        CCPriorityCalculator::lowestPriority() once we have priorities
         //        for all textures (we can't currently calculate distances for
         //        off-screen textures).
@@ skipping 26 matching lines @@
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
     ASSERT(!texture->isSelfManaged());
     ASSERT(texture->isAbovePriorityCutoff());
     if (texture->backing() || !texture->isAbovePriorityCutoff())
         return;
 
     // Find a backing below, by either recycling or allocating.
     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;
         }
     }
 
     // Otherwise reduce memory and just allocate a new backing texures.
     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();
 }
 
 void CCPrioritizedTextureManager::evictBackingsToReduceMemory(size_t limitBytes, EvictionPriorityPolicy evictionPolicy, CCResourceProvider* resourceProvider)
 {
     ASSERT(CCProxy::isImplThread());
     if (memoryUseBytes() <= limitBytes)
         return;
 
     // 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);
     }
 }
 
 void CCPrioritizedTextureManager::reduceMemory(CCResourceProvider* resourceProvider)
 {
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
 
     evictBackingsToReduceMemory(m_memoryAvailableBytes, RespectManagerPriorityCutoff, resourceProvider);
     ASSERT(memoryUseBytes() <= maxMemoryLimitBytes());
 
     // We currently collect backings from deleted textures for later recycling.
     // However, if we do that forever we will always use the max limit even if
     // we really need very little memory. This should probably be solved by reducing the
     // 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();
     }
     size_t tenPercentOfMemory = m_memoryAvailableBytes / 10;
     if (wastedMemory > tenPercentOfMemory)
         evictBackingsToReduceMemory(memoryUseBytes() - (wastedMemory - tenPercentOfMemory), RespectManagerPriorityCutoff, resourceProvider);
 
     // Unlink all evicted backings
     for (BackingVector::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
         if ((*it)->owner())
             (*it)->owner()->unlink();
     }
 
     // And clear the list of evicted backings
     deleteUnlinkedEvictedBackings();
 }
 
 void CCPrioritizedTextureManager::clearAllMemory(CCResourceProvider* resourceProvider)
 {
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
     ASSERT(resourceProvider);
     evictBackingsToReduceMemory(0, DoNotRespectManagerPriorityCutoff, resourceProvider);
 }
 
 void CCPrioritizedTextureManager::reduceMemoryOnImplThread(size_t limitBytes, CCResourceProvider* resourceProvider)
 {
     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);
 }
 
 void CCPrioritizedTextureManager::getEvictedBackings(BackingVector& evictedBackings)
 {
     ASSERT(CCProxy::isImplThread());
     evictedBackings.clear();
     evictedBackings.append(m_evictedBackings);
 }
 
@@ skipping 62 matching lines @@
         texture->unlink();
 }
 
 CCPrioritizedTexture::Backing* CCPrioritizedTextureManager::createBacking(IntSize size, GC3Denum format, CCResourceProvider* resourceProvider)
 {
     ASSERT(CCProxy::isImplThread() && CCProxy::isMainThreadBlocked());
     ASSERT(resourceProvider);
     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
     // we can delete the resource while the main thread is running, but we cannot
     // 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
     // where the bug is, call this function at the beginning and end of
     // 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));
         }
     }
     for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
         CCPrioritizedTexture* texture = (*it);
         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);
         }
     }
 
     // At all times, backings that can be evicted must always come before
     // 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)
             ASSERT(!(*it)->canBeRecycled());
         else
             ASSERT((*it)->canBeRecycled());
     }
+#endif
 }
-#endif
-
 
 } // namespace cc