Xref: utzoo comp.sys.amiga.tech:8462 comp.sys.amiga:44553
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!uunet!sco!gorn!filbo
From: filbo@gorn.santa-cruz.ca.us (Bela Lubkin)
Newsgroups: comp.sys.amiga.tech,comp.sys.amiga
Subject: Re: AmigaDos directory knowledge
Message-ID: <89.filbo@gorn.santa-cruz.ca.us>
Date: 28 Nov 89 10:10:25 GMT
References: <832@lpami.wimsey.bc.ca>
Followup-To: comp.sys.amiga.tech
Lines: 57
X-Claimer: I >am< R Pentomino!

[note that I have directed followups to the .tech group]

In article <832@lpami.wimsey.bc.ca> Larry Phillips writes:
>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.

Oh, come ois and always has been bogus.  Even MS-DOS
does far better than AmigaDOS in this area.  In the case of a known filename,
MS-DOS reads the directory (which is effectively a single small binary file),
searches it for the named file, and is done.  Since each MS-DOS directory
entry is 32 bytes, and a sector is 512 bytes, 16 entries fit in a sector; it
must read (n/16) sectors to find a file, where n=the position of the desired
file within the directory.  In general that means it has to read 1-2 sectors
for MOST files.  It would have to read 5 sectors to find ANY file in my Amiga
C: directory (70 files); 2 for my System: directory (31 files).  Those sectors
would almost always be physically contiguous.  Compare this to AmigaDOS, which
must read an arbitrary number of sectors (often 1, but sometimes more), which
are virtually guaranteed to be all over the disk.  Then compare wildcard
operations.  MS-DOS must still read the entire directory, which is still only
a few (probably contiguous) sectors.  Amiread one sector for
each file in the directory, probably scattered all over the disk.  I don't
like this tradeoff in the least.

This is a case of overblown data structures.  I'd take a monolithic directory
any day.  In AmigaDOS' case, this would probably involve keeping the current
directory blocks, but adding a true index for each directory -- a file that
has nothing in it but filenames and the block numbers of their directory
blocks.  This could be a file of 34-byte records (30 characters + a longword
block number).  It would probably be best to put 15 of these in a sector and
use the extra two bytes for something else, rather than starting a 16th entry
there and carrying it over to the 2nd directory entry, to make it easier to
reconstruct a damaged file system.

The other argument I've heard for AmigaDOS' directory structure is "unlimited
directory size", which is also bogus.  Nothing limits any directory under
MS-DOS, >except< the root directory.  All others are just files which are
treo the root directory is limited?  Well, that's the
choice MicroSoft made with MS-DOS.  Needn't be that way.  Just define a
"super-root" directory which is not directly visible to the user and which
has only one entry -- a pointer to the actual root directory, which is a
normal directory file and can grow to whatever size is needed.

[I speak of MS-DOS for two reasons: I know it well; and it uses SIMPLE
solutions which happen to work pretty well.  Perhaps in 6 months I'd be
arguing for some form of UNIX file system or something, but I don't know
it well enough yet.  Actually, what I suggest sounds suspiciously like
inodes, in a twisted kind of way.]

Bela Lubkin    * *    //  filbo@gorn.santa-cruz.ca.us  CI$: 73047,1112 (slow)
     @       * *     //  belal@sco.com  ..ucbvax!ucscc!{gorn!filbo,sco!belal}
R Pentomino    *   \X/  Filbo @ Pyrzqxgl +408-476-4633 and XBBS +408-476-4945