Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!decwrl!adobe!hawley
From: hawley@adobe.COM (Steve Hawley)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Linked Lists: Handles or Pointers?
Message-ID: <10349@adobe.UUCP>
Date: 25 Jan 91 18:09:55 GMT
References: <1991Jan23.002212.7648@umiami.ir.miami.edu> <Mbbb8a_00Uh_I4wpkg@andrew.cmu.edu> <.664719435@rw8.urc.tue.nl>
Reply-To: hawley@adobe.UUCP (Steve Hawley)
Organization: Adobe Systems Incorporated, Mountain View
Lines: 115

In article <.664719435@rw8.urc.tue.nl> rcbaab@urc.tue.nl writes:
>It's not that difficult to do but please do not use calls like MoveHHi() and
>HLock() and HUnlock(). They have given me lot's of problems and so I don't
>use them anymore...

Ooh - bad advice.  This means that you have to double dereference the handle
to your data structure every time you use it in conjunction with a Toolbox
call that may move memory.  That is going to slow you down a whole lot.

See, the cool thing about linked lists is that the data in the links can be
accessed relatively quickly on most processors because of offset addressing
modes.  This means that something like


register thing *p;

	p->foo = 0;

will compile to something like:

	clr.w xx(a2)  /* where xx is the offset of foo */
or, if you don't get the register:

	move.l p,a0
	clr.w xx(a0)

if you have
register thing **p;

	(**p).foo = 0;

you'll  get this:

	move.l (a2),a0
	clr.w xx(a0)

So, best case, you're still going to be as bad as the WORST case for simple
pointers.

So ideally, you'd want to do this:

	register thing *p;
	thing **h;

	p = *h;

	p->foo = 0; /* etc etc */

So this gets you the best of both worlds: moveable memory and fast access.
Being an intrepid programmer, you decide that you do the following:

typedef struct thing {
	short count, frobnotz, fibblebean;
	struct thing **next;
} thing *thingptr, **thinghandle;

thinghandle
MakeThingList()
{
	thinghandle h, head;
	register thingptr p;
	Boolean notdone = false;

	
	head = h = (thinghandle)Newhandle((long)sizeof(thing));
	p = *h;
	p->count = -1; /* signal the head */
	while (notdone) {
		p->frobnotz = FinkNottle();
		p->fibblebean = FeldWrent();
		notdone = AmIdone();
		if (notdone) {
			p->next = (thinghandle)NewHandle((long)sizeof(thing));
			h = p->next;
			p = *h;
		/* Here's the trouble.  At this point, p is a stale pointer.
		 * h could have moved during NewHandle(), so p may or may not
		 * actually point to a valid data structure.  This is an
		 * easy mistake to make, and may go undetected FOR A LONG
		 * TIME.
		 * This can be solved by:
		 * 1) Keeping h locked until we're done with the handle.
		 * 2) HLocking h before any call that may move memory, and
		 *    unlocking it later
		 * 3) reassigning p after every call that may move memory
		 */
		}
	}
	return(head);
}

Solution 1 has a trade-off: it is possible that your handle is causing heap
fragmentation that prevents an allocation from happening.  In other words,
there may be a situation where there is enough memory to complete a task, but
it is inaccessible because your handle is in the way.  The good news about
this method is that is the least prone to human error of the three, and
probably the most efficient in terms of cycles.

Solution 2 and 3 will work, but are tedious and prone to much more insidious
problems.  Suppose you're not responsible for maintaining FinkNottle(), and
your boss goes to the person who is and says, "Gee, FinkNottle() is really
slow.  Since you can't speed it up, why not put up a window that has a picture
of a guy tapping his foot."  Oh no!  That means that FinkNottle() may move
memory as well.  What if FinkNottle() itself doen't move memory, but the
function Nitfol() that gets called by WinkleBlat() that gets called by
FeldSpar() that gets called by FinkNottle() does.  You see the problem.

Program defensively.

Steve Hawley
hawley@adobe.com
-- 
"Did you know that a cow was *MURDERED* to make that jacket?"
"Yes.    I didn't think there were any witnesses, so I guess I'll have to kill
 you too." -Jake Johansen