2011/5/8 Dylan Smith dylan.ah.smith@gmail.com:
On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni matteo.mystral@gmail.com wrote:
2011/5/6 Dylan Smith dylan.ah.smith@gmail.com:
+struct vertex_attrib_duplication {
- DWORD attrib;
- DWORD vertex_index;
- struct vertex_attrib_duplication *ptr;
+};
...
- struct vertex_attrib_duplication **heads = NULL; /* head of
list for each vertex */
You probably want to use Wine lists (from include/wine/list.h) instead of your own implementation.
I only wanted a singly linked list. The back links would be unused, but would waste memory and update operations. The linked list also gets invalidated by sorting, so the ptr field is actually also used to store the original position in the array for performing a stable sort. I don't think using include/wine/list.h would make the code clearer, since it would be like trying to abstract the implementation details, when those details are relevant to the implementation (see the answer to the next question for an example).
It is an ongoing effort (almost complete I think) to replace custom list implementations with the generic one through the Wine codebase. I don't think this case is so special to require a custom list. I don't have a strong opinion here, but, e.g., I don't find adding one or two fields to the structure a big drawback.
- heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices *
sizeof(*heads) + max_entries * sizeof(*duplications));
- duplications = (struct vertex_attrib_duplication *)(heads +
This->numvertices);
I'm not sure why you are usually sticking together many arrays in a single allocation. Economizing on the number of HeapAllocs is not a great reason IMHO.
Reducing memory allocations and keeping locality of memory references seemed like a good idea, but in this case it actually affects the behaviour of the sort. The pointer values are used in vertex_attrib_compare as a secondary value, which largely affects the result since many vertices share the same attribute value. Pointers into the heads array are used to keep the first use of each vertex in the original order of the vertices, and duplications of those vertices must be sorted using a stable sort, so their original position in the array are compared where the attribute value is the same.
I was referring to allocating "heads" and "duplications" from the same call, which, as far as I can see, is not required. Regarding the sorting requirements, those can also be addressed by adding another index field to the structure.