tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work

On Wed 20 Nov 2013 at 15:32:20 -0800, Dennis Ferguson wrote:
> If one were starting this from scratch [...]

Ever since I grokked the elegance of Lists in AmigaOS, I've always
wondered why other list implementations do it differently.

A list is double linked, and it has dummy first and last nodes (which
aren't part of the data and consist just of the next and prev pointers).
They are elegantly combined in the list header, which consists of 3

    mlh_Head            which points to the first real node,
    mlh_Tail            which is always NULL
    mlh_TailPred        which points to the last real node.

Each node in the list starts with a ln_Next and a ln_Prev pointer.

When the list is empty,

    mlh_Head            points to mlh_Tail
    mlh_Tail            is always NULL
    mlh_TailPred        points to mlh_Head.

The first dummy node consists of mlh_Head and mlh_Tail, i.e. its ln_Prev
is NULL, and the last dummy node consists of  mlh_Tail and mlh_TailPred,
where its ln_Next is NULL.

This initially confusing situation eliminates all special cases for
node insertion and removal (and traversal isn't made more complicated).

This is more extensively explained in .

___ Olaf 'Rhialto' Seibert  -- The Doctor: No, 'eureka' is Greek for
\X/ rhialto/at/    -- 'this bath is too hot.'

Attachment: pgpPfYq3NI6mm.pgp
Description: PGP signature

Home | Main Index | Thread Index | Old Index