scheme_rs/
hashtables.rs

1//! Scheme compatible hashtables
2
3use indexmap::IndexSet;
4use parking_lot::RwLock;
5use std::{
6    collections::HashSet,
7    fmt,
8    hash::{DefaultHasher, Hash, Hasher},
9};
10
11use crate::{
12    exceptions::Exception,
13    gc::{Gc, Trace},
14    proc::Procedure,
15    registry::bridge,
16    strings::WideString,
17    symbols::Symbol,
18    value::{Expect1, Value, ValueType},
19};
20
21#[derive(Clone, Trace)]
22struct TableEntry {
23    key: Value,
24    val: Value,
25    hash: u64,
26}
27
28impl TableEntry {
29    fn get_hash(&self) -> u64 {
30        self.hash
31    }
32}
33
34#[derive(Trace)]
35pub(crate) struct HashTableInner {
36    /// Inner table of values. This uses an inner RwLock to ensure that we can
37    /// access eq and hash even if the table is locked.
38    ///
39    /// We can't use the std library hashmap since we don't want to bundle the
40    /// eq and hash functions with the key Value, so we use hashbrown's
41    /// HashTable
42    table: RwLock<hashbrown::HashTable<TableEntry>>,
43    /// Equivalence function.
44    eq: Procedure,
45    /// Hash function.
46    hash: Procedure,
47    /// Whether or not the hashtable is mutable
48    mutable: bool,
49}
50
51impl HashTableInner {
52    pub fn size(&self) -> usize {
53        self.table.read().len()
54    }
55
56    #[cfg(not(feature = "async"))]
57    pub fn hash(&self, val: Value) -> Result<u64, Exception> {
58        self.hash.call(&[val])?.expect1()
59    }
60
61    #[cfg(feature = "async")]
62    pub fn hash(&self, val: Value) -> Result<u64, Exception> {
63        self.hash.call_sync(&[val])?.expect1()
64    }
65
66    #[cfg(not(feature = "async"))]
67    pub fn eq(&self, lhs: Value, rhs: Value) -> Result<bool, Exception> {
68        self.eq.call(&[lhs, rhs])?.expect1()
69    }
70
71    #[cfg(feature = "async")]
72    pub fn eq(&self, lhs: Value, rhs: Value) -> Result<bool, Exception> {
73        self.eq.call_sync(&[lhs, rhs])?.expect1()
74    }
75
76    /// Equivalent to `hashtable-ref`
77    pub fn get(&self, key: &Value, default: &Value) -> Result<Value, Exception> {
78        let table = self.table.read();
79        let hash = self.hash(key.clone())?;
80        for entry in table.iter_hash(hash) {
81            if entry.hash == hash && self.eq(key.clone(), entry.key.clone())? {
82                return Ok(entry.val.clone());
83            }
84        }
85        Ok(default.clone())
86    }
87
88    pub fn set(&self, key: &Value, val: &Value) -> Result<(), Exception> {
89        if !self.mutable {
90            return Err(Exception::error("hashtable is immutable"));
91        }
92
93        let mut table = self.table.write();
94        let hash = self.hash(key.clone())?;
95        for entry in table.iter_hash_mut(hash) {
96            if entry.hash == hash && self.eq(key.clone(), entry.key.clone())? {
97                entry.val = val.clone();
98                return Ok(());
99            }
100        }
101
102        // Insert the new entry, guaranteed to be unique.
103        table.insert_unique(
104            hash,
105            TableEntry {
106                key: key.clone(),
107                val: val.clone(),
108                hash,
109            },
110            TableEntry::get_hash,
111        );
112
113        Ok(())
114    }
115
116    pub fn delete(&self, key: &Value) -> Result<(), Exception> {
117        if !self.mutable {
118            return Err(Exception::error("hashtable is immutable"));
119        }
120
121        let mut table = self.table.write();
122        let hash = self.hash(key.clone())?;
123        let buckets = table.iter_hash_buckets(hash).collect::<Vec<_>>();
124        for bucket in buckets.into_iter() {
125            if let Ok(entry) = table.get_bucket_entry(bucket)
126                && let inner = entry.get()
127                && inner.hash == hash
128                && self.eq(key.clone(), inner.key.clone())?
129            {
130                entry.remove();
131                return Ok(());
132            }
133        }
134
135        Ok(())
136    }
137
138    pub fn contains(&self, key: &Value) -> Result<bool, Exception> {
139        let table = self.table.write();
140        let hash = self.hash(key.clone())?;
141        for entry in table.iter_hash(hash) {
142            if entry.hash == hash && self.eq(key.clone(), entry.key.clone())? {
143                return Ok(true);
144            }
145        }
146
147        Ok(false)
148    }
149
150    pub fn update(&self, key: &Value, proc: &Procedure, default: &Value) -> Result<(), Exception> {
151        use std::slice;
152
153        if !self.mutable {
154            return Err(Exception::error("hashtable is immutable"));
155        }
156
157        let mut table = self.table.write();
158        let hash = self.hash(key.clone())?;
159        for entry in table.iter_hash_mut(hash) {
160            if entry.hash == hash && self.eq(key.clone(), entry.key.clone())? {
161                #[cfg(not(feature = "async"))]
162                let updated = proc.call(slice::from_ref(&entry.val))?[0].clone();
163
164                #[cfg(feature = "async")]
165                let updated = proc.call_sync(slice::from_ref(&entry.val))?[0].clone();
166
167                entry.val = updated;
168                return Ok(());
169            }
170        }
171
172        #[cfg(not(feature = "async"))]
173        let updated = proc.call(slice::from_ref(default))?[0].clone();
174
175        #[cfg(feature = "async")]
176        let updated = proc.call_sync(slice::from_ref(default))?[0].clone();
177
178        table.insert_unique(
179            hash,
180            TableEntry {
181                key: key.clone(),
182                val: updated,
183                hash,
184            },
185            TableEntry::get_hash,
186        );
187
188        Ok(())
189    }
190
191    pub fn copy(&self, mutable: bool) -> Self {
192        Self {
193            table: RwLock::new(self.table.read().clone()),
194            eq: self.eq.clone(),
195            hash: self.hash.clone(),
196            mutable,
197        }
198    }
199
200    pub fn clear(&self) -> Result<(), Exception> {
201        if !self.mutable {
202            return Err(Exception::error("hashtable is immutable"));
203        }
204
205        self.table.write().clear();
206
207        Ok(())
208    }
209
210    pub fn keys(&self) -> Vec<Value> {
211        self.table
212            .read()
213            .iter()
214            .map(|entry| entry.key.clone())
215            .collect()
216    }
217
218    pub fn entries(&self) -> (Vec<Value>, Vec<Value>) {
219        self.table
220            .read()
221            .iter()
222            .map(|entry| (entry.key.clone(), entry.val.clone()))
223            .unzip()
224    }
225}
226
227#[derive(Clone, Trace)]
228pub struct HashTable(pub(crate) Gc<HashTableInner>);
229
230impl HashTable {
231    /*
232    pub fn new_eq() -> Self {
233        todo!()
234    }
235
236    pub fn new_eqv() -> Self {
237        todo!()
238    }
239
240    pub fn new_equal() -> Self {
241        todo!()
242    }
243    */
244
245    pub fn new(hash: Procedure, eq: Procedure) -> Self {
246        Self(Gc::new(HashTableInner {
247            table: RwLock::new(hashbrown::HashTable::new()),
248            eq,
249            hash,
250            mutable: true,
251        }))
252    }
253
254    pub fn with_capacity(hash: Procedure, eq: Procedure, cap: usize) -> Self {
255        Self(Gc::new(HashTableInner {
256            table: RwLock::new(hashbrown::HashTable::with_capacity(cap)),
257            eq,
258            hash,
259            mutable: true,
260        }))
261    }
262
263    pub fn size(&self) -> usize {
264        self.0.size()
265    }
266
267    pub fn get(&self, key: &Value, default: &Value) -> Result<Value, Exception> {
268        self.0.get(key, default)
269    }
270
271    pub fn set(&self, key: &Value, val: &Value) -> Result<(), Exception> {
272        self.0.set(key, val)
273    }
274
275    pub fn delete(&self, key: &Value) -> Result<(), Exception> {
276        self.0.delete(key)
277    }
278
279    pub fn contains(&self, key: &Value) -> Result<bool, Exception> {
280        self.0.contains(key)
281    }
282
283    pub fn update(&self, key: &Value, proc: &Procedure, default: &Value) -> Result<(), Exception> {
284        self.0.update(key, proc, default)
285    }
286
287    pub fn copy(&self, mutable: bool) -> Self {
288        Self(Gc::new(self.0.copy(mutable)))
289    }
290
291    pub fn clear(&self) -> Result<(), Exception> {
292        self.0.clear()
293    }
294
295    pub fn keys(&self) -> Vec<Value> {
296        self.0.keys()
297    }
298
299    pub fn entries(&self) -> (Vec<Value>, Vec<Value>) {
300        self.0.entries()
301    }
302}
303
304impl fmt::Debug for HashTable {
305    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
306        write!(f, "#hash(")?;
307        for (i, entry) in self.0.table.read().iter().enumerate() {
308            if i > 0 {
309                write!(f, " ")?;
310            }
311            write!(f, "({:?} . {:?})", entry.key, entry.val)?;
312        }
313        write!(f, ")")
314    }
315}
316
317#[derive(Default, Trace)]
318pub struct EqualHashSet {
319    set: HashSet<EqualValue>,
320}
321
322impl EqualHashSet {
323    pub fn new() -> Self {
324        Self::default()
325    }
326
327    pub fn insert(&mut self, new_value: Value) {
328        let new_value = EqualValue(new_value);
329        if !self.set.contains(&new_value) {
330            self.set.insert(new_value);
331        }
332    }
333
334    pub fn get(&mut self, val: &Value) -> &Value {
335        let val = EqualValue(val.clone());
336        &self.set.get(&val).unwrap().0
337    }
338}
339
340#[derive(Clone, Eq, Trace)]
341pub struct EqualValue(pub Value);
342
343impl PartialEq for EqualValue {
344    fn eq(&self, rhs: &Self) -> bool {
345        self.0.equal(&rhs.0)
346    }
347}
348
349impl Hash for EqualValue {
350    fn hash<H: Hasher>(&self, state: &mut H) {
351        self.0.equal_hash(&mut IndexSet::new(), state)
352    }
353}
354
355#[bridge(name = "make-hashtable", lib = "(rnrs hashtables builtins (6))")]
356pub fn make_hashtable(
357    hash_function: &Value,
358    equiv: &Value,
359    rest: &[Value],
360) -> Result<Vec<Value>, Exception> {
361    let hash: Procedure = hash_function.clone().try_into()?;
362    let equiv: Procedure = equiv.clone().try_into()?;
363    let k = match rest {
364        [] => None,
365        [k] => Some(k.try_into()?),
366        x => return Err(Exception::wrong_num_of_args(3, 2 + x.len())),
367    };
368    let hashtable = if let Some(k) = k {
369        HashTable::with_capacity(hash, equiv, k)
370    } else {
371        HashTable::new(hash, equiv)
372    };
373    Ok(vec![Value::from(hashtable)])
374}
375
376#[bridge(name = "hashtable?", lib = "(rnrs hashtables builtins (6))")]
377pub fn hashtable_pred(hashtable: &Value) -> Result<Vec<Value>, Exception> {
378    Ok(vec![Value::from(
379        hashtable.type_of() == ValueType::HashTable,
380    )])
381}
382
383#[bridge(name = "hashtable-size", lib = "(rnrs hashtables builtins (6))")]
384pub fn hashtable_size(hashtable: &Value) -> Result<Vec<Value>, Exception> {
385    let hashtable: HashTable = hashtable.clone().try_into()?;
386    Ok(vec![Value::from(hashtable.size())])
387}
388
389#[bridge(name = "hashtable-ref", lib = "(rnrs hashtables builtins (6))")]
390pub fn hashtable_ref(
391    hashtable: &Value,
392    key: &Value,
393    default: &Value,
394) -> Result<Vec<Value>, Exception> {
395    let hashtable: HashTable = hashtable.clone().try_into()?;
396    Ok(vec![hashtable.get(key, default)?])
397}
398
399#[bridge(name = "hashtable-set!", lib = "(rnrs hashtables builtins (6))")]
400pub fn hashtable_set_bang(
401    hashtable: &Value,
402    key: &Value,
403    obj: &Value,
404) -> Result<Vec<Value>, Exception> {
405    let hashtable: HashTable = hashtable.clone().try_into()?;
406    hashtable.set(key, obj)?;
407    Ok(Vec::new())
408}
409
410#[bridge(name = "hashtable-delete!", lib = "(rnrs hashtables builtins (6))")]
411pub fn hashtable_delete_bang(hashtable: &Value, key: &Value) -> Result<Vec<Value>, Exception> {
412    let hashtable: HashTable = hashtable.clone().try_into()?;
413    hashtable.delete(key)?;
414    Ok(Vec::new())
415}
416
417#[bridge(name = "hashtable-contains?", lib = "(rnrs hashtables builtins (6))")]
418pub fn hashtable_contains_pred(hashtable: &Value, key: &Value) -> Result<Vec<Value>, Exception> {
419    let hashtable: HashTable = hashtable.clone().try_into()?;
420    Ok(vec![Value::from(hashtable.contains(key)?)])
421}
422
423#[bridge(name = "hashtable-update!", lib = "(rnrs hashtables builtins (6))")]
424pub fn hashtable_update_bang(
425    hashtable: &Value,
426    key: &Value,
427    proc: &Value,
428    default: &Value,
429) -> Result<Vec<Value>, Exception> {
430    let hashtable: HashTable = hashtable.clone().try_into()?;
431    let proc: Procedure = proc.clone().try_into()?;
432    hashtable.update(key, &proc, default)?;
433    Ok(Vec::new())
434}
435
436#[bridge(name = "hashtable-copy", lib = "(rnrs hashtables builtins (6))")]
437pub fn hashtable_copy(hashtable: &Value, rest: &[Value]) -> Result<Vec<Value>, Exception> {
438    let hashtable: HashTable = hashtable.clone().try_into()?;
439    let mutable = match rest {
440        [] => false,
441        [mutable] => mutable.is_true(),
442        x => return Err(Exception::wrong_num_of_args(2, 1 + x.len())),
443    };
444    let new_hashtable = hashtable.copy(mutable);
445    Ok(vec![Value::from(new_hashtable)])
446}
447
448#[bridge(name = "hashtable-clear!", lib = "(rnrs hashtables builtins (6))")]
449pub fn hashtable_clear_bang(hashtable: &Value, rest: &[Value]) -> Result<Vec<Value>, Exception> {
450    let hashtable: HashTable = hashtable.clone().try_into()?;
451    let k = match rest {
452        [] => None,
453        [k] => Some(k.try_into()?),
454        x => return Err(Exception::wrong_num_of_args(3, 2 + x.len())),
455    };
456
457    hashtable.clear()?;
458
459    if let Some(k) = k {
460        let mut table = hashtable.0.table.write();
461        if table.capacity() < k {
462            table.shrink_to(k, TableEntry::get_hash);
463        } else {
464            table.reserve(k, TableEntry::get_hash);
465        }
466    }
467
468    Ok(Vec::new())
469}
470
471#[bridge(name = "hashtable-keys", lib = "(rnrs hashtables builtins (6))")]
472pub fn hashtable_keys(hashtable: &Value) -> Result<Vec<Value>, Exception> {
473    let hashtable: HashTable = hashtable.clone().try_into()?;
474    let keys = Value::from(hashtable.keys());
475    Ok(vec![keys])
476}
477
478#[bridge(name = "hashtable-entries", lib = "(rnrs hashtables builtins (6))")]
479pub fn hashtable_entries(hashtable: &Value) -> Result<Vec<Value>, Exception> {
480    let hashtable: HashTable = hashtable.clone().try_into()?;
481    let (keys, values) = hashtable.entries();
482    Ok(vec![Value::from(keys), Value::from(values)])
483}
484
485#[bridge(
486    name = "hashtable-equivalence-function",
487    lib = "(rnrs hashtables builtins (6))"
488)]
489pub fn hashtable_equivalence_function(hashtable: &Value) -> Result<Vec<Value>, Exception> {
490    let hashtable: HashTable = hashtable.clone().try_into()?;
491    let eqv_func = Value::from(hashtable.0.eq.clone());
492    Ok(vec![eqv_func])
493}
494
495#[bridge(
496    name = "hashtable-hash-function",
497    lib = "(rnrs hashtables builtins (6))"
498)]
499pub fn hashtable_hash_function(hashtable: &Value) -> Result<Vec<Value>, Exception> {
500    let hashtable: HashTable = hashtable.clone().try_into()?;
501    let hash_func = Value::from(hashtable.0.hash.clone());
502    Ok(vec![hash_func])
503}
504
505#[bridge(name = "hashtable-mutable?", lib = "(rnrs hashtables builtins (6))")]
506pub fn hashtable_mutable_pred(hashtable: &Value) -> Result<Vec<Value>, Exception> {
507    let hashtable: HashTable = hashtable.clone().try_into()?;
508    let is_mutable = Value::from(hashtable.0.mutable);
509    Ok(vec![is_mutable])
510}
511
512#[bridge(name = "eq-hash", lib = "(rnrs hashtables builtins (6))")]
513pub fn eq_hash(obj: &Value) -> Result<Vec<Value>, Exception> {
514    let mut hasher = DefaultHasher::new();
515    obj.eq_hash(&mut hasher);
516    Ok(vec![Value::from(hasher.finish())])
517}
518
519#[bridge(name = "eqv-hash", lib = "(rnrs hashtables builtins (6))")]
520pub fn eqv_hash(obj: &Value) -> Result<Vec<Value>, Exception> {
521    let mut hasher = DefaultHasher::new();
522    obj.eqv_hash(&mut hasher);
523    Ok(vec![Value::from(hasher.finish())])
524}
525
526#[bridge(name = "equal-hash", lib = "(rnrs hashtables builtins (6))")]
527pub fn equal_hash(obj: &Value) -> Result<Vec<Value>, Exception> {
528    let mut hasher = DefaultHasher::new();
529    obj.equal_hash(&mut IndexSet::default(), &mut hasher);
530    Ok(vec![Value::from(hasher.finish())])
531}
532
533#[bridge(name = "string-hash", lib = "(rnrs hashtables builtins (6))")]
534pub fn string_hash(string: &Value) -> Result<Vec<Value>, Exception> {
535    let string: WideString = string.clone().try_into()?;
536    let mut hasher = DefaultHasher::new();
537    string.hash(&mut hasher);
538    Ok(vec![Value::from(hasher.finish())])
539}
540
541#[bridge(name = "string-ci-hash", lib = "(rnrs hashtables builtins (6))")]
542pub fn string_ci_hash(string: &Value) -> Result<Vec<Value>, Exception> {
543    let string: WideString = string.clone().try_into()?;
544    let mut hasher = DefaultHasher::new();
545    let chars = string.0.chars.read();
546    hasher.write_usize(chars.len());
547    for lowercase in chars.iter().copied().flat_map(char::to_lowercase) {
548        lowercase.hash(&mut hasher);
549    }
550    Ok(vec![Value::from(hasher.finish())])
551}
552
553#[bridge(name = "symbol-hash", lib = "(rnrs hashtables builtins (6))")]
554pub fn symbol_hash(symbol: &Value) -> Result<Vec<Value>, Exception> {
555    let symbol: Symbol = symbol.clone().try_into()?;
556    let mut hasher = DefaultHasher::new();
557    symbol.hash(&mut hasher);
558    Ok(vec![Value::from(hasher.finish())])
559}
scheme_rs/hashtables.rs

scheme_rs/
hashtables.rs
