1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

use crate::reference::*;
use crate::table::Table;
use crate::weak_entry::*;

pub struct TableVecSortedWeak<D, R, RW> {
    // Vector will be sorted by hash.
    // Entries with equivalent hash will be contiguous, but not sorted further.
    // We can do a binary search to find an entry with the given hash,
    // or the next position if not present.
    // The binary search will not necessarily find the first position with an equivalent hash, so
    // we need to do a linear scan in both directions while the hash is equivalent.
    v: Vec<WeakEntry<D, R, RW>>,
}

impl<D, R, RW> TableVecSortedWeak<D, R, RW>
where
    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
    R: Reference<D>,
    RW: ReferenceWeak<D, R>,
{
    fn linear_search<Range>(&self, range: Range, hash: u64, data: &D) -> Option<R>
    where
        // Range is necessary because the reverse iterator adapter is a different type.
        Range: Iterator<Item = usize>,
    {
        for x in range {
            let m = self.v[x].get_existing_near(hash, &data);
            match m {
                Err(()) => {
                    break;
                }
                Ok(y) => {
                    if let Some(p) = y {
                        return Some(p);
                    }
                }
            }
        }
        None
    }
    fn linear_search_up(&self, idx: usize, hash: u64, data: &D) -> Option<R> {
        self.linear_search(idx..self.v.len(), hash, data)
    }
    fn linear_search_down(&self, idx: usize, hash: u64, data: &D) -> Option<R> {
        self.linear_search((0..idx).rev(), hash, data)
    }
    fn linear_search_around(&self, idx: usize, hash: u64, data: &D) -> Option<R> {
        // Start with up, because up will include idx.
        self.linear_search_up(idx, hash, data)
            .or_else(|| self.linear_search_down(idx, hash, data))
    }
}

impl<D, R, RW> Default for TableVecSortedWeak<D, R, RW>
where
    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
    R: Reference<D>,
    RW: ReferenceWeak<D, R>,
{
    fn default() -> Self {
        Self { v: Vec::new() }
    }
}

impl<D, R, RW> Table<D, R> for TableVecSortedWeak<D, R, RW>
where
    D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
    R: Reference<D>,
    RW: ReferenceWeak<D, R>,
{
    fn get(&self, hash: u64, data: &D) -> Option<R> {
        // Binary search
        let result = self.v.binary_search_by(|probe| probe.hash_cmp(&hash));
        match result {
            Ok(idx) => {
                // Linear search up and down
                if let Some(p) = self.linear_search_around(idx, hash, data) {
                    return Some(p);
                }
            }
            Err(_) => {}
        };
        None
    }

    fn get_or_insert<CF>(&mut self, hash: u64, mut data: D, creation_meta: CF) -> R
    where
        D: std::hash::Hash + std::cmp::Eq + std::fmt::Debug,
        CF: FnOnce(&mut D),
    {
        // Binary search
        let result = self.v.binary_search_by(|probe| probe.hash_cmp(&hash));
        let index = match result {
            Ok(idx) => {
                // Linear search up and down
                if let Some(p) = self.linear_search_around(idx, hash, &data) {
                    return p;
                }
                idx
            }
            Err(idx) => idx,
        };

        creation_meta(&mut data);
        let obj = R::new(data);
        let weak = RW::weak_downgrade(&obj);
        self.v.insert(index, WeakEntry::new(hash, weak));

        return obj;
    }
}