pointer to pointer (was: gitk problems: can't unset "idinlist(...)")

Linus Torvalds <torvalds@linux-foundation.org> writes:

When I have doubly-linked lists where there is only forward traversal (the backlink being for convenient deletions without context), I make the backlink a pointer to pointer. This also means that one can remove at the front of the list without needing to know the head separately.

Anyway, here is some really, really ancient code of mine (file date is of 1990 but it's older than that) which sorts linked lists stably without extra storage and makes heavy use of pointer to pointer traversal in both code and interface. There is also a strictly non-recursive variant with the same data flow (except for never making a redundant assignment) and just one instead of two functions which consistently beats good qsort implementations, but this old version is quite more fun to read.

Basically, if head is the pointer to a sorted list of at least n elements, mergesort(&head, n) will sort the first n elements and return a pointer to that link which contains the tail of the list. So if you did not already 0-terminate your list, *mergesort(&head,n)=0; will both sort and terminate your list.

#include "mergesrt.h" int (*mergecompare)(void *p1, void *p2); int mergelink; #define getlink(adr) (*(void**)((char*)(adr)+mergelink))

static void **merge(void **head1, void **tail1, void **tail2, unsigned n1, unsigned n2)
{
	register void *p1 = *head1, *p2 = *tail1;
	for(;;) {
		if ((*mergecompare)(p1, p2) <= 0) {
			p1 = *(head1 = &getlink(*head1 = p1));
			if (--n1 == 0)
				return *head1 = p2, tail2;
		} else {
			p2 = *(head1 = &getlink(*head1 = p2));
			if (--n2 == 0)
				return *tail1 = p2, *head1 = p1, tail1;
		}
	}
}

void **mergesort(void **head, unsigned n)
{
	switch (n) {
	case 0:
		return head;
	case 1:
		return &getlink(*head);
	case 2:
		{
			register void *p1, *p2;

			p2 = getlink(p1 = *head);
			if ((*mergecompare)(p1, p2) <= 0)
				return &getlink(p2);
			getlink(p1) = getlink(*head=p2);
			return &getlink(getlink(p2) = p1);
		}
	default:
		{
			unsigned m;
			void **h2;
			n -= m = n / 2;
			h2 = mergesort(head, n);
			return merge(head,h2,mergesort(h2,m),n,m);
		}
	}
}