Use separate arrays for UIntMap keys and values

8 files changed, 87 insertions, 58 deletions

diff --git a/Alc/ALc.c b/Alc/ALc.c
index ca73bd57..83cd59f5 100644
--- a/Alc/ALc.c
+++ b/Alc/ALc.c
@@ -1580,7 +1580,7 @@ void ALCcontext_ProcessUpdates(ALCcontext *context)
         V0(device->Backend,lock)();
         for(pos = 0;pos < context->SourceMap.size;pos++)
         {
-            ALsource *Source = context->SourceMap.array[pos].value;
+            ALsource *Source = context->SourceMap.values[pos];
             ALenum new_state;
 
             if((Source->state == AL_PLAYING || Source->state == AL_PAUSED) &&
@@ -2064,7 +2064,7 @@ static ALCenum UpdateDeviceParams(ALCdevice *device, const ALCint *attrList)
         LockUIntMapRead(&context->EffectSlotMap);
         for(pos = 0;pos < context->EffectSlotMap.size;pos++)
         {
-            ALeffectslot *slot = context->EffectSlotMap.array[pos].value;
+            ALeffectslot *slot = context->EffectSlotMap.values[pos];
             ALeffectState *state = slot->Effect.State;
 
             state->OutBuffer = device->Dry.Buffer;
@@ -2084,7 +2084,7 @@ static ALCenum UpdateDeviceParams(ALCdevice *device, const ALCint *attrList)
         LockUIntMapRead(&context->SourceMap);
         for(pos = 0;pos < context->SourceMap.size;pos++)
         {
-            ALsource *source = context->SourceMap.array[pos].value;
+            ALsource *source = context->SourceMap.values[pos];
             ALuint s = device->NumAuxSends;
             while(s < MAX_SENDS)
             {
diff --git a/OpenAL32/alAuxEffectSlot.c b/OpenAL32/alAuxEffectSlot.c
index b0fd3385..bbaf0668 100644
--- a/OpenAL32/alAuxEffectSlot.c
+++ b/OpenAL32/alAuxEffectSlot.c
@@ -660,8 +660,8 @@ ALvoid ReleaseALAuxiliaryEffectSlots(ALCcontext *Context)
     ALsizei pos;
     for(pos = 0;pos < Context->EffectSlotMap.size;pos++)
     {
-        ALeffectslot *temp = Context->EffectSlotMap.array[pos].value;
-        Context->EffectSlotMap.array[pos].value = NULL;
+        ALeffectslot *temp = Context->EffectSlotMap.values[pos];
+        Context->EffectSlotMap.values[pos] = NULL;
 
         DeinitEffectSlot(temp);
 
diff --git a/OpenAL32/alBuffer.c b/OpenAL32/alBuffer.c
index 193ab44f..c52924a9 100644
--- a/OpenAL32/alBuffer.c
+++ b/OpenAL32/alBuffer.c
@@ -1402,8 +1402,8 @@ ALvoid ReleaseALBuffers(ALCdevice *device)
     ALsizei i;
     for(i = 0;i < device->BufferMap.size;i++)
     {
-        ALbuffer *temp = device->BufferMap.array[i].value;
-        device->BufferMap.array[i].value = NULL;
+        ALbuffer *temp = device->BufferMap.values[i];
+        device->BufferMap.values[i] = NULL;
 
         al_free(temp->data);
 
diff --git a/OpenAL32/alEffect.c b/OpenAL32/alEffect.c
index 5a036091..1057f3c1 100644
--- a/OpenAL32/alEffect.c
+++ b/OpenAL32/alEffect.c
@@ -375,8 +375,8 @@ ALvoid ReleaseALEffects(ALCdevice *device)
     ALsizei i;
     for(i = 0;i < device->EffectMap.size;i++)
     {
-        ALeffect *temp = device->EffectMap.array[i].value;
-        device->EffectMap.array[i].value = NULL;
+        ALeffect *temp = device->EffectMap.values[i];
+        device->EffectMap.values[i] = NULL;
 
         // Release effect structure
         FreeThunkEntry(temp->id);
diff --git a/OpenAL32/alFilter.c b/OpenAL32/alFilter.c
index 7be3e339..7b96263a 100644
--- a/OpenAL32/alFilter.c
+++ b/OpenAL32/alFilter.c
@@ -636,8 +636,8 @@ ALvoid ReleaseALFilters(ALCdevice *device)
     ALsizei i;
     for(i = 0;i < device->FilterMap.size;i++)
     {
-        ALfilter *temp = device->FilterMap.array[i].value;
-        device->FilterMap.array[i].value = NULL;
+        ALfilter *temp = device->FilterMap.values[i];
+        device->FilterMap.values[i] = NULL;
 
         // Release filter structure
         FreeThunkEntry(temp->id);
diff --git a/OpenAL32/alSource.c b/OpenAL32/alSource.c
index e79f0fc3..7d34f368 100644
--- a/OpenAL32/alSource.c
+++ b/OpenAL32/alSource.c
@@ -3373,8 +3373,8 @@ ALvoid ReleaseALSources(ALCcontext *Context)
     ALsizei pos;
     for(pos = 0;pos < Context->SourceMap.size;pos++)
     {
-        ALsource *temp = Context->SourceMap.array[pos].value;
-        Context->SourceMap.array[pos].value = NULL;
+        ALsource *temp = Context->SourceMap.values[pos];
+        Context->SourceMap.values[pos] = NULL;
 
         DeinitSource(temp);
 
diff --git a/common/uintmap.c b/common/uintmap.c
index 041f46c1..d3b51923 100644
--- a/common/uintmap.c
+++ b/common/uintmap.c
@@ -17,7 +17,8 @@ extern inline void UnlockUIntMapWrite(UIntMap *map);
 
 void InitUIntMap(UIntMap *map, ALsizei limit)
 {
-    map->array = NULL;
+    map->keys = NULL;
+    map->values = NULL;
     map->size = 0;
     map->capacity = 0;
     map->limit = limit;
@@ -27,8 +28,9 @@ void InitUIntMap(UIntMap *map, ALsizei limit)
 void ResetUIntMap(UIntMap *map)
 {
     WriteLock(&map->lock);
-    al_free(map->array);
-    map->array = NULL;
+    al_free(map->keys);
+    map->keys = NULL;
+    map->values = NULL;
     map->size = 0;
     map->capacity = 0;
     WriteUnlock(&map->lock);
@@ -46,17 +48,17 @@ ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
         while(low < high)
         {
             ALsizei mid = low + (high-low)/2;
-            if(map->array[mid].key < key)
+            if(map->keys[mid] < key)
                 low = mid + 1;
             else
                 high = mid;
         }
-        if(map->array[low].key < key)
+        if(map->keys[low] < key)
             low++;
         pos = low;
     }
 
-    if(pos == map->size || map->array[pos].key != key)
+    if(pos == map->size || map->keys[pos] != key)
     {
         if(map->size == map->limit)
         {
@@ -66,34 +68,53 @@ ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
 
         if(map->size == map->capacity)
         {
-            ALvoid *temp = NULL;
-            ALsizei newsize;
-
-            newsize = (map->capacity ? (map->capacity<<1) : 4);
-            if(map->limit > 0 && newsize > map->limit)
-                newsize = map->limit;
-            if(newsize > map->capacity)
-                temp = al_malloc(16, newsize * sizeof(map->array[0]));
-            if(!temp)
+            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)
             {
                 WriteUnlock(&map->lock);
                 return AL_OUT_OF_MEMORY;
             }
+            values = (ALvoid**)((ALbyte*)keys + keylen);
 
-            if(map->array)
-                memcpy(temp, map->array, map->size*sizeof(map->array[0]));
-            al_free(map->array);
-            map->array = temp;
-            map->capacity = newsize;
+            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->array[pos+1], &map->array[pos],
-                    (map->size-pos)*sizeof(map->array[0]));
+        {
+            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->array[pos].key = key;
-    map->array[pos].value = value;
+    map->keys[pos] = key;
+    map->values[pos] = value;
     WriteUnlock(&map->lock);
 
     return AL_NO_ERROR;
@@ -110,17 +131,21 @@ ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
         while(low < high)
         {
             ALsizei mid = low + (high-low)/2;
-            if(map->array[mid].key < key)
+            if(map->keys[mid] < key)
                 low = mid + 1;
             else
                 high = mid;
         }
-        if(map->array[low].key == key)
+        if(map->keys[low] == key)
         {
-            ptr = map->array[low].value;
+            ptr = map->values[low];
             if(low < map->size-1)
-                memmove(&map->array[low], &map->array[low+1],
-                        (map->size-1-low)*sizeof(map->array[0]));
+            {
+                memmove(&map->keys[low], &map->keys[low+1],
+                        (map->size-1-low)*sizeof(map->keys[0]));
+                memmove(&map->values[low], &map->values[low+1],
+                        (map->size-1-low)*sizeof(map->values[0]));
+            }
             map->size--;
         }
     }
@@ -137,17 +162,21 @@ ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
         while(low < high)
         {
             ALsizei mid = low + (high-low)/2;
-            if(map->array[mid].key < key)
+            if(map->keys[mid] < key)
                 low = mid + 1;
             else
                 high = mid;
         }
-        if(map->array[low].key == key)
+        if(map->keys[low] == key)
         {
-            ALvoid *ptr = map->array[low].value;
+            ALvoid *ptr = map->values[low];
             if(low < map->size-1)
-                memmove(&map->array[low], &map->array[low+1],
-                        (map->size-1-low)*sizeof(map->array[0]));
+            {
+                memmove(&map->keys[low], &map->keys[low+1],
+                        (map->size-1-low)*sizeof(map->keys[0]));
+                memmove(&map->values[low], &map->values[low+1],
+                        (map->size-1-low)*sizeof(map->values[0]));
+            }
             map->size--;
             return ptr;
         }
@@ -166,13 +195,13 @@ ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
         while(low < high)
         {
             ALsizei mid = low + (high-low)/2;
-            if(map->array[mid].key < key)
+            if(map->keys[mid] < key)
                 low = mid + 1;
             else
                 high = mid;
         }
-        if(map->array[low].key == key)
-            ptr = map->array[low].value;
+        if(map->keys[low] == key)
+            ptr = map->values[low];
     }
     ReadUnlock(&map->lock);
     return ptr;
@@ -187,13 +216,13 @@ ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
         while(low < high)
         {
             ALsizei mid = low + (high-low)/2;
-            if(map->array[mid].key < key)
+            if(map->keys[mid] < key)
                 low = mid + 1;
             else
                 high = mid;
         }
-        if(map->array[low].key == key)
-            return map->array[low].value;
+        if(map->keys[low] == key)
+            return map->values[low];
     }
     return NULL;
 }
diff --git a/include/uintmap.h b/include/uintmap.h
index e7c3f93d..acb2749a 100644
--- a/include/uintmap.h
+++ b/include/uintmap.h
@@ -9,16 +9,16 @@ extern "C" {
 #endif
 
 typedef struct UIntMap {
-    struct {
-        ALuint key;
-        ALvoid *value;
-    } *array;
+    ALuint *keys;
+    /* Shares memory with keys. */
+    ALvoid **values;
+
     ALsizei size;
     ALsizei capacity;
     ALsizei limit;
     RWLock lock;
 } UIntMap;
-#define UINTMAP_STATIC_INITIALIZE_N(_n) { NULL, 0, 0, (_n), RWLOCK_STATIC_INITIALIZE }
+#define UINTMAP_STATIC_INITIALIZE_N(_n) { NULL, NULL, 0, 0, (_n), RWLOCK_STATIC_INITIALIZE }
 #define UINTMAP_STATIC_INITIALIZE UINTMAP_STATIC_INITIALIZE_N(~0)
 
 void InitUIntMap(UIntMap *map, ALsizei limit);