moonbitstack/moonstl/phf

README
U
AhoCorasick
U
ArcCache
U
ArenaTree
U
BiMap
U
BitSet
U
BitVec
U
BloomFilter
U
BloomOptions
U
BoyerMoore
U
CacheStats
U
ChainMap
U
Combinations
U
CombinationsWithReplacement
U
CountMinSketch
U
Counter
U
CuckooFilter
U
CuckooOptions
U
DaryHeap
U
DefaultMap
U
DenseSlotMap
U
DisjointSet
U
DisjointSetMap
U
ExpiringCache
U
Fenwick
U
FibonacciHeap
U
FlatMap
U
FlatMultiMap
U
FlatMultiSet
U
FlatSet
U
GapBuffer
U
GrayCode
U
Growth
U
HeapKey
U
HyperLogLog
U
IndexHeap
U
IndexMap
U
IndexSet
U
IntervalKey
U
IntervalTree
U
JoinEntry
U
Kmp
U
LazySegmentTree
U
LfuCache
U
LinkedList
U
LruCache
U
Match
U
MinMaxHeap
U
MultiMap
U
MultiSet
U
Opcode
U
Order
U
OrderStatisticTree
U
Overflow
U
Overlap
U
PairingHeap
U
Permutations
U
PhfBuild
U
PhfBuilder
U
PhfLayout
U
PhfMap
U
PhfOptions
U
PhfOrderedMap
U
PhfOrderedSet
U
PhfSet
U
Position
U
Powerset
U
Product
U
RadixHeap
U
RadixTree
U
RangeMap
U
RangeSet
U
Refused
U
RingBuffer
U
Rope
U
RopeBuilder
U
RopeView
U
SecondaryMap
U
SegmentTree
U
SequenceMatcher
U
SequenceMatcherOptions
U
SkipList
U
SkipListOptions
U
Slab
U
SlotKey
U
SlotMap
U
SortedMultiMap
U
SortedMultiSet
U
SparseSet
U
SuffixArray
U
SuffixAutomaton
U
TDigest
U
ThetaSketch
U
Treap
U
TreeId
U
Trie

moonbitstack/moonstl/phf does not have a README file

PhfKey

pub(open) trait PhfKey {
  fn to_bytes(Self) -> Bytes
}

The byte encoding a key is hashed from.

A perfect hash table can only be probed with the exact encoding it was built from, so String and StringView share one encoding on purpose: a table generated for string keys answers both. Every implementation has to be deterministic and independent of the backend, because PhfBuilder::build_source output is compared byte for byte across machines.

impl PhfKey for Int

impl PhfKey for Int64

impl PhfKey for UInt64

impl PhfKey for String

impl PhfKey for StringView

PhfBuild

source

pub(all) enum PhfBuild {
  Search
  Quick
  Minimal
} derive(Eq, @moonbitlang/core/debug.Debug
Debug)

The trade PhfBuilder makes between build time, table size and stored index.

Search is the phf crate's default: a displacement table over a table of about 10/9 slots per key, found by searching each bucket's displacement. Quick follows quickphf: the table holds about two slots per key, so almost every bucket is placed at displacement zero and the search disappears. Minimal follows entropy-map: the entries are kept dense and the slot is turned into an entry index by a rank structure over the occupied slots.

impl Show for PhfBuild

PhfBuild::equal

source

fn PhfBuild::equal(PhfBuild, PhfBuild) -> Bool

PhfBuild::not_equal

source

fn PhfBuild::not_equal(x : PhfBuild, y : PhfBuild) -> Bool

PhfBuild::output

source

fn PhfBuild::output(self : PhfBuild, logger : &Logger) -> Unit

PhfBuild::to_repr

source

fn PhfBuild::to_repr(PhfBuild) -> @moonbitlang/core/debug.Repr
Repr

PhfBuild::to_string

source

fn PhfBuild::to_string(self : PhfBuild) -> String

PhfBuilder

source

pub struct PhfBuilder[K, V] {
  options : PhfOptions
  keys : Array[K]
  values : Array[V]
  seen : Map[Bytes, Unit]
}

Builds a perfect hash table from the entries it is given. A key may appear once: the second entry for the same key is refused, because a table with two entries in one bucket would have no displacement that places both.

test {
  let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
  builder.entry("x", 1)
  let refused = try {
    builder.entry("x", 2)
    Ok(())
  } catch {
    @spec.Refused::DuplicateValue => Err(true)
    _ => Err(false)
  }
  assert_true(refused == Err(true))
}

PhfBuilder::build

source

fn[K : PhfKey, V] PhfBuilder::build(self : PhfBuilder[K, V]) -> PhfMap[K, V] raise @moonbitstack/moonstl/spec.Refused
Refused

The table. The search is deterministic for a fixed seed and entry order, so the same entries give the same layout on every machine and every backend.

PhfBuilder::build_ordered

source

fn[K : PhfKey, V] PhfBuilder::build_ordered(self : PhfBuilder[K, V]) -> PhfOrderedMap[K, V] raise @moonbitstack/moonstl/spec.Refused
Refused

PhfBuilder::build_ordered_set

source

fn[K : PhfKey, V] PhfBuilder::build_ordered_set(self : PhfBuilder[K, V]) -> PhfOrderedSet[K] raise @moonbitstack/moonstl/spec.Refused
Refused

PhfBuilder::build_set

source

fn[K : PhfKey, V] PhfBuilder::build_set(self : PhfBuilder[K, V]) -> PhfSet[K] raise @moonbitstack/moonstl/spec.Refused
Refused

PhfBuilder::build_source

source

fn[K : PhfKey + Show, V : Show] PhfBuilder::build_source(self : PhfBuilder[K, V], name~ : String) -> String raise @moonbitstack/moonstl/spec.Refused
Refused

The table as MoonBit source: the layout literal and the entries, so a generated module compiles the table in instead of building it at start-up.

PhfBuilder::entry

source

fn[K : PhfKey, V] PhfBuilder::entry(self : PhfBuilder[K, V], key : K, value : V) -> Unit raise @moonbitstack/moonstl/spec.Refused
Refused

PhfBuilder::length

source

fn[K, V] PhfBuilder::length(self : PhfBuilder[K, V]) -> Int

PhfBuilder::new

source

fn[K, V] PhfBuilder::new(phf_options? : PhfOptions) -> PhfBuilder[K, V]

PhfIndex

source

pub enum PhfIndex {
  Direct(FixedArray[Int])
  Ranked(PhfRank)
}

How a slot becomes an entry index. Direct is a slot-to-index array with -1 for a free slot; Ranked is the Minimal representation.

PhfLayout

source

pub(all) struct PhfLayout {
  build : PhfBuild
  salt : UInt64
  buckets : Int
  table_len : Int
  length : Int
  disps : Array[Int]
} derive(Eq, @moonbitlang/core/debug.Debug
Debug)

A perfect hash layout: everything a lookup needs that does not depend on the key or the value type.

A key in bucket b with hash h sits in slot ((h & 0xFFFFFFFF) + disps[b]) % table_len. With build set to Minimal that slot is an intermediate value only: the map keeps a rank structure over the occupied slots and stores the entries densely.

The fields are public because a generated module embeds one of these as a plain struct literal instead of running the builder at start-up. Nothing trusts such a literal: PhfMap::from_layout re-derives the slots from the keys it is given and refuses a layout that does not fit them.

PhfLayout::equal

source

fn PhfLayout::equal(PhfLayout, PhfLayout) -> Bool

PhfLayout::not_equal

source

fn PhfLayout::not_equal(x : PhfLayout, y : PhfLayout) -> Bool

PhfLayout::to_repr

source

fn PhfLayout::to_repr(PhfLayout) -> @moonbitlang/core/debug.Repr
Repr

PhfMap

source

pub struct PhfMap[K, V] {
  layout : PhfLayout
  keys : Array[K]
  values : Array[V]
  index : PhfIndex
}

A table whose hash was computed while it was built, so a lookup is one hash, one displacement table read and one comparison — there is no probe sequence to walk and no cluster to fall into. The layout is a value, which is what lets a generated module carry one as a literal; from_layout re-derives every slot from the keys and refuses a layout that does not fit them.

test {
  let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
  builder.entry("a", 1)
  builder.entry("b", 2)
  let table = builder.build()
  assert_true(table.get("a") == Some(1))
  assert_true(table.get("b") == Some(2))
  assert_true(table.get("c") == None)
  assert_true(table.length() == 2)
}

PhfMap::contains

source

fn[K : PhfKey + Eq, V] PhfMap::contains(self : PhfMap[K, V], key : K) -> Bool

PhfMap::copy

source

fn[K, V] PhfMap::copy(self : PhfMap[K, V]) -> PhfMap[K, V]

PhfMap::from_layout

source

fn[K : PhfKey, V] PhfMap::from_layout(layout : PhfLayout, entries : Array[(K, V)]) -> PhfMap[K, V] raise @moonbitstack/moonstl/spec.Refused
Refused

A table from a layout and its entries. The entries are hashed again, so a layout that does not describe them — a stale generated table, a hand-written literal that drifted — is refused instead of answering wrongly.

PhfMap::get

source

fn[K : PhfKey + Eq, V] PhfMap::get(self : PhfMap[K, V], key : K) -> V?

PhfMap::get_index

source

fn[K, V] PhfMap::get_index(self : PhfMap[K, V], index : Int) -> (K, V)?

The entry at a stored index, which is the order the builder took the entries in.

PhfMap::get_key

source

fn[K : PhfKey + Eq, V] PhfMap::get_key(self : PhfMap[K, V], key : K) -> K?

PhfMap::get_key_value

source

fn[K : PhfKey + Eq, V] PhfMap::get_key_value(self : PhfMap[K, V], key : K) -> (K, V)?

The key and the value under key, which hands back the key the table actually holds.

PhfMap::is_empty

source

fn[K, V] PhfMap::is_empty(self : PhfMap[K, V]) -> Bool

PhfMap::iter

source

fn[K, V] PhfMap::iter(self : PhfMap[K, V]) -> Iter[(K, V)]

PhfMap::keys

source

fn[K, V] PhfMap::keys(self : PhfMap[K, V]) -> Iter[K]

PhfMap::layout

source

fn[K, V] PhfMap::layout(self : PhfMap[K, V]) -> PhfLayout

PhfMap::length

source

fn[K, V] PhfMap::length(self : PhfMap[K, V]) -> Int

PhfMap::values

source

fn[K, V] PhfMap::values(self : PhfMap[K, V]) -> Iter[V]

PhfOptions

source

pub(all) struct PhfOptions {
  build : PhfBuild
  seed : Int
} derive(Eq, @moonbitlang/core/debug.Debug
Debug)

How a table is laid out. seed is fixed rather than drawn from the process entropy on purpose: the generated source is checked in and compared byte for byte, so the search has to start from the same place on every machine.

PhfOptions::equal

source

fn PhfOptions::equal(PhfOptions, PhfOptions) -> Bool

PhfOptions::not_equal

source

fn PhfOptions::not_equal(x : PhfOptions, y : PhfOptions) -> Bool

PhfOptions::to_repr

source

fn PhfOptions::to_repr(PhfOptions) -> @moonbitlang/core/debug.Repr
Repr

PhfOrderedMap

source

pub struct PhfOrderedMap[K, V] {
  map : PhfMap[K, V]
}

A map that also reports the position its key was declared in, which is what a generated table wants when the order in the source is the order a reader should see.

test {
  let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
  builder.entry("b", 2)
  builder.entry("a", 1)
  let table = builder.build_ordered()
  assert_true(table.index("b") == Some(0))
  assert_true(table.index("a") == Some(1))
  assert_true(table.get("a") == Some(1))
}

PhfOrderedMap::contains

source

fn[K : PhfKey + Eq, V] PhfOrderedMap::contains(self : PhfOrderedMap[K, V], key : K) -> Bool

PhfOrderedMap::from_layout

source

fn[K : PhfKey, V] PhfOrderedMap::from_layout(layout : PhfLayout, entries : Array[(K, V)]) -> PhfOrderedMap[K, V] raise @moonbitstack/moonstl/spec.Refused
Refused

An ordered map from a layout and its entries in declaration order, refused when the layout does not describe them; what #phf.ordered_map generates.

PhfOrderedMap::get

source

fn[K : PhfKey + Eq, V] PhfOrderedMap::get(self : PhfOrderedMap[K, V], key : K) -> V?

PhfOrderedMap::get_index

source

fn[K, V] PhfOrderedMap::get_index(self : PhfOrderedMap[K, V], index : Int) -> (K, V)?

PhfOrderedMap::index

source

fn[K : PhfKey + Eq, V] PhfOrderedMap::index(self : PhfOrderedMap[K, V], key : K) -> Int?

The declaration position of key.

PhfOrderedMap::is_empty

source

fn[K, V] PhfOrderedMap::is_empty(self : PhfOrderedMap[K, V]) -> Bool

PhfOrderedMap::iter

source

fn[K, V] PhfOrderedMap::iter(self : PhfOrderedMap[K, V]) -> Iter[(K, V)]

PhfOrderedMap::keys

source

fn[K, V] PhfOrderedMap::keys(self : PhfOrderedMap[K, V]) -> Iter[K]

PhfOrderedMap::length

source

fn[K, V] PhfOrderedMap::length(self : PhfOrderedMap[K, V]) -> Int

PhfOrderedMap::values

source

fn[K, V] PhfOrderedMap::values(self : PhfOrderedMap[K, V]) -> Iter[V]

PhfOrderedSet

source

pub struct PhfOrderedSet[K] {
  map : PhfMap[K, Unit]
}

A set whose elements keep the order they were declared in.

PhfOrderedSet::contains

source

fn[K : PhfKey + Eq] PhfOrderedSet::contains(self : PhfOrderedSet[K], key : K) -> Bool

PhfOrderedSet::from_layout

source

fn[K : PhfKey] PhfOrderedSet::from_layout(layout : PhfLayout, keys : Array[K]) -> PhfOrderedSet[K] raise @moonbitstack/moonstl/spec.Refused
Refused

An ordered set from a layout and its keys in declaration order, refused when the layout does not describe them; what #phf.ordered_set generates.

PhfOrderedSet::get_index

source

fn[K] PhfOrderedSet::get_index(self : PhfOrderedSet[K], index : Int) -> K?

PhfOrderedSet::index

source

fn[K : PhfKey + Eq] PhfOrderedSet::index(self : PhfOrderedSet[K], key : K) -> Int?

PhfOrderedSet::is_empty

source

fn[K] PhfOrderedSet::is_empty(self : PhfOrderedSet[K]) -> Bool

PhfOrderedSet::iter

source

fn[K] PhfOrderedSet::iter(self : PhfOrderedSet[K]) -> Iter[K]

PhfOrderedSet::length

source

fn[K] PhfOrderedSet::length(self : PhfOrderedSet[K]) -> Int

PhfRank

source

pub struct PhfRank {
  words : FixedArray[UInt64]
  prefixes : FixedArray[Int]
  dense : FixedArray[Int]
}

The Minimal index: a bitmap of the occupied slots, the number of set bits before each word, and one Int32 per entry in slot order. Reading an index costs a shift, a mask and a popcount instead of a table lookup, and the stored data is one word per 64 slots plus one index per key.

PhfSet

source

pub struct PhfSet[K] {
  map : PhfMap[K, Unit]
}

A set with the same layout as PhfMap, holding only the keys.

test {
  let builder : @phf.PhfBuilder[String, Unit] = @phf.PhfBuilder::new()
  builder.entry("in", ())
  let set = builder.build_set()
  assert_true(set.contains("in"))
  assert_true(!set.contains("out"))
}

PhfSet::contains

source

fn[K : PhfKey + Eq] PhfSet::contains(self : PhfSet[K], key : K) -> Bool

PhfSet::from_layout

source

fn[K : PhfKey] PhfSet::from_layout(layout : PhfLayout, keys : Array[K]) -> PhfSet[K] raise @moonbitstack/moonstl/spec.Refused
Refused

A set from a layout and its keys, refused when the layout does not describe them; what #phf.set generates.

PhfSet::get_index

source

fn[K] PhfSet::get_index(self : PhfSet[K], index : Int) -> K?

PhfSet::is_empty

source

fn[K] PhfSet::is_empty(self : PhfSet[K]) -> Bool

PhfSet::iter

source

fn[K] PhfSet::iter(self : PhfSet[K]) -> Iter[K]

PhfSet::length

source

fn[K] PhfSet::length(self : PhfSet[K]) -> Int

phf_options

source

let phf_options : PhfOptions

The preset: the phf crate's displacement search, starting from seed zero.

Source Files

Install

Download zip

Data structures and algorithms the MoonBit core library leaves out.

data-structuresalgorithmscollectionscontainersstlmoonbitindex-mapindex-setmultimapbimapcounterflat-mapsorted-maprange-maptrieradix-treelru-cachelfu-cachearc-cacheexpiring-cachememoizesortingselectionbisectbinary-searchpermutationscombinationspowersetpartitionmergering-bufferslotmapgap-bufferbit-vectorbit-setlinked-listbinary-heapfibonacci-heappairing-heapmin-max-heapradix-heapdisjoint-setunion-findsegment-treefenwick-treeinterval-treeskip-listtreapbloom-filtercuckoo-filtercount-min-sketchhyperloglogtheta-sketcht-digeststring-searchsuffix-arraysuffix-automatondiffropeperfect-hash

moonbitstack

Apache-2.0

github.com/moonbitstack/moonstl

Updated 4 hours ago

102 downloads

Site source Report issue Modules Skills CLI Build queue Statistics

#PhfKey

#PhfBuild

#PhfBuild::equal

#PhfBuild::not_equal

#PhfBuild::output

#PhfBuild::to_repr

#PhfBuild::to_string

#PhfBuilder

#PhfBuilder::build

#PhfBuilder::build_ordered

#PhfBuilder::build_ordered_set

#PhfBuilder::build_set

#PhfBuilder::build_source

#PhfBuilder::entry

#PhfBuilder::length

#PhfBuilder::new

#PhfIndex

#PhfLayout

#PhfLayout::equal

#PhfLayout::not_equal

#PhfLayout::to_repr

#PhfMap

#PhfMap::contains

#PhfMap::copy

#PhfMap::from_layout

#PhfMap::get

#PhfMap::get_index

#PhfMap::get_key

#PhfMap::get_key_value

#PhfMap::is_empty

#PhfMap::iter

#PhfMap::keys

#PhfMap::layout

#PhfMap::length

#PhfMap::values

#PhfOptions

#PhfOptions::equal

#PhfOptions::not_equal

#PhfOptions::to_repr

#PhfOrderedMap

#PhfOrderedMap::contains

#PhfOrderedMap::from_layout

#PhfOrderedMap::get

#PhfOrderedMap::get_index

#PhfOrderedMap::index

#PhfOrderedMap::is_empty

#PhfOrderedMap::iter

#PhfOrderedMap::keys

#PhfOrderedMap::length

#PhfOrderedMap::values

#PhfOrderedSet

#PhfOrderedSet::contains

#PhfOrderedSet::from_layout

#PhfOrderedSet::get_index

#PhfOrderedSet::index

#PhfOrderedSet::is_empty

#PhfOrderedSet::iter

#PhfOrderedSet::length

#PhfRank

#PhfSet

#PhfSet::contains

#PhfSet::from_layout

#PhfSet::get_index

#PhfSet::is_empty

#PhfSet::iter

#PhfSet::length

#phf_options

Source Files

PhfKey

PhfBuild

PhfBuild::equal

PhfBuild::not_equal

PhfBuild::output

PhfBuild::to_repr

PhfBuild::to_string

PhfBuilder

PhfBuilder::build

PhfBuilder::build_ordered

PhfBuilder::build_ordered_set

PhfBuilder::build_set

PhfBuilder::build_source

PhfBuilder::entry

PhfBuilder::length

PhfBuilder::new

PhfIndex

PhfLayout

PhfLayout::equal

PhfLayout::not_equal

PhfLayout::to_repr

PhfMap

PhfMap::contains

PhfMap::copy

PhfMap::from_layout

PhfMap::get

PhfMap::get_index

PhfMap::get_key

PhfMap::get_key_value

PhfMap::is_empty

PhfMap::iter

PhfMap::keys

PhfMap::layout

PhfMap::length

PhfMap::values

PhfOptions

PhfOptions::equal

PhfOptions::not_equal

PhfOptions::to_repr

PhfOrderedMap

PhfOrderedMap::contains

PhfOrderedMap::from_layout

PhfOrderedMap::get

PhfOrderedMap::get_index

PhfOrderedMap::index

PhfOrderedMap::is_empty

PhfOrderedMap::iter

PhfOrderedMap::keys

PhfOrderedMap::length

PhfOrderedMap::values

PhfOrderedSet

PhfOrderedSet::contains

PhfOrderedSet::from_layout

PhfOrderedSet::get_index

PhfOrderedSet::index

PhfOrderedSet::is_empty

PhfOrderedSet::iter

PhfOrderedSet::length

PhfRank

PhfSet

PhfSet::contains

PhfSet::from_layout

PhfSet::get_index

PhfSet::is_empty

PhfSet::iter

PhfSet::length

phf_options