Re: Propsoal: a lua dialect without nil

[<jgiors@...>]

> -------- Original Message --------
> Date: Wed, 16 Feb 2011 08:07:39 +0100
> From: Axel Kittenberger <axkibe@gmail.com>
> Subject: Re: Propsoal: a lua dialect without nil
> To: Lua mailing list <lua-l@lists.lua.org>
> Message-ID:
> 	<AANLkTinLWoCn+jHaKAE9wHj5w65kEfcjuSh-Y=9H0OAq@mail.gmail.com>
> Content-Type: text/plain; charset=windows-1252
> 
<...snip...>
>
> ...I don't see how a static typed
> language could work without null pointers. How would it cap linked
> lists? It would need some sort of singleton as cap marker, not there
> marker, etc. which would eventually boil down to the same as if it
> would be 0.
> 
<...snip...>

Circular lists accomplish that without NULL and without a singleton. The
"head" of the list acts as the "anchor" for the list (and also as a
sentinel). The doubly-linked circular list is especially nice because
you can just copy pointers around without special cases for NULL, which
avoids branch-prediction problems (and also makes implementation less
error-prone).

The "tricky" parts are: making sure every node is initialized properly,
and to remember *not* to test for NULL when iterating.

I've used them frequently, especially when I want to add a linked list
to a library without creating a dependency to a more general list
implementation.

Unfortunately, it's hard to get people on board with circular lists
because most programmers are used to checking for NULL, and the circular
list throws them for a loop.

A brief search didn't turn up (what I felt was) a nice example, so I
whipped up a sample file. It builds and runs (at least in MS VC++).

//BEGIN SAMPLE
//
//Circular doubly linked list sample. NOTE: NOT THOROUGHLY TESTED.
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

typedef struct CLIST
{
    struct CLIST *pPrev;
    struct CLIST *pNext;
    int x;
} CLIST;

void clist_init(CLIST *p, int x)
{
    p->pPrev = p->pNext = p;
    p->x = x;
}

void clist_link(CLIST *p, CLIST *pPredecessor)
{
    p->pPrev = pPredecessor;
    p->pNext = pPredecessor->pNext;
    pPredecessor->pNext->pPrev = p;
    pPredecessor->pNext = p;
}

void clist_unlink(CLIST *p)
{
    p->pPrev->pNext = p->pNext;
    p->pNext->pPrev = p->pPrev;
    p->pPrev = p->pNext = p;
}

static CLIST anchor;
static CLIST node1;
static CLIST node2;
static CLIST node3;

int main(int argc, char *argv[])
{
    CLIST *p;

    clist_init(&anchor,42);
    clist_init(&node1,1);
    clist_init(&node2,2);
    clist_init(&node3,3);

    clist_link(&node1, &anchor);
    clist_link(&node2, &node1);
    clist_link(&node3, &node2);

    printf("Initial node list:\n"); //note: does not include "anchor"
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)
        printf("\t%d\n",p->x);

    printf("\nRemove node 2 and the result is:\n");
    clist_unlink(&node2);
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)
        printf("\t%d\n",p->x);

    printf("\nRe-link node 2 after node 3 to get:\n");
    clist_link(&node2, &node3);
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)
        printf("\t%d\n",p->x);

    printf("\nDone. Press any key...");
    getch();

    return EXIT_SUCCESS;
}
//
//END SAMPLE


John Giors
Independent Programmer
Three Eyes Software
jgiors@ThreeEyesSoftware.com
http://ThreeEyesSoftware.com