🚀 go-pugleaf

In article <4jibmd$8b5@solutions.solon.com> <Ed.L.Karrels@zippo.com> writes:
>... I have a few that _were_ asked of me [recently]....  Then, he
>asks, "OK, you've correctly told me that some operations are more
>efficient for doubly linked lists than for singly linked lists,
>but doubly linked lists use the extra memory of a pointer at each node.
>How can we get all the efficiency of a doubly linked list, but use
>only as much memory as a singly linked list, assuming the full significance
>of the pointers is required?

>This one, I heard about once on this newsgroup.  Store the bitwise XOR
>of the addresses of the next and previous nodes in each node.

It is probably worth pointing out that, while this trick works
quite often, it is ultimately not portable and should generally be
avoided.  (Your first problem is finding an integral type long
enough to hold a pointer on every implementation.  On some, there
may not be any such type, and you might even have to resort to an
array of `unsigned char'!)

Indeed, if space is *that* tight, you may be better off using an
array of elements, doing the linking with array indices.  That is,
instead of:

	struct elem {
		struct elem *forw, *back;
		...
	};

	void init_queue(struct elem *headp) {
		headp->forw = headp->back = headp;
	}

	/* insert element `e' after element `after' */
	void insert(struct elem *e, struct elem *after) {
		e->forw = after->forw;
		e->back = after;
		after->forw = e;
		e->forw->back = e;
	}

you might have as your initial transformation:

	struct elem {
		unsigned int forw, back;
		...
	};

	struct elem space[MAX_ELEM];
	#define qptoix(qp) ((qp) - &space[0])
	#define ixtoqp(ix) (&space[ix])

	void init_queue(struct elem *headp) {
		headp->forw = headp->back = qptoix(headp);
	}

	/* insert element `e' after element `after' */
	void insert(struct elem *e, struct elem *after) {
		e->forw = after->forw;
		e->back = qptoix(after);
		after->forw = qptoix(e);
		ixtoqp(e->forw)->back = qptoix(e);
	}

Now two indices *can* be xor'd portably, and the result uses the
same number of bits as the original values.  If the array size is
65536 or smaller, an index can be stored in an unsigned short.  On
a machine with 64-bit pointers, this could save 14 bytes per element.
(Of course, we might wonder why a machine with 64-bit pointers was
so tight on space in the first place. :-) )
-- 
In-Real-Life: Chris Torek, Berkeley Software Design Inc
El Cerrito, CA	Domain:	torek@bsdi.com	+1 510 234 3167