LinkList implementation

LinkList implementation

[Michael Hwang]

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

Re: LinkList implementation

[Michael Hwang]

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
>

Re: LinkList implementation

[Andrey Borzenkov]

[-- Attachment #1: Type: Text/Plain, Size: 1022 bytes --]

On Sunday 28 of February 2010 01:33:24 Michael Hwang 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;
> }
> 
BTW decnode applies to node, not list - it should be decnode(node)

> Since no nodes have been added to the LinkList, one would expect the
> body of the loop to not run at all.

Well, you have to accept that and use another termination condition, 
like e.g. in zle_hist.c:isearch_newpos():

        for (node = lastnode(matchlist);
             node != (LinkNode)matchlist; decnode(node)) {

For the sake of purity this actually should be
             node != &matchlist->node

The games linklist.c plays are really daunting ... but to change it now 
you have to carefully go through all of code to adjust snippets like 
above.

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: LinkList implementation

[Michael Hwang]

On Sun, Feb 28, 2010 at 4:06 AM, Andrey Borzenkov <arvidjaar@gmail.com> wrote:
> On Sunday 28 of February 2010 01:33:24 Michael Hwang 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;
>> }
>>
> BTW decnode applies to node, not list - it should be decnode(node)

Right, that's another typo on my part.

>> Since no nodes have been added to the LinkList, one would expect the
>> body of the loop to not run at all.
>
> Well, you have to accept that and use another termination condition,
> like e.g. in zle_hist.c:isearch_newpos():
>
>        for (node = lastnode(matchlist);
>             node != (LinkNode)matchlist; decnode(node)) {
>
> For the sake of purity this actually should be
>             node != &matchlist->node
>
> The games linklist.c plays are really daunting ... but to change it now
> you have to carefully go through all of code to adjust snippets like
> above.

I solved my problem by simply reversing the direction I added on to
the LinkList, and therefore the direction I walked through it. I'll
see if I can't make the LinkList implementation simpler and more
intuitive. These "gotcha!"'s are a bit annoying.

Michael Hwang

Re: LinkList implementation

[Peter Stephenson]

Michael Hwang wrote:
> I solved my problem by simply reversing the direction I added on to
> the LinkList, and therefore the direction I walked through it. I'll
> see if I can't make the LinkList implementation simpler and more
> intuitive. These "gotcha!"'s are a bit annoying.

If you're doing *anything* to the linked list code, the first imperative
is documenting what it currently does.  I'm not interested in improving
it until it's clearly written in <your foreground colour> and <your
background colour> what it is that's being improved.

To get on my high horse, in fact the first and last imperative with lots
of the code is better documentation.  I have wasted days of my life
having to puzzle things out.

-- 
Peter Stephenson <pws@csr.com>            Software Engineer
Tel: +44 (0)1223 692070                   Cambridge Silicon Radio Limited
Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, UK



Member of the CSR plc group of companies. CSR plc registered in England and Wales, registered number 4187346, registered office Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, United Kingdom

[PATCH] Added LinkList documentation to linklist.c

[Michael Hwang]

After getting an intimate look at LinkList, I've decided that I don't want to
change it either. But I may as well add some documentation. I hope it's
acceptable to have these ASCII drawings in the source code.

Michael Hwang

---
 Src/linklist.c |   70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 70 insertions(+), 0 deletions(-)

diff --git a/Src/linklist.c b/Src/linklist.c
index b51d881..1e364fb 100644
--- a/Src/linklist.c
+++ b/Src/linklist.c
@@ -30,6 +30,72 @@
 #include "zsh.mdh"
 #include "linklist.pro"
 
+/*
+ * Anatomy of a LinkList
+ *
+ * LinkList with 4 nodes:
+ *
+ * LinkList is a        first   last   flags   (LinkList)
+ * union; see zsh.h     next    prev   dat     (LinkNode)
+ *                    +-------+------+------+
+ *                    |       |      |      | See comment in subst.c
+ *     +------------> |   |   |   |  |      | about LF_ARRAY.
+ *     |              +---|---+---|--+------+
+ *     |                  |       |
+ *     |     +------------+       +--------------+
+ *     |     |                                   |
+ *     |    \|/                                 \|/
+ *     |   +----+      +----+      +----+      +----+
+ *     |   |    |      |    |      |    |      | \/ |  X here is NULL.
+ *     |   |  -------> |  -------> |  -------> | /\ |
+ *     |   |next|      |next|      |next|      |next|
+ *     |   +----+      +----+      +----+      +----+
+ *     |   |    |      |    |      |    |      |    |
+ *     +------  | <-------  | <-------  | <-------  |
+ *         |prev|      |prev|      |prev|      |prev|
+ *         +----+      +----+      +----+      +----+
+ *         |    |      |    |      |    |      |    | Pointers to data,
+ *         |dat |      |dat |      |dat |      |dat | usually char **.
+ *         +----+      +----+      +----+      +----+
+ *        LinkNode    LinkNode    LinkNode    LinkNode
+ *
+ *
+ * Empty LinkList:
+ *                    first   last   flags
+ *                   +------+------+-------+
+ *             +---> | NULL |      |   0   |
+ *             |     |      |   |  |       |
+ *             |     +------+---|--+-------+
+ *             |                |
+ *             +----------------+
+ *
+ * Traversing a LinkList:
+ * Traversing forward through a list uses an iterator-style paradigm.
+ * for (LinkNode node = firstnode(list); node; incnode(node)) {
+ *     // Access/manipulate the node using macros (see zsh.h)
+ * }
+ *
+ * Traversing backwards is the same, with a small caveat.
+ * for (LinkNode node = lastnode(list); node != &list->node; decnode(node)) {
+ *     // The loop condition should be obvious given the above diagrams.
+ * }
+ *
+ * If you're going to be moving back and forth, best to AND both
+ * conditions.
+ *
+ * while (node && node != &list->node) {
+ *     // If both incnode(list) and decnode(list) are used, and it's
+ *     // unknown at which end of the list traversal will stop.
+ * }
+ *
+ * Macros and functions prefixed with 'z' (ie znewlinklist,
+ * zinsertlinknode) use permanent allocation, which you have to free
+ * manually (with freelinklist(), maybe?). Non-z-prefixed
+ * macros/functions allocate from heap, which will be automatically
+ * freed.
+ *
+ */
+
 /* Get an empty linked list header */
 
 /**/
@@ -240,6 +306,8 @@ countlinknodes(LinkList list)
     return ct;
 }
 
+/* Make specified node first, moving preceding nodes to end */
+
 /**/
 mod_export void
 rolllist(LinkList l, LinkNode nd)
@@ -252,6 +320,8 @@ rolllist(LinkList l, LinkNode nd)
     l->list.last->next = 0;
 }
 
+/* Create linklist of specified size. node->dats are not initialized. */
+
 /**/
 mod_export LinkList
 newsizedlist(int size)
-- 
1.6.6.1

Re: [PATCH] Added LinkList documentation to linklist.c

[Peter Stephenson]

On Fri,  5 Mar 2010 22:48:48 -0500
Michael Hwang <michael.a.hwang@gmail.com> wrote:
> After getting an intimate look at LinkList, I've decided that I don't want to
> change it either. But I may as well add some documentation. I hope it's
> acceptable to have these ASCII drawings in the source code.

That's fine, that's a useful aid, thanks.

pws