Eric Pouech : dbghelp: Sparse array speed up.
Alexandre Julliard
julliard at wine.codeweavers.com
Mon Dec 11 07:44:53 CST 2006
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");
More information about the wine-cvs
mailing list