nadkarni@ashok.dec.com (Ashok P. Nadkarni) (11/12/90)
I am porting an application to Windows 3.0 that makes extensive use of linked lists. Storage needs are sufficiently large that I have to use global memory. I know just enough about Windows programming that I realize it is Bad Thing to leave memory locked. However, unlocking means that all the links pointing to the prev/next list elements are garbage every time Windows moves memory around. Is there a solution to this problem? I was hoping to avoid using a different type of 'collection' data structure as that would involve considerable rewriting. Thanks for any answers, /Ashok
spolsky-joel@cs.yale.edu (Joel Spolsky) (11/12/90)
In article <17167@shlump.nac.dec.com> nadkarni@ashok.dec.com (Ashok P. Nadkarni) writes: >I am porting an application to Windows 3.0 that makes extensive use >of linked lists. Storage needs are sufficiently large that I have >to use global memory. I know just enough about Windows programming that >I realize it is Bad Thing to leave memory locked. However, unlocking means >that all the links pointing to the prev/next list elements are garbage >every time Windows moves memory around. Is there a solution to this problem? Here are two possibilities: either keep handles, not pointers in the linked list, and lock them when you need them. However this does make traversing the linked list a bit messy, if you do that a lot, locking and unlocking as you move along. (sadness). The other possibility; if your program is only going to be run on 386's (in enhanced mode), it doesn't hurt to keep everything locked down, because the hardware can still move things about without the far pointers changing. I ported a large system to windows this way; it is enough to replace malloc(x) with GlocalLock(GlobalAlloc(GMEM_MOVEABLE,x)); Joel Spolsky spolsky@cs.yale.edu Silence = Death
johnc@plx.UUCP (John C.) (11/13/90)
In article <17167@shlump.nac.dec.com> nadkarni@ashok.dec.com (Ashok P. Nadkarni) writes: >I am porting an application to Windows 3.0 that makes extensive use >of linked lists. Storage needs are sufficiently large that I have >to use global memory. I know just enough about Windows programming that >I realize it is Bad Thing to leave memory locked. However, unlocking means >that all the links pointing to the prev/next list elements are garbage >every time Windows moves memory around. Is there a solution to this problem? > >/Ashok My application also uses linked lists in Global memory. I found it quite cumbersome to keep the "next" and "previous" pointers unlocked; debugging the lock/unlock logic involved in list traversal was very tedious. Also, you typically don't want to have *many* global objects since Windows imposes a limit on the number of handles. A better approach is to allocate all the list nodes in one variable- length "dynamic array", using array indices for 'next' and 'previous', rather than actual pointers. If the data to be managed is large or variable-length, have the nodes themselves contain handles to the data. Keep the management of the node *data* separate from the Add/Delete Node logic. Of course, typedef the node structure for convenience (call it, say, NODE_T). Use the following variables to describe the array: * a handle, initially zero * nBlocks, the number of blocks allocated, initially zero. The array will be allocated in multiples of 'N' (the number of nodes per block) nodes, to keep from having to GlobalRealloc each time a node is added or deleted. * nNodes, the number of used nodes, initially zero. AddNode resizes the array whenever it needs to expand by another block of N. Initially the array has 0 blocks, so the first AddNode call will GlobalAlloc(N * sizeof(NODE_T)), and increment the node count and block count. When the list grows past N elements, AddNode GlobalRealloc's the array to '2 * N * sizeof(NODE_T)', and increments the block count. If a DeleteNode call shrinks the array below 'N' elements again, you can either GlobalRealloc it back down to 'N' or keep its size at the 'high-water' mark, whatever makes sense for your app. The AddNode logic will vary depending on whether nodes are always added/deleted to the end of the list. If they are not, then you need some way of indicating that a node is available for reuse (for example, the node's data handle could be set to zero). AddNode then has to be smart enough to reuse available "empty" nodes. The algorithm becomes: /* Add a list node to a dynamic array. Returns the array index of the node that was added.*/ int AddNode( ... ) { int nIndex; /* returned */ if (nNodes==N*nBlocks) { /* all alloc'd nodes are used; (re)alloc */ if (nBlocks==0) { /* empty array; alloc first block */ nBlocks++; hArray = GlobalAlloc( N * sizeof(NODE_T) ); } else { /* array already has at least one block; realloc */ nBlocks++; hArray = GlobalRealloc( hArray, nBlocks * N * sizeof(NODE_T)); } nIndex = (nBlocks * (N-1)) /* first node in the new block */ } /* end if 'need to (re)alloc' */ else { /* must be an empty node somewhere, so find it */ nIndex = FindEmptyNode(...); } /* One way or another, we have our new node */ nNodes++; ...logic to initialize the node... return nIndex; } /* end AddNode */ [This is pseudocode and I'm writing it from memory; please forgive any algorithmic errors; the main idea is there...] -- John Ciccarelli Plexus Software, 5200 Great America Pkwy, Suite 200, Santa Clara CA 95054 email: ...sun!plx!johnc, voice: 408-982-4842, fax: 408-727-4864