Lockless hash trie

Description

The hash trie uses semaphores for locking to manage concurrency in shared memory. We could use CAS semantics, if the links (indices in arrays) in a node are tagged with an additonal bit. E.g. values < 0 could be reserved for other nodes and values >= 0 for hash codes.

This would mess with additional infomartion because usually a CAS is only supported for up to eight byte. Fine-grained locking (on hash-code basis via CAS on the checked/unchecked byte) could be used. Another solution would be immutable tuples of hash code and information that are controlled via a more sophisticated memory management.

Environment

None

Assignee

Philipp Koerner

Reporter

Philipp Koerner

Priority

Major