<div class="gmail_quote">On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni <span dir="ltr"><<a href="mailto:matteo.mystral@gmail.com">matteo.mystral@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
2011/5/6 Dylan Smith <<a href="mailto:dylan.ah.smith@gmail.com">dylan.ah.smith@gmail.com</a>>:<br>
<div class="im">> +struct vertex_attrib_duplication {<br>
> + DWORD attrib;<br>
> + DWORD vertex_index;<br>
> + struct vertex_attrib_duplication *ptr;<br>
> +};<br>
</div>...<br>
<div class="im">> + struct vertex_attrib_duplication **heads = NULL; /* head of list for each vertex */<br>
<br>
</div>You probably want to use Wine lists (from include/wine/list.h) instead<br>
of your own implementation.<br>
<div class="im"><br></div></blockquote><div>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).</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">
> + heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*heads) + max_entries * sizeof(*duplications));<br>
</div><div class="im">> + duplications = (struct vertex_attrib_duplication *)(heads + This->numvertices);<br>
<br>
</div>I'm not sure why you are usually sticking together many arrays in a<br>
single allocation. Economizing on the number of HeapAllocs is not a<br>
great reason IMHO.<br>
</blockquote></div><div><br></div><div>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.</div>