Eric Pouech : dbghelp: Added another basic type for storage:
the sparse array.
Alexandre Julliard
julliard at wine.codeweavers.com
Tue Jun 20 05:23:29 CDT 2006
Module: wine
Branch: refs/heads/master
Commit: ad02173d210fcf341d00543b797358f8c07cb1cc
URL: http://source.winehq.org/git/?p=wine.git;a=commit;h=ad02173d210fcf341d00543b797358f8c07cb1cc
Author: Eric Pouech <eric.pouech at wanadoo.fr>
Date: Sun Jun 18 21:31:10 2006 +0200
dbghelp: Added another basic type for storage: the sparse array.
---
dlls/dbghelp/dbghelp_private.h | 11 +++++
dlls/dbghelp/storage.c | 85 ++++++++++++++++++++++++++++++++++++++++
2 files changed, 96 insertions(+), 0 deletions(-)
diff --git a/dlls/dbghelp/dbghelp_private.h b/dlls/dbghelp/dbghelp_private.h
index ef7916e..d10b120 100644
--- a/dlls/dbghelp/dbghelp_private.h
+++ b/dlls/dbghelp/dbghelp_private.h
@@ -63,6 +63,17 @@ void* vector_add(struct vector* v, st
void* vector_iter_up(const struct vector* v, void* elt);
void* vector_iter_down(const struct vector* v, void* elt);
+struct sparse_array
+{
+ struct vector key2index;
+ struct vector elements;
+};
+
+void sparse_array_init(struct sparse_array* sa, unsigned elt_sz, unsigned bucket_sz);
+void* sparse_array_find(const struct sparse_array* sa, unsigned long idx);
+void* sparse_array_add(struct sparse_array* sa, unsigned long key, struct pool* pool);
+unsigned sparse_array_length(const struct sparse_array* sa);
+
struct hash_table_elt
{
const char* name;
diff --git a/dlls/dbghelp/storage.c b/dlls/dbghelp/storage.c
index 77c7f2d..3aef566 100644
--- a/dlls/dbghelp/storage.c
+++ b/dlls/dbghelp/storage.c
@@ -225,6 +225,91 @@ void* vector_iter_down(const struct vect
return vector_at(v, pos - 1);
}
+/* We construct the sparse array as two vectors (of equal size)
+ * The first vector (key2index) is the lookup table between the key and
+ * an index in the second vector (elements)
+ * When inserting an element, it's always appended in second vector (and
+ * never moved in memory later on), only the first vector is reordered
+ */
+struct key2index
+{
+ unsigned long key;
+ unsigned index;
+};
+
+void sparse_array_init(struct sparse_array* sa, unsigned elt_sz, unsigned bucket_sz)
+{
+ vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
+ vector_init(&sa->elements, elt_sz, bucket_sz);
+}
+
+/******************************************************************
+ * spare_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)
+{
+ struct key2index* pk2i;
+
+ /* FIXME: should use bsearch here */
+ for (*idx = 0; *idx < sa->elements.num_elts; (*idx)++)
+ {
+ pk2i = vector_at(&sa->key2index, *idx);
+ if (pk2i && pk2i->key >= key) return pk2i;
+ }
+ return NULL;
+}
+
+void* sparse_array_find(const struct sparse_array* sa, unsigned long key)
+{
+ unsigned idx;
+ struct key2index* pk2i;
+
+ if ((pk2i = spare_array_lookup(sa, key, &idx)) && pk2i->key == key)
+ return vector_at(&sa->elements, pk2i->index);
+ return NULL;
+}
+
+void* sparse_array_add(struct sparse_array* sa, unsigned long key,
+ struct pool* pool)
+{
+ unsigned idx, i;
+ struct key2index* pk2i;
+ struct key2index* to;
+
+ pk2i = spare_array_lookup(sa, key, &idx);
+ if (pk2i && pk2i->key == key)
+ {
+ FIXME("re adding an existing key\n");
+ return NULL;
+ }
+ to = vector_add(&sa->key2index, pool);
+ if (pk2i)
+ {
+ /* we need to shift vector's content... */
+ /* let's do it brute force... (FIXME) */
+ assert(sa->key2index.num_elts >= 2);
+ for (i = sa->key2index.num_elts - 1; i > idx; i--)
+ {
+ pk2i = vector_at(&sa->key2index, i - 1);
+ *to = *pk2i;
+ to = pk2i;
+ }
+ }
+
+ to->key = key;
+ to->index = sa->elements.num_elts;
+
+ return vector_add(&sa->elements, pool);
+}
+
+unsigned sparse_array_length(const struct sparse_array* sa)
+{
+ return sa->elements.num_elts;
+}
+
unsigned hash_table_hash(const char* name, unsigned num_buckets)
{
unsigned hash = 0;
More information about the wine-cvs
mailing list