From: Michael Hwang <michael.a.hwang@gmail.com>
To: zsh-workers@zsh.org
Cc: Michael Hwang <michael.a.hwang@gmail.com>
Subject: [PATCH] Added LinkList documentation to linklist.c
Date: Fri, 5 Mar 2010 22:48:48 -0500 [thread overview]
Message-ID: <1267847328-9284-1-git-send-email-michael.a.hwang@gmail.com> (raw)
In-Reply-To: <201003011812.o21ICUCu026435@news01.csr.com>
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
next prev parent reply other threads:[~2010-03-06 4:16 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-02-27 22:33 LinkList implementation Michael Hwang
2010-02-27 22:45 ` Michael Hwang
2010-02-28 9:06 ` Andrey Borzenkov
2010-03-01 18:00 ` Michael Hwang
2010-03-01 18:12 ` Peter Stephenson
2010-03-06 3:48 ` Michael Hwang [this message]
2010-03-07 21:36 ` [PATCH] Added LinkList documentation to linklist.c Peter Stephenson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1267847328-9284-1-git-send-email-michael.a.hwang@gmail.com \
--to=michael.a.hwang@gmail.com \
--cc=zsh-workers@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).