Eric Pouech : dbghelp: Sparse array speed up.

[Alexandre Julliard]

Module: wine
Branch: master
Commit: 9a41a4e98429295601a8e9c3e35c2f814f6497f0
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=9a41a4e98429295601a8e9c3e35c2f814f6497f0

Author: Eric Pouech <eric.pouech at wanadoo.fr>
Date:   Sat Dec  9 14:30:56 2006 +0100

dbghelp: Sparse array speed up.

---

 dlls/dbghelp/storage.c |   51 +++++++++++++++++++++++++++++++++++++++--------
 1 files changed, 42 insertions(+), 9 deletions(-)

diff --git a/dlls/dbghelp/storage.c b/dlls/dbghelp/storage.c
index 3aee97d..2d88d8c 100644
--- a/dlls/dbghelp/storage.c
+++ b/dlls/dbghelp/storage.c
@@ -244,22 +244,55 @@ void sparse_array_init(struct sparse_arr
 }
 
 /******************************************************************
- *		spare_array_lookup
+ *		sparse_array_lookup
  *
  * Returns the first index which key is >= at passed key
  */
-static struct key2index* spare_array_lookup(const struct sparse_array* sa,
-                                            unsigned long key, unsigned* idx)
+static struct key2index* sparse_array_lookup(const struct sparse_array* sa,
+                                             unsigned long key, unsigned* idx)
 {
     struct key2index*   pk2i;
+    unsigned            low, high;
 
-    /* FIXME: should use bsearch here */
-    for (*idx = 0; *idx < sa->elements.num_elts; (*idx)++)
+    if (!sa->elements.num_elts)
     {
+        *idx = 0;
+        return NULL;
+    }
+    high = sa->elements.num_elts;
+    pk2i = vector_at(&sa->key2index, high - 1);
+    if (pk2i->key < key)
+    {
+        *idx = high;
+        return NULL;
+    }
+    if (pk2i->key == key)
+    {
+        *idx = high - 1;
+        return pk2i;
+    }
+    low = 0;
+    pk2i = vector_at(&sa->key2index, low);
+    if (pk2i->key >= key)
+    {
+        *idx = 0;
+        return pk2i;
+    }
+    /* now we have: sa(lowest key) < key < sa(highest key) */
+    while (low < high)
+    {
+        *idx = (low + high) / 2;
         pk2i = vector_at(&sa->key2index, *idx);
-        if (pk2i && pk2i->key >= key) return pk2i;
+        if (pk2i->key > key)            high = *idx;
+        else if (pk2i->key < key)       low = *idx + 1;
+        else                            return pk2i;
     }
-    return NULL;
+    /* binary search could return exact item, we search for highest one
+     * below the key
+     */
+    if (pk2i->key < key)
+        pk2i = vector_at(&sa->key2index, ++(*idx));
+    return pk2i;
 }
 
 void*   sparse_array_find(const struct sparse_array* sa, unsigned long key)
@@ -267,7 +300,7 @@ void*   sparse_array_find(const struct s
     unsigned            idx;
     struct key2index*   pk2i;
 
-    if ((pk2i = spare_array_lookup(sa, key, &idx)) && pk2i->key == key)
+    if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
         return vector_at(&sa->elements, pk2i->index);
     return NULL;
 }
@@ -279,7 +312,7 @@ void*   sparse_array_add(struct sparse_a
     struct key2index*   pk2i;
     struct key2index*   to;
 
-    pk2i = spare_array_lookup(sa, key, &idx);
+    pk2i = sparse_array_lookup(sa, key, &idx);
     if (pk2i && pk2i->key == key)
     {
         FIXME("re adding an existing key\n");