Path: utzoo!attcan!telly!ziebmef!mcp From: mcp@ziebmef.uucp (Marc Plumb) Newsgroups: comp.sys.amiga.tech Subject: Re: fib_DiskKey semantics Message-ID: <1989May30.202159.9554@ziebmef.uucp> Date: 31 May 89 00:21:58 GMT References: <1989May12.183725.25380@ziebmef.uucp> <104761@sun.Eng.Sun.COM> <1989May22.162035.19970@ziebmef.uucp> Reply-To: mcp@ziebmef.UUCP (Marc Plumb) Organization: Ziebmef Public Access Unix, Toronto, Ontario Lines: 24 In article limonce@pilot.njin.net (Tom Limoncelli) writes: >How about using a hash table? Wildcards would be a little slow if the >cache system isn't good (could be improved in a later FS release) but >lookups (finding commands, opening files, all the things I usually do) >would be SUPER FAST! > >Nah, it'll never work. :-) I do! A directory is an array of pointers to inodes, so you have all the pointers at once and can sort them by track for fast access, but each array element also contains an 8-bit hash value (an 8-bit CRC of the name) so you can throw away 255/256 of the directory if you know the name exactly. And you have pointers directly to all the file names with that hash value, so you can sort *them*, trying everything in cache before resorting to disk access. The hashing is one good idea AmigaDOG had that I didn't throw away. I considered an extensible hashing scheme (if I detect a collision, I use a second-, third-, etc. order hash on the colliding names until they are resolved) that would allow a directory to map a name onto a unique inode directly, but it didn't seem worth it. Does anyone dissent? -- -Colin Plumb