delorie.com/archives/browse.cgi   search  
Mail Archives: djgpp-workers/2001/02/13/11:12:11

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 -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019