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

/*
 * Copyright 2021 Actyx AG
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//! Interning library based on atomic reference counting
//!
//! This library differs from [`arc-interner`](https://crates.io/crates/arc-interner)
//! (which served as initial inspiration) in that
//!
//!  - interners must be created and can be dropped (for convenience functions see below)
//!  - it does not dispatch based on [`TypeId`](https://doc.rust-lang.org/std/any/struct.TypeId.html)
//!    (each interner is for exactly one type)
//!  - it offers both [`Hash`](https://doc.rust-lang.org/std/hash/trait.Hash.html)-based
//!    and [`Ord`](https://doc.rust-lang.org/std/cmp/trait.Ord.html)-based storage
//!  - it handles unsized types without overhead, so you should inline
//!    [`str`](https://doc.rust-lang.org/std/primitive.str.html) instead of
//!    [`String`](https://doc.rust-lang.org/std/string/struct.String.html)
//!
//! Unfortunately, this combination of features makes it inevitable to use unsafe Rust.
//! The construction of unsized values has been adapted from the standard library’s
//! [`Arc`](https://doc.rust-lang.org/std/sync/struct.Arc.html) type; reference counting
//! employs a [`parking_lot`](https://docs.rs/parking_lot) mutex since it must also ensure
//! consistent access to and usage of the cleanup function that will remove the value from its interner.
//! The test suite passes also under [miri](https://github.com/rust-lang/miri) to
//! check against some classes of undefined behavior in the unsafe code (including memory leaks).
//!
//! ## API flavors
//!
//! The same API is provided in two flavors:
//!
//!  - [`HashInterner`](struct.HashInterner.html) uses hash-based storage, namely the standard
//!    [`HashSet`](https://doc.rust-lang.org/std/collections/struct.HashSet.html)
//!  - [`OrdInterner`](struct.OrdInterner.html) uses ord-based storage, namely the standard
//!    [`BTreeSet`](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html)
//!
//! Interning small values takes of the order of 100–200ns on a typical server CPU. The ord-based
//! storage has an advantage when interning large values (like slices greater than 1kB). The
//! hash-based storage has an advantage when keeping lots of values (many thousands and up)
//! interned at the same time.
//!
//! Nothing beats your own benchmarking, though.
//!
//! ## Convenience access to interners
//!
//! When employing interning for example within a dedicated deserialiser thread, it is best to create
//! and locally use an interner, avoiding further synchronisation overhead. You can also store interners
//! in thread-local variables if you only care about deduplication per thread.
//!
//! That said, this crate also provides convenience functions based on a global type-indexed pool:
//!
//! ```
//! use intern_arc::{global::hash_interner};
//!
//! let i1 = hash_interner().intern_ref("hello"); // -> InternedHash<str>
//! let i2 = hash_interner().intern_sized(vec![1, 2, 3]); // -> InternedHash<Vec<i32>>
//! # use std::any::{Any, TypeId}; // using TypeId to avoid influencing type interence
//! # use intern_arc::InternedHash;
//! # assert_eq!(i1.type_id(), TypeId::of::<InternedHash<str>>());
//! # assert_eq!(i2.type_id(), TypeId::of::<InternedHash<Vec<i32>>>());
//! ```
//!
//! You can also use the type-indexed pool yourself to control its lifetime:
//!
//! ```
//! use intern_arc::{global::OrdInternerPool, InternedOrd};
//!
//! let mut pool = OrdInternerPool::new();
//! let i: InternedOrd<[u8]> = pool.get_or_create().intern_box(vec![1, 2, 3].into());
//! ```
#![doc(html_logo_url = "https://developer.actyx.com/img/logo.svg")]
#![doc(html_favicon_url = "https://developer.actyx.com/img/favicon.ico")]

pub mod global;
mod hash;
mod ref_count;
mod tree;

pub use hash::{HashInterner, InternedHash};
pub use tree::{InternedOrd, OrdInterner};

#[cfg(loom)]
mod loom {
    pub use ::loom::{
        alloc::{alloc, dealloc, Layout},
        sync::{
            atomic::{spin_loop_hint, AtomicPtr, AtomicUsize, Ordering::*},
            MutexGuard, RwLock,
        },
        thread::{current, yield_now},
    };

    pub struct Mutex<T>(::loom::sync::Mutex<T>);
    impl<T> Mutex<T> {
        pub fn new(t: T) -> Self {
            Self(::loom::sync::Mutex::new(t))
        }
        pub fn lock(&self) -> MutexGuard<'_, T> {
            self.0.lock().unwrap()
        }
    }
}

#[cfg(not(loom))]
mod loom {
    pub use parking_lot::{Mutex, MutexGuard, RwLock, RwLockUpgradableReadGuard};
    pub use std::{
        alloc::{alloc, dealloc, Layout},
        sync::atomic::{spin_loop_hint, AtomicPtr, AtomicUsize, Ordering::*},
        thread::{current, yield_now},
    };
}