Bug 513144. Allow nsMediaCache blocks to belong to more than one BlockList at the same time. r=doublec
authorRobert O'Callahan <robert@ocallahan.org>
Tue, 15 Sep 2009 14:30:44 +1200
changeset 32902 857725884e1e74fde2ee0f4b3110e3a29c970dfb
parent 32901 c4bca0456beb30fc115e924e6c1f0ee004c20500
child 32903 a4ef15912d218af253eefa53cba30e0376a64349
push idunknown
push userunknown
push dateunknown
reviewersdoublec
bugs513144
milestone1.9.3a1pre
Bug 513144. Allow nsMediaCache blocks to belong to more than one BlockList at the same time. r=doublec
content/media/nsMediaCache.cpp
content/media/nsMediaCache.h
--- a/content/media/nsMediaCache.cpp
+++ b/content/media/nsMediaCache.cpp
@@ -218,32 +218,27 @@ protected:
     PLAYED_BLOCK,
     // block belongs to the stream's mReadaheadBlockList because its
     // offset is greater than or equal to the stream's current
     // reader position
     READAHEAD_BLOCK
   };
 
   struct Block {
-    Block() : mStream(nsnull), mClass(FREE_BLOCK),
-      mNextBlock(-1), mPrevBlock(-1) {}
+    Block() : mStream(nsnull), mClass(FREE_BLOCK) {}
 
     // The stream that owns this block, or null if the block is free.
     nsMediaCacheStream* mStream;
     // The block index in the stream. Valid only if mStream is non-null.
     PRUint32            mStreamBlock;
     // Time at which this block was last used. Valid only if
     // mClass is METADATA_BLOCK or PLAYED_BLOCK.
     TimeStamp           mLastUseTime;
     // The class is FREE_BLOCK if and only if mStream is null
     BlockClass          mClass;
-    // Next and previous blocks of this class (circular links, so
-    // always nonnegative)
-    PRInt32             mNextBlock;
-    PRInt32             mPrevBlock;
   };
 
   // Get the BlockList that the block should belong to given its
   // current mClass and mStream
   BlockList* GetListForBlock(Block* aBlock);
   // Add the block to the free list, mark it FREE_BLOCK, and mark
   // its stream (if any) as not having the block in cache
   void FreeBlock(PRInt32 aBlock);
@@ -292,83 +287,101 @@ protected:
 
 // There is at most one media cache (although that could quite easily be
 // relaxed if we wanted to manage multiple caches with independent
 // size limits).
 static nsMediaCache* gMediaCache;
 
 void nsMediaCacheStream::BlockList::AddFirstBlock(PRInt32 aBlock)
 {
-  nsMediaCache::Block* block = &gMediaCache->mIndex[aBlock];
-  NS_ASSERTION(block->mNextBlock == -1 && block->mPrevBlock == -1,
-               "Block already in list");
+  NS_ASSERTION(!mEntries.GetEntry(aBlock), "Block already in list");
+  Entry* entry = mEntries.PutEntry(aBlock);
+
   if (mFirstBlock < 0) {
-    block->mNextBlock = block->mPrevBlock = aBlock;
+    entry->mNextBlock = entry->mPrevBlock = aBlock;
   } else {
-    block->mNextBlock = mFirstBlock;
-    block->mPrevBlock = gMediaCache->mIndex[mFirstBlock].mPrevBlock;
-    gMediaCache->mIndex[block->mNextBlock].mPrevBlock = aBlock;
-    gMediaCache->mIndex[block->mPrevBlock].mNextBlock = aBlock;
+    entry->mNextBlock = mFirstBlock;
+    entry->mPrevBlock = mEntries.GetEntry(mFirstBlock)->mPrevBlock;
+    mEntries.GetEntry(entry->mNextBlock)->mPrevBlock = aBlock;
+    mEntries.GetEntry(entry->mPrevBlock)->mNextBlock = aBlock;
   }
   mFirstBlock = aBlock;
   ++mCount;
 }
 
 void nsMediaCacheStream::BlockList::AddAfter(PRInt32 aBlock, PRInt32 aBefore)
 {
-  nsMediaCache::Block* block = &gMediaCache->mIndex[aBlock];
-  NS_ASSERTION(block->mNextBlock == -1 && block->mPrevBlock == -1,
-               "Block already in list");
-  NS_ASSERTION(mFirstBlock >= 0, "Can't AddAfter to an empty list");
+  NS_ASSERTION(!mEntries.GetEntry(aBlock), "Block already in list");
+  Entry* entry = mEntries.PutEntry(aBlock);
 
-  block->mNextBlock = gMediaCache->mIndex[aBefore].mNextBlock;
-  block->mPrevBlock = aBefore;
-  gMediaCache->mIndex[block->mNextBlock].mPrevBlock = aBlock;
-  gMediaCache->mIndex[block->mPrevBlock].mNextBlock = aBlock;
+  Entry* addAfter = mEntries.GetEntry(aBefore);
+  NS_ASSERTION(addAfter, "aBefore not in list");
+
+  entry->mNextBlock = addAfter->mNextBlock;
+  entry->mPrevBlock = aBefore;
+  mEntries.GetEntry(entry->mNextBlock)->mPrevBlock = aBlock;
+  mEntries.GetEntry(entry->mPrevBlock)->mNextBlock = aBlock;
   ++mCount;
 }
 
 void nsMediaCacheStream::BlockList::RemoveBlock(PRInt32 aBlock)
 {
-  nsMediaCache::Block* block = &gMediaCache->mIndex[aBlock];
-  if (block->mNextBlock == aBlock) {
-    NS_ASSERTION(block->mPrevBlock == aBlock, "Linked list inconsistency");
+  Entry* entry = mEntries.GetEntry(aBlock);
+  NS_ASSERTION(entry, "Block not in list");
+
+  if (entry->mNextBlock == aBlock) {
+    NS_ASSERTION(entry->mPrevBlock == aBlock, "Linked list inconsistency");
     NS_ASSERTION(mFirstBlock == aBlock, "Linked list inconsistency");
     mFirstBlock = -1;
   } else {
     if (mFirstBlock == aBlock) {
-      mFirstBlock = block->mNextBlock;
+      mFirstBlock = entry->mNextBlock;
     }
-    gMediaCache->mIndex[block->mNextBlock].mPrevBlock = block->mPrevBlock;
-    gMediaCache->mIndex[block->mPrevBlock].mNextBlock = block->mNextBlock;
+    mEntries.GetEntry(entry->mNextBlock)->mPrevBlock = entry->mPrevBlock;
+    mEntries.GetEntry(entry->mPrevBlock)->mNextBlock = entry->mNextBlock;
   }
-  block->mPrevBlock = block->mNextBlock = -1;
+  mEntries.RemoveEntry(aBlock);
   --mCount;
 }
 
 PRInt32 nsMediaCacheStream::BlockList::GetLastBlock() const
 {
   if (mFirstBlock < 0)
     return -1;
-  return gMediaCache->mIndex[mFirstBlock].mPrevBlock;
+  return mEntries.GetEntry(mFirstBlock)->mPrevBlock;
+}
+
+PRInt32 nsMediaCacheStream::BlockList::GetNextBlock(PRInt32 aBlock) const
+{
+  PRInt32 block = mEntries.GetEntry(aBlock)->mNextBlock;
+  if (block == mFirstBlock)
+    return -1;
+  return block;
+}
+
+PRInt32 nsMediaCacheStream::BlockList::GetPrevBlock(PRInt32 aBlock) const
+{
+  if (aBlock == mFirstBlock)
+    return -1;
+  return mEntries.GetEntry(aBlock)->mPrevBlock;
 }
 
 #ifdef DEBUG
 void nsMediaCacheStream::BlockList::Verify()
 {
   PRInt32 count = 0;
   if (mFirstBlock >= 0) {
     PRInt32 block = mFirstBlock;
-    nsMediaCache::Block* elem = gMediaCache->mIndex.Elements();
     do {
-      NS_ASSERTION(elem[elem[block].mNextBlock].mPrevBlock == block,
+      Entry* entry = mEntries.GetEntry(block);
+      NS_ASSERTION(mEntries.GetEntry(entry->mNextBlock)->mPrevBlock == block,
                    "Bad prev link");
-      NS_ASSERTION(elem[elem[block].mPrevBlock].mNextBlock == block,
-                   "Bad prev link");
-      block = gMediaCache->mIndex[block].mNextBlock;
+      NS_ASSERTION(mEntries.GetEntry(entry->mPrevBlock)->mNextBlock == block,
+                   "Bad next link");
+      block = entry->mNextBlock;
       ++count;
     } while (block != mFirstBlock);
   }
   NS_ASSERTION(count == mCount, "Bad count");
 }
 #endif
 
 static void UpdateSwappedBlockIndex(PRInt32* aBlockIndex,
@@ -381,17 +394,65 @@ static void UpdateSwappedBlockIndex(PRIn
     *aBlockIndex = aBlock1Index;
   }
 }
 
 void
 nsMediaCacheStream::BlockList::NotifyBlockSwapped(PRInt32 aBlockIndex1,
                                                   PRInt32 aBlockIndex2)
 {
+  Entry* e1 = mEntries.GetEntry(aBlockIndex1);
+  Entry* e2 = mEntries.GetEntry(aBlockIndex2);
+  PRInt32 e1Prev = -1, e1Next = -1, e2Prev = -1, e2Next = -1;
+
+  // Fix mFirstBlock
   UpdateSwappedBlockIndex(&mFirstBlock, aBlockIndex1, aBlockIndex2);
+
+  // Fix mNextBlock/mPrevBlock links. First capture previous/next links
+  // so we don't get confused due to aliasing.
+  if (e1) {
+    e1Prev = e1->mPrevBlock;
+    e1Next = e1->mNextBlock;
+  }
+  if (e2) {
+    e2Prev = e2->mPrevBlock;
+    e2Next = e2->mNextBlock;
+  }
+  // Update the entries.
+  if (e1) {
+    mEntries.GetEntry(e1Prev)->mNextBlock = aBlockIndex2;
+    mEntries.GetEntry(e1Next)->mPrevBlock = aBlockIndex2;
+  }
+  if (e2) {
+    mEntries.GetEntry(e2Prev)->mNextBlock = aBlockIndex1;
+    mEntries.GetEntry(e2Next)->mPrevBlock = aBlockIndex1;
+  }
+
+  // Fix hashtable keys. First remove stale entries.
+  if (e1) {
+    e1Prev = e1->mPrevBlock;
+    e1Next = e1->mNextBlock;
+    mEntries.RemoveEntry(aBlockIndex1);
+  }
+  if (e2) {
+    e2Prev = e2->mPrevBlock;
+    e2Next = e2->mNextBlock;
+    mEntries.RemoveEntry(aBlockIndex2);
+  }
+  // Put new entries back.
+  if (e1) {
+    e1 = mEntries.PutEntry(aBlockIndex2);
+    e1->mNextBlock = e1Next;
+    e1->mPrevBlock = e1Prev;
+  }
+  if (e2) {
+    e2 = mEntries.PutEntry(aBlockIndex1);
+    e2->mNextBlock = e2Next;
+    e2->mPrevBlock = e2Prev;
+  }
 }
 
 nsresult
 nsMediaCache::Init()
 {
   NS_ASSERTION(NS_IsMainThread(), "Only call on main thread");
 
   if (!mMonitor) {
@@ -576,33 +637,32 @@ nsMediaCache::FindBlockForIncomingData(T
 
 void
 nsMediaCache::AppendMostReusableBlock(BlockList* aBlockList,
                                       nsTArray<PRUint32>* aResult,
                                       PRInt32 aBlockIndexLimit)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
-  PRInt32 lastBlock = aBlockList->GetLastBlock();
-  if (lastBlock < 0)
+  PRInt32 blockIndex = aBlockList->GetLastBlock();
+  if (blockIndex < 0)
     return;
-  PRInt32 blockIndex = lastBlock;
   do {
     // Don't consider blocks for pinned streams, or blocks that are
     // beyond the specified limit, or the block that contains its stream's
     // current read position (such a block contains both played data
     // and readahead data)
     nsMediaCacheStream* stream = mIndex[blockIndex].mStream;
     if (stream->mPinCount == 0 && blockIndex < aBlockIndexLimit &&
         stream->mStreamOffset/BLOCK_SIZE != mIndex[blockIndex].mStreamBlock) {
       aResult->AppendElement(blockIndex);
       return;
     }
-    blockIndex = mIndex[blockIndex].mPrevBlock;
-  } while (blockIndex != lastBlock);
+    blockIndex = aBlockList->GetPrevBlock(blockIndex);
+  } while (blockIndex >= 0);
 }
 
 PRInt32
 nsMediaCache::FindReusableBlock(TimeStamp aNow,
                                 nsMediaCacheStream* aForStream,
                                 PRInt32 aForStreamBlock,
                                 PRInt32 aMaxSearchBlockIndex)
 {
@@ -619,23 +679,22 @@ nsMediaCache::FindReusableBlock(TimeStam
       for (PRUint32 i = prevCacheBlock; i < freeBlockScanEnd; ++i) {
         if (mIndex[i].mClass == FREE_BLOCK)
           return i;
       }
     }
   }
 
   if (!mFreeBlocks.IsEmpty()) {
-    PRInt32 firstBlock = mFreeBlocks.GetFirstBlock();
-    PRInt32 blockIndex = firstBlock;
+    PRInt32 blockIndex = mFreeBlocks.GetFirstBlock();
     do {
       if (blockIndex < aMaxSearchBlockIndex)
         return blockIndex;
-      blockIndex = mIndex[blockIndex].mNextBlock;
-    } while (blockIndex != firstBlock);
+      blockIndex = mFreeBlocks.GetNextBlock(blockIndex);
+    } while (blockIndex >= 0);
   }
 
   // Build a list of the blocks we should consider for the "latest
   // predicted time of next use". We can exploit the fact that the block
   // linked lists are ordered by increasing time of next use. This is
   // actually the whole point of having the linked lists.
   nsAutoTArray<PRUint32,8> candidates;
   AppendMostReusableBlock(&mMetadataBlocks, &candidates, length);
@@ -644,25 +703,24 @@ nsMediaCache::FindReusableBlock(TimeStam
     nsMediaCacheStream* stream = mStreams[i];
     // Don't consider a) blocks for pinned streams or b) blocks in
     // non-seekable streams that contain data ahead of the current reader
     // position. In the latter case, if we remove the block we won't be
     // able to seek back to read it later.
     if (!stream->mReadaheadBlocks.IsEmpty() && stream->mIsSeekable &&
         stream->mPinCount == 0) {
       // Find a readahead block that's in the given limit
-      PRInt32 lastBlock = stream->mReadaheadBlocks.GetLastBlock();
-      PRInt32 blockIndex = lastBlock;
+      PRInt32 blockIndex = stream->mReadaheadBlocks.GetLastBlock();
       do {
         if (PRUint32(blockIndex) < length) {
           candidates.AppendElement(blockIndex);
           break;
         }
-        blockIndex = mIndex[blockIndex].mPrevBlock;
-      } while (blockIndex != lastBlock);
+        blockIndex = stream->mReadaheadBlocks.GetPrevBlock(blockIndex);
+      } while (blockIndex >= 0);
     }
   }
 
   TimeDuration latestUse;
   PRInt32 latestUseBlock = -1;
   for (PRUint32 i = 0; i < candidates.Length(); ++i) {
     TimeDuration nextUse = PredictNextUse(aNow, candidates[i]);
     if (nextUse > latestUse) {
@@ -733,36 +791,16 @@ nsMediaCache::SwapBlocks(PRInt32 aBlockI
   BlockList* list1 = GetListForBlock(block1);
   list1->NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
   BlockList* list2 = GetListForBlock(block2);
   // We have to be careful we don't swap the same reference twice!
   if (list1 != list2) {
     list2->NotifyBlockSwapped(aBlockIndex1, aBlockIndex2);
   }
 
-  // Find all the blocks that have references to the swapped blocks
-  nsAutoTArray<PRInt32,4> blocksWithReferences;
-  blocksWithReferences.AppendElement(block1->mPrevBlock);
-  blocksWithReferences.AppendElement(block1->mNextBlock);
-  blocksWithReferences.AppendElement(block2->mPrevBlock);
-  blocksWithReferences.AppendElement(block2->mNextBlock);
-  blocksWithReferences.Sort();
-  for (PRUint32 i = 0; i < 4; ++i) {
-    // We have to be careful we don't swap the same reference twice!
-    if (i == 0 || blocksWithReferences[i] != blocksWithReferences[i - 1]) {
-      PRInt32 blockIndex = blocksWithReferences[i];
-      // Note that the references we collected may belong to swapped
-      // blocks ... make sure we update the right block
-      UpdateSwappedBlockIndex(&blockIndex, aBlockIndex1, aBlockIndex2);
-      Block* block = &mIndex[blockIndex];
-      UpdateSwappedBlockIndex(&block->mNextBlock, aBlockIndex1, aBlockIndex2);
-      UpdateSwappedBlockIndex(&block->mPrevBlock, aBlockIndex1, aBlockIndex2);
-    }
-  }
-
   Verify();
 }
 
 void
 nsMediaCache::FreeBlock(PRInt32 aBlock)
 {
   PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
 
@@ -1109,26 +1147,25 @@ nsMediaCache::Verify()
   mFreeBlocks.Verify();
   mPlayedBlocks.Verify();
   mMetadataBlocks.Verify();
   for (PRUint32 i = 0; i < mStreams.Length(); ++i) {
     nsMediaCacheStream* stream = mStreams[i];
     stream->mReadaheadBlocks.Verify();
     if (!stream->mReadaheadBlocks.IsEmpty()) {
       // Verify that the readahead blocks are listed in stream block order
-      PRInt32 firstBlock = stream->mReadaheadBlocks.GetFirstBlock();
-      PRInt32 block = firstBlock;
+      PRInt32 block = stream->mReadaheadBlocks.GetFirstBlock();
       PRInt32 lastStreamBlock = -1;
       do {
         NS_ASSERTION(mIndex[block].mStream == stream, "Bad stream");
         NS_ASSERTION(lastStreamBlock < PRInt32(mIndex[block].mStreamBlock),
                      "Blocks not increasing in readahead stream");
         lastStreamBlock = PRInt32(mIndex[block].mStreamBlock);
-        block = mIndex[block].mNextBlock;
-      } while (block != firstBlock);
+        block = stream->mReadaheadBlocks.GetNextBlock(block);
+      } while (block >= 0);
     }
   }
 }
 #endif
 
 void
 nsMediaCache::InsertReadaheadBlock(PRInt32 aBlockIndex)
 {
@@ -1138,27 +1175,26 @@ nsMediaCache::InsertReadaheadBlock(PRInt
   nsMediaCacheStream* stream = block->mStream;
   if (stream->mReadaheadBlocks.IsEmpty()) {
     stream->mReadaheadBlocks.AddFirstBlock(aBlockIndex);
     return;
   }
 
   // Find the last block whose stream block is before aBlockIndex's
   // stream block, and insert after it
-  PRInt32 lastIndex = stream->mReadaheadBlocks.GetLastBlock();
-  PRInt32 readaheadIndex = lastIndex;
+  PRInt32 readaheadIndex = stream->mReadaheadBlocks.GetLastBlock();
   do {
     if (mIndex[readaheadIndex].mStreamBlock < block->mStreamBlock) {
       stream->mReadaheadBlocks.AddAfter(aBlockIndex, readaheadIndex);
       return;
     }
     NS_ASSERTION(mIndex[readaheadIndex].mStreamBlock > block->mStreamBlock,
                  "Duplicated blocks??");
-    readaheadIndex = mIndex[readaheadIndex].mPrevBlock;
-  } while (readaheadIndex != lastIndex);
+    readaheadIndex = stream->mReadaheadBlocks.GetPrevBlock(readaheadIndex);
+  } while (readaheadIndex >= 0);
   stream->mReadaheadBlocks.AddFirstBlock(aBlockIndex);
   Verify();
 }
 
 void
 nsMediaCache::AllocateAndWriteBlock(nsMediaCacheStream* aStream, const void* aData,
                                     nsMediaCacheStream::ReadMode aMode)
 {
--- a/content/media/nsMediaCache.h
+++ b/content/media/nsMediaCache.h
@@ -336,49 +336,66 @@ public:
   // this will block until the data is available or the stream is
   // closed, otherwise it won't block.
   nsresult Read(char* aBuffer, PRUint32 aCount, PRUint32* aBytes);
 
 private:
   friend class nsMediaCache;
 
   /**
-   * A doubly-linked list of blocks. Each block can belong to at most
-   * one list at a time. Add/Remove/Get methods are all constant time.
-   * We declare this here so that a stream can contain a BlockList of its
-   * read-ahead blocks. Blocks are referred to by index into the
-   * nsMediaCache::mIndex array.
+   * A doubly-linked list of blocks. Add/Remove/Get methods are all
+   * constant time. We declare this here so that a stream can contain a
+   * BlockList of its read-ahead blocks. Blocks are referred to by index
+   * into the nsMediaCache::mIndex array.
+   * 
+   * Blocks can belong to more than one list at the same time, because
+   * the next/prev pointers are not stored in the block.
    */
   class BlockList {
   public:
-    BlockList() : mFirstBlock(-1), mCount(0) {}
+    BlockList() : mFirstBlock(-1), mCount(0) { mEntries.Init(); }
     ~BlockList() {
       NS_ASSERTION(mFirstBlock == -1 && mCount == 0,
                    "Destroying non-empty block list");
     }
     void AddFirstBlock(PRInt32 aBlock);
     void AddAfter(PRInt32 aBlock, PRInt32 aBefore);
     void RemoveBlock(PRInt32 aBlock);
     // Returns the first block in the list, or -1 if empty
     PRInt32 GetFirstBlock() const { return mFirstBlock; }
     // Returns the last block in the list, or -1 if empty
     PRInt32 GetLastBlock() const;
+    // Returns the next block in the list after aBlock or -1 if
+    // aBlock is the last block
+    PRInt32 GetNextBlock(PRInt32 aBlock) const;
+    // Returns the previous block in the list before aBlock or -1 if
+    // aBlock is the first block
+    PRInt32 GetPrevBlock(PRInt32 aBlock) const;
     PRBool IsEmpty() const { return mFirstBlock < 0; }
     PRInt32 GetCount() const { return mCount; }
-    // The contents of aBlockIndex1 and aBlockIndex2 have been swapped;
-    // update mFirstBlock if it refers to either of these
+    // The contents of aBlockIndex1 and aBlockIndex2 have been swapped
     void NotifyBlockSwapped(PRInt32 aBlockIndex1, PRInt32 aBlockIndex2);
 #ifdef DEBUG
     // Verify linked-list invariants
     void Verify();
 #else
     void Verify() {}
 #endif
 
   private:
+    struct Entry : public nsUint32HashKey {
+      Entry(KeyTypePointer aKey) : nsUint32HashKey(aKey) { }
+      Entry(const Entry& toCopy) : nsUint32HashKey(&toCopy.GetKey()),
+        mNextBlock(toCopy.mNextBlock), mPrevBlock(toCopy.mPrevBlock) {}
+
+      PRInt32 mNextBlock;
+      PRInt32 mPrevBlock;
+    };
+    nsTHashtable<Entry> mEntries;
+
     // The index of the first block in the list, or -1 if the list is empty.
     PRInt32 mFirstBlock;
     // The number of blocks in the list.
     PRInt32 mCount;
   };
 
   // Returns the end of the bytes starting at the given offset
   // which are in cache.