Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> writes:
> Anyway, just because this is actually something I've noticed a lot
> of people do wrong, I actually do tend to think that when you
> traverse a singly-linked list and remove entries, you should *never*
> traverse the list itself, you should only ever traverse the "pointer
> to the pointer".
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);
}
}
}
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
