1 files changed, 96 insertions, 58 deletions

diff --git a/common/uintmap.c b/common/uintmap.c
index b7a9a29c..18d52d64 100644
--- a/common/uintmap.c
+++ b/common/uintmap.c
@@ -6,6 +6,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "almalloc.h"
+
 
 extern inline void LockUIntMapRead(UIntMap *map);
 extern inline void UnlockUIntMapRead(UIntMap *map);
@@ -15,9 +17,10 @@ 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->maxsize = 0;
+    map->capacity = 0;
     map->limit = limit;
     RWLockInit(&map->lock);
 }
@@ -25,10 +28,11 @@ void InitUIntMap(UIntMap *map, ALsizei limit)
 void ResetUIntMap(UIntMap *map)
 {
     WriteLock(&map->lock);
-    free(map->array);
-    map->array = NULL;
+    al_free(map->keys);
+    map->keys = NULL;
+    map->values = NULL;
     map->size = 0;
-    map->maxsize = 0;
+    map->capacity = 0;
     WriteUnlock(&map->lock);
 }
 
@@ -39,53 +43,77 @@ ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
     WriteLock(&map->lock);
     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;
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
             else
-                high = mid;
-        }
-        if(map->array[low].key < key)
-            low++;
-        pos = low;
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
     }
 
-    if(pos == map->size || map->array[pos].key != key)
+    if(pos == map->size || map->keys[pos] != key)
     {
-        if(map->size == map->limit)
+        if(map->size >= map->limit)
         {
             WriteUnlock(&map->lock);
             return AL_OUT_OF_MEMORY;
         }
 
-        if(map->size == map->maxsize)
+        if(map->size == map->capacity)
         {
-            ALvoid *temp = NULL;
-            ALsizei newsize;
-
-            newsize = (map->maxsize ? (map->maxsize<<1) : 4);
-            if(newsize >= map->maxsize)
-                temp = realloc(map->array, 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;
             }
-            map->array = temp;
-            map->maxsize = newsize;
+            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->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;
@@ -97,22 +125,29 @@ ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
     WriteLock(&map->lock);
     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;
+        ALsizei pos = 0;
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
             else
-                high = mid;
-        }
-        if(map->array[low].key == key)
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+        if(pos < map->size && map->keys[pos] == key)
         {
-            ptr = map->array[low].value;
-            if(low < map->size-1)
-                memmove(&map->array[low], &map->array[low+1],
-                        (map->size-1-low)*sizeof(map->array[0]));
+            ptr = map->values[pos];
+            if(pos < map->size-1)
+            {
+                memmove(&map->keys[pos], &map->keys[pos+1],
+                        (map->size-1-pos)*sizeof(map->keys[0]));
+                memmove(&map->values[pos], &map->values[pos+1],
+                        (map->size-1-pos)*sizeof(map->values[0]));
+            }
             map->size--;
         }
     }
@@ -126,18 +161,21 @@ ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
     ReadLock(&map->lock);
     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;
+        ALsizei pos = 0;
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
             else
-                high = mid;
-        }
-        if(map->array[low].key == key)
-            ptr = map->array[low].value;
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+        if(pos < map->size && map->keys[pos] == key)
+            ptr = map->values[pos];
     }
     ReadUnlock(&map->lock);
     return ptr;