PATCH: make zstyle use hash

[Peter Stephenson <pws@xxxxxxx>]

I'm fed up with styles not being listed in alphabetic order.  It's high
time they were stored in a hash rather than a linked list anyway, since
they're widely used.  The old doc for listing styles half implied there
was something magic about the ordering of styles ("listed in the order
zstyle will test them"), but that's only true for patterns; looking up
of style names was always by exact match, it just happened to traverse a
list to find them which is an implementation detail.

I've added some tests to try to assure myself I haven't broken anything.

Index: Src/Modules/zutil.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Modules/zutil.c,v
retrieving revision 1.21
diff -u -r1.21 zutil.c
--- Src/Modules/zutil.c	28 May 2007 22:57:41 -0000	1.21
+++ Src/Modules/zutil.c	8 Jun 2007 13:40:23 -0000
@@ -38,9 +38,8 @@
 /* A pattern and the styles for it. */
 
 struct style {
-    Style next;			/* next in stypat list */
+    struct hashnode node;
     Stypat pats;		/* patterns */
-    char *name;
 };
 
 struct stypat {
@@ -51,13 +50,42 @@
     Eprog eval;			/* eval-on-retrieve? */
     char **vals;
 };
-    
-/* List of styles. */
 
-static Style zstyles;
+/* Hash table of styles and associated functions. */
+
+static HashTable zstyletab;
 
 /* Memory stuff. */
 
+static void
+freestylepatnode(Stypat p)
+{
+    zsfree(p->pat);
+    freepatprog(p->prog);
+    if (p->vals)
+	freearray(p->vals);
+    if (p->eval)
+	freeeprog(p->eval);
+    zfree(p, sizeof(*p));
+}
+
+static void
+freestylenode(HashNode hn)
+{
+    Style s = (Style) hn;
+    Stypat p, pn;
+
+    p = s->pats;
+    while (p) {
+	pn = p->next;
+	freestylepatnode(p);
+	p = pn;
+    }
+
+    zsfree(s->node.nam);
+    zfree(s, sizeof(struct style));
+}
+
 /*
  * Free the information for one of the patterns associated with
  * a style.
@@ -79,60 +107,135 @@
 	    s->pats = p->next;
     }
 
-    zsfree(p->pat);
-    freepatprog(p->prog);
-    if (p->vals)
-	freearray(p->vals);
-    if (p->eval)
-	freeeprog(p->eval);
-    zfree(p, sizeof(*p));
+    freestylepatnode(p);
 
     if (s && !s->pats) {
 	/* No patterns left, free style */
-	if (s == zstyles) {
-	    zstyles = s->next;
-	} else {
-	    Style s2;
-	    for (s2 = zstyles; s2->next != s; s2 = s2->next)
-		;
-	    s2->next = s->next;
-	}
-	zsfree(s->name);
+	zstyletab->removenode(zstyletab, s->node.nam);
+	zsfree(s->node.nam);
 	zfree(s, sizeof(*s));
     }
 }
 
+/* Pattern to match context when printing nodes */
+
+static Patprog zstyle_contprog;
+
+/*
+ * Print a node.  Print flags as shown.
+ */
+enum {
+    ZSLIST_NONE,
+    ZSLIST_BASIC,
+    ZSLIST_SYNTAX,
+};
+
 static void
-freeallstyles(void)
+printstylenode(HashNode hn, int printflags)
 {
-    Style s, sn;
-    Stypat p, pn;
+    Style s = (Style)hn;
+    Stypat p;
+    char **v;
+
+    if (printflags == ZSLIST_BASIC) {
+	quotedzputs(s->node.nam, stdout);
+	putchar('\n');
+    }
 
-    for (s = zstyles; s; s = sn) {
-	sn = s->next;
-	for (p = s->pats; p; p = pn) {
-	    pn = p->next;
-	    freestypat(p, NULL, NULL);
+    for (p = s->pats; p; p = p->next) {
+	if (zstyle_contprog && !pattry(zstyle_contprog, p->pat))
+	    continue;
+	if (printflags == ZSLIST_BASIC)
+	    printf("%s  %s", (p->eval ? "(eval)" : "      "), p->pat);
+	else {
+	    printf("zstyle %s", (p->eval ? "-e " : ""));
+	    quotedzputs(p->pat, stdout);
+	    printf(" %s", s->node.nam);
+	}
+	for (v = p->vals; *v; v++) {
+	    putchar(' ');
+	    quotedzputs(*v, stdout);
 	}
-	zsfree(s->name);
-	zfree(s, sizeof(*s));
+	putchar('\n');
     }
-    zstyles = NULL;
 }
 
-/* Get the style struct for a name. */
+/*
+ * Scan the list for a particular pattern, maybe adding matches to
+ * the link list (heap memory).  Value to be added as
+ * shown in enum
+ */
+static LinkList zstyle_list;
+static char *zstyle_patname;
 
-static Style
-getstyle(char *name)
+enum {
+    ZSPAT_NAME,		/* Add style names for matched pattern to list */
+    ZSPAT_PAT,		/* Add all patterns to list, doesn't use patname */
+    ZSPAT_REMOVE,	/* Remove matched pattern, doesn't use list */
+};
+
+static void
+scanpatstyles(HashNode hn, int spatflags)
 {
-    Style s;
+    Style s = (Style)hn;
+    Stypat p, q;
+    LinkNode n;
+
+    for (q = NULL, p = s->pats; p; q = p, p = p->next) {
+	switch (spatflags) {
+	case ZSPAT_NAME:
+	    if (!strcmp(p->pat, zstyle_patname)) {
+		addlinknode(zstyle_list, s->node.nam);
+		return;
+	    }
+	    break;
+
+	case ZSPAT_PAT:
+	    /* Check pattern isn't already there */
+	    for (n = firstnode(zstyle_list); n; incnode(n))
+		if (!strcmp(p->pat, (char *) getdata(n)))
+		    break;
+	    if (!n)
+		addlinknode(zstyle_list, p->pat);
+	    break;
 
-    for (s = zstyles; s; s = s->next)
-	if (!strcmp(name, s->name)) {
-	    return s;
+	case ZSPAT_REMOVE:
+	    if (!strcmp(p->pat, zstyle_patname)) {
+		freestypat(p, s, q);
+		/*
+		 * May remove link node itself; that's OK
+		 * when scanning but we need to make sure
+		 * we don't look at it any more.
+		 */
+		return;
+	    }
+	    break;
 	}
+    }
+}
 
-    return NULL;
+
+static HashTable
+newzstyletable(int size, char const *name)
+{
+    HashTable ht;
+    ht = newhashtable(size, name, NULL);
+
+    ht->hash        = hasher;
+    ht->emptytable  = emptyhashtable;
+    ht->filltable   = NULL;
+    ht->cmpnodes    = strcmp;
+    ht->addnode     = addhashnode;
+    /* DISABLED is not supported */
+    ht->getnode     = gethashnode2;
+    ht->getnode2    = gethashnode2;
+    ht->removenode  = removehashnode;
+    ht->disablenode = NULL;
+    ht->enablenode  = NULL;
+    ht->freenode    = freestylenode;
+    ht->printnode   = printstylenode;
+
+    return ht;
 }
 
 /* Store a value for a style. */
@@ -226,15 +329,9 @@
 static Style
 addstyle(char *name)
 {
-    Style s;
-
-    s = (Style) zalloc(sizeof(*s));
-    s->next = NULL;
-    s->pats = NULL;
-    s->name = ztrdup(name);
+    Style s = (Style) zshcalloc(sizeof(*s));
 
-    s->next = zstyles;
-    zstyles = s;
+    zstyletab->addnode(zstyletab, ztrdup(name), s);
 
     return s;
 }
@@ -274,11 +371,12 @@
     Style s;
     Stypat p;
 
-    for (s = zstyles; s; s = s->next)
-	if (!strcmp(s->name, style))
-	    for (p = s->pats; p; p = p->next)
-		if (pattry(p->prog, ctxt))
-		    return (p->eval ? evalstyle(p) : p->vals);
+    s = (Style)zstyletab->getnode2(zstyletab, style);
+    if (!s)
+	return NULL;
+    for (p = s->pats; p; p = p->next)
+	if (pattry(p->prog, ctxt))
+	    return (p->eval ? evalstyle(p) : p->vals);
 
     return NULL;
 }
@@ -286,10 +384,10 @@
 static int
 bin_zstyle(char *nam, char **args, UNUSED(Options ops), UNUSED(int func))
 {
-    int min, max, n, add = 0, list = 0, eval = 0;
+    int min, max, n, add = 0, list = ZSLIST_NONE, eval = 0;
 
     if (!args[0])
-	list = 1;
+	list = ZSLIST_BASIC;
     else if (args[0][0] == '-') {
 	char oc;
 
@@ -299,7 +397,7 @@
 		return 1;
 	    }
 	    if (oc == 'L') {
-		list = 2;
+		list = ZSLIST_SYNTAX;
 		args++;
 	    } else if (oc == 'e') {
 		eval = add = 1;
@@ -328,16 +426,13 @@
 	    zwarnnam(nam, "invalid pattern: %s", args[0]);
 	    return 1;
 	}
-	if (!(s = getstyle(args[1])))
+	if (!(s = (Style)zstyletab->getnode2(zstyletab, args[1])))
 	    s = addstyle(args[1]);
 	return setstypat(s, args[0], prog, args + 2, eval);
     }
     if (list) {
 	Style s;
-	Stypat p;
-	char **v;
 	char *context, *stylename;
-	Patprog contprog;
 
 	switch (arrlen(args)) {
 	case 2:
@@ -360,34 +455,23 @@
 	}
 	if (context) {
 	    tokenize(context);
-	    contprog = patcompile(context, PAT_STATIC, NULL);
+	    zstyle_contprog = patcompile(context, PAT_STATIC, NULL);
+
+	    if (!zstyle_contprog)
+		return 1;
 	} else
-	    contprog = NULL;
+	    zstyle_contprog = NULL;
 
-	for (s = zstyles; s; s = s->next) {
-	    if (list == 1) {
-		quotedzputs(s->name, stdout);
-		putchar('\n');
-	    }
-	    if (stylename && strcmp(s->name, stylename) != 0)
-		continue;
-	    for (p = s->pats; p; p = p->next) {
-		if (contprog && !pattry(contprog, p->pat))
-		    continue;
-		if (list == 1)
-		    printf("%s  %s", (p->eval ? "(eval)" : "      "), p->pat);
-		else {
-		    printf("zstyle %s", (p->eval ? "-e " : ""));
-		    quotedzputs(p->pat, stdout);
-		    printf(" %s", s->name);
-		}
-		for (v = p->vals; *v; v++) {
-		    putchar(' ');
-		    quotedzputs(*v, stdout);
-		}
-		putchar('\n');
-	    }
+	if (stylename) {
+	    s = (Style)zstyletab->getnode2(zstyletab, stylename);
+	    if (!s)
+		return 1;
+	    zstyletab->printnode(&s->node, list);
+	} else {
+	    scanhashtable(zstyletab, 1, 0, 0,
+			  zstyletab->printnode, list);
 	}
+
 	return 0;
     }
     switch (args[0][1]) {
@@ -421,7 +505,8 @@
 		    char *pat = args[1];
 
 		    for (args += 2; *args; args++) {
-			if ((s = getstyle(*args))) {
+			if ((s = (Style)zstyletab->getnode2(zstyletab,
+							    *args))) {
 			    Stypat p, q;
 
 			    for (q = NULL, p = s->pats; p;
@@ -434,22 +519,14 @@
 			}
 		    }
 		} else {
-		    Style next;
-		    Stypat p, q;
+		    zstyle_patname = args[1];
 
-		    /* careful! style itself may be deleted */
-		    for (s = zstyles; s; s = next) {
-			next = s->next;
-			for (q = NULL, p = s->pats; p; q = p, p = p->next) {
-			    if (!strcmp(p->pat, args[1])) {
-				freestypat(p, s, q);
-				break;
-			    }
-			}
-		    }
+		    /* sorting not needed for deletion */
+		    scanhashtable(zstyletab, 0, 0, 0, scanpatstyles,
+				  ZSPAT_REMOVE);
 		}
 	    } else
-		freeallstyles();
+		zstyletab->emptytable(zstyletab);
 	}
 	break;
     case 's':
@@ -554,20 +631,21 @@
 	break;
     case 'g':
 	{
-	    LinkList l = newlinklist();
 	    int ret = 1;
 	    Style s;
 	    Stypat p;
 
+	    zstyle_list = newlinklist();
+
 	    if (args[2]) {
 		if (args[3]) {
-		    if ((s = getstyle(args[3]))) {
+		    if ((s = (Style)zstyletab->getnode2(zstyletab, args[3]))) {
 			for (p = s->pats; p; p = p->next) {
 			    if (!strcmp(args[2], p->pat)) {
 				char **v = p->vals;
 
 				while (*v)
-				    addlinknode(l, *v++);
+				    addlinknode(zstyle_list, *v++);
 
 				ret = 0;
 				break;
@@ -575,28 +653,17 @@
 			}
 		    }
 		} else {
-		    for (s = zstyles; s; s = s->next)
-			for (p = s->pats; p; p = p->next)
-			    if (!strcmp(args[2], p->pat)) {
-				addlinknode(l, s->name);
-				break;
-			    }
+		    zstyle_patname = args[2];
+		    scanhashtable(zstyletab, 1, 0, 0, scanpatstyles,
+				  ZSPAT_NAME);
 		    ret = 0;
 		}
 	    } else {
-		LinkNode n;
-
-		for (s = zstyles; s; s = s->next)
-		    for (p = s->pats; p; p = p->next) {
-			for (n = firstnode(l); n; incnode(n))
-			    if (!strcmp(p->pat, (char *) getdata(n)))
-				break;
-			if (!n)
-			    addlinknode(l, p->pat);
-		    }
+		scanhashtable(zstyletab, 1, 0, 0, scanpatstyles,
+			      ZSPAT_PAT);
 		ret = 0;
 	    }
-	    set_list_array(args[1], l);
+	    set_list_array(args[1], zstyle_list);
 
 	    return ret;
 	}
@@ -1752,7 +1819,7 @@
 int
 setup_(UNUSED(Module m))
 {
-    zstyles = NULL;
+    zstyletab = newzstyletable(17, "zstyletab");
 
     return 0;
 }
@@ -1790,7 +1857,7 @@
 int
 finish_(UNUSED(Module m))
 {
-    freeallstyles();
+    deletehashtable(zstyletab);
 
     return 0;
 }
Index: Test/V05styles.ztst
===================================================================
RCS file: Test/V05styles.ztst
diff -N Test/V05styles.ztst
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ Test/V05styles.ztst	8 Jun 2007 13:40:23 -0000
@@ -0,0 +1,145 @@
+%prep
+
+# Test the use of styles, if the zsh/zutil module is available.
+
+  if (zmodload zsh/zutil >/dev/null 2>/dev/null); then
+    zmodload zsh/zutil
+  else
+    ZTST_unimplemented="can't load the zsh/zutil module for testing"
+  fi
+
+%test
+  zstyle :random:stuff any-old-style with any old value
+  zstyle :randomly:chosen some-other-style I can go on and on
+  zstyle -d
+  zstyle
+0:zstyle -d restores a pristine state
+
+# patterns should be ordered by weight, so add in reverse order to check
+  zstyle ':ztst:context*' scalar-style other-scalar-value
+  zstyle ':ztst:context:*' scalar-style second-scalar-value
+  zstyle ':ztst:context:sub1' scalar-style scalar-value
+  zstyle ':ztst:context:sub1' array-style array value elements 'with spaces'
+  zstyle ':ztst:context*' boolean-style false
+  zstyle ':ztst:context:sub1' boolean-style true
+0:defining styles
+
+# styles are now sorted, but patterns are in order of definition
+  zstyle
+0:listing styles in default format
+>array-style
+>        :ztst:context:sub1 array value elements 'with spaces'
+>boolean-style
+>        :ztst:context:sub1 true
+>        :ztst:context* false
+>scalar-style
+>        :ztst:context:sub1 scalar-value
+>        :ztst:context:* second-scalar-value
+>        :ztst:context* other-scalar-value
+
+  zstyle -L
+0:listing styles in zstyle format
+>zstyle :ztst:context:sub1 array-style array value elements 'with spaces'
+>zstyle :ztst:context:sub1 boolean-style true
+>zstyle ':ztst:context*' boolean-style false
+>zstyle :ztst:context:sub1 scalar-style scalar-value
+>zstyle ':ztst:context:*' scalar-style second-scalar-value
+>zstyle ':ztst:context*' scalar-style other-scalar-value
+
+  zstyle -b :ztst:context:sub1 boolean-style bool; print $bool
+  zstyle -t :ztst:context:sub1 boolean-style
+0:boolean test -b/-t + true
+>yes
+
+  zstyle -b :ztst:context:sub2 boolean-style bool; print $bool
+  zstyle -t :ztst:context:sub2 boolean-style
+1:boolean test -b/-t + false
+>no
+
+  zstyle -b :ztst:context:sub1 boolean-unset-style bool; print $bool
+  zstyle -t :ztst:context:sub1 boolean-unset-style
+2:boolean test -b/-t + unset
+>no
+
+  zstyle -T :ztst:context:sub1 boolean-style
+0:boolean test -T + true
+
+  zstyle -T :ztst:context:sub2 boolean-style
+1:boolean test -T + false
+
+  zstyle -T :ztst:context:sub1 boolean-unset-style
+0:boolean test -T + unset
+
+  zstyle -s :ztst:context:sub1 scalar-style scalar && print $scalar
+  zstyle -s :ztst:context:sub2 scalar-style scalar && print $scalar
+  zstyle -s :ztst:contextual-psychedelia scalar-style scalar && print $scalar
+  zstyle -s :ztst:contemplative scalar-style scalar || print no match
+0:pattern matching rules
+>scalar-value
+>second-scalar-value
+>other-scalar-value
+>no match
+
+  zstyle -s :ztst:context:sub1 array-style scalar + && print $scalar
+0:scalar with separator
+>array+value+elements+with spaces
+
+  zstyle -e :ztst:\* eval-style 'reply=($something)'
+  something=(one two three)
+  zstyle -a :ztst:eval eval-style array && print -l $array
+0:zstyle -e evaluations
+>one
+>two
+>three
+
+# pattern ordering on output is not specified, so although in the
+# current implementation it's deterministic we shouldn't
+# assume it's always the same.  Thus we sort the array.
+# (It might be a nice touch to order patterns by weight, which is
+# the way they are stored for each separate style.)
+  zstyle -g array && print -l ${(o)array}
+0:retrieving patterns
+>:ztst:*
+>:ztst:context*
+>:ztst:context:*
+>:ztst:context:sub1
+
+  zstyle -m :ztst:context:sub1 array-style 'w* *s'
+0:positive pattern match
+
+  zstyle -m :ztst:context:sub1 array-style 'v'
+1:negative pattern match
+
+  zstyle -g array ':ztst:context*' && print -l $array
+0:retrieving styles by pattern
+>boolean-style
+>scalar-style
+
+  zstyle -g array ':ztst:context:sub1' array-style && print -l $array
+0:retrieving values by pattern and name
+>array
+>value
+>elements
+>with spaces
+
+  zstyle -d :ztst:context:sub1
+  zstyle
+0:deleting styles by pattern only
+>boolean-style
+>        :ztst:context* false
+>eval-style
+>(eval)  :ztst:* 'reply=($something)'
+>scalar-style
+>        :ztst:context:* second-scalar-value
+>        :ztst:context* other-scalar-value
+
+  zstyle -d :ztst:context\* scalar-style
+  zstyle
+0:deleting styles by pattern and style name
+>boolean-style
+>        :ztst:context* false
+>eval-style
+>(eval)  :ztst:* 'reply=($something)'
+>scalar-style
+>        :ztst:context:* second-scalar-value
+
Index: Doc/Zsh/mod_zutil.yo
===================================================================
RCS file: /cvsroot/zsh/zsh/Doc/Zsh/mod_zutil.yo,v
retrieving revision 1.18
diff -u -r1.18 mod_zutil.yo
--- Doc/Zsh/mod_zutil.yo	16 Aug 2006 09:06:40 -0000	1.18
+++ Doc/Zsh/mod_zutil.yo	8 Jun 2007 13:40:24 -0000
@@ -30,7 +30,8 @@
 complex patterns are considered to be more specific than the pattern
 `tt(*)'.
 
-The first form (without arguments) lists the definitions in the order
+The first form (without arguments) lists the definitions.  Styles
+are shown in alphabetic order and patterns are shown in the order
 tt(zstyle) will test them.
 
 If the tt(-L) option is given, listing is done in the form of calls to

-- 
Peter Stephenson <pws@xxxxxxx>                  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