From 62eb7be845762692491a0c2a228de64f26bbaab2 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 1 Aug 2010 23:22:46 -0300 Subject: [PATCH 1/1] Do a binary search in findPool() Since findPool() is sorted, a binary search is more appropriate than a linear search. --- rt/gc/cdgc/gc.d | 38 ++++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-) 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; } -- 2.43.0