Struct zerotrie::ZeroTrie

source ·
pub struct ZeroTrie<Store>(pub(crate) ZeroTrieFlavor<Store>);
Expand description

A data structure that compactly maps from byte sequences to integers.

There are several variants of ZeroTrie which are very similar but are optimized for different use cases:

  • ZeroTrieSimpleAscii is the most compact structure. Very fast for small data. Only stores ASCII-encoded strings. Can be const-constructed!
  • ZeroTriePerfectHash is also compact, but it also supports arbitrary binary strings. It also scales better to large data. Cannot be const-constructed.
  • ZeroTrieExtendedCapacity can be used if more than 2^32 bytes are required.

You can create a ZeroTrie directly, in which case the most appropriate backing implementation will be chosen.

§Backing Store

The data structure has a flexible backing data store. The only requirement for most functionality is that it implement AsRef<[u8]>. All of the following are valid ZeroTrie types:

  • ZeroTrie<[u8]> (dynamically sized type: must be stored in a reference or Box)
  • ZeroTrie<&[u8]> (borrows its data from a u8 buffer)
  • ZeroTrie<Vec<u8>> (fully owned data)
  • ZeroTrie<ZeroVec<u8>> (the recommended borrowed-or-owned signature)
  • Cow<ZeroTrie<[u8]>> (another borrowed-or-owned signature)
  • ZeroTrie<Cow<[u8]>> (another borrowed-or-owned signature)

§Examples

use litemap::LiteMap;
use zerotrie::ZeroTrie;

let mut map = LiteMap::<&[u8], usize>::new_vec();
map.insert("foo".as_bytes(), 1);
map.insert("bar".as_bytes(), 2);
map.insert("bazzoo".as_bytes(), 3);

let trie = ZeroTrie::try_from(&map)?;

assert_eq!(trie.get("foo"), Some(1));
assert_eq!(trie.get("bar"), Some(2));
assert_eq!(trie.get("bazzoo"), Some(3));
assert_eq!(trie.get("unknown"), None);

Tuple Fields§

§0: ZeroTrieFlavor<Store>

Implementations§

source§

impl<Store> ZeroTrie<Store>

source

pub fn take_store(self) -> Store

Takes the byte store from this trie.

source

pub fn convert_store<NewStore>(self) -> ZeroTrie<NewStore>
where NewStore: From<Store>,

Converts this trie’s store to a different store implementing the From trait.

For example, use this to change ZeroTrie<Vec<u8>> to ZeroTrie<Cow<[u8]>>.

source§

impl<Store> ZeroTrie<Store>
where Store: AsRef<[u8]>,

source

pub fn get<K>(&self, key: K) -> Option<usize>
where K: AsRef<[u8]>,

Queries the trie for a string.

source

pub fn is_empty(&self) -> bool

Returns true if the trie is empty.

source

pub fn byte_len(&self) -> usize

Returns the size of the trie in number of bytes.

To get the number of keys in the trie, use .iter().count().

source§

impl<Store> ZeroTrie<Store>
where Store: AsRef<[u8]>,

source

pub fn to_btreemap(&self) -> BTreeMap<Box<[u8]>, usize>

Exports the data from this ZeroTrie into a BTreeMap.

source§

impl ZeroTrie<Vec<u8>>

source

pub(crate) fn try_from_tuple_slice( items: &[(&ByteStr, usize)], ) -> Result<Self, Error>

Trait Implementations§

source§

impl<Store: Clone> Clone for ZeroTrie<Store>

source§

fn clone(&self) -> ZeroTrie<Store>

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl<Store: Debug> Debug for ZeroTrie<Store>

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<K> FromIterator<(K, usize)> for ZeroTrie<Vec<u8>>
where K: AsRef<[u8]>,

source§

fn from_iter<T: IntoIterator<Item = (K, usize)>>(iter: T) -> Self

Creates a value from an iterator. Read more
source§

impl<Store: PartialEq> PartialEq for ZeroTrie<Store>

source§

fn eq(&self, other: &ZeroTrie<Store>) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl<'a, Store> Yokeable<'a> for ZeroTrie<Store>
where Store: 'static, Self: Sized,

source§

type Output = ZeroTrie<Store>

This type MUST be Self with the 'static replaced with 'a, i.e. Self<'a>
source§

fn transform(&self) -> &Self::Output

This method must cast self between &'a Self<'static> and &'a Self<'a>. Read more
source§

fn transform_owned(self) -> Self::Output

This method must cast self between Self<'static> and Self<'a>. Read more
source§

unsafe fn make(this: Self::Output) -> Self

This method can be used to cast away Self<'a>’s lifetime. Read more
source§

fn transform_mut<F>(&'a mut self, f: F)
where F: 'static + for<'b> FnOnce(&'b mut Self::Output),

This method must cast self between &'a mut Self<'static> and &'a mut Self<'a>, and pass it to f. Read more
source§

impl<'zf, Store1, Store2> ZeroFrom<'zf, ZeroTrie<Store1>> for ZeroTrie<Store2>
where Store2: ZeroFrom<'zf, Store1>,

source§

fn zero_from(other: &'zf ZeroTrie<Store1>) -> Self

Clone the other C into a struct that may retain references into C.
source§

impl<Store: Copy> Copy for ZeroTrie<Store>

source§

impl<Store: Eq> Eq for ZeroTrie<Store>

source§

impl<Store> StructuralPartialEq for ZeroTrie<Store>

Auto Trait Implementations§

§

impl<Store> Freeze for ZeroTrie<Store>
where Store: Freeze,

§

impl<Store> RefUnwindSafe for ZeroTrie<Store>
where Store: RefUnwindSafe,

§

impl<Store> Send for ZeroTrie<Store>
where Store: Send,

§

impl<Store> Sync for ZeroTrie<Store>
where Store: Sync,

§

impl<Store> Unpin for ZeroTrie<Store>
where Store: Unpin,

§

impl<Store> UnwindSafe for ZeroTrie<Store>
where Store: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

source§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> ErasedDestructor for T
where T: 'static,