🚀 go-pugleaf

In article <May.24.00.02.54.1989.15356@pilot.njin.net> 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