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 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: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 Precedence: bulk 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.