hashrope
A BB[2/7] weight-balanced binary tree augmented with polynomial hash metadata at every node.
Zero dependencies. Rust 2021 edition.
What it does
hashrope is a rope data structure where every node carries a polynomial hash. This enables:
- O(k log w) concat and split with strict BB[2/7] rebalancing via recursive join
- O(k log q) repetition encoding via RepeatNode
- O(k log w) substring hashing without allocating new nodes
- O(1) whole-sequence hash at any point during streaming ingestion
- Bounded-memory sliding window with eviction
All arithmetic uses Mersenne prime modular reduction (bit-shift, no division). Nodes are immutable with structural sharing via Arc.
Install
[]
= "0.1"
Quick start
use *;
let ph = default_hash;
let mut h = default_hash;
let a = rope_from_bytes;
let b = rope_from_bytes;
let ab = rope_concat;
assert_eq!;
// Split at any byte position
let = rope_split;
// Substring hash without allocation
assert_eq!;
Benchmarks
Uses Criterion.rs with HTML reports.
Provenance
Translated from the Python implementation which was extracted from UHC.
License
MIT