1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//! Caches strings efficiently, with minimal memory footprint and associates them with unique symbols.
//! These symbols allow constant time comparisons and look-ups to the underlying interned strings.
//!
//! ### Example: Interning & Symbols
//!
//! ```
//! use string_interner::StringInterner;
//!
//! let mut interner = StringInterner::default();
//! let sym0 = interner.get_or_intern("Elephant");
//! let sym1 = interner.get_or_intern("Tiger");
//! let sym2 = interner.get_or_intern("Horse");
//! let sym3 = interner.get_or_intern("Tiger");
//! assert_ne!(sym0, sym1);
//! assert_ne!(sym0, sym2);
//! assert_ne!(sym1, sym2);
//! assert_eq!(sym1, sym3); // same!
//! ```
//!
//! ### Example: Creation by `FromIterator`
//!
//! ```
//! # use string_interner::DefaultStringInterner;
//! let interner = ["Elephant", "Tiger", "Horse", "Tiger"]
//! .into_iter()
//! .collect::<DefaultStringInterner>();
//! ```
//!
//! ### Example: Look-up
//!
//! ```
//! # use string_interner::StringInterner;
//! let mut interner = StringInterner::default();
//! let sym = interner.get_or_intern("Banana");
//! assert_eq!(interner.resolve(sym), Some("Banana"));
//! ```
//!
//! ### Example: Iteration
//!
//! ```
//! # use string_interner::{DefaultStringInterner, Symbol};
//! let interner = <DefaultStringInterner>::from_iter(["Earth", "Water", "Fire", "Air"]);
//! for (sym, str) in &interner {
//! println!("{} = {}", sym.to_usize(), str);
//! }
//! ```
//!
//! ### Example: Use Different Backend
//!
//! ```
//! # use string_interner::StringInterner;
//! use string_interner::backend::BufferBackend;
//! type Interner = StringInterner<BufferBackend>;
//! let mut interner = Interner::new();
//! let sym1 = interner.get_or_intern("Tiger");
//! let sym2 = interner.get_or_intern("Horse");
//! let sym3 = interner.get_or_intern("Tiger");
//! assert_ne!(sym1, sym2);
//! assert_eq!(sym1, sym3); // same!
//! ```
//!
//! ### Example: Use Different Backend & Symbol
//!
//! ```
//! # use string_interner::StringInterner;
//! use string_interner::{backend::BucketBackend, symbol::SymbolU16};
//! type Interner = StringInterner<BucketBackend<SymbolU16>>;
//! let mut interner = Interner::new();
//! let sym1 = interner.get_or_intern("Tiger");
//! let sym2 = interner.get_or_intern("Horse");
//! let sym3 = interner.get_or_intern("Tiger");
//! assert_ne!(sym1, sym2);
//! assert_eq!(sym1, sym3); // same!
//! ```
//!
//! ## Backends
//!
//! The `string_interner` crate provides different backends with different strengths.
//! The table below compactly shows when to use which backend according to the following
//! performance characteristics and properties.
//!
//! | **Property** | **BucketBackend** | **StringBackend** | **BufferBackend** | | Explanation |
//! |:-------------|:-----------------:|:-----------------:|:-----------------:|:--|:--|
//! | Fill | 🤷 | 👍 | ⭐ | | Efficiency of filling an empty string interner. |
//! | Fill Duplicates | 1) | 1) | 1) | | Efficiency of filling a string interner with strings that are already interned. |
//! | Resolve | ⭐ | 👍 | 👎 | | Efficiency of resolving a symbol of an interned string. |
//! | Allocations | 🤷 | 👍 | ⭐ | | The number of allocations performed by the backend. |
//! | Footprint | 🤷 | 👍 | ⭐ | | The total heap memory consumed by the backend. |
//! | Iteration | ⭐ | 👍 | 👎 | | Efficiency of iterating over the interned strings. |
//! | | | | | | |
//! | Contiguous | ✅ | ✅ | ❌ | | The returned symbols have contiguous values. |
//! | Stable Refs | ✅ | ❌ | ❌ | | The interned strings have stable references. |
//! | Static Strings | ✅ | ❌ | ❌ | | Allows to intern `&'static str` without heap allocations. |
//!
//! 1. Performance of interning pre-interned string is the same for all backends since
//! this is implemented in the `StringInterner` front-end via a `HashMap` query for
//! all `StringInterner` instances.
//!
//! ### Legend
//!
//! | ⭐ | **best performance** | 👍 | **good performance** | 🤷 | **okay performance** | 👎 | **bad performance** |
//! |-|-|-|-|-|-|-|-|
//!
//! ## When to use which backend?
//!
//! ### Bucket Backend
//!
//! Given the table above the `BucketBackend` might seem inferior to the other backends.
//! However, it allows to efficiently intern `&'static str` and avoids deallocations.
//!
//! ### String Backend
//!
//! Overall the `StringBackend` performs really well and therefore is the backend
//! that the `StringInterner` uses by default.
//!
//! ### Buffer Backend
//!
//! The `BufferBackend` is in some sense similar to the `StringBackend` on steroids.
//! Some operations are even slightly more efficient and it consumes less memory.
//! However, all this is at the costs of a less efficient resolution of symbols.
//! Note that the symbols generated by the `BufferBackend` are not contiguous.
extern crate alloc;
extern crate std;
/// A convenience [`StringInterner`] type based on the [`DefaultBackend`].
pub type DefaultStringInterner<B = DefaultBackend, H = DefaultHashBuilder> =
StringInterner;
pub use DefaultBackend;
pub use ;
pub use DefaultHashBuilder;