Module: wine Branch: master Commit: 9a41a4e98429295601a8e9c3e35c2f814f6497f0 URL: http://source.winehq.org/git/wine.git/?a=commit;h=9a41a4e98429295601a8e9c3e3...
Author: Eric Pouech eric.pouech@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");