Use separate arrays for UIntMap keys and values

1 files changed, 69 insertions, 40 deletions

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;
 }