From: Leandro Lucarella <llucax@gmail.com>
Date: Mon, 2 Aug 2010 02:22:46 +0000 (-0300)
Subject: Do a binary search in findPool()
X-Git-Url: https://git.llucax.com/software/dgc/cdgc.git/commitdiff_plain/62eb7be845762692491a0c2a228de64f26bbaab2?ds=sidebyside;hp=5578146600d4ace17878e3b010aa09efdb202fb4

Do a binary search in findPool()

Since findPool() is sorted, a binary search is more appropriate than
a linear search.
---

diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d
index c008177..1df824c 100644
--- a/rt/gc/cdgc/gc.d
+++ b/rt/gc/cdgc/gc.d
@@ -264,26 +264,28 @@ bool Invariant()
  * Return null if not in a Pool.
  * Assume pools is sorted.
  */
-Pool *findPool(void *p)
+Pool* findPool(void* p)
 {
-    if (p >= gc.min_addr && p < gc.max_addr)
-    {
-        if (gc.pools.length == 1)
-        {
-            return gc.pools[0];
-        }
-
-        for (size_t i = 0; i < gc.pools.length; i++)
-        {
-            Pool* pool = gc.pools[i];
-            if (p < pool.topAddr)
-            {
-                if (pool.baseAddr <= p)
-                    return pool;
-                break;
-            }
-        }
+    if (p < gc.min_addr || p >= gc.max_addr)
+        return null;
+    if (gc.pools.length == 0)
+        return null;
+    if (gc.pools.length == 1)
+        return gc.pools[0];
+    /// The pooltable[] is sorted by address, so do a binary search
+    size_t low = 0;
+    size_t high = gc.pools.length - 1;
+    while (low <= high) {
+        size_t mid = (low + high) / 2;
+        auto pool = gc.pools[mid];
+        if (p < pool.baseAddr)
+            high = mid - 1;
+        else if (p >= pool.topAddr)
+            low = mid + 1;
+        else
+            return pool;
     }
+    // Not found
     return null;
 }