Re: Large LS_COLORS makes auto_cd very slow

["Václav Zeman" <vhaisman@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 797 bytes --]

On 5 April 2012 17:51, Bart Schaefer wrote:
> On Apr 5, 11:30am, Vaclav Zeman wrote:
> }
> } > Anybody want to have a stab at creating a vastly more efficient version
> } > of Src/params.c:arrayuniq() ?
> } I wonder if the attached patch does what you want here. It is fairly
> } untested and incomplete as I have not been able to find out how to
> } make sure that search.h gets included.
>
> Zsh has its own hash table implementation which ought to be used rather
> than introducing any new external dependencies, but otherwise this is
> the kind of thing I was suggesting.
>
> Or perhaps someone else has an even more clever idea.  Anything better
> than O(N^2) would help.
I have reimplemented the change using ZSH's own hash table. Please see
the attached patch.

-- 
VZ

[-- Attachment #2: hash_arrayuniq-2.diff.txt --]
[-- Type: text/plain, Size: 1877 bytes --]

=== modified file 'Src/params.c'
--- Src/params.c	2012-03-13 09:47:01 +0000
+++ Src/params.c	2012-04-06 09:42:20 +0000
@@ -29,6 +29,7 @@
 
 #include "zsh.mdh"
 #include "params.pro"
+#include "hashtable.pro"
 
 #include "version.h"
 #ifdef CUSTOM_PATCHLEVEL
@@ -3456,7 +3457,7 @@
 
 /**/
 static void
-arrayuniq(char **x, int freeok)
+simple_arrayuniq(char **x, int freeok)
 {
     char **t, **p = x;
 
@@ -3471,6 +3472,73 @@
 }
 
 /**/
+static void
+arrayuniq_freenode(HashNode hn)
+{
+    (void)hn;
+}
+
+/**/
+static void
+arrayuniq(char **x, int freeok)
+{
+    char **it, **write_it;
+    size_t array_size;
+    int ret;
+    HashNode found_item;
+    struct hashnode new_node;
+    HashTable ht;
+
+    if (*x == NULL)
+	return;
+
+    for (it = x; *it != NULL; ++it)
+	;
+
+    array_size = it - x;
+    if (array_size <= 10u) {
+	/* fallback to simpler routine */
+	simple_arrayuniq(x, freeok);
+	return;
+    }
+
+    ht = newhashtable((int)array_size * 2, "arrayuniq", NULL);
+    /* ??? error checking */
+    ht->hash        = hasher;
+    ht->emptytable  = emptyhashtable;
+    ht->filltable   = NULL;
+    ht->cmpnodes    = strcmp;
+    ht->addnode     = addhashnode;
+    ht->getnode     = gethashnode2;
+    ht->getnode2    = gethashnode2;
+    ht->removenode  = removehashnode;
+    ht->disablenode = disablehashnode;
+    ht->enablenode  = enablehashnode;
+    ht->freenode    = arrayuniq_freenode;
+    ht->printnode   = NULL;
+    
+    for (it = x, write_it = x; *it;) {
+	found_item = gethashnode(ht, *it);
+	if (! found_item) {
+	    found_item = addhashnode2(ht, *it, &new_node);
+	    /*assert(! found_item);*/
+	    *write_it = *it;
+	    if (it != write_it)
+		*it = NULL;
+	    ++write_it;
+	}
+	else {
+	    if (freeok)
+		zsfree(*it);
+	    *it = NULL;
+	}
+	++it;
+    }
+    
+    deletehashtable(ht);
+}
+
+/**/
 void
 uniqarray(char **x)
 {