fn test_interpolation_search()

in mdb_shard/src/interpolation_search.rs [182:242]

• 42 lines of code
• 4 McCabe index (conditional complexity)

    fn test_interpolation_search(keys: &[u64], alt_query_keys: &[u64]) -> Result<(), std::io::Error> {
        let mut values: Vec<(u64, u64)> = keys.iter().enumerate().map(|(i, k)| (*k, 100 + i as u64)).collect();
        values.sort_unstable();

        // First, serialize out the values, and build a
        let data_start = 0;
        let mut data = vec![0xFFu8; data_start]; // Start off with some.

        let mut all_values = HashMap::<u64, Vec<u64>>::new();

        for (k, v) in values.iter() {
            all_values.entry(*k).or_default().push(*v);
            write_u64(&mut data, *k)?;
            write_u64(&mut data, *v)?;
        }

        // Now, loop through all the values, running the query function and checking if it works.
        let mut dest_values = Vec::<u64>::new();

        for (k, v) in all_values {
            dest_values.clear();
            dest_values.resize(v.len() + 1, 0);

            let n_items_found = search_on_sorted_u64s(
                &mut Cursor::new(&data),
                data_start as u64,
                values.len() as u64,
                k,
                read_u64::<Cursor<&Vec<u8>>>,
                &mut dest_values,
            )?;

            // Make sure we found the correct amount.
            assert_eq!(n_items_found, v.len());

            // Clip off the last one, unused.
            dest_values.resize(v.len(), 0);

            // Sort it so we can do a proper comparison
            dest_values.sort_unstable();

            assert_eq!(dest_values, v);
        }

        // Now test all the other values given that are not in the map.
        dest_values.resize(8, 0);

        for k in alt_query_keys {
            let n_items_found = search_on_sorted_u64s(
                &mut Cursor::new(&data),
                data_start as u64,
                values.len() as u64,
                *k,
                read_u64::<Cursor<&Vec<u8>>>,
                &mut dest_values,
            )?;
            assert_eq!(n_items_found, 0);
        }

        Ok(())
    }