2011/5/8 Dylan Smith <dylan.ah.sm...@gmail.com>: > On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni <matteo.myst...@gmail.com> > wrote: >> >> 2011/5/6 Dylan Smith <dylan.ah.sm...@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.