--- 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.