perfect_hash.rs.html -- source

Files

ansi_term

ansi.rs debug.rs difference.rs display.rs lib.rs style.rs util.rs windows.rs write.rs

base64

read

decoder.rs mod.rs

write

encoder.rs encoder_string_writer.rs mod.rs

chunked_encoder.rs decode.rs display.rs encode.rs lib.rs tables.rs

bitflags

byteorder

bytes

buf

ext

chain.rs limit.rs mod.rs reader.rs take.rs writer.rs

buf_impl.rs buf_mut.rs iter.rs mod.rs vec_deque.rs

fmt

debug.rs hex.rs mod.rs

bytes.rs bytes_mut.rs lib.rs loom.rs

cfg_if

chrono

format

mod.rs parse.rs parsed.rs scan.rs strftime.rs

naive

date.rs datetime.rs internals.rs isoweek.rs time.rs

offset

fixed.rs local.rs mod.rs utc.rs

sys

date.rs datetime.rs div.rs lib.rs round.rs sys.rs

crossbeam_channel

flavors

array.rs at.rs list.rs mod.rs never.rs tick.rs zero.rs

channel.rs context.rs counter.rs err.rs lib.rs select.rs select_macro.rs utils.rs waker.rs

crossbeam_utils

atomic

atomic_cell.rs consume.rs mod.rs seq_lock.rs

sync

mod.rs parker.rs sharded_lock.rs wait_group.rs

backoff.rs cache_padded.rs lib.rs thread.rs

either

encoding_rs

ascii.rs big5.rs data.rs euc_jp.rs euc_kr.rs gb18030.rs handles.rs iso_2022_jp.rs lib.rs macros.rs mem.rs replacement.rs shift_jis.rs single_byte.rs utf_16.rs utf_8.rs variant.rs x_user_defined.rs

fnv

foreign_types

foreign_types_shared

form_urlencoded

lib.rs query_encoding.rs

futures

futures_channel

mpsc

mod.rs queue.rs sink_impl.rs

lib.rs lock.rs oneshot.rs

futures_core

task

__internal

atomic_waker.rs mod.rs

future.rs lib.rs stream.rs

futures_executor

enter.rs lib.rs local_pool.rs

futures_io

futures_macro

join.rs lib.rs select.rs

futures_sink

futures_task

arc_wake.rs future_obj.rs lib.rs noop_waker.rs spawn.rs waker.rs waker_ref.rs

futures_util

async_await

join_mod.rs mod.rs pending.rs poll.rs random.rs select_mod.rs

future

io

lock

bilock.rs mod.rs mutex.rs

sink

buffer.rs close.rs drain.rs err_into.rs fanout.rs flush.rs map_err.rs mod.rs send.rs send_all.rs with.rs with_flat_map.rs

stream

task

mod.rs spawn.rs

fns.rs lib.rs never.rs

getrandom

error.rs error_impls.rs lib.rs linux_android.rs use_file.rs util.rs util_libc.rs

h2

hashbrown

external_trait_impls

raw

bitmask.rs mod.rs sse2.rs

lib.rs macros.rs map.rs scopeguard.rs set.rs

http

header

map.rs mod.rs name.rs value.rs

uri

authority.rs builder.rs mod.rs path.rs port.rs scheme.rs

byte_str.rs convert.rs error.rs extensions.rs lib.rs method.rs request.rs response.rs status.rs version.rs

http_body

lib.rs next.rs size_hint.rs

httparse

simd

avx2.rs mod.rs sse42.rs

iter.rs lib.rs macros.rs

httpdate

httpdate.rs lib.rs

hyper

body

aggregate.rs body.rs mod.rs to_bytes.rs

client

connect

dns.rs http.rs mod.rs

conn.rs dispatch.rs mod.rs pool.rs service.rs

common

io

mod.rs rewind.rs

buf.rs drain.rs exec.rs lazy.rs mod.rs never.rs task.rs watch.rs

proto

h1

conn.rs date.rs decode.rs dispatch.rs encode.rs io.rs mod.rs role.rs

h2

client.rs mod.rs ping.rs server.rs

server

accept.rs conn.rs mod.rs shutdown.rs tcp.rs

service

http.rs make.rs mod.rs oneshot.rs util.rs

error.rs headers.rs lib.rs rt.rs upgrade.rs

hyper_tls

client.rs lib.rs stream.rs

idna

lib.rs punycode.rs uts46.rs

indexmap

map

core

equivalent.rs lib.rs macros.rs map.rs mutable_keys.rs set.rs util.rs

instant

lib.rs native.rs

iovec

sys

ipnet

ipext.rs ipnet.rs lib.rs parser.rs

itertools

itoa

lazy_static

inline_lazy.rs lib.rs

libc

unix

linux_like

linux

gnu

b64

x86_64

align.rs mod.rs not_x32.rs

align.rs mod.rs

align.rs mod.rs

align.rs mod.rs

fixed_width_ints.rs lib.rs macros.rs

libhoney

builder.rs client.rs errors.rs event.rs eventdata.rs events.rs fields.rs lib.rs mock.rs response.rs sender.rs transmission.rs

lock_api

lib.rs mutex.rs remutex.rs rwlock.rs

log

lib.rs macros.rs

matchers

matches

memchr

x86

avx.rs mod.rs sse2.rs

fallback.rs iter.rs lib.rs naive.rs

mime

lib.rs parse.rs

mime_guess

impl_bin_search.rs lib.rs

mio

mio_uds

datagram.rs lib.rs listener.rs socket.rs stream.rs

native_tls

imp

net2

sys

unix

impls.rs mod.rs

ext.rs lib.rs socket.rs tcp.rs udp.rs unix.rs utils.rs

num_cpus

lib.rs linux.rs

num_integer

average.rs lib.rs roots.rs

num_traits

ops

checked.rs inv.rs mod.rs mul_add.rs overflowing.rs saturating.rs wrapping.rs

bounds.rs cast.rs float.rs identities.rs int.rs lib.rs macros.rs pow.rs real.rs sign.rs

once_cell

imp_std.rs lib.rs

openssl

openssl_probe

openssl_sys

opentelemetry

api

exporter

metrics

prometheus

trace

mod.rs stdout.rs

sdk

metrics

trace

config.rs evicted_hash_map.rs evicted_queue.rs id_generator.rs mod.rs provider.rs sampler.rs span.rs span_processor.rs tracer.rs

mod.rs resource.rs

global.rs lib.rs

parking_lot

condvar.rs deadlock.rs elision.rs fair_mutex.rs lib.rs mutex.rs once.rs raw_fair_mutex.rs raw_mutex.rs raw_rwlock.rs remutex.rs rwlock.rs util.rs

parking_lot_core

thread_parker

linux.rs mod.rs

lib.rs parking_lot.rs spinwait.rs util.rs word_lock.rs

percent_encoding

pin_project

pin_project_internal

pin_project

args.rs attribute.rs derive.rs mod.rs

lib.rs pinned_drop.rs utils.rs

pin_project_lite

pin_utils

lib.rs projection.rs stack_pin.rs

ppv_lite86

x86_64

lib.rs soft.rs types.rs

proc_macro2

detection.rs fallback.rs lib.rs marker.rs parse.rs wrapper.rs

proc_macro_hack

error.rs iter.rs lib.rs parse.rs quote.rs

proc_macro_nested

prometheus

encoder

mod.rs pb.rs text.rs

proto

atomic64.rs counter.rs desc.rs errors.rs gauge.rs histogram.rs lib.rs macros.rs metrics.rs registry.rs value.rs vec.rs

protobuf

quick_error

quote

ext.rs format.rs ident_fragment.rs lib.rs runtime.rs spanned.rs to_tokens.rs

rand

rand_chacha

chacha.rs guts.rs lib.rs

rand_core

block.rs error.rs impls.rs le.rs lib.rs os.rs

regex

literal

backtrack.rs cache.rs compile.rs error.rs exec.rs expand.rs find_byte.rs input.rs lib.rs pikevm.rs prog.rs re_builder.rs re_bytes.rs re_set.rs re_trait.rs re_unicode.rs sparse.rs utf8.rs

regex_automata

nfa

compiler.rs map.rs mod.rs range_trie.rs

classes.rs dense.rs determinize.rs dfa.rs error.rs lib.rs minimize.rs regex.rs sparse.rs sparse_set.rs state_id.rs

regex_syntax

reqwest

ryu

buffer

pretty

exponent.rs mantissa.rs mod.rs

common.rs d2s.rs d2s_full_table.rs d2s_intrinsics.rs digit_table.rs f2s.rs f2s_intrinsics.rs lib.rs

scopeguard

serde

de

from_primitive.rs ignored_any.rs impls.rs mod.rs utf8.rs value.rs

private

de.rs macros.rs mod.rs ser.rs

ser

fmt.rs impls.rs impossible.rs mod.rs

export.rs integer128.rs lib.rs macros.rs

serde_derive

internals

ast.rs attr.rs case.rs check.rs ctxt.rs mod.rs symbol.rs

bound.rs de.rs dummy.rs fragment.rs lib.rs pretend.rs ser.rs try.rs

serde_json

features_check

io

value

de.rs from.rs index.rs mod.rs partial_eq.rs ser.rs

de.rs error.rs iter.rs lib.rs macros.rs map.rs number.rs read.rs ser.rs

serde_urlencoded

ser

key.rs mod.rs pair.rs part.rs value.rs

sharded_slab

page

mod.rs slot.rs stack.rs

cfg.rs clear.rs implementation.rs iter.rs lib.rs pool.rs shard.rs sync.rs tid.rs

signal_hook_registry

half_lock.rs lib.rs

slab

smallvec

socket2

sys

lib.rs sockaddr.rs socket.rs utils.rs

spin

lib.rs mutex.rs once.rs rw_lock.rs

syn

thread_local

cached.rs lib.rs thread_id.rs unreachable.rs

time

display.rs duration.rs lib.rs parse.rs sys.rs

tinyvec

array

generated_impl.rs

array.rs arrayvec.rs arrayvec_drain.rs lib.rs slicevec.rs tinyvec.rs

tinyvec_macros

tokio

fs

future

maybe_done.rs mod.rs poll_fn.rs ready.rs try_join.rs

io

loom

std

atomic_ptr.rs atomic_u16.rs atomic_u32.rs atomic_u64.rs atomic_u8.rs atomic_usize.rs mod.rs unsafe_cell.rs

macros

cfg.rs join.rs loom.rs mod.rs pin.rs ready.rs scoped_tls.rs select.rs support.rs thread_local.rs try_join.rs

net

park

either.rs mod.rs thread.rs

process

unix

mod.rs orphan.rs reap.rs

runtime

signal

ctrl_c.rs mod.rs registry.rs unix.rs

stream

all.rs any.rs chain.rs collect.rs empty.rs filter.rs filter_map.rs fold.rs fuse.rs iter.rs map.rs merge.rs mod.rs next.rs once.rs pending.rs skip.rs skip_while.rs stream_map.rs take.rs take_while.rs timeout.rs try_next.rs

sync

task

blocking.rs local.rs mod.rs spawn.rs task_local.rs yield_now.rs

time

driver

atomic_stack.rs entry.rs handle.rs mod.rs registration.rs stack.rs

wheel

level.rs mod.rs stack.rs

clock.rs delay.rs delay_queue.rs error.rs instant.rs interval.rs mod.rs throttle.rs timeout.rs

util

slab

addr.rs entry.rs generation.rs mod.rs page.rs shard.rs slot.rs stack.rs

bit.rs intrusive_double_linked_list.rs linked_list.rs mod.rs rand.rs trace.rs try_lock.rs wake.rs

coop.rs lib.rs prelude.rs

tokio_macros

entry.rs lib.rs select.rs

tokio_tls

tokio_util

codec

bytes_codec.rs decoder.rs encoder.rs framed.rs framed_read.rs framed_write.rs length_delimited.rs lines_codec.rs mod.rs

tower_service

tracing

dispatcher.rs field.rs instrument.rs level_filters.rs lib.rs macros.rs span.rs stdlib.rs subscriber.rs

tracing_attributes

tracing_core

callsite.rs dispatcher.rs event.rs field.rs lib.rs metadata.rs parent.rs span.rs stdlib.rs subscriber.rs

tracing_distributed

lib.rs telemetry.rs telemetry_layer.rs trace.rs

tracing_futures

executor

lib.rs stdlib.rs

tracing_honeycomb

honeycomb.rs lib.rs visitor.rs

tracing_jaeger

lib.rs opentelemetry.rs visitor.rs

tracing_log

lib.rs log_tracer.rs

tracing_serde

fields.rs lib.rs

tracing_subscriber

field

debug.rs delimited.rs display.rs mod.rs

filter

env

directive.rs field.rs mod.rs

level.rs mod.rs

fmt

format

json.rs mod.rs pretty.rs

time

fmt_layer.rs mod.rs writer.rs

registry

extensions.rs mod.rs sharded.rs stack.rs

layer.rs lib.rs prelude.rs reload.rs sync.rs thread.rs util.rs

try_lock

unicase

unicode

ascii.rs lib.rs

unicode_bidi

char_data

mod.rs tables.rs

deprecated.rs explicit.rs format_chars.rs implicit.rs level.rs lib.rs prepare.rs

unicode_normalization

__test_api.rs decompose.rs lib.rs lookups.rs no_std_prelude.rs normalize.rs perfect_hash.rs quick_check.rs recompose.rs stream_safe.rs tables.rs

unicode_xid

lib.rs tables.rs

url

host.rs lib.rs origin.rs parser.rs path_segments.rs quirks.rs slicing.rs

want

// Copyright 2019 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Support for lookups based on minimal perfect hashing.

// This function is based on multiplication being fast and is "good enough". Also
// it can share some work between the unsalted and salted versions.
#[inline]
fn my_hash(key: u32, salt: u32, n: usize) -> usize {
    let y = key.wrapping_add(salt).wrapping_mul(2654435769);
    let y = y ^ key.wrapping_mul(0x31415926);
    (((y as u64) * (n as u64)) >> 32) as usize
}

/// Do a lookup using minimal perfect hashing.
///
/// The table is stored as a sequence of "salt" values, then a sequence of
/// values that contain packed key/value pairs. The strategy is to hash twice.
/// The first hash retrieves a salt value that makes the second hash unique.
/// The hash function doesn't have to be very good, just good enough that the
/// resulting map is unique.
#[inline]
pub(crate) fn mph_lookup<KV, V, FK, FV>(
    x: u32,
    salt: &[u16],
    kv: &[KV],
    fk: FK,
    fv: FV,
    default: V,
) -> V
where
    KV: Copy,
    FK: Fn(KV) -> u32,
    FV: Fn(KV) -> V,
{
    let s = salt[my_hash(x, 0, salt.len())] as u32;
    let key_val = kv[my_hash(x, s, salt.len())];
    if x == fk(key_val) {
        fv(key_val)
    } else {
        default
    }
}

Keyboard Shortcuts

?: Show this help dialog
S: Focus the search field
↑: Move up in search results
↓: Move down in search results
↹: Switch tab
⏎: Go to active search result
+: Expand all sections
-: Collapse all sections

Search Tricks

Prefix searches with a type followed by a colon (e.g., fn:) to restrict the search to a given type.

Accepted types are: fn, mod, struct, enum, trait, type, macro, and const.

Search functions by type signature (e.g., vec -> usize or * -> vec)

Search multiple things at once by splitting your query with comma (e.g., str,u8 or String,struct:Vec,test)

You can look for items with an exact name by putting double quotes around your request: "string"

Look for items inside another one by searching for a path: vec::Vec