libdiskfs: use a hash table for the name cache

Previously, name cache lookup operation completed in O(n) time.  This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size.

Implement the name cache using a hash table.

We use buckets of a fixed size.  We approximate the least-frequently
used cache algorithm by counting the number of lookups using
saturating arithmetic in the two lowest bits of the pointer to the
name.  Using this strategy we achieve a constant worst-case lookup and
insertion time.

Since we are not bound by the size of the cache anymore, increase its
size from 200 to 1024.

* libdiskfs/name-cache.c: Implement the name cache using a hash table.
(diskfs_enter_lookup_cache): Change accordingly.
(diskfs_purge_lookup_cache): Likewise.
(diskfs_check_lookup_cache): Likewise.  Also, hard code a
cache miss for the parent of the root directory and merge unlocking
and releasing of node references.

0 files changed, 0 insertions, 0 deletions