perfect_hash.rs.html -- source

Files

adler

aho_corasick

packed

teddy

compile.rs mod.rs runtime.rs

api.rs mod.rs pattern.rs rabinkarp.rs vector.rs

ahocorasick.rs automaton.rs buffer.rs byte_frequencies.rs classes.rs dfa.rs error.rs lib.rs nfa.rs prefilter.rs state_id.rs

async_compression

codec

flate

decoder.rs encoder.rs mod.rs

gzip

decoder.rs encoder.rs header.rs mod.rs

stream

generic

decoder.rs encoder.rs mod.rs

macros

decoder.rs encoder.rs mod.rs

lib.rs macros.rs unshared.rs util.rs

async_trait

args.rs expand.rs lib.rs lifetime.rs parse.rs receiver.rs respan.rs

base64

read

decoder.rs mod.rs

write

encoder.rs mod.rs

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

bitflags

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

crc32fast

specialized

mod.rs pclmulqdq.rs

baseline.rs combine.rs lib.rs table.rs

dirs

dirs_sys

lib.rs xdg_user_dirs.rs

dtoa

diyfp.rs dtoa.rs lib.rs

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

eui48

fallible_iterator

flate2

deflate

bufread.rs mod.rs read.rs write.rs

ffi

gz

bufread.rs mod.rs read.rs write.rs

zlib

bufread.rs mod.rs read.rs write.rs

bufreader.rs crc.rs lib.rs mem.rs zio.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

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

iovec

sys

ipnet

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

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

linked_hash_map

log

lib.rs macros.rs

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

miniz_oxide

deflate

buffer.rs core.rs mod.rs stream.rs

inflate

core.rs mod.rs output_buffer.rs stream.rs

lib.rs shared.rs

mio

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_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 sign.rs

once_cell

imp_std.rs lib.rs

openssl

openssl_probe

openssl_sys

openstack

osauth

loading

config.rs env.rs mod.rs

adapter.rs apiversion.rs auth.rs basic.rs endpointfilters.rs error.rs identity.rs lib.rs protocol.rs request.rs services.rs session.rs sync.rs url.rs utils.rs

osproto

common.rs identity.rs lib.rs

percent_encoding

pin_project

pin_project_internal

pin_project

attribute.rs derive.rs mod.rs

lib.rs pinned_drop.rs project.rs utils.rs

pin_project_lite

pin_utils

lib.rs projection.rs stack_pin.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

quote

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

regex

regex_syntax

reqwest

async_impl

body.rs client.rs decoder.rs mod.rs multipart.rs request.rs response.rs

connect.rs error.rs into_url.rs lib.rs proxy.rs redirect.rs tls.rs util.rs

rustc_serialize

base64.rs collection_impls.rs hex.rs json.rs lib.rs serialize.rs

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

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

serde_yaml

value

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

de.rs error.rs lib.rs mapping.rs number.rs path.rs ser.rs

slab

socket2

sys

lib.rs sockaddr.rs socket.rs utils.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.rs arrayvec.rs lib.rs tinyvec.rs

tokio

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

tcp

incoming.rs listener.rs mod.rs split.rs split_owned.rs stream.rs

park

either.rs mod.rs thread.rs

runtime

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 mod.rs spawn.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 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_core

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

tracing_futures

executor

lib.rs stdlib.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

waiter

want

yaml_rust

emitter.rs lib.rs parser.rs scanner.rs yaml.rs

// 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