From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-30383-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 21201 invoked by alias); 4 Apr 2012 08:08:17 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
X-Seq: 30383
Received: (qmail 23660 invoked from network); 4 Apr 2012 08:08:16 -0000
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on f.primenet.com.au
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE
	autolearn=ham version=3.3.2
Received-SPF: none (ns1.primenet.com.au: domain at closedmail.com does not designate permitted sender hosts)
From: Bart Schaefer <schaefer@brasslantern.com>
Message-id: <120404010807.ZM11646@torch.brasslantern.com>
Date: Wed, 04 Apr 2012 01:08:07 -0700
In-reply-to: <120404005237.ZM10249@torch.brasslantern.com>
Comments: In reply to Bart Schaefer <schaefer@brasslantern.com>
 "Re: Large LS_COLORS makes auto_cd very slow" (Apr  4, 12:52am)
References:
 <CABZhJg-xieMZAOEmbYzSb5T-3O8aLNurvPk=SiXsPGjTpAMg-Q@mail.gmail.com>
	<120404005237.ZM10249@torch.brasslantern.com>
X-Mailer: OpenZMail Classic (0.9.2 24April2005)
To: zsh-workers@zsh.org
Subject: Improving arrayuniq
MIME-version: 1.0
Content-type: text/plain; charset=us-ascii

} Anybody want to have a stab at creating a vastly more efficient version
} of Src/params.c:arrayuniq() ?  I came up with a faster way to remove the
} duplicate elements, but the problem here is to efficiently determine
} that there are no duplicates to remove.  Perhaps throw the elements into
} a hash table and then make one pass looking up each element.

Here's the improved way to collapse out the duplicates (one pass instead
of shifting the whole remainder of the array each time a duplicate is
found).  I haven't changed the basic find-duplicates algorithm, which is
optimized for space rather than speed.


/**/
static void
arrayuniq(char **x, int freeok)
{
    char **t, **p = x;
    char *hole = "";

    /* Find duplicates and replace them with holes */
    while (*++p)
	for (t = x; t < p; t++)
	    if (*t != hole && !strcmp(*p, *t)) {
		if (freeok)
		    zsfree(*p);
		*p = hole;
		break;
	    }
    /* Swap non-holes into holes in optimal jumps */
    for (p = t = x; *t != NULL; t++) {
	if (*t == hole) {
	    while (*p == hole)
		++p;
	    if ((*t = *p) != NULL)
		*p++ = hole;
	} else if (p == t)
	    p++;
    }
    /* Erase all the remaining holes, just in case */
    while (++t < p)
	*t = NULL;
}