# 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.

```text
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,ignore
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

| Контекст | Bounds на T |
|----------|-------------|
| 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,ignore
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

| Feature | Codec struct | Trait bounds |
|---------|-------------|--------------|
| `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,ignore
use armdb::{TypedTree, Config, RapiraCodec};

let tree = TypedTree::<16, User, RapiraCodec>::open(
    "data/users",
    Config::balanced().build(),
    RapiraCodec,
)?;

tree.put(&key, user)?;

if let Some(r) = tree.get(&key) {
    println!("{:?}", &*r);  // TypedRef<User> -> &User
}

tree.close()?;
```

### Custom Codec

```rust,ignore
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,ignore
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,ignore
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,ignore
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

### Основные операции

| Method | Signature | Return | Notes |
|--------|-----------|--------|-------|
| `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,ignore
// 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,ignore
let config = Config::balanced().build(); // reversed: true by default
let tree = TypedTree::<16, Post, RapiraCodec>::open("data/posts", config, RapiraCodec)?;
// forward iteration yields keys descending — newest first
```

### Atomic multi-key operations

```rust,ignore
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,ignore
let new_data = TypedData { disk: new_loc, value: current.value.clone() };
```

## Сравнение tree types

| | TypedTree | ConstTree | VarTree |
|-|-----------|-----------|---------|
| Значение | `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` с ручной (де)сериализацией
