Crate cphf 

CPHF is a library to generate efficient lookup tables at compile time using perfect hash functions.

It currently uses the CHD algorithm and can generate a 120 entry map in roughly 1 second.

MSRV (minimum supported rust version) is Rust 1.85.

In contrast to the excellent phf crate, this crate uses no code generation outside of normal macro_rules. Instead it generates maps using const expressions. As such, this crate is several orders of magnitude slower than phf (so maps with thousands of entries would probably be better served by phf), but doing so allows it to avoid all the major drawbacks. Namely, nested maps are supported any type can be used as a key (provided it implements the correct traits and pseudo-traits).

Usage

Simply add cphf as a depenency and utilize the included phf_ordered_map macro to construct an OrderedMap or the phf_ordered_set macro to construct an OrderedSet

use cphf::{phf_ordered_map, OrderedMap};

#[derive(Clone)]
pub enum Keyword {
    Loop,
    Continue,
    Break,
    Fn,
    Extern,
}

static KEYWORDS: OrderedMap<&'static str, Keyword> = phf_ordered_map! {&'static str, Keyword;
    "loop" => Keyword::Loop,
    "continue" => Keyword::Continue,
    "break" => Keyword::Break,
    "fn" => Keyword::Fn,
    "extern" => Keyword::Extern,
};

pub fn parse_keyword(keyword: &str) -> Option<Keyword> {
    KEYWORDS.get(keyword).cloned()
}

Inclusion of duplicate keys will result in a compiler error.

use cphf::{phf_ordered_set, OrderedSet};
static DUPLICATE_KEYS: OrderedSet<u32> = phf_ordered_set! {u32;
    0,
    1,
    0,
};

use cphf::{phf_ordered_map, OrderedMap};
static DUPLICATE_KEYS: OrderedMap<u32, ()> = phf_ordered_map! {u32, ();
    0 => (),
    1 => (),
    0 => (),
};

Advanced Usage

If we wanted to make the above example Keyword usable as a key, we would implement traits (and pseudo-traits) like this:

use core::borrow::Borrow;
use cphf::{ConstKey, PhfKey, PhfKeyProxy, Hasher};

// We now require `Eq` to be a key
#[derive(Clone, PartialEq, Eq)]
pub enum Keyword {
    Loop,
    Continue,
    Break,
    Fn,
    Extern,
}

// Define a new type for our pseudo-trait
pub struct KeywordMarker;

// Glue our marker type to the real type.
impl PhfKey for Keyword {
    type ConstKey = KeywordMarker;
}
impl ConstKey for KeywordMarker {
    type PhfKey = Keyword;
}

// Implement our pseudo-trait. These are `const` inherent methods since there
// is current no method of adding `const` methods to a trait
impl KeywordMarker {
    pub const fn pfh_hash(value: &Keyword, state: &mut Hasher) {
        // We can only use `const` functions here
        // If Keyword were `Copy` would could use `*value as u32`
        // But for the sake of this example, we will do this the hard way
        use Keyword::*;
        let value = match value {
            Loop => 0,
            Continue => 1,
            Break => 2,
            Fn => 3,
            Extern => 4,
        };
        <u32 as PhfKey>::ConstKey::pfh_hash(&value, state)
    }
    pub const fn pfh_eq(lhs: &Keyword, rhs: &Keyword) -> bool {
        // We can only use `const` equality functions here
        // If Keyword were `Copy` would could use `*lhs as u32 == *rhs as u32`
        // But for the sake of this example, we will do this the hard way
        use Keyword::*;
        match (lhs, rhs) {
            (Loop, Loop) | (Continue, Continue) | (Break, Break) | (Fn, Fn) | (Extern, Extern) => true,
            _ => false,
        }
    }
}

// Finally we add a trait implementation to allow usage of indexing methods like `get`.
// You can make this broad or narrow as you would like, doing so just modifies what types callers can pass to `OrderedMap::get`,
// but `?Sized + Borrow<Self>` is a pretty good baseline.
impl<PK: ?Sized + Borrow<Keyword>> PhfKeyProxy<PK> for Keyword {
    fn pfh_hash(pk: &PK, state: &mut Hasher) {
        // Call the above hash function (or else make an equivalent hash somehow)
        KeywordMarker::pfh_hash(pk.borrow(), state)
    }
    fn pfh_eq(&self, other: &PK) -> bool {
        // Implement equality
        self == other.borrow()
    }
}

// Now we can make use `Keyword` as a key
static KEYWORDS: cphf::OrderedMap<Keyword, &'static str> = cphf::phf_ordered_map! {Keyword, &'static str;
    Keyword::Loop => "loop",
    Keyword::Continue => "continue",
    Keyword::Break => "break",
    Keyword::Fn => "fn",
    Keyword::Extern => "extern",
};

Modules

ordered_map

ordered_set

Macros

phf_ordered_map

Generate an crate::OrderedMap.

phf_ordered_map_from_builder

Takes the name of a type which implements crate::MapBuilder and returns an crate::OrderedMap filled with the entries from crate::MapBuilder::ENTRIES.

phf_ordered_set

Generate an crate::OrderedSet.

phf_ordered_set_from_builder

Takes the name of a type which implements crate::SetBuilder and returns an crate::OrderedSet filled with the entries from crate::SetBuilder::ENTRIES.

Structs

Generator

Hasher

An implementation of SipHash128 1-3.

OrderedMap

An order-preserving map which can be constructed at compile time.

OrderedSet

An order-preserving set which can be constructed at compile time.

UncasedStr

Traits

ConstKey

A type which can be hashed and equality checked at compile time.

MapBuilder

A trait which stores the entries necessary to create an crate::OrderedMap

PhfKey

This type allows the

PhfKeyProxy

Runtime support for indexing into a map.

SetBuilder

A trait which stores the entries necessary to create an crate::OrderedSet