txt: ## dist_cpan-JNTHN-Concurrent-Trie.md
  # 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.
  