# Итераторы коллекций armdb
## Обзор
Итерация доступна только для **Tree-типов** (SkipList-индекс): ConstTree, VarTree, TypedTree, ZeroTree.
**Map-типы** (HashMap-индекс) итерацию не поддерживают.
| `iter()` | Все записи | полный обход |
| `range(start, end)` | Диапазон `[start, end)` | включая start, исключая end |
| `range_bounds(start, end)` | Диапазон с произвольными `Bound` | `Included`, `Excluded`, `Unbounded` |
| `prefix_iter(prefix)` | Ключи с заданным префиксом | автоматические границы |
Все методы возвращают итератор, реализующий `Iterator` + `DoubleEndedIterator`.
---
## Типы итераторов
| ConstTree | `ConstIter<'a, K, V>` | `(K, [u8; V])` — копия | нет |
| VarTree | `VarIter<'a, K, H>` | `(K, ByteView)` — RC | возможен (cache miss) |
| TypedTree | `TypedIter<'a, K, T>` | `(K, &'a T)` — ссылка | нет |
| ZeroTree | `ZeroIter<'a, K, V, T>` | `(K, T)` — копия | нет |
### Возврат значений
- **ConstTree** — `[u8; V]` копируется из inline SeqLock (`node.read_value()`)
- **VarTree** — `ByteView` читается через `read_value_cached(&disk)`, при промахе block cache — pread с диска
- **TypedTree** — `&'a T` ссылка на значение в `TypedData`, защищённая seize guard
- **ZeroTree** — обёртка над `ConstIter`, `[u8; V]` → `T` через zerocopy (`from_value_bytes`)
---
## Структура итератора
Все итераторы (кроме ZeroIter) имеют одинаковую структуру:
```rust
pub struct ConstIter<'a, K: Key, const V: usize> {
list: &'a SkipList<ConstNode<K, V>>,
front: *mut ConstNode<K, V>, // указатель вперёд
back: *mut ConstNode<K, V>, // указатель назад
end: Bound<K>, // верхняя граница (forward)
start: Bound<K>, // нижняя граница (backward)
reversed: bool, // флаг обратного порядка
done: bool, // front == back — итерация завершена
_guard: seize::LocalGuard<'a>, // предотвращает reclamation нод
}
```
`ZeroIter` — тонкая обёртка:
```rust
pub struct ZeroIter<'a, K: Key, const V: usize, T> {
inner: ConstIter<'a, K, V>,
_marker: PhantomData<T>,
}
```
`VarIter` отличается тем, что хранит `tree: &'a VarTree<K, H>` вместо `list`,
чтобы читать значения через block cache.
---
## Алгоритм обхода
### next() — прямой обход
```
loop:
converged = (front == back)
front = node.tower[0].next() // двигаем front вперёд
if converged → done = true
if node.is_marked() → skip // удалённая нода
if !check_end(node.key) → None // вышли за границу
return Some((key, value))
```
### next_back() — обратный обход
```
loop:
converged = (front == back)
back = list.find_last_lt(key) // двигаем back назад
if converged → done = true
if node.is_marked() → skip
if !check_start(node.key) → None
return Some((key, value))
```
Асимметрия: `next()` использует `tower[0].next()` (O(1)), а `next_back()` — `find_last_lt()` (O(log n)).
### Конвергенция
Когда `front == back`, итератор устанавливает `done = true`. После этого и `next()`, и `next_back()` возвращают `None`. Это предотвращает повторную выдачу элемента.
---
## Reversed ordering
По умолчанию `Config::reversed = true` — SkipList хранит ключи в обратном порядке (компаратор `b.cmp(a)`).
| true (default) | descending | ascending |
| false | ascending | descending |
Проверка границ учитывает `reversed`:
```rust
// check_end (forward direction)
fn check_end(&self, key: &K) -> bool {
match &self.end {
Bound::Unbounded => true,
Bound::Excluded(end) => {
if self.reversed { key > end } else { key < end }
}
Bound::Included(end) => {
if self.reversed { key >= end } else { key <= end }
}
}
}
```
---
## Prefix search
`prefix_iter(prefix)` вычисляет границы через `prefix_bounds()`:
**reversed = false:**
- `search_key` = prefix + `0x00` padding → первый ключ с этим префиксом
- `end` = `prefix + 1` (инкремент последнего байта) как `Excluded` bound; если overflow (все `0xFF`) — `Unbounded`
**reversed = true:**
- `search_key` = prefix + `0xFF` padding → последний ключ с этим префиксом
- `end` = prefix + `0x00` padding как `Included` bound
```rust
// Пример: prefix = [0x01]
// reversed=true:
// search = [0x01, 0xFF, 0xFF, ...] — ищем от конца группы
// end = [0x01, 0x00, 0x00, ...] — до начала группы (Included)
// reversed=false:
// search = [0x01, 0x00, 0x00, ...] — ищем от начала группы
// end = [0x02, 0x00, 0x00, ...] — до следующей группы (Excluded)
```
---
## Weakly-consistent семантика
Итераторы **не** создают snapshot. Они являются weakly-consistent:
- Конкурентные вставки/обновления **могут быть видны** во время итерации
- Удалённые записи (marked nodes) автоматически **пропускаются**
- `seize::LocalGuard` предотвращает reclamation памяти нод на время жизни итератора
---
## VarTree: disk I/O при итерации
`VarIter` — единственный итератор, который может выполнять disk I/O:
```rust
fn next(&mut self) -> Option<Self::Item> {
// ... обход SkipList ...
let disk = *node.load_disk();
match self.tree.read_value_cached(&disk) {
Some(value) => return Some((node.key, value)),
None => continue, // значение недоступно (compacted), пропускаем
}
}
```
При промахе block cache выполняется `pread` с диска. Для предзагрузки кэша используйте `warmup()`.
---
## Helper-методы
| ConstIter | `collect_vec()` | `Vec<(K, [u8; V])>` |
| TypedIter | `collect_vec()` | `Vec<(K, &T)>` |
| VarIter | `collect_keys()` | `Vec<K>` — только ключи |
| VarIter | `collect_entries()` | `Vec<(K, ByteView)>` |
---
## Send safety
Все итераторы содержат raw pointers и реализуют `unsafe impl Send`:
```rust
// SAFETY: итератор держит seize guard, который предотвращает
// reclamation нод. Raw pointer разыменовывается только пока guard жив.
unsafe impl<K: Key, const V: usize> Send for ConstIter<'_, K, V> {}
unsafe impl<K: Key, H: WriteHook<K>> Send for VarIter<'_, K, H> {}
unsafe impl<K: Key, T: Send + Sync> Send for TypedIter<'_, K, T> {}
```
ZeroIter наследует Send от ConstIter (обёртка).
---
## Стоимость операций
| `next()` | O(1), zero I/O | O(1) + возможен pread | O(1), zero I/O | O(1), zero I/O |
| `next_back()` | O(log n), zero I/O | O(log n) + возможен pread | O(log n), zero I/O | O(log n), zero I/O |
| `prefix_iter()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
| `range()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
---
## Примеры использования
### Полный обход
```rust
// ConstTree
for (key, value) in tree.iter() {
// key: [u8; K], value: [u8; V]
}
// TypedTree
for (key, user) in tree.iter() {
// key: [u8; K], user: &User
}
// ZeroTree
for (key, counters) in tree.iter() {
// key: [u8; K], counters: Counters (Copy)
}
```
### Prefix search — "последние N записей"
```rust
// Составной ключ: [user_id:8][post_id:8]
// reversed=true (default) → prefix_iter возвращает от новых к старым
let latest_posts: Vec<_> = tree
.prefix_iter(&user_id)
.take(20)
.collect();
```
### Range query
```rust
// Диапазон [start, end) — start включительно, end исключительно
let start = 5u64.to_be_bytes();
let end = 10u64.to_be_bytes();
for (key, value) in tree.range(&start, &end) {
// reversed=true → ключи 9, 8, 7, 6, 5
}
```
### range_bounds — произвольные границы
`range_bounds(start: Bound<&K>, end: Bound<&K>)` — обобщение `range()`.
Каждая граница может быть `Included`, `Excluded` или `Unbounded`.
`range(start, end)` эквивалентен `range_bounds(Bound::Included(start), Bound::Excluded(end))`.
```rust
use std::ops::Bound;
// (5, 10] — исключить 5, включить 10
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6
// [5, 10] — включить обе границы
let entries: Vec<_> = tree.range_bounds(
Bound::Included(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6, 5
// (5, ..) — от 5 исключительно до конца
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Unbounded,
).collect();
// (.., 10) — от начала до 10 исключительно
let entries: Vec<_> = tree.range_bounds(
Bound::Unbounded,
Bound::Excluded(&10u64.to_be_bytes()),
).collect();
```
### DoubleEndedIterator
```rust
// .rev() — обратный порядок
let oldest: Vec<_> = tree.prefix_iter(&user_id).rev().take(10).collect();
// Смешанный обход: next() + next_back()
let mut iter = tree.iter();
let first = iter.next(); // первый в порядке итерации
let last = iter.next_back(); // последний в порядке итерации
// Итератор схлопывается к центру
```
### VarTree — предзагрузка кэша
```rust
// Предзагрузить все значения в block cache перед итерацией
tree.warmup()?;
for (key, value) in tree.iter() {
// value: ByteView — без disk I/O после warmup
}
```