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
    }
  1. Loop should go up to the int size, 32 or 128
  2. 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