<commit_before>#labels Featured
The design of trees in this project to support concurrent lock-free reads with ongoing writes.

== Architecture and Concurrency Mechanism ==
All of the trees in this project (derivatives of the Radix Tree, the Suffix Tree, and derivatives of the Suffix Tree) are based on the implementation of the Concurrent Radix Tree.

The Concurrent Radix Tree supports lock-free reads while allowing concurrent writes, by _calculating the changes which would be made to the tree were it mutable_, and assembling those changes into a *patch*, which is then applied to the tree in a *single atomic operation*.

===Atomic updates by patching the tree===
Inserting an entry into Concurrent Radix Tree which requires an existing node within the tree to be split.
[http://concurrent-trees.googlecode.com/svn/wiki/images/tree-apply-patch.png]

Reading threads traversing the tree while the patch above is being applied, will either see the _old version_ or the _new version_ of the (sub-)tree, but both versions are consistent views of the tree, which preserve the invariants.

The node 'te' will be garbage collected when threads which are traversing the old version of the tree, finish traversing that version and release their reference to that node.

===Restrictions on Mutability===
To support atomicity of updates as above, nodes in the tree have the following restrictions in their design:
  * Nodes are _mostly-immutable_
  * The characters for an incoming "edge" to a node (a reference from a parent node to a child node which has some characters of a key associated with it) are stored in the child node rather than a dedicated Edge object<commit_msg>Edited wiki page TreeDesign through web user interface.<commit_after>#summary Architecture of the trees and algorithms to support concurrency
#labels Featured

The design of trees in this project to support concurrent lock-free reads with ongoing writes.

== Architecture and Concurrency Mechanism ==
All of the trees in this project (derivatives of the Radix Tree, the Suffix Tree, and derivatives of the Suffix Tree) are based on the implementation of the Concurrent Radix Tree.

The Concurrent Radix Tree supports lock-free reads while allowing concurrent writes, by _calculating the changes which would be made to the tree were it mutable_, and assembling those changes into a *patch*, which is then applied to the tree in a *single atomic operation*.

===Atomic updates by patching the tree===
Inserting an entry into Concurrent Radix Tree which requires an existing node within the tree to be split.
[http://concurrent-trees.googlecode.com/svn/wiki/images/tree-apply-patch.png]

Reading threads traversing the tree while the patch above is being applied, will either see the _old version_ or the _new version_ of the (sub-)tree, but both versions are consistent views of the tree, which preserve the invariants.

The node 'te' will be garbage collected when threads which are traversing the old version of the tree, finish traversing that version and release their reference to that node.

===Restrictions on Mutability===
To support atomicity of updates as above, nodes in the tree have the following restrictions in their design:
  * Nodes are _mostly-immutable_
  * The characters for an incoming "edge" to a node (a reference from a parent node to a child node which has some characters of a key associated with it) are stored in the child node rather than a dedicated Edge object
{'fraction_non_alphanumeric': 0.04214780600461894, 'fraction_numerical': 0.0, 'mean_word_length': 4.813758389261745, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2185327', 'n_tokens_mistral': 826, 'n_tokens_neox': 799, 'n_words': 522}