Module concread::hashtrie

HashTrie - A concurrently readable HashTrie

A HashTrie is similar to the Tree based HashMap, however instead of storing hashes in a tree arrangement, we use Trie behaviours to slice a hash into array indexes for accessing the elements. This reduces memory consumed as we do not need to store hashes of values in branches, but it can cause memory to increase as we don’t have node-split behaviour like a BTree that backs the HashMap.

Generally, this structure is faster than the HashMap, but at the expense that it may consume more memory for it’s internal storage. However, even at large sizes such as ~16,000,000 entries, this will only consume ~16KB for branches. The majority of your space will be taken by your keys and values.

If in doubt, use HashMap 😁

This structure is very different to the im crate. The im crate is sync + send over individual operations. This means that multiple writes can be interleaved atomicly and safely, and the readers always see the latest data. While this is potentially useful to a set of problems, transactional structures are suited to problems where readers have to maintain consistent data views for a duration of time, cpu cache friendly behaviours and database like transaction properties (ACID).

Modules

asynch

HashTrie - A async locked concurrently readable HashTrie

Structs

HashTrie

A concurrently readable map based on a modified Trie.

HashTrieReadSnapshot

A point-in-time snapshot of the tree from within a read OR write. This is useful for building other transactional types ontop of this structure, as you need a way to downcast both HashTrieReadTxn or HashTrieWriteTxn to a singular reader type for a number of get_inner() style patterns.

HashTrieReadTxn

An active read transaction over a HashTrie. The data in this tree is guaranteed to not change and will remain consistent for the life of this transaction.

HashTrieWriteTxn

An active write transaction for a HashTrie. The data in this tree may be modified exclusively through this transaction without affecting readers. The write may be rolledback/aborted by dropping this guard without calling commit(). Once commit() is called, readers will be able to access and percieve changes in new transactions.