tpl_rope.H File Reference

Immutable, structurally-shared rope (Aleph::Rope) for large character sequences. More...

#include <algorithm>
#include <bit>
#include <limits>
#include <memory>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_small_vector.H>

Include dependency graph for tpl_rope.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Rope< Char, LeafSize >
	Immutable, structurally-shared rope over a sequence of Char. More...
struct	Aleph::Rope< Char, LeafSize >::Node

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Concepts
concept	Aleph::RopeCharTraitsCompatible
	True exactly for the character types std::char_traits is specialized for by the standard (char, wchar_t, char8_t, char16_t, char32_t), i.e.

Detailed Description

Immutable, structurally-shared rope (Aleph::Rope) for large character sequences.

Rope<Char, LeafSize> is a persistent binary tree of character chunks: every operation that "modifies" a rope (concat, substr, insert, erase) returns a brand-new Rope and never mutates the receiver or any existing rope. Unmodified subtrees are shared (via std::shared_ptr<const Node>) between the old and new ropes instead of being copied, so a concat of two large ropes is cheap (it wraps both existing trees in one new node) and an old snapshot stays valid and unaffected by later operations on a derived rope.

Structure

Leaves hold up to LeafSize characters each (Aleph::SmallVector<Char, LeafSize>); internal nodes hold no character data, just a left and a right child and the total length of their subtree. at(pos) descends in O(depth), comparing pos against each visited node's left-subtree length to choose a side.

Rebalancing

Rebalancing is explicit and deliberately simple, not the classical Fibonacci-threshold criterion from Boehm, Atkinson & Plass, "Ropes: An Alternative to Strings": after every concat, if the resulting node's depth exceeds 2 * bit_width(length) + 8 (a generous, easy-to- state upper bound – true balanced depth is close to log2(length)), the whole subtree is rebuilt from its leaves into a balanced tree (O(number of leaves), reusing every leaf node unchanged – only internal nodes are rebuilt, so no character data is copied). Once a subtree is balanced, at/substr on it cost O(log n); a concat that does not itself trigger a rebuild is O(1).

Leaf absorption (small-piece concat fast path)

Before wrapping two subtrees in a new node, concat first checks whether one side is a lone leaf and, if so, tries to merge it directly into the adjacent leaf on the other side (the rightmost leaf of the left operand for an append, or the leftmost leaf of the right operand for a prepend) when that leaf still has room below LeafSize. This touches only the O(depth) nodes on that one spine, shares everything else, and – because a leaf is only ever replaced by another leaf of the same depth – never changes the tree's depth and therefore never needs a rebalance. This exists specifically for the common pattern of building a rope by repeatedly concat-ing one small piece at a time (e.g. one character per loop iteration): without it, that pattern triggered a whole-subtree rebuild roughly every O(log n) concats, for a cost close to O(n^2 / LeafSize) over the whole loop; with it, appending is O(depth) per call as long as the trailing leaf has spare room, and a full-size internal node (with its own occasional rebalance) is only created once every LeafSize calls. Measured effect: 50000 single-character concats went from several seconds to single-digit milliseconds.

What this type does NOT provide (see docs/missing_data_structures_plan.md)

No mutable iterators, no lazy/incremental rebalancing, and no Unicode awareness – Char is treated as an opaque, fixed-width code unit; a Rope<char> over UTF-8 text indexes and splits by byte, not by Unicode code point or grapheme cluster.

Recursion / stack depth

Every internal traversal (slice, collect_leaves, build_balanced_from_leaves, flatten_into, string_append_into, try_absorb_right/try_absorb_left, verify_rec) is recursive, with depth bounded by the tree's depth field – which the rebalancing contract above keeps O(log size()) once a subtree has been through at least one concat. The one path built without ever calling maybe_rebalance is the initial Rope(View) constructor (build_from_view), whose own midpoint-splitting recursion is separately O(log(size()/LeafSize)) by construction. Neither path produces stack depth proportional to size() itself.

Thread safety

Rope has no built-in synchronization, but its immutability makes most concurrent usage safe by construction: since no operation ever mutates an existing node, any number of threads may concurrently call any method on their own distinct Rope objects – including ones that were copied from a common source and therefore share the same underlying tree – with no locking, exactly like std::shared_ptr (whose reference-count updates are atomic). What is not safe, again exactly as for std::shared_ptr, is multiple threads reading and/or writing the same Rope variable (the same root_ member) concurrently without external synchronization – e.g. two threads both executing shared_rope = shared_rope.concat(x); on one shared variable is a data race on that variable's assignment, not on the tree it points to. The common "give each worker its own copy" pattern is therefore free; a single Rope variable shared and mutated across threads still needs a lock or an atomic wrapper around the variable itself.

See also

prefix-tree.H, tpl_radix_tree.H, tpl_patricia_trie.H for other recently-added Aleph-w data structures.

Author

Leandro Rabindranath Leon

Definition in file tpl_rope.H.