Dynamically sort the effect slots when mixing

This is to be able to support effects that output to other effects. When an
effect outputs to another effect, the former needs to process first, so the
former mixes to the latter's buffer before the latter is processed.

This sorting needs to happen in the mixer because the effect slot's "Target"
property changes asynchronously.

4 files changed, 51 insertions, 8 deletions

diff --git a/Alc/alc.cpp b/Alc/alc.cpp
index fb7f9c67..a5353cb9 100644
--- a/Alc/alc.cpp
+++ b/Alc/alc.cpp
@@ -2327,9 +2327,13 @@ static ALvoid InitContext(ALCcontext *Context)
     //Validate Context
     if(Context->DefaultSlot)
     {
+        static constexpr int count{1};
+        /* Allocate twice as much space for effect slots so the mixer has a
+         * place to sort them.
+         */
         auxslots = static_cast<ALeffectslotArray*>(al_calloc(DEF_ALIGN,
-            FAM_SIZE(ALeffectslotArray, slot, 1)));
-        auxslots->count = 1;
+            FAM_SIZE(ALeffectslotArray, slot, count*2)));
+        auxslots->count = count;
         auxslots->slot[0] = Context->DefaultSlot.get();
     }
     else
diff --git a/Alc/alu.cpp b/Alc/alu.cpp
index a6e53f4b..3ea82354 100644
--- a/Alc/alu.cpp
+++ b/Alc/alu.cpp
@@ -1429,8 +1429,10 @@ void ProcessParamUpdates(ALCcontext *ctx, const ALeffectslotArray *slots)
     IncrementRef(&ctx->UpdateCount);
 }
 
-void ProcessContext(ALCcontext *ctx, ALsizei SamplesToDo)
+void ProcessContext(ALCcontext *ctx, const ALsizei SamplesToDo)
 {
+    ASSUME(SamplesToDo > 0);
+
     const ALeffectslotArray *auxslots{ctx->ActiveAuxSlots.load(std::memory_order_acquire)};
 
     /* Process pending propery updates for objects on the context. */
@@ -1465,7 +1467,42 @@ void ProcessContext(ALCcontext *ctx, ALsizei SamplesToDo)
     );
 
     /* Process effects. */
-    std::for_each(auxslots->slot, auxslots->slot+auxslots->count,
+    if(auxslots->count < 1) return;
+    auto slots = auxslots->slot;
+    auto slots_end = slots + auxslots->count;
+
+    /* First sort the slots into scratch storage, so that effects come before
+     * their effect target (or their targets' target).
+     */
+    auto sorted_slots = const_cast<ALeffectslot**>(slots_end);
+    auto sorted_slots_end = sorted_slots;
+    auto in_chain = [](const ALeffectslot *slot1, const ALeffectslot *slot2) noexcept -> bool
+    {
+        while((slot1=slot1->Params.Target) != nullptr) {
+            if(slot1 == slot2) return true;
+        }
+        return false;
+    };
+
+    *sorted_slots_end = *slots;
+    ++sorted_slots_end;
+    while(++slots != slots_end)
+    {
+        /* If this effect slot targets an effect slot already in the list (i.e.
+         * slots outputs to something in sorted_slots), directly or indirectly,
+         * insert it prior to that element.
+         */
+        auto checker = sorted_slots;
+        do {
+            if(in_chain(*slots, *checker)) break;
+        } while(++checker != sorted_slots_end);
+
+        checker = std::move_backward(checker, sorted_slots_end, sorted_slots_end+1);
+        *--checker = *slots;
+        ++sorted_slots_end;
+    }
+
+    std::for_each(sorted_slots, sorted_slots_end,
         [SamplesToDo](const ALeffectslot *slot) -> void
         {
             EffectState *state{slot->Params.mEffectState};
diff --git a/OpenAL32/Include/alAuxEffectSlot.h b/OpenAL32/Include/alAuxEffectSlot.h
index 539cee53..04f00758 100644
--- a/OpenAL32/Include/alAuxEffectSlot.h
+++ b/OpenAL32/Include/alAuxEffectSlot.h
@@ -78,6 +78,7 @@ struct ALeffectslot {
     struct {
         ALfloat   Gain{1.0f};
         ALboolean AuxSendAuto{AL_TRUE};
+        ALeffectslot *Target{nullptr};
 
         ALenum EffectType{AL_EFFECT_NULL};
         ALeffectProps EffectProps{};
diff --git a/OpenAL32/alAuxEffectSlot.cpp b/OpenAL32/alAuxEffectSlot.cpp
index db22ca4c..ca279aee 100644
--- a/OpenAL32/alAuxEffectSlot.cpp
+++ b/OpenAL32/alAuxEffectSlot.cpp
@@ -71,10 +71,11 @@ void AddActiveEffectSlots(const ALuint *slotids, ALsizei count, ALCcontext *cont
     ALsizei newcount{curarray->count + count};
 
     /* Insert the new effect slots into the head of the array, followed by the
-     * existing ones.
+     * existing ones. Allocate twice as much space for effect slots so the
+     * mixer has a place to sort them.
      */
     auto newarray = static_cast<ALeffectslotArray*>(al_calloc(DEF_ALIGN,
-        FAM_SIZE(ALeffectslotArray, slot, newcount)));
+        FAM_SIZE(ALeffectslotArray, slot, newcount*2)));
     newarray->count = newcount;
     auto slotiter = std::transform(slotids, slotids+count, newarray->slot,
         [context](ALuint id) noexcept -> ALeffectslot*
@@ -99,7 +100,7 @@ void AddActiveEffectSlots(const ALuint *slotids, ALsizei count, ALCcontext *cont
     {
         curarray = newarray;
         newarray = static_cast<ALeffectslotArray*>(al_calloc(DEF_ALIGN,
-            FAM_SIZE(ALeffectslotArray, slot, newcount)));
+            FAM_SIZE(ALeffectslotArray, slot, newcount*2)));
         newarray->count = newcount;
         std::copy_n(curarray->slot, newcount, newarray->slot);
         al_free(curarray);
@@ -122,7 +123,7 @@ void RemoveActiveEffectSlots(const ALuint *slotids, ALsizei count, ALCcontext *c
      * any) of the effect slots to remove are in the array.
      */
     auto newarray = static_cast<ALeffectslotArray*>(al_calloc(DEF_ALIGN,
-        FAM_SIZE(ALeffectslotArray, slot, curarray->count)));
+        FAM_SIZE(ALeffectslotArray, slot, curarray->count*2)));
 
     /* Copy each element in curarray to newarray whose ID is not in slotids. */
     const ALuint *slotids_end{slotids + count};