Errata [entries|reading|network|archive]
simont

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Fri 2011-03-18 13:33
Errata

Ahem. In yesterday's post about iterating over a circularly linked list, I made a mistake. The construction I exhibited, because it completely skips any test at the start of the loop, will crash if the list is empty and hence its head pointer is NULL.

Fortunately, this is fixable by putting an additional test in the switch statement:

    switch ((elephant = head) == NULL)
while (elephant = elephant->next, elephant != head)
case 0:

Then if the head pointer is NULL, the switch's input value will be 1, so it won't execute anything in its body at all.

However, I now also realise that there's a better answer in the first place. One commenter yesterday observed (and I had also thought myself) that the problem would be easy if only you could declare an extra flag variable and use it to suppress the first loop test. You can't, under the constraints of C90 syntax, because there's nowhere to put the declaration that doesn't cause further syntactic problems. But actually, I just realised, you don't need an extra variable at all – all you need is an extra value for the loop variable you've already got, and we already have a good special value for pointer variables in the form of NULL. So you can just do this:

    for (elephant = NULL;
elephant ? elephant != head : (elephant = head) != NULL;
elephant = elephant->next)

So if elephant is NULL on entry to the loop test clause, that's the signal that it's the very first iteration, and we reassign elephant to the loop head pointer (and terminate if even that is NULL). Otherwise, it's a non-initial test, and we do the obvious thing of checking whether we've arrived back at head.

This is a cleaner solution than the switch-based one, because it doesn't interfere with case statements inside the user-provided loop body. It's far less exciting, but there we go.

[xpost |http://simont.livejournal.com/231512.html]

LinkReply
[personal profile] gerald_duckFri 2011-03-18 14:26
(Surely "erratum", since you're only making one correction? (And an improvement.) Except that if you now correct it, you'll have made a second correction so "erratum" will be wrong. You clearly need to make, and correct, a third error to avoid a paradox.)

OK. Yesterday, I was too busy boggling at this kind of stuff still being done in C rather than C++ to look at the nitty gritty. Now that I see in more detail what you're up to…

What precise structure for a cyclic list did you have in mind? When I implement a cyclic list, I tend to include the head as well as all the elements in the cycle. This may involve some careful casting, but it tends to make other things easier:
typedef struct Link_str { struct Link_str *next; } Link;

for (elephant = head->next; elephant!=head; elephant = elephant->next) {
    ...
}

In practice, my cyclic lists are invariably doubly-linked. In that circumstance, including the head in the cycle is especially valuable: it avoids a special case when unlinking the first or last element from the list.
Link Reply to this | Thread
[personal profile] simontFri 2011-03-18 14:34
Right, so in your cyclic lists the "list head" is a special list node that has the same data type as all the other nodes but doesn't contain useful payload data? No, I was thinking of the simpler case in which all nodes in the list are real nodes containing real payload, and head is not a node but just a pointer.

I don't think your approach would even have occurred to me, and it certainly wasn't the version used by the actual list of elephants I encountered in the incident that gave rise to this entire thought process. The whole point of them using a cyclic list was that they wanted to be able to go round and round the list very efficiently, so they made advancing to the next (real) element a trivial operation requiring no test. But if a dummy list-head node appears at some point in the list, that advantage is lost, because now advancing to the next element looks something like
    elephant = elephant->next;
    if (elephant == head)
        elephant = elephant->next;
which is no more convenient than doing the obvious thing with a linear list
    elephant = elephant->next;
    if (!elephant)
        elephant = head;
Link Reply to this | Parent | Thread
[personal profile] gerald_duckFri 2011-03-18 14:49
Mmm. The doubly-linked cyclic list model is almost canonical for implementing a list that supports bidirectional traversal with arbitrary insertions and removals (there's a sneakier version where one instead stores in each node the difference between the addresses of its previous and next nodes — this saves a word in each node, but complicates updates). There, treating the head/tail as the next element after the last one and the previous element before the first one gives considerable orthogonality and symmetry benefits, making the code simpler and more efficient. A nicety particularly relevant is that the empty list ceases to be a special case for anything. The objective is emphatically not to allow one to iterate through the list's head/tail in some kind of wrap-around.

The data structure you're looking at seems much more specialised and peculiar; I'm left wondering what its purpose is, and what operations it's expected to permit, with what complexity order. Particularly, any kind of insertion or removal is fiddly, but if the structure is essentially static, why not just use contiguous memory with modular arithmetic?
Link Reply to this | Parent | Thread
[personal profile] simontFri 2011-03-18 14:57
Oh, I don't think we're talking about complexity order. We're right down in the realm of cycle-shaving here, making the constant-time operations happen in smaller or larger constant amounts of time.
Link Reply to this | Parent | Thread
[personal profile] gerald_duckFri 2011-03-18 19:55
If you're down to cycle-shaving, surely your for loop spells disaster? That the list is cyclic is not so intrinsic that the optimiser can spot it and the null check in elephant ? elephant != head : (elephant = head) != NULL will have to be performed each time round the loop.
Link Reply to this | Parent | Thread
[identity profile] cartesiandaemon.livejournal.comSat 2011-03-19 15:42
I know what you mean, but once I got my head round the conversation, Simon's description made sense to me: if you want to traverse the circle more often than you want to do anything which involves treating the head=null case specially, then the circular implementation without distinguished elements is conceptually simpler, and gives you the freedom to write extremely optimised assembly later, at any point it's needed, even if in the meantime you only have a simple loop.
Link Reply to this | Parent
[identity profile] cartesiandaemon.livejournal.comSat 2011-03-19 15:31
Surely "erratum", since you're only making one correction?

Well, not any more, is it? :)

Alternatively, perhaps "errata" has come to act as a mass noun when referring to corrections which are measured in effectively continuous units like paragraphs, rather than traditional lists? :)
Link Reply to this | Parent
[identity profile] cartesiandaemon.livejournal.comSat 2011-03-19 15:38
Ah! I was trying something similar, but couldn't quite get it to work. Using NULL as a flag on the first iteration was the key I hadn't thought of.

(I also interpreted the structure of your list slightly wrongly, but it didn't make any difference to my result, I don't think.)
Link Reply to this
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]