# TypedTree — generic tree with typed values
## Мотивация
`ConstTree<K, V>` хранит значения как `[u8; V]`, `VarTree<K>` — как `ByteView` (сырые байты).
`TypedTree<K, T, C>` хранит произвольный `T` в памяти, сериализует на диск через `Codec<T>`.
Reads — zero I/O, zero deserialization. Writes — encode + append.
## Архитектура
### In-memory модель (как ConstTree)
Все значения `T` живут в памяти в нодах SkipList. Диск — только для durability.
Десериализация происходит один раз при recovery.
```
put(key, user) -> encode(user) -> append to disk
-> store user в TypedNode (T moved in)
get(key) -> load_data() из SkipList -> TypedRef<T> (zero I/O)
```
### TypedRef — Clone-free возврат значений
Ключевое отличие от ConstTree: значения возвращаются как `TypedRef<'_, T>` —
guard-protected ссылка. Seize guard перемещается в TypedRef, предотвращая
reclamation старых данных. Shard lock дропается при return.
```rust
pub struct TypedRef<'a, T> {
_guard: seize::LocalGuard<'a>,
data: *const TypedData<T>,
_marker: PhantomData<&'a T>,
}
impl<T> Deref for TypedRef<'_, T> {
type Target = T;
fn deref(&self) -> &T { unsafe { &(*self.data).value } }
}
```
Это позволяет `put()`, `delete()`, `update()` возвращать ссылку на старое значение
**без `T: Clone`**. RCU-паттерн гарантирует валидность: после atomic swap старый
`TypedData` ещё жив (seize guard предотвращает reclamation).
### Trait bounds
| Struct definition | `T: Send + Sync` |
| get, put, insert, delete, iter | — (кроме Send + Sync) |
| cas | `+ PartialEq` |
| compact | `+ Clone` (единственное место) |
`T: Clone` нужен только для `compact()` — CompactionIndex создаёт новый
`TypedData { disk: new_loc, value: old.clone() }` при перемещении entry.
## Codec trait
Zero-sized marker structs — zero runtime overhead.
```rust
pub trait Codec<T>: Send + Sync {
fn encode_to(&self, value: &T, buf: &mut Vec<u8>);
fn decode_from(&self, bytes: &[u8]) -> DbResult<T>;
}
```
### Feature flags
| `typed-tree` | Codec trait only | — |
| `rapira-codec` | `RapiraCodec` | `T: rapira::Rapira` |
| `bitcode-codec` | `BitcodeCodec` | `T: bitcode::Encode + bitcode::Decode` |
`rapira-codec` и `bitcode-codec` автоматически включают `typed-tree`.
### Использование
```rust
use armdb::{TypedTree, Config, RapiraCodec};
let tree = TypedTree::<16, User, RapiraCodec>::open(
Config::new("data/users"),
RapiraCodec,
)?;
tree.put(&key, user)?;
if let Some(r) = tree.get(&key) {
println!("{:?}", &*r); // TypedRef<User> -> &User
}
tree.close()?;
```
### Custom Codec
```rust
struct MyCodec;
impl Codec<MyType> for MyCodec {
fn encode_to(&self, value: &MyType, buf: &mut Vec<u8>) { /* ... */ }
fn decode_from(&self, bytes: &[u8]) -> DbResult<MyType> { /* ... */ }
}
let tree = TypedTree::<16, MyType, MyCodec>::open(config, MyCodec)?;
```
## TypedWriteHook — typed hook trait
Отдельный trait от `WriteHook<K>`. Получает `&T` напрямую (не `&[u8]`).
Hook вызывается **до** atomic swap — оба значения доступны как `&T`.
Encode/decode для hook не нужен.
```rust
pub trait TypedWriteHook<const K: usize, T>: Send + Sync {
const NEEDS_OLD_VALUE: bool;
fn on_write(&self, key: &[u8; K], old: Option<&T>, new: Option<&T>);
}
```
`NoHook` реализует оба trait (`WriteHook<K>` и `TypedWriteHook<K, T>`).
```rust
struct MyIndex { /* ... */ }
impl TypedWriteHook<16, User> for MyIndex {
const NEEDS_OLD_VALUE: bool = true;
fn on_write(&self, key: &[u8; 16], old: Option<&User>, new: Option<&User>) {
// update secondary index — значения уже десериализованы
}
}
let tree = TypedTree::<16, User, RapiraCodec, MyIndex>::open_hooked(
config, RapiraCodec, my_index,
)?;
```
## Нода SkipList
```rust
pub struct TypedData<T> {
pub disk: DiskLoc,
pub value: T,
}
pub struct TypedNode<const K: usize, T> {
pub key: [u8; K],
pub data: AtomicPtr<TypedData<T>>,
height: u8,
marked: AtomicBool,
tower: SmallVec<[AtomicPtr<Self>; 2]>,
}
```
Паттерн идентичен `ConstNode<K, V>` / `ConstData<V>`, но с `T` вместо `[u8; V]`.
Head sentinel использует null data pointer (Drop проверяет null перед free).
## API
### Основные операции
| `get` | `(&self, &[u8; K])` | `Option<TypedRef<T>>` | lock-free, zero I/O |
| `put` | `(&self, &[u8; K], T)` | `DbResult<Option<TypedRef<T>>>` | ref to **old** value |
| `insert` | `(&self, &[u8; K], T)` | `DbResult<()>` | Err(KeyExists) if exists |
| `delete` | `(&self, &[u8; K])` | `DbResult<Option<TypedRef<T>>>` | ref to **old** value |
| `cas` | `(&self, &[u8; K], &T, T)` | `DbResult<()>` | T: PartialEq |
| `update` | `(&self, &[u8; K], FnOnce(&T)->T)` | `DbResult<Option<TypedRef<T>>>` | ref to **new** value |
| `contains` | `(&self, &[u8; K])` | `bool` | |
| `compact` | `(&self)` | `DbResult<usize>` | T: Clone |
### Iteration
```rust
// All entries
for (key, value) in tree.iter() { /* value: &T */ }
// Prefix search
let latest = tree.prefix_iter(&user_id).take(20).collect::<Vec<_>>();
// Range [start, end)
for (key, value) in tree.range(&start, &end) { }
// Reverse (DoubleEndedIterator)
let oldest = tree.prefix_iter(&user_id).rev().take(10);
```
`TypedIter` implements `Iterator<Item = ([u8; K], &T)> + DoubleEndedIterator`.
### Reversed ordering
```rust
let mut config = Config::new("data/posts");
config.reversed = true;
let tree = TypedTree::<16, Post, RapiraCodec>::open(config, RapiraCodec)?;
// forward iteration yields keys descending — newest first
```
### Atomic multi-key operations
```rust
tree.atomic(&shard_key, |shard| {
let old = shard.get(&key1);
shard.put(&key2, new_value)?;
Ok(())
})?;
```
## Recovery
`recover_typed_tree<K, T, C>()` — параллельный по шардам (один поток на шард).
Два пути:
1. **Hint path** (быстрый): hint-файл содержит (gsn, key, offset, len). Значение
читается с диска по offset и декодируется через `codec.decode_from()`.
2. **Full scan** (fallback): сканирует весь data-файл, проверяет CRC, декодирует значения.
Codec передаётся как `&C` (shared ref через `std::thread::scope`, `C: Sync`).
## CompactionIndex
`T: Clone` bound. При compaction entry перемещается в новый файл — DiskLoc
меняется, value `T` клонируется в новый `TypedData`:
```rust
let new_data = TypedData { disk: new_loc, value: current.value.clone() };
```
## Сравнение tree types
| Значение | `T` (in-memory) | `[u8; V]` (in-memory) | `ByteView` (disk + cache) |
| get() | `TypedRef<T>` (zero I/O) | `[u8; V]` copy (zero I/O) | disk read on miss |
| put() return | `TypedRef<T>` (no Clone) | `[u8; V]` (Copy) | `ByteView` |
| Память | все T в RAM | все `[u8; V]` в RAM | ключи + DiskLoc |
| Dataset > RAM | нет | нет | да |
| Hook | `TypedWriteHook` (`&T`) | `WriteHook` (`&[u8]`) | `WriteHook` (`&[u8]`) |
### Когда что использовать
- **T: Pod (bytemuck/zerocopy)** -> `ConstTree` напрямую
- **T: Rapira/bitcode, dataset в RAM, read-heavy** -> `TypedTree`
- **T: Rapira/bitcode, dataset > RAM** -> `VarTree` с ручной (де)сериализацией