3 ms·

I wanted to drop strings which are not used anymore, you do need Rc for that (no way around it I think), but my problem was that I also needed that strings as a

I wanted to drop strings which are not used anymore, you do need Rc for that (no way around it I think), but my problem was that I also needed that strings as a key to HashMap<String, Weak<String>>. So I use that HashMap to check if the string is interned and give a new counted reference as needed and also periodically check any weak refs that should be dropped. This works, but the key better be immutable (I think?) so you cant do HashMap<Weak<String>, Weak<String>> (HashSet?) and hence need second copy as a key.

iudqnolq 5y ago
That's an interesting case. This won't solve your whole problem, but you should be able to make the key the hash of the string and then have a HashMap<u64, Weak<String>>. I feel like there's a pretty solution where you stick the whole map in a Rc and stick that in every interned string. Then strings can remove/lookup themselves. To make that work you'll want some sort of concurrent hash map.
- CraigJPerry 5y ago
  But how would you handle hash collisions if the value is just a Weak<String> rather than some kind of nested container type? I started thinking along the lines of an arena allocator, that would allow a shorter lifetime than static so you could remove unused references by dropping the arena and moving over still live references to a new arena. I guess arenas the wrong term with that behaviour, maybe generational mark and sweep garbage collector is closer to describing this approach. It a avoids the double reference though of the Rc<> model.
  - iudqnolq 5y ago
    You'd need to pick a hash that won't have collisions within your expected use. Edit: this might be interesting to you: https://docs.rs/crossbeam-epoch/0.9.4/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/0.9.4/crossbeam_epoch/
  - bombela 5y ago
    What about using a HashSet<Rc<str>>. And returning a type that implements Drop. The drop method can remove the string from the cache when the last reference is dropped. Since the cache must be accessed by the interning function and drop, I used interior mutability. By putting the cache behind a Rc<RefCell<>>. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=abfe8779f8dd5b8391489f5fa19c746c https://play.rust-lang.org/?version=stable&mode=debug&editio... With the same principle, we can use a static, arc and mutex to use a the cache as a global variable. And implement thread-safe string interning. Here, locking the cache at the wrong time during the drop can lead to a race condition. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=50d7697dd7abc69e756668962dbe36f9 https://play.rust-lang.org/?version=stable&mode=debug&editio... To make the InternedStr behaves a bit more like &str or an immutable String, I implemented Clone, Display, Pointer, conversion from &Interned to &str. Ideally it should probably resemble how String de-references to &str for everything (Deref<Target = str>).

iudqnolq 5y ago

That's an interesting case. This won't solve your whole problem, but you should be able to make the key the hash of the string and then have a HashMap<u64, Weak<String>>. I feel like there's a pretty solution where you stick the whole map in a Rc and stick that in every interned string. Then strings can remove/lookup themselves. To make that work you'll want some sort of concurrent hash map.

CraigJPerry 5y ago
But how would you handle hash collisions if the value is just a Weak<String> rather than some kind of nested container type? I started thinking along the lines of an arena allocator, that would allow a shorter lifetime than static so you could remove unused references by dropping the arena and moving over still live references to a new arena. I guess arenas the wrong term with that behaviour, maybe generational mark and sweep garbage collector is closer to describing this approach. It a avoids the double reference though of the Rc<> model.
- iudqnolq 5y ago
  You'd need to pick a hash that won't have collisions within your expected use. Edit: this might be interesting to you: https://docs.rs/crossbeam-epoch/0.9.4/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/0.9.4/crossbeam_epoch/
- bombela 5y ago
  What about using a HashSet<Rc<str>>. And returning a type that implements Drop. The drop method can remove the string from the cache when the last reference is dropped. Since the cache must be accessed by the interning function and drop, I used interior mutability. By putting the cache behind a Rc<RefCell<>>. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=abfe8779f8dd5b8391489f5fa19c746c https://play.rust-lang.org/?version=stable&mode=debug&editio... With the same principle, we can use a static, arc and mutex to use a the cache as a global variable. And implement thread-safe string interning. Here, locking the cache at the wrong time during the drop can lead to a race condition. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=50d7697dd7abc69e756668962dbe36f9 https://play.rust-lang.org/?version=stable&mode=debug&editio... To make the InternedStr behaves a bit more like &str or an immutable String, I implemented Clone, Display, Pointer, conversion from &Interned to &str. Ideally it should probably resemble how String de-references to &str for everything (Deref<Target = str>).