Path: utzoo!attcan!uunet!olivea!decwrl!ogicse!pdxgate!pdxgate.cs.pdx.edu!cfry
From: cfry@jove.cs.pdx.edu (Chall Fry)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Linked Lists: Handles or Pointers?
Message-ID: <CFRY.91Jan28035944@jove.cs.pdx.edu>
Date: 28 Jan 91 11:59:44 GMT
References: <1991Jan23.002212.7648@umiami.ir.miami.edu>
Sender: news@pdxgate.UUCP
Organization: Portland State University, CS Dept.
Lines: 70
In-reply-to: gross@umiami.ir.miami.edu's message of 23 Jan 91 05:22:11 GMT

In article <1991Jan23.002212.7648@umiami.ir.miami.edu> gross@umiami.ir.miami.edu (Mondo) writes:

   If you want to create a linked list, do you have to:

       a) Use a handle to the head node only and use pointers 
              for the rest of the list (Problem we see: the Memory
              Manager will compact the heap and make all those ptrs invalid.)

                       or

       b) Use linked handles for every node in the list.

(** Naming conventions for this post **)
struct link {
   some_type data;
   link * or ** next;
} * or ** head, * or ** p;

So far there's been all sorts of good advice in this thread. No one yet,
however, has advocated my personal favorite memory allocation algorithm:

    char *ptr = Random () * Random (); /* Look Ma, no handles! */

(I'd include *lots* of smilies, but I can't draw to save my life)

Really, I can think of four decent data structures for managing a linklist
on the Mac. Your choice a) seems to be flawed, at least in your wording.
Having a handle to the head node and pointers for the body of the list
seems pretty pointless. Either you mean for head to point to a handle sized
to one link only, which makes the head relocatable but the rest of the list
will be created with NewPtr, and a bunch of small nonrelocatable blocks
being created and deleted all the time is the sort of thing that turns
heaps into abysmal messes. BTW, if you're using malloc () to allocate your
pointers, you're using NewPtr (Think C, alloc.c). In this case, having the
head relocatable does very little to improve heap usage.  The other
interpretation is that you want head to be a handle large enough to hold
the entire list, and use your own memory management scheme to add and
delete links using space within the handle. This will work, but if you use
pointers in your link.next fields, you can't ever move the block around,
and again, you might as well make it a pointer to begin with as make it a
handle and keep it locked all the time. 

The other choice you mention, using handles for every link, would be good
for a list without many links, or if you were making a list of structures
which were already handles (region and Picture handles come to mind).
However, though I haven't run any tests, I'd think the Memory Manager might
get bogged down if it had compact a large (5-10 thousand?) number of small
blocks very often. 

Allocating a large block of memory with NewPtr and subletting using your
own routines really isn't a bad method, particularly if your use SetPtrSize
in your allocation function to grow and shrink your memory block as your
list grows and shrinks (Don't use on every call.) However, if you allocated
p as a large relocatable NewHandle block, and made your link.next fields
integer offsets into p, you could get some of both worlds. I believe
the 68030 at least has an addressing mode which allows double indirection
with displacement in one instruction. (Memory Indirect [pre][post]indexed
mode--will Think and MPW generate this mode?) Or, you can lock the handle
and derefence it, which should execute searches pretty fast. Either way,
your handle can be unlocked when not in use, and heap compaction won't
require any pointer updating. It'll pack efficiently (everything's
relocatable), and quickly (there's only one block). Only real problem is
that you need your own link allocation code (and it can't call malloc or
NewPtr). 

Not that I still don't prefer my Random () method, for the sheer adventure
of it. 

--Chall Fry         cfry@jove.cs.pdx.edu
"Chall, 'nifty' I can deal with, but 'goshums' is just too much." -Anastasia