rusty_bubbles/internal/
memoization.rs

1//! Cleanroom Rust port of upstream Go source file: `internal/memoization/memoization.go`
2//! Upstream Target Tag / Version: `v2.1.0`
3
4use sha2::{Digest, Sha256};
5use std::collections::HashMap;
6
7/// Hasher is an interface that requires a Hash method. The Hash method is
8/// expected to return a string representation of the hash of the object.
9pub trait Hasher {
10    /// Hash returns the string representation of the hash of the object.
11    fn hash(&self) -> String;
12}
13
14struct Entry<T> {
15    #[allow(dead_code)]
16    key: String,
17    value: T,
18}
19
20/// MemoCache is a struct that represents a cache with a set capacity. It
21/// uses an LRU (Least Recently Used) eviction policy.
22pub struct MemoCache<T> {
23    capacity: usize,
24    cache: HashMap<String, Entry<T>>,
25    order: Vec<String>,
26}
27
28/// NewMemoCache is a function that creates a new MemoCache with a given
29/// capacity.
30pub fn new_memo_cache<T>(capacity: usize) -> MemoCache<T> {
31    MemoCache {
32        capacity,
33        cache: HashMap::new(),
34        order: Vec::new(),
35    }
36}
37
38impl<T> MemoCache<T> {
39    /// Capacity returns the capacity of the MemoCache.
40    pub fn capacity(&self) -> usize {
41        self.capacity
42    }
43
44    /// Size returns the current size of the MemoCache. It is the number of
45    /// items currently stored in the cache.
46    pub fn size(&self) -> usize {
47        self.order.len()
48    }
49
50    /// Get returns the value associated with the given hashable item in the
51    /// MemoCache. If there is no corresponding value, the method returns None.
52    pub fn get<H: Hasher>(&mut self, h: &H) -> Option<&T> {
53        let hashed_key = h.hash();
54        if let Some(entry) = self.cache.get(&hashed_key) {
55            // Move to front (most recently used).
56            if let Some(pos) = self.order.iter().position(|k| *k == hashed_key) {
57                let k = self.order.remove(pos);
58                self.order.push(k);
59            }
60            return Some(&entry.value);
61        }
62        None
63    }
64
65    /// Set sets the value for the given hashable item in the MemoCache. If
66    /// the cache is at capacity, it evicts the least recently used item
67    /// before adding the new item.
68    pub fn set<H: Hasher>(&mut self, h: &H, value: T) {
69        let hashed_key = h.hash();
70        if let Some(entry) = self.cache.get_mut(&hashed_key) {
71            entry.value = value;
72            if let Some(pos) = self.order.iter().position(|k| *k == hashed_key) {
73                let k = self.order.remove(pos);
74                self.order.push(k);
75            }
76            return;
77        }
78
79        // Check if the cache is at capacity
80        if self.order.len() >= self.capacity {
81            // Evict the least recently used item from the cache
82            if let Some(oldest) = self.order.first().cloned() {
83                self.order.remove(0);
84                self.cache.remove(&oldest);
85            }
86        }
87
88        let entry = Entry {
89            key: hashed_key.clone(),
90            value,
91        };
92        self.cache.insert(hashed_key.clone(), entry);
93        self.order.push(hashed_key);
94    }
95}
96
97/// HString is a type that implements the Hasher interface for strings.
98#[derive(Debug, Clone, PartialEq, Eq)]
99pub struct HString(pub String);
100
101impl Hasher for HString {
102    fn hash(&self) -> String {
103        let digest = Sha256::digest(self.0.as_bytes());
104        let mut s = String::new();
105        for b in digest.iter() {
106            s.push_str(&format!("{:02x}", b));
107        }
108        s
109    }
110}
111
112/// HInt is a type that implements the Hasher interface for integers.
113#[derive(Debug, Clone, Copy, PartialEq, Eq)]
114pub struct HInt(pub i64);
115
116impl Hasher for HInt {
117    fn hash(&self) -> String {
118        let digest = Sha256::digest(self.0.to_string().as_bytes());
119        let mut s = String::new();
120        for b in digest.iter() {
121            s.push_str(&format!("{:02x}", b));
122        }
123        s
124    }
125}
rusty_bubbles/internal/memoization.rs

rusty_bubbles/internal/
memoization.rs
