Module dir_trie

Shallow byte-partitied directory tries.

This is an implementation of the same on-disk data structure as the git object store, used for storing objects in an object store keyed on a content-addressed 32-byte hash.

Objects’ location in the trie is computed based on the (64 character) hexadecimal encoding of their (32 byte) Blake3 hash. The leading 2 digits of this hash are the name of the directory, and the remaining 62 digits are the name of the file itself.

Storing files in this way is beneficial because directories internally are unsorted arrays of file entries, so searching for a file within a directory is O(directory_size). The trie structure implemented here is still O(n), but with a drastically reduced constant factor (1/128th), which we expect to shrink the linear lookups to an acceptable size.

Structs

CountCreated

Counter for objects written newly to disk versus hardlinked, for diagnostic purposes with operations that may hardlink or write.

DirTrie

A directory trie.

Functions

o_excl

OpenOptions corresponding to opening a file with O_EXCL, i.e. creating a new writeable file, failing if it already exists.

o_rdonly

OpenOptions corresponding to opening a file with O_RDONLY, i.e. opening an existing file for reading.

o_rdonly_async

OpenOptions corresponding to opening a file with O_RDONLY, i.e. opening an existing file for reading.