From 1652dc02abe309b7f7eafca7d9a4f4f81744bc55 Mon Sep 17 00:00:00 2001
From: Chris Robinson <chris.kcat@gmail.com>
Date: Mon, 10 May 2010 11:40:57 -0700
Subject: [PATCH] Look for the map insertion point using a binary search

---
 Alc/ALc.c | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

diff --git a/Alc/ALc.c b/Alc/ALc.c
index 85d39872..56a08e9e 100644
--- a/Alc/ALc.c
+++ b/Alc/ALc.c
@@ -654,12 +654,23 @@ void ResetUIntMap(UIntMap *map)
 
 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
 {
-    ALsizei pos;
+    ALsizei pos = 0;
 
-    for(pos = 0;pos < map->size;pos++)
+    if(map->size > 0)
     {
-        if(map->array[pos].key >= key)
-            break;
+        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)
+            low++;
+        pos = low;
     }
 
     if(pos == map->size || map->array[pos].key != key)
-- 
2.11.4.GIT