From owner-freebsd-current@FreeBSD.ORG  Wed Jun  8 07:50:50 2005
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
X-Original-To: freebsd-current@freebsd.org
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 9196016A41F;
	Wed,  8 Jun 2005 07:50:50 +0000 (GMT) (envelope-from des@des.no)
Received: from tim.des.no (tim.des.no [194.63.250.121])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 0800C43D5C;
	Wed,  8 Jun 2005 07:50:49 +0000 (GMT) (envelope-from des@des.no)
Received: from tim.des.no (localhost [127.0.0.1])
	by spam.des.no (Postfix) with ESMTP id ECD0B60F3;
	Wed,  8 Jun 2005 09:50:44 +0200 (CEST)
Received: from xps.des.no (des.no [80.203.228.37])
	by tim.des.no (Postfix) with ESMTP id 5EA6560F2;
	Wed,  8 Jun 2005 09:50:44 +0200 (CEST)
Received: by xps.des.no (Postfix, from userid 1001)
	id 38AA833C3B; Wed,  8 Jun 2005 09:50:44 +0200 (CEST)
To: Giorgos Keramidas <keramida@freebsd.org>
References: <17059.7150.269428.448187@roam.psg.com>
	<42A4D5D0.9040500@elischer.org> <42A59367.6060307@centtech.com>
	<20050607175242.D61131@fledge.watson.org> <86ll5lmhs3.fsf@xps.des.no>
	<20050608074613.GA979@orion.daedalusnetworks.priv>
From: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=)
Date: Wed, 08 Jun 2005 09:50:44 +0200
In-Reply-To: <20050608074613.GA979@orion.daedalusnetworks.priv> (Giorgos
	Keramidas's message of "Wed, 8 Jun 2005 10:46:14 +0300")
Message-ID: <86zmu1l223.fsf@xps.des.no>
User-Agent: Gnus/5.110002 (No Gnus v0.2) Emacs/21.3 (berkeley-unix)
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on tim.des.no
X-Spam-Level: 
X-Spam-Status: No, score=-5.1 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 
	autolearn=ham version=3.0.2
Cc: freebsd-fs@freebsd.org, Randy Bush <randy@psg.com>,
	FreeBSD Current <freebsd-current@freebsd.org>,
	Robert Watson <rwatson@freebsd.org>, Julian Elischer <julian@elischer.org>,
	Eric Anderson <anderson@centtech.com>
Subject: Re: you are in an fs with millions of small files
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>, 
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 08 Jun 2005 07:50:50 -0000

Giorgos Keramidas <keramida@freebsd.org> writes:
> Is there a better way to sort a linked list (not necessarily a
> singly-linked list, like the one fts_link is used for).

Don't build a linked list to begin with.  The comparison function is
known at the time the directory entries are read, so it should be a
simple matter to read them into a red-black tree instead of a singly-
linked list.  I'm working on a patch.

DES
--=20
Dag-Erling Sm=F8rgrav - des@des.no