How do I make a generic function that can operate on u32 and u128 integers?

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

There may be more to it, but keep in mind that size_of gives you the size in bytes, and not bits as your function expects it to: size_of in std::mem - Rust

You'll want to multiply the output by 8 or check for 4 to detect a 32 bit value.

1 Like

Thanks for the tip! I'll make these changes, still haven't figured out a way to make this compile

If you give more complete code (imports, types, etc) it will be more likely someone will help. Ideally you could put it in a playground such that the only compiler errors are those you don't know how to solve.

Hi,

The function can be found here, geofw/geofw/src/maxmind.rs at 5f359e953979b4709a6c87842cfe24c1fc96fc06 · ishanjain28/geofw · GitHub

I don't have a small input size(The data comes from Maxmind geolocation databases) it could be tested on and I forgot to share a rust playground link