ano@blake.acs.washington.edu (John Michael Ano) (08/01/89)
What is the best way to generate and maintain a linked list or B-tree in memory using Windows' memory management scheme? I'm working with relatively small structures (elements < 50) and they have a fairly long life-span. So I'm torn between allocating space in either the global or local data segment. For now I've decided that the structures are small enough to sit in the local DS, and now I'm wondering what the best way to allocate memory is. Is it wiser to allocate one big block and do lots of pointer arithmetic to maintain the list, or should I allocate one small block for each element and use the handles generated by LocalAlloc() to get pointers (with LocalLock()) to adjacent nodes? The drawback with the second method is that I have to lock and unlock each node to traverse the list. It seems awkward, but Petzold mentions that the GlobalLock and GlobalUnlock functions are fairly fast, and I assume the same applies to the local versions even though he says nothing about them. The allocated blocks are all allocated as LM_MOVEABLE so that Windows can move the blocks when memory gets scarce. How have other people dealt with data structure management under Windows? John Ano Dept. Psychology UW
hdccorp@nwnexus.WA.COM (hDC Computer Corp. ) (08/01/89)
ano@blake.acs.washington.edu (John Michael Ano) writes: >What is the best way to generate and maintain a linked list or B-tree in >memory using Windows' memory management scheme? .... >The drawback with the second method >is that I have to lock and unlock each node to traverse the list. >John Ano >Dept. Psychology >UW Use the local heap, and use **p to dereference a handle. A local heap handle is a pointer to a pointer - not true of a global handle. This saves a lot of locks and unlocks, especially in things like list traversals. You have to be wary of aliasing, however, for example if you have: (**p).x = foo ((**p).x); then your compiler may decide to optimize by calculating **p only once, and saving it in a register across the call to foo(). If foo() does any LocalAlloc() calls (or calls anyone that does) then the saved value of **p will be invalid upon return, and you will end up writing into random memory. To avoid this, turn off aliasing or lock p first in these cases. The local memory manager is pretty quick and pretty solid. It is not bulletproof, however, and in particular there is a heap-trashing bug in LocalReAlloc(). Somewhere (but not right in front of me) I have a simple Windows program that executes a simple sequence of three local memory manager calls (including a ReAlloc) which dies with a "Local Heap is NOT Busy" RIP and requires a cold reboot. I spent most of a day once tracing through LocalReAlloc() and actually think I found the problem - it seems to be a design (rather than coding) error. When an object is freed, a 4 byte special object is placed in its space (seems to be a pointer to prev free and next free). This means that LocalAlloc() ALWAYS allocates at least 4 bytes, even if you ask for less. But LocalReAlloc() does no such checking. Therefore if you allocate a local object, ReAlloc it to less than 4 bytes, and then cause another local object to be allocated (or moved) directly after the first object, the heap will get corrupted when the first object is freed. To work around this, be sure that you never ReAlloc to less than 4 bytes. At hDC we actually use a macro to ensure this. Brian Conte hDC Computer Corporation -- hDC Computer Corporation hdccorp@nwnexus.wa.com
brent@well.UUCP (Brent Southard) (08/02/89)
In article <3033@blake.acs.washington.edu> ano@blake.acs.washington.edu (John Michael Ano) writes: >........... Is it wiser to allocate one big block and do lots of pointer >arithmetic to maintain the list, or should I allocate one small block for >each element and use the handles generated by LocalAlloc() to get pointers >(with LocalLock()) to adjacent nodes? I know you've heard this before, but it can't be stressed enough: Keep memory objects unlocked. This is not as big a deal in the local heap as it is in global memory, but it is proper. You may want to consider using global memory from the start in case your memory needs increase (the way they always do). >The drawback with the second method >is that I have to lock and unlock each node to traverse the list. It seems >awkward, but Petzold mentions that the GlobalLock and GlobalUnlock functions >are fairly fast, and I assume the same applies to the local versions even >though he says nothing about them. Yes, the lock/unlock functions are pretty quick. However, you may find the real drawback is the meomory overhead Windows associates with allocated memory blocks. I believe there is something like a 16-byte block associated with each global handle (though I could be way off!). >The allocated blocks are all allocated as LM_MOVEABLE so that Windows can move >the blocks when memory gets scarce. How have other people dealt with data >structure management under Windows? Yes. Isn't it fun? Let's hope 3.0 eases things a bit... brent -- brent southard (313) 656-8349 | oh mona mona ImageTech Corp (313) 362-3141 | you can close your eyes | i've got a twelve gauge surprise usenet: ...!well!brent | waiting for you -- James Taylor
kyle@cpsc.ucalgary.ca (David Kyle) (08/03/89)
We've just gotten our debugging version of Windows up and running
(we're using symdeb). Problem is, the data segments keep moving
around in memory, making it kinda hard to set breakpoints in the
code :-) Can anyone help?? We've tried setting up the .def file
so that the CODE segments are FIXED but that doesn't seem to work.
thanks in advance
david kylebturner@hpcvlx.HP.COM (Bill Turner) (08/11/89)
/ hpcvlx:comp.windows.ms / kyle@cpsc.ucalgary.ca (David Kyle) / 4:22 pm Aug 2, 1989 /
We've just gotten our debugging version of Windows up and running
(we're using symdeb). Problem is, the data segments keep moving
around in memory, making it kinda hard to set breakpoints in the
code :-) Can anyone help?? We've tried setting up the .def file
so that the CODE segments are FIXED but that doesn't seem to work.
thanks in advance
david kyle
----------
The Windows-aware versions of symdeb and CodeView understand this and can
set breakpoints in moving segments.
--Bill Turner (bturner@hp-pcd.hp.com)
HP Corvallis Information Systems