Concurrent::Trie

A lock-free trie (Text Retrieval) data structure, safe for concurrent use.

Synopsis

use Concurrent::Trie;

my $trie = Concurrent::Trie.new;
say $trie.contains('brie');         # False
say so $trie;                       # False
say $trie.elems;                    # 0

$trie.insert('brie');
say $trie.contains('brie');         # True
say so $trie;                       # True
say $trie.elems;                    # 1

$trie.insert('babybel');
$trie.insert('gorgonzola');
say $trie.elems;                    # 3
say $trie.entries();                # (gorgonzola babybel brie)
say $trie.entries('b');             # (babybel brie)

Overview

A trie stores strings as a tree, with each level in the tree representing a character in the string (so the tree's maximum depth is equal to the number of characters in the longest entry). A trie is especially useful for prefix searches, where all entries with a given prefix are required, since this is obtained simply by walking the tree according to the prefix, and then visiting all nodes below that point to find entries.

This is a lock-free trie. Checking if the trie contains a particular string never blocks. Iterating the entries never blocks either, and will provide a snapshot of all the entries at the time the entries method was called. An insertion uses optimistic concurrency control, building an updated tree and then trying to commit it. This offers a global progress bound: if one thread fails to insert, it's because another thread did a successful insert.

This data structure is well suited to auto-complete style features in concurrent applications, where new entries and lookups may occur when, for example, processing web requests in parallel.

Methods

insert(Str $value --> Nil)

Inserts the passed string value into the trie.

contains(Str $value --> Bool)

Checks if the passed string value is in the trie. Returns True if so, and False otherwise.

entries($prefix = '' --> Seq)

Returns a lazy iterator of all entries in the trie with the specified prefix. If no prefix is passed, the default is the empty prefix, meaning that a call like $trie.entries() will iterate all entries in the trie. The order of the results is not defined.

The results will be a snapshot of what was in the trie at the point entries was called; additions after that point will not be in the entries list.

elems(--> Int)

Gets the number of entries in the trie. The data structure maintains a count, making this O(1) (as opposed to $trie.entries.elems, which would be O(n)).

Bool()

Returns True if the number of entries in the trie is non-zero, and False otherwise.