symtern/
basic.rs

1// Copyright (C) 2016 Symtern Project Contributors
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-Apache
4// or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
5// license <LICENSE-MIT or http://opensource.org/licenses/MIT>,
6// at your option. This file may not be copied, modified, or
7// distributed except according to those terms.
8//! Basic hash-based generic interner.
9
10use std::hash::Hash;
11use std::borrow::{Borrow, ToOwned};
12#[cfg(debug_assertions)] use std::sync::atomic::{self, AtomicUsize, Ordering};
13
14use traits::{Intern, Resolve, ResolveUnchecked, Len, SymbolId};
15use {core, Result, ErrorKind};
16use sym::{Symbol as ISymbol, Pool as IPool};
17
18
19#[cfg(debug_assertions)]
20static NEXT_POOL_ID: AtomicUsize = atomic::ATOMIC_USIZE_INIT;
21
22
23#[cfg(feature = "fnv")]
24type HashMap<K, V> = ::fnv::FnvHashMap<K, V>;
25
26#[cfg(not(feature = "fnv"))]
27type HashMap<K, V> = ::std::collections::HashMap<K, V>;
28
29make_sym! {
30    pub Sym<I>:
31    "Symbol type used by [`Pool`](struct.Pool.html)'s [`Intern`](../traits/trait.Intern.html) and [`Resolve`](../traits/trait.Resolve.html) implementations.";
32}
33
34/// Simple hash-based interner generic over both the type of interned values
35/// and the type used to represent symbol IDs.
36///
37/// `Pool` can intern any type that implements `ToOwned`, `Eq`, and `Hash`,
38/// where its owned type (`ToOwned::Owned`) also implements `Eq` and `Hash`.
39///
40/// ```rust file="examples/you-can-intern-anything.rs"
41/// use symtern::prelude::*;
42/// use symtern::Pool;
43///
44/// #[derive(Clone, Eq, PartialEq, Hash)]
45/// struct WibbleWobble {
46///     whee: Vec<u32>
47/// }
48///
49/// let mut pool = Pool::<_,u8>::new();
50/// assert!(pool.intern(&WibbleWobble{whee: vec![1, 2, 3, 4, 5]}).is_ok());
51/// ```
52#[derive(Debug)]
53pub struct Pool<T: ?Sized, I = usize>
54    where T: ToOwned + Eq + Hash,
55          T::Owned: Eq + Hash,
56          I: SymbolId
57{
58    ids_map: HashMap<u64, I>,
59    lookup_vec: Vec<T::Owned>,
60    #[cfg(debug_assertions)]
61    pool_id: usize
62}
63
64impl<T: ?Sized, I> Clone for Pool<T, I>
65    where T: ToOwned + Eq + Hash,
66          T::Owned: Eq + Hash + Clone,
67          I: SymbolId,
68{
69    #[cfg(debug_assertions)]
70    fn clone(&self) -> Self {
71        Pool{ids_map: self.ids_map.clone(),
72             lookup_vec: self.lookup_vec.clone(),
73             pool_id: self.pool_id}
74    }
75    #[cfg(not(debug_assertions))]
76    fn clone(&self) -> Self {
77        Pool{ids_map: self.ids_map.clone(),
78             lookup_vec: self.lookup_vec.clone()}
79    }
80}
81
82// (inherent impl)
83impl<T: ?Sized, I> Pool<T, I>
84    where T: ToOwned + Eq + Hash,
85          T::Owned: Eq + Hash,
86          I: SymbolId
87{
88    /// Create a new, empty `Pool` instance.
89    pub fn new() -> Self {
90        Default::default()
91    }
92}
93
94impl<'a, T: ?Sized, I> Len for Pool<T, I>
95    where T: ToOwned + Eq + Hash,
96          T::Owned: Eq + Hash,
97          I: SymbolId
98{
99    /// Get the number of entries contained in the pool.
100    fn len(&self) -> usize {
101        self.lookup_vec.len()
102    }
103
104    /// Check if the pool is "empty", i.e. has zero stored values.
105    fn is_empty(&self) -> bool {
106        self.lookup_vec.is_empty()
107    }
108
109    /// Check if the number of interned symbols has reached the maximum allowed
110    /// for the pool's ID type.
111    fn is_full(&self) -> bool {
112        // Symbol IDs range from 0 to M, where M is given by `I::max_value()`;
113        // hence a pool containing N entries is full iff N == M + 1.
114        let len = self.len();
115        len >= 1 && len - 1 >= I::max_value().to_usize().expect("Unexpected failure to convert index type `max_value()` result to usize")
116    }
117}
118
119impl<'a, T: ?Sized, I> ::sym::Pool for Pool<T, I>
120    where T: ToOwned + Eq + Hash,
121          T::Owned: Eq + Hash,
122          I: SymbolId
123{
124    type Symbol = Sym<I>;
125
126    #[cfg(debug_assertions)]
127    fn id(&self) -> ::sym::PoolId {
128        self.pool_id
129    }
130
131    #[cfg(not(debug_assertions))]
132    fn create_symbol(&self, id: <Self::Symbol as ::sym::Symbol>::Id) -> Self::Symbol {
133        Sym::create(id)
134    }
135
136    #[cfg(debug_assertions)]
137    fn create_symbol(&self, id: <Self::Symbol as ::sym::Symbol>::Id) -> Self::Symbol {
138        Sym::create(id, self.id())
139    }
140}
141
142// Default
143impl<T: ?Sized, I> Default for Pool<T, I>
144    where T: ToOwned + Eq + Hash,
145          T::Owned: Eq + Hash,
146          I: SymbolId
147{
148    #[cfg(not(debug_assertions))]
149    fn default() -> Self {
150        Pool{ids_map: Default::default(),
151             lookup_vec: Default::default()}
152    }
153    #[cfg(debug_assertions)]
154    fn default() -> Self {
155        Pool{ids_map: Default::default(),
156             lookup_vec: Default::default(),
157             pool_id: NEXT_POOL_ID.fetch_add(1, Ordering::SeqCst)}
158    }
159}
160
161// Intern
162impl<'a, T: ?Sized, I> Intern for &'a mut Pool<T, I>
163    where I: SymbolId,
164          T: ToOwned + Eq + Hash,
165          T::Owned: Eq + Hash + Borrow<T>,
166{
167    type Input = T;
168    type Symbol = Sym<I>;
169
170    fn intern(mut self, value: &Self::Input) -> Result<Self::Symbol> {
171        let key = core::hash::<T, core::DefaultHashAlgo>(value);
172        if let Some(&id) = self.ids_map.get(&key) {
173            return Ok(self.create_symbol(id))
174        } else if self.is_full() {
175            return Err(ErrorKind::PoolOverflow.into())
176        } else {
177            self.lookup_vec.push(value.to_owned());
178
179            // We do not expect this conversion to fail, since the condition in
180            // the previous branch (`is_full()`) checks if a new ID would be
181            // a representable value.
182            let id = I::from_usize(self.lookup_vec.len() - 1)
183                .expect("Unexpected failure to convert symbol ID from usize");
184            self.ids_map.insert(key, id);
185
186            Ok(self.create_symbol(id))
187        }
188    }
189}
190
191#[cfg(debug_assertions)]
192macro_rules! check_matching_pool {
193    ($slf: ident, $sym: ident) => {
194        if $sym.pool_id() != $slf.id() {
195            panic!(concat!("\nDetected an invalid attempt to resolve a symbol on a pool that did not\n",
196                           "create it.  This is a bug in the program or library using Symtern; do not\n",
197                           "report it to the Symtern developers."));
198        }
199    };
200}
201
202#[cfg(not(debug_assertions))]
203macro_rules! check_matching_pool {
204    ($slf: ident, $sym: ident) => {};
205}
206
207// ----------------------------------------------------------------
208// Resolve
209impl<'a,T: ?Sized, I> Resolve for &'a Pool<T, I>
210    where T: ToOwned + Eq + Hash,
211          T::Owned: Eq + Hash + Borrow<T>,
212          I: SymbolId
213{
214    type Input = <&'a mut Pool<T, I> as Intern>::Symbol;
215    type Output = &'a T;
216
217    fn resolve(self, s: Self::Input) -> Result<Self::Output> {
218        check_matching_pool!(self, s);
219        // We previously converted the ID _from_ a usize, so this conversion should _not_ fail.
220        let idx = s.id().to_usize().expect("Unexpected failure to convert symbol ID to usize");
221
222        if self.lookup_vec.len() > idx {
223            Ok(self.lookup_vec[idx].borrow())
224        } else {
225            Err(ErrorKind::NoSuchSymbol.into())
226        }
227    }
228}
229impl<'a, T: ?Sized, I> ResolveUnchecked for &'a Pool<T, I>
230    where T: ToOwned + Eq + Hash,
231          T::Owned: Eq + Hash + Borrow<T>,
232          I: SymbolId
233{
234    unsafe fn resolve_unchecked(self, symbol: Self::Input) -> Self::Output {
235        let idx = symbol.id().to_usize().expect("Unexpected failure to convert symbol ID to usize");
236        self.lookup_vec.get_unchecked(idx).borrow()
237    }
238}
239
240
241#[cfg(test)]
242mod tests {
243    use super::Pool;
244    use traits::*;
245    use ErrorKind;
246
247    #[test]
248    fn resolve_returns_expected_results() {
249        let mut p1 = Pool::<str,u16>::new();
250        let mut p2 = Pool::<str,u16>::new();
251
252        let s1 = p1.intern("foo").unwrap();
253        let s2 = p2.intern("bar").unwrap();
254
255        assert_eq!(Ok("foo"), p1.resolve(s1));
256        assert_eq!(Ok("bar"), p2.resolve(s2));
257    }
258
259    #[test]
260    fn has_expected_len_and_capacity() {
261        let mut pool = Pool::<u16,u8>::new();
262
263        assert!(pool.is_empty());
264
265        for i in 0u16..200 {
266            pool.intern(&i).expect("failed to intern value");
267        }
268        assert_eq!(200, pool.len());
269        assert!(! pool.is_full());
270
271        for i in 150u16..250 {
272            pool.intern(&i).expect("failed to intern value");
273        }
274        assert_eq!(250, pool.len());
275        assert!(! pool.is_full());
276
277        for i in 250u16..256 {
278            pool.intern(&i).expect("failed to intern value");
279        }
280        assert_eq!(256, pool.len());
281        assert!(pool.is_full());
282
283        // The pool is full, but interning previously-interned values should
284        // still result in Ok(_).
285        pool.intern(&123).expect("failed to intern previously-interned value");
286        match pool.intern(&456) {
287            Ok(_) => panic!("unexpected `Ok` when interning unseen value in full pool"),
288            Err(e) => assert_eq!(ErrorKind::PoolOverflow, e.kind()),
289        }
290    }
291}
symtern/basic.rs

symtern/
basic.rs
