Bug 882543 - Use a linked list for ordering stream instead of an array. r=ehsan
authorPaul Adenot <paul@paul.cx>
Fri, 19 Jul 2013 16:40:58 +0200
changeset 140184 d2967ea984a7aa53c54e79ab638cbfd72f6cb1e2
parent 140183 f202d49605d6f882694efac1b50d6162e71b121f
child 140185 01bf6add1d1fbb7349dce9f2b481ab245ba25cd6
push idunknown
push userunknown
push dateunknown
reviewersehsan
bugs882543
milestone25.0a1
Bug 882543 - Use a linked list for ordering stream instead of an array. r=ehsan
content/media/MediaStreamGraph.cpp
content/media/MediaStreamGraph.h
content/media/MediaStreamGraphImpl.h
--- a/content/media/MediaStreamGraph.cpp
+++ b/content/media/MediaStreamGraph.cpp
@@ -1,14 +1,15 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-*/
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "MediaStreamGraphImpl.h"
+#include "mozilla/LinkedList.h"
 
 #include "AudioSegment.h"
 #include "VideoSegment.h"
 #include "nsContentUtils.h"
 #include "nsIAppShell.h"
 #include "nsIObserver.h"
 #include "nsServiceManagerUtils.h"
 #include "nsWidgetsCID.h"
@@ -460,41 +461,43 @@ MediaStreamGraphImpl::MarkConsumed(Media
   }
   // Mark all the inputs to this stream as consumed
   for (uint32_t i = 0; i < ps->mInputs.Length(); ++i) {
     MarkConsumed(ps->mInputs[i]->mSource);
   }
 }
 
 void
-MediaStreamGraphImpl::UpdateStreamOrderForStream(nsTArray<MediaStream*>* aStack,
+MediaStreamGraphImpl::UpdateStreamOrderForStream(mozilla::LinkedList<MediaStream>* aStack,
                                                  already_AddRefed<MediaStream> aStream)
 {
   nsRefPtr<MediaStream> stream = aStream;
   NS_ASSERTION(!stream->mHasBeenOrdered, "stream should not have already been ordered");
   if (stream->mIsOnOrderingStack) {
-    for (int32_t i = aStack->Length() - 1; ; --i) {
-      aStack->ElementAt(i)->AsProcessedStream()->mInCycle = true;
-      if (aStack->ElementAt(i) == stream)
-        break;
+    MediaStream* iter = aStack->getLast();
+    if (iter) {
+      do {
+        iter->AsProcessedStream()->mInCycle = true;
+        iter = iter->getPrevious();
+      } while (iter && iter != stream);
     }
     return;
   }
   ProcessedMediaStream* ps = stream->AsProcessedStream();
   if (ps) {
-    aStack->AppendElement(stream);
+    aStack->insertBack(stream);
     stream->mIsOnOrderingStack = true;
     for (uint32_t i = 0; i < ps->mInputs.Length(); ++i) {
       MediaStream* source = ps->mInputs[i]->mSource;
       if (!source->mHasBeenOrdered) {
         nsRefPtr<MediaStream> s = source;
         UpdateStreamOrderForStream(aStack, s.forget());
       }
     }
-    aStack->RemoveElementAt(aStack->Length() - 1);
+    aStack->popLast();
     stream->mIsOnOrderingStack = false;
   }
 
   stream->mHasBeenOrdered = true;
   *mStreams.AppendElement() = stream.forget();
 }
 
 void
@@ -509,17 +512,17 @@ MediaStreamGraphImpl::UpdateStreamOrder(
     stream->mIsOnOrderingStack = false;
     stream->mInBlockingSet = false;
     ProcessedMediaStream* ps = stream->AsProcessedStream();
     if (ps) {
       ps->mInCycle = false;
     }
   }
 
-  nsAutoTArray<MediaStream*,10> stack;
+  mozilla::LinkedList<MediaStream> stack;
   for (uint32_t i = 0; i < mOldStreams.Length(); ++i) {
     nsRefPtr<MediaStream>& s = mOldStreams[i];
     if (!s->mAudioOutputs.IsEmpty() || !s->mVideoOutputs.IsEmpty()) {
       MarkConsumed(s);
     }
     if (!s->mHasBeenOrdered) {
       UpdateStreamOrderForStream(&stack, s.forget());
     }
--- a/content/media/MediaStreamGraph.h
+++ b/content/media/MediaStreamGraph.h
@@ -2,16 +2,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef MOZILLA_MEDIASTREAMGRAPH_H_
 #define MOZILLA_MEDIASTREAMGRAPH_H_
 
 #include "mozilla/Mutex.h"
+#include "mozilla/LinkedList.h"
 #include "AudioStream.h"
 #include "nsTArray.h"
 #include "nsIRunnable.h"
 #include "nsISupportsImpl.h"
 #include "StreamBuffer.h"
 #include "TimeVarying.h"
 #include "VideoFrameContainer.h"
 #include "VideoSegment.h"
@@ -252,17 +253,17 @@ struct AudioChunk;
  * the DOM wrappers must keep upstream MediaStreams alive as long as they
  * could be being used in the media graph.
  *
  * At any time, however, a set of MediaStream wrappers could be
  * collected via cycle collection. Destroy messages will be sent
  * for those objects in arbitrary order and the MediaStreamGraph has to be able
  * to handle this.
  */
-class MediaStream {
+class MediaStream : public mozilla::LinkedListElement<MediaStream> {
 public:
   NS_INLINE_DECL_THREADSAFE_REFCOUNTING(MediaStream)
 
   MediaStream(DOMMediaStream* aWrapper)
     : mBufferStartTime(0)
     , mExplicitBlockerCount(0)
     , mBlocked(false)
     , mGraphUpdateIndices(0)
--- a/content/media/MediaStreamGraphImpl.h
+++ b/content/media/MediaStreamGraphImpl.h
@@ -10,16 +10,19 @@
 
 #include "mozilla/Monitor.h"
 #include "mozilla/TimeStamp.h"
 #include "nsIThread.h"
 #include "nsIRunnable.h"
 
 namespace mozilla {
 
+template <typename T>
+class LinkedList;
+
 #ifdef PR_LOGGING
 extern PRLogModuleInfo* gMediaStreamGraphLog;
 #define LOG(type, msg) PR_LOG(gMediaStreamGraphLog, type, msg)
 #else
 #define LOG(type, msg)
 #endif
 
 /**
@@ -216,17 +219,17 @@ public:
   /**
    * Update "have enough data" flags in aStream.
    */
   void UpdateBufferSufficiencyState(SourceMediaStream* aStream);
   /*
    * If aStream hasn't already been ordered, push it onto aStack and order
    * its children.
    */
-  void UpdateStreamOrderForStream(nsTArray<MediaStream*>* aStack,
+  void UpdateStreamOrderForStream(mozilla::LinkedList<MediaStream>* aStack,
                                   already_AddRefed<MediaStream> aStream);
   /**
    * Mark aStream and all its inputs (recursively) as consumed.
    */
   static void MarkConsumed(MediaStream* aStream);
   /**
    * Sort mStreams so that every stream not in a cycle is after any streams
    * it depends on, and every stream in a cycle is marked as being in a cycle.