Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!nwnexus!hdccorp
From: hdccorp@nwnexus.WA.COM (hDC Computer Corp. )
Newsgroups: comp.windows.ms
Subject: Re: Memory Management & Data Structures
Keywords: linked lists, moveable data segments
Message-ID: <147@nwnexus.WA.COM>
Date: 1 Aug 89 00:05:50 GMT
References: <3033@blake.acs.washington.edu>
Distribution: comp.windows.ms
Organization: Northwest Nexus Inc.; Seattle, WA
Lines: 51


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