PATCH: linked lists

[Peter Stephenson <pws@csr.com>]

This does the rather strange of operation of trying to make the code
more rational.  It adds and removing some library functions for linked
lists.  (There's no point having both a function that returns "node"
when found and a function that returns "1" when found.)

Index: Src/linklist.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/linklist.c,v
retrieving revision 1.6
diff -u -r1.6 linklist.c
--- Src/linklist.c	7 Mar 2006 22:05:44 -0000	1.6
+++ Src/linklist.c	27 Jun 2007 13:39:34 -0000
@@ -273,28 +273,84 @@
     return list;
 }
 
+/*
+ * Return the node whose data is the pointer "dat", else NULL.
+ * Can be used as a boolean test.
+ */
+
 /**/
-mod_export int
-listcontains(LinkList list, void *dat)
+mod_export LinkNode
+linknodebydatum(LinkList list, void *dat)
 {
     LinkNode node;
 
     for (node = firstnode(list); node; incnode(node))
 	if (getdata(node) == dat)
-	    return 1;
+	    return node;
 
-    return 0;
+    return NULL;
 }
 
+/*
+ * Return the node whose data matches the string "dat", else NULL.
+ */
+
 /**/
 mod_export LinkNode
-linknodebydatum(LinkList list, void *dat)
+linknodebystring(LinkList list, char *dat)
 {
     LinkNode node;
 
     for (node = firstnode(list); node; incnode(node))
-	if (getdata(node) == dat)
+	if (!strcmp((char *)getdata(node), dat))
 	    return node;
 
     return NULL;
 }
+
+/*
+ * Convert a linked list whose data elements are strings to
+ * an array.  Memory is off the heap and the elements of the
+ * array are the same elements as the linked list data if copy is
+ * 0, else copied onto the heap.
+ */
+
+/**/
+mod_export char **
+hlinklist2array(LinkList list, int copy)
+{
+    int l = countlinknodes(list);
+    char **ret = (char **) zhalloc((l + 1) * sizeof(char *)), **p;
+    LinkNode n;
+
+    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
+	*p = (char *) getdata(n);
+	if (copy)
+	    *p = dupstring(*p);
+    }
+    *p = NULL;
+
+    return ret;
+}
+
+/*
+ * Convert a linked list whose data elements are strings to
+ * an array.  The result is a permanently allocated, freearrayable
+ * array.
+ */
+
+/**/
+mod_export char **
+zlinklist2array(LinkList list)
+{
+    int l = countlinknodes(list);
+    char **ret = (char **) zalloc((l + 1) * sizeof(char *)), **p;
+    LinkNode n;
+
+    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
+	*p = ztrdup((char *) getdata(n));
+    }
+    *p = NULL;
+
+    return ret;
+}
Index: Src/loop.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/loop.c,v
retrieving revision 1.20
diff -u -r1.20 loop.c
--- Src/loop.c	19 Jan 2007 21:36:03 -0000	1.20
+++ Src/loop.c	27 Jun 2007 13:39:34 -0000
@@ -311,20 +311,14 @@
 selectlist(LinkList l, size_t start)
 {
     size_t longest = 1, fct, fw = 0, colsz, t0, t1, ct;
-    LinkNode n;
     char **arr, **ap;
 
     trashzleptr();
-    ct = countlinknodes(l);
-    ap = arr = (char **) zhalloc((countlinknodes(l) + 1) * sizeof(char **));
-
-    for (n = (LinkNode) firstnode(l); n; incnode(n))
-	*ap++ = (char *)getdata(n);
-    *ap = NULL;
+    arr = hlinklist2array(l, 0);
     for (ap = arr; *ap; ap++)
 	if (strlen(*ap) > longest)
 	    longest = strlen(*ap);
-    t0 = ct;
+    t0 = ct = ap - arr;
     longest++;
     while (t0)
 	t0 /= 10, longest++;
Index: Src/module.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/module.c,v
retrieving revision 1.31
diff -u -r1.31 module.c
--- Src/module.c	20 Jun 2007 20:59:17 -0000	1.31
+++ Src/module.c	27 Jun 2007 13:39:35 -0000
@@ -2698,9 +2698,7 @@
 	}
 	if(!m->deps) {
 	    if (!node) {
-		for (node = firstnode(modules); node; incnode(node))
-		    if (m == (Module) getdata(node))
-			break;
+		node = linknodebydatum(modules, m);
 		if (!node)
 		    return 1;
 	    }
Index: Src/parse.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/parse.c,v
retrieving revision 1.66
diff -u -r1.66 parse.c
--- Src/parse.c	29 May 2007 09:27:43 -0000	1.66
+++ Src/parse.c	27 Jun 2007 13:39:36 -0000
@@ -2933,7 +2933,7 @@
 	    }
 	    for (i = 0; i < shfunctab->hsize; i++)
 		for (hn = shfunctab->nodes[i]; hn; hn = hn->next)
-		    if (!listcontains(lnames, hn->nam) &&
+		    if (!linknodebydatum(lnames, hn->nam) &&
 			pattry(pprog, hn->nam) &&
 			cur_add_func(nam, (Shfunc) hn, lnames, progs,
 				     &hlen, &tlen, what)) {
Index: Src/subst.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/subst.c,v
retrieving revision 1.78
diff -u -r1.78 subst.c
--- Src/subst.c	18 Jun 2007 13:25:06 -0000	1.78
+++ Src/subst.c	27 Jun 2007 13:39:37 -0000
@@ -2973,14 +2973,7 @@
 	else if (!nextnode(firstnode(list)))
 	    val = getdata(firstnode(list));
 	else {
-	    char **ap;
-	    LinkNode node;
-
-	    aval = ap = (char **) zhalloc((countlinknodes(list) + 1) *
-					  sizeof(char *));
-	    for (node = firstnode(list); node; incnode(node))
-		*ap++ = (char *) getdata(node);
-	    *ap = NULL;
+	    aval = hlinklist2array(list, 0);
 	    isarr = 2;
 	    l->list.flags |= LF_ARRAY;
 	}
Index: Src/Modules/parameter.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Modules/parameter.c,v
retrieving revision 1.42
diff -u -r1.42 parameter.c
--- Src/Modules/parameter.c	18 Jun 2007 13:25:09 -0000	1.42
+++ Src/Modules/parameter.c	27 Jun 2007 13:39:41 -0000
@@ -793,19 +793,6 @@
 }
 
 /**/
-static int
-findmodnode(LinkList l, char *nam)
-{
-    LinkNode node;
-
-    for (node = firstnode(l); node; incnode(node))
-	if (!strcmp(nam, (char *) getdata(node)))
-	    return 1;
-
-    return 0;
-}
-
-/**/
 static HashNode
 getpmmodule(UNUSED(HashTable ht), char *name)
 {
@@ -889,14 +876,14 @@
     for (i = 0; i < builtintab->hsize; i++)
 	for (hn = builtintab->nodes[i]; hn; hn = hn->next) {
 	    if (!(((Builtin) hn)->node.flags & BINF_ADDED) &&
-		!findmodnode(done, ((Builtin) hn)->optstr)) {
+		!linknodebystring(done, ((Builtin) hn)->optstr)) {
 		pm.node.nam = ((Builtin) hn)->optstr;
 		addlinknode(done, pm.node.nam);
 		func(&pm.node, flags);
 	    }
 	}
     for (p = condtab; p; p = p->next)
-	if (p->module && !findmodnode(done, p->module)) {
+	if (p->module && !linknodebystring(done, p->module)) {
 	    pm.node.nam = p->module;
 	    addlinknode(done, pm.node.nam);
 	    func(&pm.node, flags);
@@ -904,7 +891,7 @@
     for (i = 0; i < realparamtab->hsize; i++)
 	for (hn = realparamtab->nodes[i]; hn; hn = hn->next) {
 	    if ((((Param) hn)->node.flags & PM_AUTOLOAD) &&
-		!findmodnode(done, ((Param) hn)->u.str)) {
+		!linknodebystring(done, ((Param) hn)->u.str)) {
 		pm.node.nam = ((Param) hn)->u.str;
 		addlinknode(done, pm.node.nam);
 		func(&pm.node, flags);
@@ -934,15 +921,7 @@
 static char **
 dirsgetfn(UNUSED(Param pm))
 {
-    int l = countlinknodes(dirstack);
-    char **ret = (char **) zhalloc((l + 1) * sizeof(char *)), **p;
-    LinkNode n;
-
-    for (n = firstnode(dirstack), p = ret; n; incnode(n), p++)
-	*p = dupstring((char *) getdata(n));
-    *p = NULL;
-
-    return ret;
+    return hlinklist2array(dirstack, 1);
 }
 
 /* Functions for the history special parameter. */
@@ -1012,7 +991,7 @@
 static char **
 histwgetfn(UNUSED(Param pm))
 {
-    char **ret, **p, *h, *e, sav;
+    char *h, *e, sav;
     LinkList l = newlinklist(), ll;
     LinkNode n;
     int i = addhistnum(curhist, -1, HIST_FOREIGN), iw;
@@ -1033,13 +1012,8 @@
 	}
 	he = up_histent(he);
     }
-    ret = (char **) zhalloc((countlinknodes(l) + 1) * sizeof(char *));
-
-    for (p = ret, n = firstnode(l); n; incnode(n), p++)
-	*p = (char *) getdata(n);
-    *p = NULL;
 
-    return ret;
+    return hlinklist2array(l, 0);
 }
 
 /* Functions for the jobtexts special parameter. */
Index: Src/Zle/compcore.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Zle/compcore.c,v
retrieving revision 1.90
diff -u -r1.90 compcore.c
--- Src/Zle/compcore.c	21 Jan 2007 22:47:41 -0000	1.90
+++ Src/Zle/compcore.c	27 Jun 2007 13:39:42 -0000
@@ -644,7 +644,7 @@
 	if (compredirs)
 	    freearray(compredirs);
         if (rdstrs)
-            compredirs = bld_list_array(rdstrs);
+            compredirs = zlinklist2array(rdstrs);
         else
             compredirs = (char **) zshcalloc(sizeof(char *));
 
@@ -1852,30 +1852,13 @@
     return 0;
 }
 
-/* This builds an array from a list of strings. */
-
-/**/
-mod_export char **
-bld_list_array(LinkList l)
-{
-    char **a, **p;
-    LinkNode n;
-
-    a = (char **) zalloc((countlinknodes(l) + 1) * sizeof(char *));
-    for (p = a, n = firstnode(l); n; incnode(n))
-	*p++ = ztrdup((char *) getdata(n));
-    *p = NULL;
-
-    return a;
-}
-
 /* This stores the strings from the list in an array. */
 
 /**/
 mod_export void
 set_list_array(char *name, LinkList l)
 {
-    setaparam(name, bld_list_array(l));
+    setaparam(name, zlinklist2array(l));
 }
 
 /* Get the words from a variable or a (list of words). */
Index: Src/Zle/computil.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Zle/computil.c,v
retrieving revision 1.103
diff -u -r1.103 computil.c
--- Src/Zle/computil.c	28 May 2007 22:57:42 -0000	1.103
+++ Src/Zle/computil.c	27 Jun 2007 13:39:45 -0000
@@ -3406,16 +3406,9 @@
         /* Again, as for comparguments.  This returns the values and their
          * arguments as an array which will be stored in val_args in _values. */
 	if (cv_laststate.vals) {
-	    char **ret, **p;
-	    LinkNode n;
-
-	    ret = (char **) zalloc((countlinknodes(cv_laststate.vals) + 1) *
-				   sizeof(char *));
-
-	    for (n = firstnode(cv_laststate.vals), p = ret; n; incnode(n), p++)
-		*p = ztrdup((char *) getdata(n));
-	    *p = NULL;
+	    char **ret;
 
+	    ret = zlinklist2array(cv_laststate.vals);
 	    sethparam(args[1], ret);
 
 	    return 0;
@@ -3738,7 +3731,6 @@
 	if (!strcmp(*args, "-m")) {
 	    char *s, *p, *q, *c, **all = comptags[lasttaglevel]->all;
 	    LinkList list = newlinklist();
-	    LinkNode node;
 	    int num = 0;
 	    Ctset set;
 
@@ -3833,16 +3825,11 @@
 		    }
 		}
 		if (num) {
-		    char **a;
 		    Ctset l;
 
 		    set = (Ctset) zalloc(sizeof(*set));
 
-		    a = set->tags = (char **) zalloc((num + 1) * sizeof(char *));
-		    for (node = firstnode(list); node; incnode(node))
-			*a++ = ztrdup((char *) getdata(node));
-
-		    *a = NULL;
+		    set->tags = zlinklist2array(list);
 		    set->next = NULL;
 		    set->ptr = NULL;
 		    set->tag = NULL;

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


To access the latest news from CSR copy this link into a web browser:  http://www.csr.com/email_sig.php

To get further information regarding CSR, please visit our Investor Relations page at http://ir.csr.com/csr/about/overview