• Mark Fasheh's avatar
    ocfs2: Add a name indexed b-tree to directory inodes · 9b7895ef
    Mark Fasheh authored
    This patch makes use of Ocfs2's flexible btree code to add an additional
    tree to directory inodes. The new tree stores an array of small,
    fixed-length records in each leaf block. Each record stores a hash value,
    and pointer to a block in the traditional (unindexed) directory tree where a
    dirent with the given name hash resides. Lookup exclusively uses this tree
    to find dirents, thus providing us with constant time name lookups.
    
    Some of the hashing code was copied from ext3. Unfortunately, it has lots of
    unfixed checkpatch errors. I left that as-is so that tracking changes would
    be easier.
    Signed-off-by: default avatarMark Fasheh <mfasheh@suse.com>
    Acked-by: default avatarJoel Becker <joel.becker@oracle.com>
    9b7895ef
alloc.c 188 KB