Am Mittwoch, 9. April 2008 10:54:37 schrieb David Adam:
On 08/04/2008, David Adam <david.adam.cnrs at gmail.com
http://www.winehq.org/mailman/listinfo/wine-patches> wrote:
- This->current = This->current +1;
*>* + HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, This->matrix, (This->current +1) * sizeof(D3DXMATRIX) ); *>* + if ( This->matrix == NULL ) return E_OUTOFMEMORY;
Aside from being a bit suboptimal (doing a realloc on every push), this probably doesn't do what you want. Consider what happens to the size of the array when you do something like push/pop/push/pop/...etc.
It would be better to keep track of the current stack size, and then grow it by a factor (eg. 2 or 1.5) if a push would overflow the current stack. You could also consider shrinking the array again if a pop would make it use less than a certain percentage of the current size (eg. a third).
This would increase the size of the stack exponentially. Would it be better to do this: Take a stack_size_reference (for instance 32 items) When This->current =32, then increase the size of the stack of stack_size_reference (that is 64 items now) Then when This->current is =64, again increase the size of the stack of stack_size_reference (that is 98 items now), and so on....
This would increase the size of the stack linearly instead of exponentially.
You usually grow the memory by a factor of the old size because this reduces the number of needed grows. So growing the stack is an O(log(n)) instead of O(n), which is a huge difference.
The drawback is that you have potentially more wasted memory. I don't know what the theory says to that though. The amount of wasted memory is always smaller than the amount of used memory at least if you double the size and smaller if you grow it by 1/2 of the existing size, ...