Use a map to store sources and buffers

And do a lookup using a binary search instead of linear

10 files changed, 273 insertions, 183 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;
diff --git a/OpenAL32/Include/alBuffer.h b/OpenAL32/Include/alBuffer.h
index 9035ccd6..9561b057 100644
--- a/OpenAL32/Include/alBuffer.h
+++ b/OpenAL32/Include/alBuffer.h
@@ -22,8 +22,6 @@ typedef struct ALbuffer
 
     // Index to itself
     ALuint buffer;
-
-    struct ALbuffer *next;
 } ALbuffer;
 
 ALvoid ReleaseALBuffers(ALCdevice *device);
diff --git a/OpenAL32/Include/alMain.h b/OpenAL32/Include/alMain.h
index 27c1f981..5f40bcc7 100644
--- a/OpenAL32/Include/alMain.h
+++ b/OpenAL32/Include/alMain.h
@@ -226,6 +226,41 @@ void alc_pulse_deinit(void);
 void alc_pulse_probe(int type);
 
 
+typedef struct UIntMap {
+    struct {
+        ALuint key;
+        ALvoid *value;
+    } *array;
+    ALsizei size;
+    ALsizei maxsize;
+} UIntMap;
+
+void InitUIntMap(UIntMap *map);
+void ResetUIntMap(UIntMap *map);
+ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value);
+void RemoveUIntMapKey(UIntMap *map, ALuint key);
+
+static inline ALvoid *LookupUIntMapKey(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)
+            return map->array[low].value;
+    }
+    return NULL;
+}
+
+
 struct ALCdevice_struct
 {
     ALCboolean   Connected;
@@ -249,9 +284,8 @@ struct ALCdevice_struct
     ALCuint      NumStereoSources;
     ALuint       NumAuxSends;
 
-    // Linked List of Buffers for this device
-    struct ALbuffer *BufferList;
-    ALuint           BufferCount;
+    // Map of Buffers for this device
+    UIntMap BufferMap;
 
     // Linked List of Effects for this device
     struct ALeffect *EffectList;
@@ -311,8 +345,7 @@ struct ALCcontext_struct
 {
     ALlistener  Listener;
 
-    struct ALsource *SourceList;
-    ALuint           SourceCount;
+    UIntMap SourceMap;
 
     struct ALeffectslot *EffectSlotList;
     ALuint               EffectSlotCount;
diff --git a/OpenAL32/Include/alSource.h b/OpenAL32/Include/alSource.h
index d82ac1c0..0802cbaa 100644
--- a/OpenAL32/Include/alSource.h
+++ b/OpenAL32/Include/alSource.h
@@ -104,8 +104,6 @@ typedef struct ALsource
 
     // Index to itself
     ALuint source;
-
-    struct ALsource *next;
 } ALsource;
 
 ALvoid ReleaseALSources(ALCcontext *Context);
diff --git a/OpenAL32/alAuxEffectSlot.c b/OpenAL32/alAuxEffectSlot.c
index 90e28431..0ff10ab2 100644
--- a/OpenAL32/alAuxEffectSlot.c
+++ b/OpenAL32/alAuxEffectSlot.c
@@ -232,9 +232,10 @@ AL_API ALvoid AL_APIENTRY alAuxiliaryEffectSloti(ALuint effectslot, ALenum param
     // sending parameters
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             ALuint i;
             for(i = 0;i < MAX_SENDS;i++)
             {
@@ -244,7 +245,6 @@ AL_API ALvoid AL_APIENTRY alAuxiliaryEffectSloti(ALuint effectslot, ALenum param
                 source->NeedsUpdate = AL_TRUE;
                 break;
             }
-            source = source->next;
         }
     }
 
diff --git a/OpenAL32/alBuffer.c b/OpenAL32/alBuffer.c
index bfcbcc8e..2e232792 100644
--- a/OpenAL32/alBuffer.c
+++ b/OpenAL32/alBuffer.c
@@ -39,7 +39,7 @@ static void ConvertDataIMA4(ALfloat *dst, const ALvoid *src, ALint origChans, AL
 static void ConvertDataMULaw(ALfloat *dst, const ALvoid *src, ALsizei len);
 static void ConvertDataMULawRear(ALfloat *dst, const ALvoid *src, ALsizei len);
 
-DECL_VERIFIER(Buffer, ALbuffer, buffer)
+#define LookupBuffer(m, k) ((ALbuffer*)LookupUIntMapKey(&(m), (k)))
 
 /*
 * Global Variables
@@ -104,7 +104,7 @@ static const ALshort muLawDecompressionTable[256] = {
 *
 *    Generates n AL Buffers, and stores the Buffers Names in the array pointed to by puiBuffers
 */
-AL_API ALvoid AL_APIENTRY alGenBuffers(ALsizei n,ALuint *puiBuffers)
+AL_API ALvoid AL_APIENTRY alGenBuffers(ALsizei n, ALuint *buffers)
 {
     ALCcontext *Context;
     ALsizei i=0;
@@ -113,45 +113,39 @@ AL_API ALvoid AL_APIENTRY alGenBuffers(ALsizei n,ALuint *puiBuffers)
     if(!Context) return;
 
     // Check that we are actually generation some Buffers
-    if (n > 0)
+    if(n > 0)
     {
         ALCdevice *device = Context->Device;
+        ALenum err;
 
         // Check the pointer is valid (and points to enough memory to store Buffer Names)
-        if (!IsBadWritePtr((void*)puiBuffers, n * sizeof(ALuint)))
+        if(!IsBadWritePtr((void*)buffers, n * sizeof(ALuint)))
         {
-            ALbuffer *end;
-            ALbuffer **list = &device->BufferList;
-            while(*list)
-                list = &(*list)->next;
-
             // Create all the new Buffers
-            end = *list;
             while(i < n)
             {
-                *list = calloc(1, sizeof(ALbuffer));
-                if(!(*list))
+                ALbuffer *buffer = calloc(1, sizeof(ALbuffer));
+                if(!buffer)
                 {
-                    while(end->next)
-                    {
-                        ALbuffer *temp = end->next;
-                        end->next = temp->next;
-
-                        ALTHUNK_REMOVEENTRY(temp->buffer);
-                        device->BufferCount--;
-                        free(temp);
-                    }
                     alSetError(Context, AL_OUT_OF_MEMORY);
+                    alDeleteBuffers(i, buffers);
                     break;
                 }
 
-                puiBuffers[i] = (ALuint)ALTHUNK_ADDENTRY(*list);
-                (*list)->buffer = puiBuffers[i];
-
-                device->BufferCount++;
-                i++;
+                buffer->buffer = (ALuint)ALTHUNK_ADDENTRY(buffer);
+                err = InsertUIntMapEntry(&device->BufferMap, buffer->buffer,
+                                         buffer);
+                if(err != AL_NO_ERROR)
+                {
+                    ALTHUNK_REMOVEENTRY(buffer->buffer);
+                    memset(buffer, 0, sizeof(ALbuffer));
+                    free(buffer);
 
-                list = &(*list)->next;
+                    alSetError(Context, err);
+                    alDeleteBuffers(i, buffers);
+                    break;
+                }
+                buffers[i++] = buffer->buffer;
             }
         }
         else
@@ -191,7 +185,7 @@ AL_API ALvoid AL_APIENTRY alDeleteBuffers(ALsizei n, const ALuint *puiBuffers)
                 continue;
 
             // Check for valid Buffer ID (can be NULL buffer)
-            if((ALBuf=VerifyBuffer(device->BufferList, puiBuffers[i])) != NULL)
+            if((ALBuf=LookupBuffer(device->BufferMap, puiBuffers[i])) != NULL)
             {
                 if(ALBuf->refcount != 0)
                 {
@@ -215,23 +209,16 @@ AL_API ALvoid AL_APIENTRY alDeleteBuffers(ALsizei n, const ALuint *puiBuffers)
         {
             for (i = 0; i < n; i++)
             {
-                if((ALBuf=VerifyBuffer(device->BufferList, puiBuffers[i])) != NULL)
+                if((ALBuf=LookupBuffer(device->BufferMap, puiBuffers[i])) != NULL)
                 {
-                    ALbuffer **list = &device->BufferList;
-
-                    while(*list && *list != ALBuf)
-                        list = &(*list)->next;
-
-                    if(*list)
-                        *list = (*list)->next;
-
                     // Release the memory used to store audio data
                     free(ALBuf->data);
 
                     // Release buffer structure
-                    ALTHUNK_REMOVEENTRY(puiBuffers[i]);
+                    RemoveUIntMapKey(&device->BufferMap, ALBuf->buffer);
+                    ALTHUNK_REMOVEENTRY(ALBuf->buffer);
+
                     memset(ALBuf, 0, sizeof(ALbuffer));
-                    device->BufferCount--;
                     free(ALBuf);
                 }
             }
@@ -257,7 +244,7 @@ AL_API ALboolean AL_APIENTRY alIsBuffer(ALuint uiBuffer)
     if(!Context) return AL_FALSE;
 
     if(uiBuffer)
-        result = (VerifyBuffer(Context->Device->BufferList, uiBuffer) ?
+        result = (LookupBuffer(Context->Device->BufferMap, uiBuffer) ?
                   AL_TRUE : AL_FALSE);
 
     ProcessContext(Context);
@@ -282,7 +269,7 @@ AL_API ALvoid AL_APIENTRY alBufferData(ALuint buffer,ALenum format,const ALvoid
     if(!Context) return;
 
     device = Context->Device;
-    if((ALBuf=VerifyBuffer(device->BufferList, buffer)) != NULL)
+    if((ALBuf=LookupBuffer(device->BufferMap, buffer)) != NULL)
     {
         if(Context->SampleSource)
         {
@@ -531,7 +518,7 @@ AL_API ALvoid AL_APIENTRY alBufferSubDataEXT(ALuint buffer,ALenum format,const A
     if(!Context) return;
 
     device = Context->Device;
-    if((ALBuf=VerifyBuffer(device->BufferList, buffer)) != NULL)
+    if((ALBuf=LookupBuffer(device->BufferMap, buffer)) != NULL)
     {
         if(Context->SampleSource)
         {
@@ -679,7 +666,7 @@ AL_API void AL_APIENTRY alBufferf(ALuint buffer, ALenum eParam, ALfloat flValue)
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -710,7 +697,7 @@ AL_API void AL_APIENTRY alBuffer3f(ALuint buffer, ALenum eParam, ALfloat flValue
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -739,7 +726,7 @@ AL_API void AL_APIENTRY alBufferfv(ALuint buffer, ALenum eParam, const ALfloat*
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -768,7 +755,7 @@ AL_API void AL_APIENTRY alBufferi(ALuint buffer, ALenum eParam, ALint lValue)
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -799,7 +786,7 @@ AL_API void AL_APIENTRY alBuffer3i( ALuint buffer, ALenum eParam, ALint lValue1,
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -828,7 +815,7 @@ AL_API void AL_APIENTRY alBufferiv(ALuint buffer, ALenum eParam, const ALint* pl
     if(!pContext) return;
 
     device = pContext->Device;
-    if(VerifyBuffer(device->BufferList, buffer) != NULL)
+    if(LookupBuffer(device->BufferMap, buffer) != NULL)
     {
         switch(eParam)
         {
@@ -857,7 +844,7 @@ AL_API ALvoid AL_APIENTRY alGetBufferf(ALuint buffer, ALenum eParam, ALfloat *pf
     if (pflValue)
     {
         device = pContext->Device;
-        if(VerifyBuffer(device->BufferList, buffer) != NULL)
+        if(LookupBuffer(device->BufferMap, buffer) != NULL)
         {
             switch(eParam)
             {
@@ -891,7 +878,7 @@ AL_API void AL_APIENTRY alGetBuffer3f(ALuint buffer, ALenum eParam, ALfloat* pfl
     if ((pflValue1) && (pflValue2) && (pflValue3))
     {
         device = pContext->Device;
-        if(VerifyBuffer(device->BufferList, buffer) != NULL)
+        if(LookupBuffer(device->BufferMap, buffer) != NULL)
         {
             switch(eParam)
             {
@@ -925,7 +912,7 @@ AL_API void AL_APIENTRY alGetBufferfv(ALuint buffer, ALenum eParam, ALfloat* pfl
     if (pflValues)
     {
         device = pContext->Device;
-        if(VerifyBuffer(device->BufferList, buffer) != NULL)
+        if(LookupBuffer(device->BufferMap, buffer) != NULL)
         {
             switch(eParam)
             {
@@ -960,7 +947,7 @@ AL_API ALvoid AL_APIENTRY alGetBufferi(ALuint buffer, ALenum eParam, ALint *plVa
     if (plValue)
     {
         device = pContext->Device;
-        if((pBuffer=VerifyBuffer(device->BufferList, buffer)) != NULL)
+        if((pBuffer=LookupBuffer(device->BufferMap, buffer)) != NULL)
         {
             switch (eParam)
             {
@@ -1010,7 +997,7 @@ AL_API void AL_APIENTRY alGetBuffer3i(ALuint buffer, ALenum eParam, ALint* plVal
     if ((plValue1) && (plValue2) && (plValue3))
     {
         device = pContext->Device;
-        if(VerifyBuffer(device->BufferList, buffer) != NULL)
+        if(LookupBuffer(device->BufferMap, buffer) != NULL)
         {
             switch(eParam)
             {
@@ -1044,7 +1031,7 @@ AL_API void AL_APIENTRY alGetBufferiv(ALuint buffer, ALenum eParam, ALint* plVal
     if (plValues)
     {
         device = pContext->Device;
-        if(VerifyBuffer(device->BufferList, buffer) != NULL)
+        if(LookupBuffer(device->BufferMap, buffer) != NULL)
         {
             switch (eParam)
             {
@@ -1274,10 +1261,11 @@ static void ConvertDataMULawRear(ALfloat *dst, const ALvoid *src, ALsizei len)
 */
 ALvoid ReleaseALBuffers(ALCdevice *device)
 {
-    while(device->BufferList)
+    ALsizei i;
+    for(i = 0;i < device->BufferMap.size;i++)
     {
-        ALbuffer *temp = device->BufferList;
-        device->BufferList = temp->next;
+        ALbuffer *temp = device->BufferMap.array[i].value;
+        device->BufferMap.array[i].value = NULL;
 
         // Release sample data
         free(temp->data);
@@ -1287,5 +1275,4 @@ ALvoid ReleaseALBuffers(ALCdevice *device)
         memset(temp, 0, sizeof(ALbuffer));
         free(temp);
     }
-    device->BufferCount = 0;
 }
diff --git a/OpenAL32/alListener.c b/OpenAL32/alListener.c
index b743f207..b3c192dc 100644
--- a/OpenAL32/alListener.c
+++ b/OpenAL32/alListener.c
@@ -65,11 +65,11 @@ AL_API ALvoid AL_APIENTRY alListenerf(ALenum eParam, ALfloat flValue)
     // relative sources are affected
     if(updateAll)
     {
-        ALsource *source = pContext->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < pContext->SourceMap.size;pos++)
         {
+            ALsource *source = pContext->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -108,12 +108,12 @@ AL_API ALvoid AL_APIENTRY alListener3f(ALenum eParam, ALfloat flValue1, ALfloat
 
     if(updateWorld)
     {
-        ALsource *source = pContext->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < pContext->SourceMap.size;pos++)
         {
+            ALsource *source = pContext->SourceMap.array[pos].value;
             if(!source->bHeadRelative)
                 source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -164,12 +164,12 @@ AL_API ALvoid AL_APIENTRY alListenerfv(ALenum eParam, const ALfloat *pflValues)
 
     if(updateWorld)
     {
-        ALsource *source = pContext->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < pContext->SourceMap.size;pos++)
         {
+            ALsource *source = pContext->SourceMap.array[pos].value;
             if(!source->bHeadRelative)
                 source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
diff --git a/OpenAL32/alSource.c b/OpenAL32/alSource.c
index 335144ba..d9fdec0a 100644
--- a/OpenAL32/alSource.c
+++ b/OpenAL32/alSource.c
@@ -37,11 +37,12 @@ static ALvoid GetSourceOffset(ALsource *Source, ALenum eName, ALdouble *Offsets,
 static ALboolean ApplyOffset(ALsource *Source);
 static ALint GetByteOffset(ALsource *Source);
 
-DECL_VERIFIER(Source, ALsource, source)
-DECL_VERIFIER(Buffer, ALbuffer, buffer)
 DECL_VERIFIER(Filter, ALfilter, filter)
 DECL_VERIFIER(EffectSlot, ALeffectslot, effectslot)
 
+#define LookupSource(m, k) ((ALsource*)LookupUIntMapKey(&(m), (k)))
+#define LookupBuffer(m, k) ((ALbuffer*)LookupUIntMapKey(&(m), (k)))
+
 AL_API ALvoid AL_APIENTRY alGenSources(ALsizei n,ALuint *sources)
 {
     ALCcontext *Context;
@@ -59,41 +60,37 @@ AL_API ALvoid AL_APIENTRY alGenSources(ALsizei n,ALuint *sources)
         if(!IsBadWritePtr((void*)sources, n * sizeof(ALuint)))
         {
             // Check that the requested number of sources can be generated
-            if((Context->SourceCount + n) <= Device->MaxNoOfSources)
+            if((Context->SourceMap.size + n) <= (ALsizei)Device->MaxNoOfSources)
             {
-                ALsource *end;
-                ALsource **list = &Context->SourceList;
-                while(*list)
-                    list = &(*list)->next;
+                ALenum err;
 
-                // Add additional sources to the list (Source->next points to the location for the next Source structure)
-                end = *list;
+                // Add additional sources to the list
                 while(i < n)
                 {
-                    *list = calloc(1, sizeof(ALsource));
-                    if(!(*list))
+                    ALsource *source = calloc(1, sizeof(ALsource));
+                    if(!source)
                     {
-                        while(end->next)
-                        {
-                            ALsource *temp = end->next;
-                            end->next = temp->next;
-
-                            ALTHUNK_REMOVEENTRY(temp->source);
-                            Context->SourceCount--;
-                            free(temp);
-                        }
                         alSetError(Context, AL_OUT_OF_MEMORY);
+                        alDeleteSources(i, sources);
                         break;
                     }
 
-                    sources[i] = (ALuint)ALTHUNK_ADDENTRY(*list);
-                    (*list)->source = sources[i];
+                    source->source = (ALuint)ALTHUNK_ADDENTRY(source);
+                    err = InsertUIntMapEntry(&Context->SourceMap, source->source,
+                                             source);
+                    if(err != AL_NO_ERROR)
+                    {
+                        ALTHUNK_REMOVEENTRY(source->source);
+                        memset(source, 0, sizeof(ALsource));
+                        free(source);
 
-                    InitSourceParams(*list);
-                    Context->SourceCount++;
-                    i++;
+                        alSetError(Context, err);
+                        alDeleteSources(i, sources);
+                        break;
+                    }
 
-                    list = &(*list)->next;
+                    sources[i++] = source->source;
+                    InitSourceParams(source);
                 }
             }
             else
@@ -118,7 +115,6 @@ AL_API ALvoid AL_APIENTRY alDeleteSources(ALsizei n, const ALuint *sources)
     ALCcontext *Context;
     ALCdevice  *Device;
     ALsource *Source;
-    ALsource **list;
     ALsizei i, j;
     ALbufferlistitem *BufferList;
     ALboolean bSourcesValid = AL_TRUE;
@@ -133,7 +129,7 @@ AL_API ALvoid AL_APIENTRY alDeleteSources(ALsizei n, const ALuint *sources)
         // Check that all Sources are valid (and can therefore be deleted)
         for (i = 0; i < n; i++)
         {
-            if(VerifySource(Context->SourceList, sources[i]) == NULL)
+            if(LookupSource(Context->SourceMap, sources[i]) == NULL)
             {
                 alSetError(Context, AL_INVALID_NAME);
                 bSourcesValid = AL_FALSE;
@@ -147,10 +143,10 @@ AL_API ALvoid AL_APIENTRY alDeleteSources(ALsizei n, const ALuint *sources)
             for(i = 0; i < n; i++)
             {
                 // Recheck that the Source is valid, because there could be duplicated Source names
-                if((Source=VerifySource(Context->SourceList, sources[i])) != NULL)
+                if((Source=LookupSource(Context->SourceMap, sources[i])) != NULL)
                 {
                     // For each buffer in the source's queue, decrement its reference counter and remove it
-                    while (Source->queue != NULL)
+                    while(Source->queue != NULL)
                     {
                         BufferList = Source->queue;
                         // Decrement buffer's reference counter
@@ -169,16 +165,8 @@ AL_API ALvoid AL_APIENTRY alDeleteSources(ALsizei n, const ALuint *sources)
                         Source->Send[j].Slot = NULL;
                     }
 
-                    // Decrement Source count
-                    Context->SourceCount--;
-
                     // Remove Source from list of Sources
-                    list = &Context->SourceList;
-                    while(*list && *list != Source)
-                        list = &(*list)->next;
-
-                    if(*list)
-                        *list = (*list)->next;
+                    RemoveUIntMapKey(&Context->SourceMap, Source->source);
                     ALTHUNK_REMOVEENTRY(Source->source);
 
                     memset(Source,0,sizeof(ALsource));
@@ -202,7 +190,7 @@ AL_API ALboolean AL_APIENTRY alIsSource(ALuint source)
     Context = GetContextSuspended();
     if(!Context) return AL_FALSE;
 
-    result = (VerifySource(Context->SourceList, source) ? AL_TRUE : AL_FALSE);
+    result = (LookupSource(Context->SourceMap, source) ? AL_TRUE : AL_FALSE);
 
     ProcessContext(Context);
 
@@ -218,7 +206,7 @@ AL_API ALvoid AL_APIENTRY alSourcef(ALuint source, ALenum eParam, ALfloat flValu
     pContext = GetContextSuspended();
     if(!pContext) return;
 
-    if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+    if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
     {
         switch(eParam)
         {
@@ -410,7 +398,7 @@ AL_API ALvoid AL_APIENTRY alSource3f(ALuint source, ALenum eParam, ALfloat flVal
     pContext = GetContextSuspended();
     if(!pContext) return;
 
-    if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+    if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
     {
         switch(eParam)
         {
@@ -456,7 +444,7 @@ AL_API ALvoid AL_APIENTRY alSourcefv(ALuint source, ALenum eParam, const ALfloat
 
     if(pflValues)
     {
-        if(VerifySource(pContext->SourceList, source) != NULL)
+        if(LookupSource(pContext->SourceMap, source) != NULL)
         {
             switch(eParam)
             {
@@ -509,7 +497,7 @@ AL_API ALvoid AL_APIENTRY alSourcei(ALuint source,ALenum eParam,ALint lValue)
     pContext = GetContextSuspended();
     if(!pContext) return;
 
-    if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+    if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
     {
         ALCdevice *device = pContext->Device;
 
@@ -546,7 +534,7 @@ AL_API ALvoid AL_APIENTRY alSourcei(ALuint source,ALenum eParam,ALint lValue)
                     ALbuffer *buffer = NULL;
 
                     if(lValue == 0 ||
-                       (buffer=VerifyBuffer(device->BufferList, lValue)) != NULL)
+                       (buffer=LookupBuffer(device->BufferMap, lValue)) != NULL)
                     {
                         // Remove all elements in the queue
                         while(Source->queue != NULL)
@@ -711,7 +699,7 @@ AL_API void AL_APIENTRY alSource3i(ALuint source, ALenum eParam, ALint lValue1,
     pContext = GetContextSuspended();
     if(!pContext) return;
 
-    if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+    if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
     {
         ALCdevice *device = pContext->Device;
 
@@ -776,7 +764,7 @@ AL_API void AL_APIENTRY alSourceiv(ALuint source, ALenum eParam, const ALint* pl
 
     if(plValues)
     {
-        if(VerifySource(pContext->SourceList, source) != NULL)
+        if(LookupSource(pContext->SourceMap, source) != NULL)
         {
             switch(eParam)
             {
@@ -834,7 +822,7 @@ AL_API ALvoid AL_APIENTRY alGetSourcef(ALuint source, ALenum eParam, ALfloat *pf
 
     if(pflValue)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -928,7 +916,7 @@ AL_API ALvoid AL_APIENTRY alGetSource3f(ALuint source, ALenum eParam, ALfloat* p
 
     if(pflValue1 && pflValue2 && pflValue3)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -977,7 +965,7 @@ AL_API ALvoid AL_APIENTRY alGetSourcefv(ALuint source, ALenum eParam, ALfloat *p
 
     if(pflValues)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -1055,7 +1043,7 @@ AL_API ALvoid AL_APIENTRY alGetSourcei(ALuint source, ALenum eParam, ALint *plVa
 
     if(plValue)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -1172,7 +1160,7 @@ AL_API void AL_APIENTRY alGetSource3i(ALuint source, ALenum eParam, ALint* plVal
 
     if(plValue1 && plValue2 && plValue3)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -1221,7 +1209,7 @@ AL_API void AL_APIENTRY alGetSourceiv(ALuint source, ALenum eParam, ALint* plVal
 
     if(plValues)
     {
-        if((Source=VerifySource(pContext->SourceList, source)) != NULL)
+        if((Source=LookupSource(pContext->SourceMap, source)) != NULL)
         {
             switch(eParam)
             {
@@ -1315,7 +1303,7 @@ AL_API ALvoid AL_APIENTRY alSourcePlayv(ALsizei n, const ALuint *sources)
     // Check that all the Sources are valid
     for(i = 0;i < n;i++)
     {
-        if(!VerifySource(Context->SourceList, sources[i]))
+        if(!LookupSource(Context->SourceMap, sources[i]))
         {
             alSetError(Context, AL_INVALID_NAME);
             goto done;
@@ -1405,7 +1393,7 @@ AL_API ALvoid AL_APIENTRY alSourcePausev(ALsizei n, const ALuint *sources)
     // Check all the Sources are valid
     for(i = 0;i < n;i++)
     {
-        if(!VerifySource(Context->SourceList, sources[i]))
+        if(!LookupSource(Context->SourceMap, sources[i]))
         {
             alSetError(Context, AL_INVALID_NAME);
             goto done;
@@ -1446,7 +1434,7 @@ AL_API ALvoid AL_APIENTRY alSourceStopv(ALsizei n, const ALuint *sources)
     // Check all the Sources are valid
     for(i = 0;i < n;i++)
     {
-        if(!VerifySource(Context->SourceList, sources[i]))
+        if(!LookupSource(Context->SourceMap, sources[i]))
         {
             alSetError(Context, AL_INVALID_NAME);
             goto done;
@@ -1491,7 +1479,7 @@ AL_API ALvoid AL_APIENTRY alSourceRewindv(ALsizei n, const ALuint *sources)
     // Check all the Sources are valid
     for(i = 0;i < n;i++)
     {
-        if(!VerifySource(Context->SourceList, sources[i]))
+        if(!LookupSource(Context->SourceMap, sources[i]))
         {
             alSetError(Context, AL_INVALID_NAME);
             goto done;
@@ -1540,7 +1528,7 @@ AL_API ALvoid AL_APIENTRY alSourceQueueBuffers(ALuint source, ALsizei n, const A
     // Check that all buffers are valid or zero and that the source is valid
 
     // Check that this is a valid source
-    if((Source=VerifySource(Context->SourceList, source)) == NULL)
+    if((Source=LookupSource(Context->SourceMap, source)) == NULL)
     {
         alSetError(Context, AL_INVALID_NAME);
         goto done;
@@ -1579,7 +1567,7 @@ AL_API ALvoid AL_APIENTRY alSourceQueueBuffers(ALuint source, ALsizei n, const A
         if(!buffers[i])
             continue;
 
-        if((buffer=VerifyBuffer(device->BufferList, buffers[i])) == NULL)
+        if((buffer=LookupBuffer(device->BufferMap, buffers[i])) == NULL)
         {
             alSetError(Context, AL_INVALID_NAME);
             goto done;
@@ -1668,7 +1656,7 @@ AL_API ALvoid AL_APIENTRY alSourceUnqueueBuffers( ALuint source, ALsizei n, ALui
     Context = GetContextSuspended();
     if(!Context) return;
 
-    if((Source=VerifySource(Context->SourceList, source)) == NULL)
+    if((Source=LookupSource(Context->SourceMap, source)) == NULL)
     {
         alSetError(Context, AL_INVALID_NAME);
         goto done;
@@ -2080,12 +2068,12 @@ static ALint GetByteOffset(ALsource *Source)
 
 ALvoid ReleaseALSources(ALCcontext *Context)
 {
+    ALsizei pos;
     ALuint j;
-
-    while(Context->SourceList)
+    for(pos = 0;pos < Context->SourceMap.size;pos++)
     {
-        ALsource *temp = Context->SourceList;
-        Context->SourceList = temp->next;
+        ALsource *temp = Context->SourceMap.array[pos].value;
+        Context->SourceMap.array[pos].value = NULL;
 
         // For each buffer in the source's queue, decrement its reference counter and remove it
         while(temp->queue != NULL)
@@ -2111,5 +2099,4 @@ ALvoid ReleaseALSources(ALCcontext *Context)
         memset(temp, 0, sizeof(ALsource));
         free(temp);
     }
-    Context->SourceCount = 0;
 }
diff --git a/OpenAL32/alState.c b/OpenAL32/alState.c
index 4393d189..953b1a17 100644
--- a/OpenAL32/alState.c
+++ b/OpenAL32/alState.c
@@ -63,11 +63,11 @@ AL_API ALvoid AL_APIENTRY alEnable(ALenum capability)
 
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -96,11 +96,11 @@ AL_API ALvoid AL_APIENTRY alDisable(ALenum capability)
 
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -552,11 +552,11 @@ AL_API ALvoid AL_APIENTRY alDopplerFactor(ALfloat value)
     // relative sources are affected
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -581,11 +581,11 @@ AL_API ALvoid AL_APIENTRY alDopplerVelocity(ALfloat value)
 
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -610,11 +610,11 @@ AL_API ALvoid AL_APIENTRY alSpeedOfSound(ALfloat flSpeedOfSound)
 
     if(updateSources)
     {
-        ALsource *source = pContext->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < pContext->SourceMap.size;pos++)
         {
+            ALsource *source = pContext->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }
 
@@ -649,11 +649,11 @@ AL_API ALvoid AL_APIENTRY alDistanceModel(ALenum value)
 
     if(updateSources)
     {
-        ALsource *source = Context->SourceList;
-        while(source)
+        ALsizei pos;
+        for(pos = 0;pos < Context->SourceMap.size;pos++)
         {
+            ALsource *source = Context->SourceMap.array[pos].value;
             source->NeedsUpdate = AL_TRUE;
-            source = source->next;
         }
     }