On Thu, Jun 30, 2011 at 4:10 PM, Henri Verbeet hverbeet@gmail.com wrote:
On 30 June 2011 14:49, Michael Mc Donnell michael@mcdonnell.dk wrote:
In init_edge_face_map I initialize an array of edge_face structs, and in find_adjacent_face I do a linear search through that array. I would like to replace the array with a hash table, so that the search time becomes constant. I've found a standard list (wine/list.h) and red-black tree implementation (wine/rbtree.h), but not a standard hash table implementation. Is there a standard hash table implementation, should I roll my own or find an LGPL'ed one?
I'm not sure if a hash table would be faster and how much, but an easy way to make the lookup cheaper would be to store the edge -> face map as a list for each vertex.
So e.g. if you have these faces: f0: v0, v2, v1 f1: v1, v4, v3 f2: v1, v2, v4 f3: v2, v5, v4
You'd build these lists: v0: {v2:f0} v1: {v0:f0}, {v4:f1}, {v2:f2} v2: {v1:f0}, {v4:f2}, {v5:f3} v3: {v1:f1} v4: {v3:f1}, {v1:f2}, {v2:f3} v5: {v4:f3}
It's then mostly trivial to determine adjacency. This assumes most vertices are only part of a handful of edges, but I don't think that's unreasonable in practice.
Thanks for your suggestion. I think you're right that it is safe to assume that most vertices will only be a part of a few edges. I'll implement that for now.
We did have a hash table inside wined3d at some point, I suppose you could also try resurrecting that from git history.
I'll stick with your suggestion as it seems easier to implement :-)
Btw I just searched source.winehq.org for hash_table and found several hits in different dlls. I think it would be nice if they could all use the same implementation like list.h and rbtree.h. That way it could also later be used for other parts of wine. Should I add it to http://wiki.winehq.org/JanitorialProjects?