Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!gem.mps.ohio-state.edu!van-bc!
From: lphillips@lpami.wimsey.bc.ca (Larry Phillips)
Newsgroups: comp.sys.amiga
Subject: Re: AmigaDos directory knowledge
Message-ID: <832@lpami.wimsey.bc.ca>
Date: 26 Nov 89 05:33:10 GMT
Lines: 47
Return-Path: <lpami!lphillips>
To: van-bc!rnews

In <291@intersil.uucp>, hamilton@intersil.uucp (Fred Hamilton) writes:
>I just remembered a question I've had since WorkBench 1.0.  When you type
>a command like:
>
>	List c:edd     ;(A typo, for instance)
>
>You get an (almost) instant response of "object not found".
>But if you type:
>
>	List c:ed#?
>
>The OS thrashes throught the entire directory before giving you the list.
>
>What's happening here?  It's like the OS is saying "Well, I'm not sure
>what EXACTLY is in the c: directory, but I KNOW there isn't a program called
>"Edd." It seems to my feeble mind that for it to know what's NOT in the
>directory with out a long search, it has to already know what IS in the 
>directory.  What's happening here? 

Yes, this is exactly what happens.  The big advantage of the Amiga filing
system is that a fully known filename is found VERY quickly. The reason for
this is that filenames are hashed into tables in the directory blocks, and can
be found within a (relatively) few seeks, simply by looking in the appropriate
header and offset within that header to find the pointer to the file. Hash
'collisions' are handled by chaining from one directory entry to the next, but
even then, there are relatively few reads to do.

When even one character is unknown, there can be no hashing of the name, and
the only way the file system can find a match is by following ALl the table
entries in the directory until it finds the match, and then continuing on
because it has no way of knowing if that's the only match.

To find out there is not a file named 'edd', when you specify it fuly, might
take at most 10 or 15 seek/reads on a fairly large directory, while specifying
it as 'ed?' will take the same number of seek/reads as there are files and
subdirectories in C:.

-larry

--
" All I ask of my body is that it carry around my head."
         - Thomas Alva Edison -
+-----------------------------------------------------------------------+ 
|   //   Larry Phillips                                                 |
| \X/    lphillips@lpami.wimsey.bc.ca -or- uunet!van-bc!lpami!lphillips |
|        COMPUSERVE: 76703,4322  -or-  76703.4322@compuserve.com        |
+-----------------------------------------------------------------------+