chisel_stringtable/
btree_string_table.rs

1//! Default implementation of a [StringTable] based on an internal B-Tree index, which maps `u64`
2//! hash values to owned [String] instances.  When you access a given value, you will be given a
3//! [Cow] preventing unnecessary allocations within immutable use cases.
4//!
5use std::borrow::Cow;
6use std::collections::BTreeMap;
7use std::collections::hash_map::DefaultHasher;
8use std::hash::Hasher;
9
10use crate::common::StringTable;
11
12/// Default implementation just maintains a btree keyed on a 64-bit fxhash value
13#[derive()]
14pub struct BTreeStringTable<'a>
15{
16    /// The internal map carrying the actual strings
17    index: BTreeMap<u64, Cow<'a, str>>,
18}
19
20impl<'a> BTreeStringTable<'a>
21{
22    /// Create a new string table with default initial capacity using the default hasher
23    pub fn new() -> Self {
24        BTreeStringTable {
25            index: BTreeMap::default(),
26        }
27    }
28
29    /// Hash a given string slice using the hasher
30    fn hash(&self, value: &str) -> u64 {
31        let mut hasher = DefaultHasher::default();
32        hasher.write(value.as_bytes());
33        hasher.finish()
34    }
35}
36
37impl<'a> Clone for BTreeStringTable<'a> {
38    /// Clone the contents of a given [BTreeStringTable] instance
39    fn clone(&self) -> Self {
40        BTreeStringTable {
41            index: self.index.clone(),
42        }
43    }
44}
45
46impl<'a> StringTable<'a, u64> for BTreeStringTable<'a> {
47    fn add(&mut self, value: &str) -> u64 {
48        let hash = self.hash(value);
49        if !self.index.contains_key(&hash) {
50            self.index.insert(hash, Cow::Owned(String::from(value)));
51        }
52        hash
53    }
54
55    fn remove(&mut self, key: u64) -> () {
56        if self.index.contains_key(&key) {
57            self.index.remove(&key);
58        }
59    }
60
61    fn get(&self, key: u64) -> Option<&Cow<'a, str>> {
62        self.index.get(&key)
63    }
64
65    fn len(&self) -> usize {
66        self.index.len()
67    }
68
69    fn contains(&self, value: &str) -> Option<u64> {
70        let hash = self.hash(value);
71        if self.index.contains_key(&hash) {
72            return Some(hash);
73        }
74        None
75    }
76
77    fn hash(&self, value: &str) -> u64 {
78        self.hash(value)
79    }
80}
chisel_stringtable/btree_string_table.rs

chisel_stringtable/
btree_string_table.rs
