Use a map to store sources and buffers

And do a lookup using a binary search instead of linear

2 files changed, 108 insertions, 21 deletions

diff --git a/Alc/ALc.c b/Alc/ALc.c
index 438594e2..85d39872 100644
--- a/Alc/ALc.c
+++ b/Alc/ALc.c
@@ -637,6 +637,84 @@ void EnableRTPrio(ALint level)
 }
 
 
+void InitUIntMap(UIntMap *map)
+{
+    map->array = NULL;
+    map->size = 0;
+    map->maxsize = 0;
+}
+
+void ResetUIntMap(UIntMap *map)
+{
+    free(map->array);
+    map->array = NULL;
+    map->size = 0;
+    map->maxsize = 0;
+}
+
+ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
+{
+    ALsizei pos;
+
+    for(pos = 0;pos < map->size;pos++)
+    {
+        if(map->array[pos].key >= key)
+            break;
+    }
+
+    if(pos == map->size || map->array[pos].key != key)
+    {
+        if(map->size == map->maxsize)
+        {
+            ALvoid *temp;
+            ALsizei newsize;
+
+            newsize = (map->maxsize ? (map->maxsize<<1) : 4);
+            if(newsize < map->maxsize)
+                return AL_OUT_OF_MEMORY;
+
+            temp = realloc(map->array, newsize*sizeof(map->array[0]));
+            if(!temp) return AL_OUT_OF_MEMORY;
+            map->array = temp;
+            map->maxsize = newsize;
+        }
+
+        map->size++;
+        if(pos < map->size-1)
+            memmove(&map->array[pos+1], &map->array[pos],
+                    (map->size-1-pos)*sizeof(map->array[0]));
+    }
+    map->array[pos].key = key;
+    map->array[pos].value = value;
+
+    return AL_NO_ERROR;
+}
+
+void RemoveUIntMapKey(UIntMap *map, ALuint key)
+{
+    if(map->size > 0)
+    {
+        ALsizei low = 0;
+        ALsizei high = map->size - 1;
+        while(low < high)
+        {
+            ALsizei mid = low + (high-low)/2;
+            if(map->array[mid].key < key)
+                low = mid + 1;
+            else
+                high = mid;
+        }
+        if(map->array[low].key == key)
+        {
+            if(low < map->size-1)
+                memmove(&map->array[low], &map->array[low+1],
+                        (map->size-1-low)*sizeof(map->array[0]));
+            map->size--;
+        }
+    }
+}
+
+
 /*
     IsDevice
 
@@ -771,6 +849,7 @@ static ALvoid InitContext(ALCcontext *pContext)
     //Validate pContext
     pContext->LastError = AL_NO_ERROR;
     pContext->Suspended = AL_FALSE;
+    InitUIntMap(&pContext->SourceMap);
 
     //Set globals
     pContext->DistanceModel = AL_INVERSE_DISTANCE_CLAMPED;
@@ -1424,7 +1503,7 @@ ALC_API ALCcontext* ALC_APIENTRY alcCreateContext(ALCdevice *device, const ALCin
     {
         ALCcontext *context = device->Contexts[i];
         ALeffectslot *slot;
-        ALsource *source;
+        ALsizei pos;
 
         SuspendContext(context);
         for(slot = context->EffectSlotList;slot != NULL;slot = slot->next)
@@ -1444,8 +1523,9 @@ ALC_API ALCcontext* ALC_APIENTRY alcCreateContext(ALCdevice *device, const ALCin
             ALEffect_Update(slot->EffectState, context, &slot->effect);
         }
 
-        for(source = context->SourceList;source != NULL;source = source->next)
+        for(pos = 0;pos < context->SourceMap.size;pos++)
         {
+            ALsource *source = context->SourceMap.array[pos].value;
             ALuint s = device->NumAuxSends;
             while(s < MAX_SENDS)
             {
@@ -1549,13 +1629,15 @@ ALC_API ALCvoid ALC_APIENTRY alcDestroyContext(ALCcontext *context)
     // Lock context
     SuspendContext(context);
 
-    if(context->SourceCount > 0)
+    if(context->SourceMap.size > 0)
     {
 #ifdef _DEBUG
-        AL_PRINT("alcDestroyContext(): deleting %d Source(s)\n", context->SourceCount);
+        AL_PRINT("alcDestroyContext(): deleting %d Source(s)\n", context->SourceMap.size);
 #endif
         ReleaseALSources(context);
     }
+    ResetUIntMap(&context->SourceMap);
+
     if(context->EffectSlotCount > 0)
     {
 #ifdef _DEBUG
@@ -1837,6 +1919,8 @@ ALC_API ALCdevice* ALC_APIENTRY alcOpenDevice(const ALCchar *deviceName)
     device->Contexts = NULL;
     device->NumContexts = 0;
 
+    InitUIntMap(&device->BufferMap);
+
     //Set output format
     device->Frequency = GetConfigValueInt(NULL, "frequency", SWMIXER_OUTPUT_RATE);
     if(device->Frequency < 8000)
@@ -1947,13 +2031,15 @@ ALC_API ALCboolean ALC_APIENTRY alcCloseDevice(ALCdevice *pDevice)
     }
     ALCdevice_ClosePlayback(pDevice);
 
-    if(pDevice->BufferCount > 0)
+    if(pDevice->BufferMap.size > 0)
     {
 #ifdef _DEBUG
-        AL_PRINT("alcCloseDevice(): deleting %d Buffer(s)\n", pDevice->BufferCount);
+        AL_PRINT("alcCloseDevice(): deleting %d Buffer(s)\n", pDevice->BufferMap.size);
 #endif
         ReleaseALBuffers(pDevice);
     }
+    ResetUIntMap(&pDevice->BufferMap);
+
     if(pDevice->EffectCount > 0)
     {
 #ifdef _DEBUG
diff --git a/Alc/ALu.c b/Alc/ALu.c
index 8d5d85c1..db5a9eb7 100644
--- a/Alc/ALu.c
+++ b/Alc/ALu.c
@@ -943,8 +943,9 @@ static void MixSomeSources(ALCcontext *ALContext, float (*DryBuffer)[OUTPUTCHANN
     ALuint BuffersPlayed;
     ALfloat Pitch;
     ALenum State;
+    ALsizei pos;
 
-    if(!(ALSource=ALContext->SourceList))
+    if(ALContext->SourceMap.size <= 0)
         return;
 
     DuplicateStereo = ALContext->Device->DuplicateStereo;
@@ -953,13 +954,13 @@ static void MixSomeSources(ALCcontext *ALContext, float (*DryBuffer)[OUTPUTCHANN
     rampLength = DeviceFreq * MIN_RAMP_LENGTH / 1000;
     rampLength = max(rampLength, SamplesToDo);
 
-another_source:
-    if(ALSource->state != AL_PLAYING)
-    {
-        if((ALSource=ALSource->next) != NULL)
-            goto another_source;
-        return;
-    }
+    pos = ALContext->SourceMap.size;
+next_source:
+    do {
+        if(pos-- <= 0)
+            return;
+        ALSource = ALContext->SourceMap.array[pos].value;
+    } while(ALSource->state != AL_PLAYING);
     j = 0;
 
     /* Find buffer format */
@@ -1399,8 +1400,7 @@ another_source:
 
     ALSource->FirstStart = AL_FALSE;
 
-    if((ALSource=ALSource->next) != NULL)
-        goto another_source;
+    goto next_source;
 }
 
 ALvoid aluMixData(ALCdevice *device, ALvoid *buffer, ALsizei size)
@@ -1611,13 +1611,15 @@ ALvoid aluHandleDisconnect(ALCdevice *device)
     SuspendContext(NULL);
     for(i = 0;i < device->NumContexts;i++)
     {
+        ALCcontext *Context = device->Contexts[i];
         ALsource *source;
+        ALsizei pos;
 
-        SuspendContext(device->Contexts[i]);
+        SuspendContext(Context);
 
-        source = device->Contexts[i]->SourceList;
-        while(source)
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            source = Context->SourceMap.array[pos].value;
             if(source->state == AL_PLAYING)
             {
                 source->state = AL_STOPPED;
@@ -1625,9 +1627,8 @@ ALvoid aluHandleDisconnect(ALCdevice *device)
                 source->position = 0;
                 source->position_fraction = 0;
             }
-            source = source->next;
         }
-        ProcessContext(device->Contexts[i]);
+        ProcessContext(Context);
     }
 
     device->Connected = ALC_FALSE;