radix_trees 0.2.0

Various radix tree (trie) data structures.
Documentation 
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

use core::borrow::Borrow;

#[cfg(feature = "zerocopy")]
mod zerocopy_trait;

#[cfg(not(feature = "zerocopy"))]
mod unsafe_trait;

/// Trait definition for keys which are suitable to use in one of this crate's tries.
///
/// When implementing this trait yourself, the implementing type must NOT have interior mutability.
/// Phrased differently, for a non-mutable `T`, [`key_bytes`](TrieKey::key_bytes) must always return the
/// same value for the lifetime of that `T`.
///
/// When the `zerocopy` feature is included, this crate leverages [`zerocopy`](https://docs.rs/zerocopy) to offload unsafe
/// code and provide more blanket implementations for things like arrays and slices of data.
/// When `zerocopy` is not included, only basic sized primitives (plus slices and arrays of primitives)
/// are implemented.
pub trait TrieKey {
    /// Interpret this type as a sequence of bytes.
    ///
    /// All bytes in the returned slice must be readable and must not differ during subsequent
    /// calls by the same immutable object.
    fn key_bytes(&self) -> &[u8];
}

/// Key equivalence trait.
///
/// This trait allows trie lookup with key types that don't exactly match the stored key.
/// For example, this allows using `&str` to search a map with `String` keys, etc.
pub trait Equivalent<K: ?Sized> {}

impl<K: TrieKey, Q: TrieKey + Borrow<K>> Equivalent<K> for Q {}

// The below don't change based on zerocopy or not, so they can be here

impl TrieKey for str {
    fn key_bytes(&self) -> &[u8] {
        self.as_bytes()
    }
}

impl TrieKey for alloc::string::String {
    fn key_bytes(&self) -> &[u8] {
        self.as_bytes()
    }
}

impl TrieKey for core::ffi::CStr {
    fn key_bytes(&self) -> &[u8] {
        self.to_bytes()
    }
}

impl TrieKey for alloc::ffi::CString {
    fn key_bytes(&self) -> &[u8] {
        self.as_bytes()
    }
}

impl<K: TrieKey + ?Sized> TrieKey for alloc::boxed::Box<K> {
    fn key_bytes(&self) -> &[u8] {
        K::key_bytes(self)
    }
}

impl<K: TrieKey + ?Sized> TrieKey for alloc::sync::Arc<K> {
    fn key_bytes(&self) -> &[u8] {
        K::key_bytes(self)
    }
}

impl<K: TrieKey> TrieKey for alloc::vec::Vec<K>
where
    [K]: TrieKey,
{
    fn key_bytes(&self) -> &[u8] {
        self.as_slice().key_bytes()
    }
}

impl<K: TrieKey + ?Sized> TrieKey for &K {
    fn key_bytes(&self) -> &[u8] {
        (**self).key_bytes()
    }
}