X-Authentication-Warning:	acp3bf.physik.rwth-aachen.de: broeker owned process doing -bs
Date:	Tue, 13 Feb 2001 17:11:53 +0100 (MET)
From:	Hans-Bernhard Broeker <broeker AT physik DOT rwth-aachen DOT de>
X-Sender:	broeker AT acp3bf
To:	djgpp-workers AT delorie DOT com
Subject:	Re: PATCH: new djtar option
In-Reply-To:	<20010213155608.236.qmail@lauras.lt>
Message-ID:	<Pine.LNX.4.10.10102131708550.4040-100000@acp3bf>
MIME-Version:	1.0
Reply-To:	djgpp-workers AT delorie DOT com
Errors-To:	nobody AT delorie DOT com
X-Mailing-List:	djgpp-workers AT delorie DOT com
X-Unsubscribes-To:	listserv AT delorie DOT com

On Tue, 13 Feb 2001, Laurynas Biveinis wrote:

> But hash tables deal with full filenames only; I put a prefix 
> 'gcc-3.0/libjava' in it, but 'gcc-3.0/libjava/foo' generates a different
> hash code, and the match isn't detected. Maybe in this case my linked
> lists would make the code less complicated?

You can always check all parent directories against the hash table, i.e.
instead of testing only "gcc-3.0/libjava/foo", you'ld also check if
"gcc-3.0/libjava" and "gcc-3.0" are in the hash table.

Linked lists are a lot slower than hash tables, as soon as there are
lots of entries. Hash tables have a probabilistic behaviour of average
O(1) search time, and worst-case O(n). Linear lists are always O(n)
on average, too.

-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.

- Raw text -