Re: LinkList implementation

[Michael Hwang <michael.a.hwang@gmail.com>]

Sorry, I made a typo. The second code snippet is from newlinklist(),
not newlinknode(), as I wrote.

Michael Hwang

On Sat, Feb 27, 2010 at 5:33 PM, Michael Hwang
<michael.a.hwang@gmail.com> wrote:
> In the process of writing a new builtin, I discovered an oddity of
> zsh's implementation of LinkList, which is a doubly linked list.
>
> LinkList alist = newlinklist();
> LinkNode node;
> for (node = lastnode(alist); node; decnode(alist)) {
>     ((SomeStructPointer) getdata(node))->someField;
> }
>
> Since no nodes have been added to the LinkList, one would expect the
> body of the loop to not run at all. However, it does, and crashes
> because attempting to access someField dereferences a null pointer. I
> think this is due to this line in [z]newlinknode():
>
> list->list.last = &list->node;
>
> I'm not exactly sure why LinkLists are set up this way; I assume it's
> a tricky way to allow [z]insertlinknode() to be used in the pushnode()
> macro. However, this makes the lastnode() macro return non-null on an
> empty LinkList. Walking backwards along a LinkList is only done once
> in the entirety of zsh (the decnode() macro is only used once), which
> is why I think no one has run into this bug before. I'm hoping someone
> who has a better understanding of LinkLists can fix this.
>
> Michael Hwang
>