Skip to content

Instantly share code, notes, and snippets.

@gkoz
Last active July 5, 2016 20:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gkoz/c122107c8d6ce4422b2fa312d44cc1ac to your computer and use it in GitHub Desktop.
Save gkoz/c122107c8d6ce4422b2fa312d44cc1ac to your computer and use it in GitHub Desktop.
String interner with arena PoC
extern crate typed_arena;
use typed_arena::Arena;
use std::borrow::Borrow;
use std::collections::HashSet;
use std::cell::RefCell;
use std::ops::Deref;
#[derive(Hash, Eq, PartialEq, Clone, Copy, Debug)]
// A `&String` is half as big as `&str` but accessing the string
// will involve one more indirection.
pub struct Symbol<'a>(&'a String);
// Make it possible to search a hash set with a `&str`.
impl<'a> Borrow<str> for Symbol<'a> {
fn borrow(&self) -> &str {
&self.0[..]
}
}
impl<'a> Deref for Symbol<'a> {
type Target = str;
fn deref(&self) -> &str {
&self.0[..]
}
}
pub struct SymbolTable<'a> {
arena: &'a Arena<String>,
set: RefCell<HashSet<Symbol<'a>>>,
}
impl<'a> SymbolTable<'a> {
pub fn new(arena: &Arena<String>) -> SymbolTable {
return SymbolTable {
arena: arena,
set: RefCell::new(HashSet::new()),
}
}
pub fn add(&self, name: &str) -> Symbol {
let mut set = self.set.borrow_mut();
if let Some(&sym) = set.get(name) {
return sym;
}
let sym = Symbol(self.arena.alloc(name.to_string()));
set.insert(sym);
sym
}
}
#[test]
fn test() {
let arena = Arena::new();
let t = SymbolTable::new(&arena);
let s1 = t.add("symbol1");
let s2 = t.add("symbol1");
let s3 = t.add("symbol2");
assert!(s1 == s2);
assert!(s1 != s3);
assert!(&*s1 == "symbol1");
assert!(&*s2 == "symbol1");
assert!(&*s3 == "symbol2");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment