use std::marker::PhantomData;
use std::mem;
use std::sync::atomic::Ordering;
use arrayvec::ArrayVec;
use crossbeam_epoch::{Guard, Shared};
use super::config::Config;
use super::{load_data, nf, Inner, NodeFlags, Raw, LEVEL_CELLS, MAX_LEVELS};
unsafe fn extend_lifetime<'a, 'b, T: 'a + 'b>(s: Shared<'a, T>) -> Shared<'b, T> {
mem::transmute(s)
}
struct Level<'a> {
ptr: Shared<'a, Inner>,
idx: usize,
}
pub struct Iter<'a, C, S>
where
C: Config,
{
pin: Guard,
levels: ArrayVec<[Level<'a>; MAX_LEVELS + 1]>,
_map: PhantomData<&'a Raw<C, S>>,
}
impl<'a, C, S> Iter<'a, C, S>
where
C: Config,
{
pub fn new<'m: 'a>(map: &'m Raw<C, S>) -> Self {
let mut levels = ArrayVec::new();
let pin = crossbeam_epoch::pin();
let ptr = map.root.load(Ordering::Acquire, &pin);
let ptr = unsafe { extend_lifetime(ptr) };
levels.push(Level { ptr, idx: 0 });
Iter {
pin,
levels,
_map: PhantomData,
}
}
#[allow(clippy::should_implement_trait)]
pub fn next(&mut self) -> Option<&C::Payload> {
loop {
let top = self.levels.last_mut()?;
let flags = nf(top.ptr);
if top.ptr.is_null() {
self.levels.pop();
} else if flags.contains(NodeFlags::DATA) {
let data = unsafe { load_data::<C>(top.ptr) };
if top.idx < data.len() {
let result = &data[top.idx];
top.idx += 1;
return Some(result);
} else {
self.levels.pop();
}
} else if top.idx < LEVEL_CELLS {
let node = unsafe { top.ptr.deref() };
let ptr = node.0[top.idx].load(Ordering::Acquire, &self.pin);
let ptr = unsafe { extend_lifetime(ptr) };
top.idx += 1;
self.levels.push(Level { ptr, idx: 0 });
} else {
self.levels.pop();
}
}
}
}