Method lookup

crates/vm/src/dict_inner.rs:662–730

(
        &self,
        vm: &VirtualMachine,
        key: &K,
        hash_value: HashValue,
        mut lock: Option<PyRwLockReadGuard<'_, DictInner<T>>>,
    )

    /// Lookup the index for the given key.
    #[cfg_attr(feature = "flame-it", flame("Dict"))]
    fn lookup<K: DictKey + ?Sized>(
        &self,
        vm: &VirtualMachine,
        key: &K,
        hash_value: HashValue,
        mut lock: Option<PyRwLockReadGuard<'_, DictInner<T>>>,
    ) -> PyResult<LookupResult> {
        let mut idxs = None;
        let mut free_slot = None;
        let ret = 'outer: loop {
            let (entry_key, ret) = {
                let inner = lock.take().unwrap_or_else(|| self.read());
                let mask = (inner.indices.len() - 1) as i64;
                let idxs = idxs.get_or_insert_with(|| GenIndexes::new(hash_value, mask));
                if idxs.mask != mask {
                    // Dict was resized since last probe, restart
                    *idxs = GenIndexes::new(hash_value, mask);
                    free_slot = None;
                }
                loop {
                    let index_index = idxs.next();
                    let index_entry = *unsafe {
                        // Safety: index_index is generated
                        inner.indices.get_unchecked(index_index)
                    };
                    match index_entry {
                        IndexEntry::DUMMY => {
                            if free_slot.is_none() {
                                free_slot = Some(index_index);
                            }
                        }
                        IndexEntry::FREE => {
                            let idxs = match free_slot {
                                Some(free) => (IndexEntry::DUMMY, free),
                                None => (IndexEntry::FREE, index_index),
                            };
                            return Ok(idxs);
                        }
                        idx => {
                            let entry = unsafe {
                                // Safety: DUMMY and FREE are already handled above.
                                // i is always valid and entry always exists.
                                let i = idx.index().unwrap_unchecked();
                                inner.entries.get_unchecked(i).as_ref().unwrap_unchecked()
                            };
                            let ret = (idx, index_index);
                            if key.key_is(&entry.key) {
                                break 'outer ret;
                            } else if entry.hash == hash_value {
                                break (entry.key.clone(), ret);
                            } else {
                                // entry mismatch
                            }
                        }
                    }
                    // warn!("Perturb value: {}", i);
                }
            };