Use an array of pointers for effects instead of a linked list

7 files changed, 179 insertions, 66 deletions

diff --git a/Alc/ALc.c b/Alc/ALc.c
index 8d241802..84007020 100644
--- a/Alc/ALc.c
+++ b/Alc/ALc.c
@@ -2449,6 +2449,7 @@ static ALCboolean VerifyDevice(ALCdevice **device)
 static ALvoid InitContext(ALCcontext *Context)
 {
     ALlistener *listener = Context->Listener;
+    struct ALeffectslotArray *auxslots;
 
     //Initialise listener
     listener->Gain = 1.0f;
@@ -2490,6 +2491,10 @@ static ALvoid InitContext(ALCcontext *Context)
     InitUIntMap(&Context->SourceMap, Context->Device->SourcesMax);
     InitUIntMap(&Context->EffectSlotMap, Context->Device->AuxiliaryEffectSlotMax);
 
+    auxslots = al_calloc(DEF_ALIGN, offsetof(struct ALeffectslotArray, slot[0]));
+    auxslots->count = 0;
+    ATOMIC_INIT(&Context->ActiveAuxSlots, auxslots);
+
     //Set globals
     Context->DistanceModel = DefaultDistanceModel;
     Context->SourceDistanceModel = AL_FALSE;
@@ -2510,11 +2515,16 @@ static ALvoid InitContext(ALCcontext *Context)
 static void FreeContext(ALCcontext *context)
 {
     ALlistener *listener = context->Listener;
+    struct ALeffectslotArray *auxslots;
     struct ALlistenerProps *lprops;
     size_t count;
 
     TRACE("%p\n", context);
 
+    auxslots = ATOMIC_EXCHANGE(struct ALeffectslotArray*, &context->ActiveAuxSlots,
+                               NULL, almemory_order_relaxed);
+    al_free(auxslots);
+
     if(context->SourceMap.size > 0)
     {
         WARN("(%p) Deleting %d Source%s\n", context, context->SourceMap.size,
@@ -3511,7 +3521,7 @@ ALC_API ALCcontext* ALC_APIENTRY alcCreateContext(ALCdevice *device, const ALCin
         ALContext->Listener = (ALlistener*)ALContext->_listener_mem;
 
         ALContext->Device = device;
-        ATOMIC_INIT(&ALContext->ActiveAuxSlotList, NULL);
+        ATOMIC_INIT(&ALContext->ActiveAuxSlots, NULL);
 
         ALContext->Voices = NULL;
         ALContext->MaxVoices = 0;
diff --git a/Alc/ALu.c b/Alc/ALu.c
index 7936c706..f0e4d735 100644
--- a/Alc/ALu.c
+++ b/Alc/ALu.c
@@ -1281,20 +1281,18 @@ static void CalcSourceParams(ALvoice *voice, ALsource *source, ALCcontext *conte
 }
 
 
-static void UpdateContextSources(ALCcontext *ctx, ALeffectslot *slot)
+static void UpdateContextSources(ALCcontext *ctx, const struct ALeffectslotArray *slots)
 {
     ALvoice **voice, **voice_end;
     ALsource *source;
+    ALsizei i;
 
     IncrementRef(&ctx->UpdateCount);
     if(!ATOMIC_LOAD(&ctx->HoldUpdates, almemory_order_acquire))
     {
         ALboolean force = CalcListenerParams(ctx);
-        while(slot)
-        {
-            force |= CalcEffectSlotParams(slot, ctx->Device);
-            slot = ATOMIC_LOAD(&slot->next, almemory_order_relaxed);
-        }
+        for(i = 0;i < slots->count;i++)
+            force |= CalcEffectSlotParams(slots->slot[i], ctx->Device);
 
         voice = ctx->Voices;
         voice_end = voice + ctx->VoiceCount;
@@ -1417,24 +1415,23 @@ void aluMixData(ALCdevice *device, ALvoid *buffer, ALsizei size)
         if((slot=device->DefaultSlot) != NULL)
         {
             CalcEffectSlotParams(device->DefaultSlot, device);
-            for(i = 0;i < slot->NumChannels;i++)
-                memset(slot->WetBuffer[i], 0, SamplesToDo*sizeof(ALfloat));
+            for(c = 0;c < slot->NumChannels;c++)
+                memset(slot->WetBuffer[c], 0, SamplesToDo*sizeof(ALfloat));
         }
 
         ctx = ATOMIC_LOAD(&device->ContextList, almemory_order_acquire);
         while(ctx)
         {
-            ALeffectslot *slotroot;
+            const struct ALeffectslotArray *auxslots;
 
-            slotroot = ATOMIC_LOAD(&ctx->ActiveAuxSlotList, almemory_order_acquire);
-            UpdateContextSources(ctx, slotroot);
+            auxslots = ATOMIC_LOAD(&ctx->ActiveAuxSlots, almemory_order_acquire);
+            UpdateContextSources(ctx, auxslots);
 
-            slot = slotroot;
-            while(slot)
+            for(i = 0;i < auxslots->count;i++)
             {
-                for(i = 0;i < slot->NumChannels;i++)
-                    memset(slot->WetBuffer[i], 0, SamplesToDo*sizeof(ALfloat));
-                slot = ATOMIC_LOAD(&slot->next, almemory_order_relaxed);
+                ALeffectslot *slot = auxslots->slot[i];
+                for(c = 0;c < slot->NumChannels;c++)
+                    memset(slot->WetBuffer[c], 0, SamplesToDo*sizeof(ALfloat));
             }
 
             /* source processing */
@@ -1455,13 +1452,12 @@ void aluMixData(ALCdevice *device, ALvoid *buffer, ALsizei size)
             }
 
             /* effect slot processing */
-            slot = slotroot;
-            while(slot)
+            for(i = 0;i < auxslots->count;i++)
             {
+                ALeffectslot *slot = auxslots->slot[i];
                 ALeffectState *state = slot->Params.EffectState;
                 V(state,process)(SamplesToDo, SAFE_CONST(ALfloatBUFFERSIZE*,slot->WetBuffer),
                                  state->OutBuffer, state->OutChannels);
-                slot = ATOMIC_LOAD(&slot->next, almemory_order_relaxed);
             }
 
             ctx = ctx->next;
diff --git a/OpenAL32/Include/alAuxEffectSlot.h b/OpenAL32/Include/alAuxEffectSlot.h
index c6e40a55..7f95dc91 100644
--- a/OpenAL32/Include/alAuxEffectSlot.h
+++ b/OpenAL32/Include/alAuxEffectSlot.h
@@ -75,6 +75,12 @@ static const struct ALeffectStateFactoryVtable T##_ALeffectStateFactory_vtable =
 #define MAX_EFFECT_CHANNELS (4)
 
 
+struct ALeffectslotArray {
+    ALsizei count;
+    struct ALeffectslot *slot[];
+};
+
+
 struct ALeffectslotProps {
     ALfloat   Gain;
     ALboolean AuxSendAuto;
@@ -134,8 +140,6 @@ typedef struct ALeffectslot {
      * first-order device output (FOAOut).
      */
     alignas(16) ALfloat WetBuffer[MAX_EFFECT_CHANNELS][BUFFERSIZE];
-
-    ATOMIC(struct ALeffectslot*) next;
 } ALeffectslot;
 
 inline void LockEffectSlotsRead(ALCcontext *context)
diff --git a/OpenAL32/Include/alMain.h b/OpenAL32/Include/alMain.h
index 2182d3f0..9c1ef099 100644
--- a/OpenAL32/Include/alMain.h
+++ b/OpenAL32/Include/alMain.h
@@ -855,7 +855,7 @@ struct ALCcontext_struct {
     ALsizei VoiceCount;
     ALsizei MaxVoices;
 
-    ATOMIC(struct ALeffectslot*) ActiveAuxSlotList;
+    ATOMIC(struct ALeffectslotArray*) ActiveAuxSlots;
 
     ALCdevice  *Device;
     const ALCchar *ExtensionList;
diff --git a/OpenAL32/alAuxEffectSlot.c b/OpenAL32/alAuxEffectSlot.c
index 65107287..743fac14 100644
--- a/OpenAL32/alAuxEffectSlot.c
+++ b/OpenAL32/alAuxEffectSlot.c
@@ -42,8 +42,6 @@ extern inline void UnlockEffectSlotsWrite(ALCcontext *context);
 extern inline struct ALeffectslot *LookupEffectSlot(ALCcontext *context, ALuint id);
 extern inline struct ALeffectslot *RemoveEffectSlot(ALCcontext *context, ALuint id);
 
-static void RemoveEffectSlotList(ALCcontext *Context, ALeffectslot *slot);
-
 static UIntMap EffectStateFactoryMap;
 static inline ALeffectStateFactory *getFactoryByType(ALenum type)
 {
@@ -67,7 +65,7 @@ static void ALeffectState_DecRef(ALeffectState *state);
 AL_API ALvoid AL_APIENTRY alGenAuxiliaryEffectSlots(ALsizei n, ALuint *effectslots)
 {
     ALCcontext *context;
-    ALeffectslot *first, *last;
+    ALeffectslot **tmpslots = NULL;
     ALsizei cur;
     ALenum err;
 
@@ -76,8 +74,9 @@ AL_API ALvoid AL_APIENTRY alGenAuxiliaryEffectSlots(ALsizei n, ALuint *effectslo
 
     if(!(n >= 0))
         SET_ERROR_AND_GOTO(context, AL_INVALID_VALUE, done);
+    tmpslots = al_malloc(DEF_ALIGN, sizeof(ALeffectslot*)*n);
 
-    first = last = NULL;
+    LockEffectSlotsWrite(context);
     for(cur = 0;cur < n;cur++)
     {
         ALeffectslot *slot = al_calloc(16, sizeof(ALeffectslot));
@@ -85,13 +84,15 @@ AL_API ALvoid AL_APIENTRY alGenAuxiliaryEffectSlots(ALsizei n, ALuint *effectslo
         if(!slot || (err=InitEffectSlot(slot)) != AL_NO_ERROR)
         {
             al_free(slot);
+            UnlockEffectSlotsWrite(context);
+
             alDeleteAuxiliaryEffectSlots(cur, effectslots);
             SET_ERROR_AND_GOTO(context, err, done);
         }
 
         err = NewThunkEntry(&slot->id);
         if(err == AL_NO_ERROR)
-            err = InsertUIntMapEntry(&context->EffectSlotMap, slot->id, slot);
+            err = InsertUIntMapEntryNoLock(&context->EffectSlotMap, slot->id, slot);
         if(err != AL_NO_ERROR)
         {
             FreeThunkEntry(slot->id);
@@ -99,6 +100,7 @@ AL_API ALvoid AL_APIENTRY alGenAuxiliaryEffectSlots(ALsizei n, ALuint *effectslo
             if(slot->Params.EffectState)
                 ALeffectState_DecRef(slot->Params.EffectState);
             al_free(slot);
+            UnlockEffectSlotsWrite(context);
 
             alDeleteAuxiliaryEffectSlots(cur, effectslots);
             SET_ERROR_AND_GOTO(context, err, done);
@@ -106,22 +108,36 @@ AL_API ALvoid AL_APIENTRY alGenAuxiliaryEffectSlots(ALsizei n, ALuint *effectslo
 
         aluInitEffectPanning(slot);
 
-        if(!first) first = slot;
-        if(last) ATOMIC_STORE(&last->next, slot, almemory_order_relaxed);
-        last = slot;
-
+        tmpslots[cur] = slot;
         effectslots[cur] = slot->id;
     }
-    if(last != NULL)
+    if(n > 0)
     {
-        ALeffectslot *root = ATOMIC_LOAD_SEQ(&context->ActiveAuxSlotList);
-        do {
-            ATOMIC_STORE(&last->next, root, almemory_order_relaxed);
-        } while(!ATOMIC_COMPARE_EXCHANGE_WEAK_SEQ(ALeffectslot*, &context->ActiveAuxSlotList,
-                                                  &root, first));
+        struct ALeffectslotArray *curarray = ATOMIC_LOAD(&context->ActiveAuxSlots, almemory_order_acquire);
+        struct ALeffectslotArray *newarray = NULL;
+        ALsizei newcount = curarray->count + n;
+        ALCdevice *device;
+
+        newarray = al_calloc(DEF_ALIGN,
+            offsetof(struct ALeffectslotArray, slot[newcount])
+        );
+        newarray->count = newcount;
+        memcpy(newarray->slot, tmpslots, sizeof(ALeffectslot*)*n);
+        if(curarray)
+            memcpy(newarray->slot+n, curarray->slot, sizeof(ALeffectslot*)*curarray->count);
+
+        newarray = ATOMIC_EXCHANGE(struct ALeffectslotArray*,
+            &context->ActiveAuxSlots, newarray, almemory_order_acq_rel
+        );
+        device = context->Device;
+        while((ATOMIC_LOAD(&device->MixCount, almemory_order_acquire)&1))
+            althrd_yield();
+        al_free(newarray);
     }
+    UnlockEffectSlotsWrite(context);
 
 done:
+    al_free(tmpslots);
     ALCcontext_DecRef(context);
 }
 
@@ -146,13 +162,46 @@ AL_API ALvoid AL_APIENTRY alDeleteAuxiliaryEffectSlots(ALsizei n, const ALuint *
     }
 
     // All effectslots are valid
+    if(n > 0)
+    {
+        struct ALeffectslotArray *curarray = ATOMIC_LOAD(&context->ActiveAuxSlots, almemory_order_acquire);
+        struct ALeffectslotArray *newarray = NULL;
+        ALsizei newcount = curarray->count - n;
+        ALCdevice *device;
+        ALsizei j, k;
+
+        assert(newcount >= 0);
+        newarray = al_calloc(DEF_ALIGN,
+            offsetof(struct ALeffectslotArray, slot[newcount])
+        );
+        newarray->count = newcount;
+        for(i = j = 0;i < newarray->count;)
+        {
+            slot = curarray->slot[j++];
+            for(k = 0;k < n;k++)
+            {
+                if(slot->id == effectslots[k])
+                    break;
+            }
+            if(k == n)
+                newarray->slot[i++] = slot;
+        }
+
+        newarray = ATOMIC_EXCHANGE(struct ALeffectslotArray*,
+            &context->ActiveAuxSlots, newarray, almemory_order_acq_rel
+        );
+        device = context->Device;
+        while((ATOMIC_LOAD(&device->MixCount, almemory_order_acquire)&1))
+            althrd_yield();
+        al_free(newarray);
+    }
+
     for(i = 0;i < n;i++)
     {
         if((slot=RemoveEffectSlot(context, effectslots[i])) == NULL)
             continue;
         FreeThunkEntry(slot->id);
 
-        RemoveEffectSlotList(context, slot);
         DeinitEffectSlot(slot);
 
         memset(slot, 0, sizeof(*slot));
@@ -430,27 +479,6 @@ done:
 }
 
 
-static void RemoveEffectSlotList(ALCcontext *context, ALeffectslot *slot)
-{
-    ALCdevice *device = context->Device;
-    ALeffectslot *root, *next;
-
-    root = slot;
-    next = ATOMIC_LOAD_SEQ(&slot->next);
-    if(!ATOMIC_COMPARE_EXCHANGE_STRONG_SEQ(ALeffectslot*, &context->ActiveAuxSlotList, &root, next))
-    {
-        ALeffectslot *cur;
-        do {
-            cur = root;
-            root = slot;
-        } while(!ATOMIC_COMPARE_EXCHANGE_STRONG_SEQ(ALeffectslot*, &cur->next, &root, next));
-    }
-    /* Wait for any mix that may be using these effect slots to finish. */
-    while((ReadRef(&device->MixCount)&1) != 0)
-        althrd_yield();
-}
-
-
 void InitEffectFactoryMap(void)
 {
     InitUIntMap(&EffectStateFactoryMap, ~0);
@@ -595,8 +623,6 @@ ALenum InitEffectSlot(ALeffectslot *slot)
     slot->Params.DecayTime = 0.0f;
     slot->Params.AirAbsorptionGainHF = 1.0f;
 
-    ATOMIC_INIT(&slot->next, NULL);
-
     return AL_NO_ERROR;
 }
 
@@ -677,15 +703,16 @@ void UpdateEffectSlotProps(ALeffectslot *slot)
 
 void UpdateAllEffectSlotProps(ALCcontext *context)
 {
-    ALeffectslot *slot;
+    struct ALeffectslotArray *auxslots;
+    ALsizei i;
 
     LockEffectSlotsRead(context);
-    slot = ATOMIC_LOAD_SEQ(&context->ActiveAuxSlotList);
-    while(slot)
+    auxslots = ATOMIC_LOAD(&context->ActiveAuxSlots, almemory_order_acquire);
+    for(i = 0;i < auxslots->count;i++)
     {
+        ALeffectslot *slot = auxslots->slot[i];
         if(!ATOMIC_FLAG_TEST_AND_SET(&slot->PropsClean, almemory_order_acq_rel))
             UpdateEffectSlotProps(slot);
-        slot = ATOMIC_LOAD(&slot->next, almemory_order_relaxed);
     }
     UnlockEffectSlotsRead(context);
 }
diff --git a/common/uintmap.c b/common/uintmap.c
index 7b27b36e..21a921b2 100644
--- a/common/uintmap.c
+++ b/common/uintmap.c
@@ -119,6 +119,81 @@ ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
     return AL_NO_ERROR;
 }
 
+ALenum InsertUIntMapEntryNoLock(UIntMap *map, ALuint key, ALvoid *value)
+{
+    ALsizei pos = 0;
+
+    if(map->size > 0)
+    {
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
+            else
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+    }
+
+    if(pos == map->size || map->keys[pos] != key)
+    {
+        if(map->size == map->limit)
+            return AL_OUT_OF_MEMORY;
+
+        if(map->size == map->capacity)
+        {
+            ALuint *keys = NULL;
+            ALvoid **values;
+            ALsizei newcap, keylen;
+
+            newcap = (map->capacity ? (map->capacity<<1) : 4);
+            if(map->limit > 0 && newcap > map->limit)
+                newcap = map->limit;
+            if(newcap > map->capacity)
+            {
+                /* Round the memory size for keys up to a multiple of the
+                 * pointer size.
+                 */
+                keylen = newcap * sizeof(map->keys[0]);
+                keylen += sizeof(map->values[0]) - 1;
+                keylen -= keylen%sizeof(map->values[0]);
+
+                keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
+            }
+            if(!keys)
+                return AL_OUT_OF_MEMORY;
+            values = (ALvoid**)((ALbyte*)keys + keylen);
+
+            if(map->keys)
+            {
+                memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
+                memcpy(values, map->values, map->size*sizeof(map->values[0]));
+            }
+            al_free(map->keys);
+            map->keys = keys;
+            map->values = values;
+            map->capacity = newcap;
+        }
+
+        if(pos < map->size)
+        {
+            memmove(&map->keys[pos+1], &map->keys[pos],
+                    (map->size-pos)*sizeof(map->keys[0]));
+            memmove(&map->values[pos+1], &map->values[pos],
+                    (map->size-pos)*sizeof(map->values[0]));
+        }
+        map->size++;
+    }
+    map->keys[pos] = key;
+    map->values[pos] = value;
+
+    return AL_NO_ERROR;
+}
+
 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
 {
     ALvoid *ptr = NULL;
diff --git a/include/uintmap.h b/include/uintmap.h
index acb2749a..f70d99fd 100644
--- a/include/uintmap.h
+++ b/include/uintmap.h
@@ -24,6 +24,7 @@ typedef struct UIntMap {
 void InitUIntMap(UIntMap *map, ALsizei limit);
 void ResetUIntMap(UIntMap *map);
 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value);
+ALenum InsertUIntMapEntryNoLock(UIntMap *map, ALuint key, ALvoid *value);
 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key);
 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key);
 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key);