Hi, I have this function which traverses a binary tree. It looks like this,
#[allow(unused)]
pub fn lookup(&self, addr: IpAddr) -> Option<Data> {
let node_size = self.metadata.record_size as usize * 2 / 8;
let mut node = 0;
let mut ip = match addr {
IpAddr::V4(a) => a.to_bits() as u128,
IpAddr::V6(a) => a.to_bits(),
};
let mut i = 0;
while i < 128 && node < self.metadata.node_count {
let bit = ip & (1 << 127);
ip <<= 1;
let n = &self.data[node as usize * node_size..(node as usize * node_size) + node_size];
node = Self::node_from_bytes(n, if bit > 0 { 1 } else { 0 }, self.metadata.record_size);
i += 1;
}
if node == self.metadata.node_count {
None
} else {
return None;
let data_section_offset = node - self.metadata.node_count;
let (data, _) = self
.read_data(self.metadata.data_section_start + data_section_offset as usize - 16);
Some(data)
}
}
Just for fun/curiosity, I want to make an optimization where node
starts at 96
instead of 0
for IPv4 addresses. I was trying to write a generic function to do this but I haven't been able to make it work.
My broken generic version looks like this,
#[allow(unused)]
pub fn lookup(&self, addr: IpAddr) -> Option<Data> {
let node = match addr {
IpAddr::V4(a) => self.lookup_internal(a.to_bits()),
IpAddr::V6(a) => self.lookup_internal(a.to_bits()),
};
if node == self.metadata.node_count {
None
} else {
return None;
let data_section_offset = node - self.metadata.node_count;
let (data, _) = self
.read_data(self.metadata.data_section_start + data_section_offset as usize - 16);
Some(data)
}
}
fn lookup_internal<T>(&self, mut ip: T) -> u32
where
T: BitAnd<T, Output = T> + Copy + ShlAssign<T> + PartialOrd<T>,
{
let node_size = self.metadata.record_size as usize * 2 / 8;
let mut node = 0;
let mut i = 0;
if std::mem::size_of::<T>() == 32 {
// This is an optimization for faster traversal for V4 addresses
// and it assumes we are working with a dataset that has v4 addresses in v6
node = 96;
};
while i < std::mem::size_of::<T>() && node < self.metadata.node_count {
let bit = ip & (1 << (std::mem::size_of::<T>() - 1));
ip <<= 1;
let n = &self.data[node as usize * node_size..(node as usize * node_size) + node_size];
node = Self::node_from_bytes(n, if bit > 0 { 1 } else { 0 }, self.metadata.record_size);
i += 1;
}
node
}
- Loop should go up to the int size, 32 or 128
- We need to check the left most bit on every iteration.
let bit = ip & (1 << (std::mem::size_of::<T>() - 1));
does that by shifting the integer to the left. I think there must be a better way to do this
Source: View source