Re: GSoC-2011: Implement Missing Mesh Functions in Wine’s D3DX9

Michael Mc Donnell michael at
Thu Jun 30 11:42:08 CDT 2011

On Thu, Jun 30, 2011 at 4:10 PM, Henri Verbeet <hverbeet at> wrote:
> On 30 June 2011 14:49, Michael Mc Donnell <michael at> 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 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

More information about the wine-devel mailing list