string_interner/
lib.rs

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
#![no_std]
#![doc(html_root_url = "https://docs.rs/crate/string-interner/0.18.0")]
#![warn(unsafe_op_in_unsafe_fn, clippy::redundant_closure_for_method_calls)]

//! 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.
//!
//! - **Fill:** Efficiency of filling an empty string interner.
//! - **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.
//! - **Contiguous:** True if the returned symbols have contiguous values.
//! - **Iteration:** Efficiency of iterating over the interned strings.
//!
//! | **Property** | **BucketBackend** | **StringBackend** | **BufferBackend** |
//! |:-------------|:-----------------:|:-----------------:|:-----------------:|
//! | **Fill**     | ok                | good              | best              |
//! | **Resolve**  | best              | good              | bad               |
//! | Allocations  | ok                | good              | best              |
//! | Footprint    | ok                | good              | best              |
//! | Contiguous   | yes               | yes               | no                |
//! | Iteration    | best              | good              | bad               |
//!
//! ## 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;
#[cfg(feature = "std")]
#[macro_use]
extern crate std;

#[cfg(feature = "serde")]
mod serde_impl;

pub mod backend;
mod interner;
pub mod symbol;

/// A convenience [`StringInterner`] type based on the [`DefaultBackend`].
#[cfg(feature = "backends")]
pub type DefaultStringInterner<B = DefaultBackend, H = DefaultHashBuilder> =
    self::interner::StringInterner<B, H>;

#[cfg(feature = "backends")]
#[doc(inline)]
pub use self::backend::DefaultBackend;
#[doc(inline)]
pub use self::{
    interner::StringInterner,
    symbol::{DefaultSymbol, Symbol},
};

#[doc(inline)]
pub use hashbrown::DefaultHashBuilder;