perfect_hash.rs.html -- source

Files

adler32

backtrace

backtrace

libunwind.rs mod.rs

symbolize

dladdr.rs libbacktrace.rs mod.rs

capture.rs lib.rs print.rs types.rs

backtrace_sys

base64

write

encoder.rs mod.rs

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

bigtable

any.rs bigtable.rs data.rs error.rs lib.rs method.rs request.rs status.rs support.rs utils.rs wrappers.rs wraps.rs

bitflags

byteorder

bytes

buf

buf.rs buf_mut.rs chain.rs from_buf.rs into_buf.rs iter.rs mod.rs reader.rs take.rs vec_deque.rs writer.rs

bytes.rs debug.rs either.rs lib.rs

cfg_if

cookie

builder.rs delta.rs draft.rs jar.rs lib.rs parse.rs

cookie_store

cookie.rs cookie_domain.rs cookie_expiration.rs cookie_path.rs cookie_store.rs lib.rs utils.rs

crc32fast

specialized

mod.rs pclmulqdq.rs

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

crossbeam_deque

crossbeam_epoch

sync

list.rs mod.rs queue.rs

atomic.rs collector.rs default.rs deferred.rs epoch.rs guard.rs internal.rs lib.rs

crossbeam_queue

array_queue.rs err.rs lib.rs seg_queue.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

curl

easy

form.rs handle.rs handler.rs list.rs mod.rs windows.rs

error.rs lib.rs multi.rs panic.rs version.rs

curl_sys

dtoa

diyfp.rs dtoa.rs lib.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

error_chain

backtrace.rs error_chain.rs impl_error_chain_kind.rs lib.rs quick_main.rs

failure

backtrace

internal.rs mod.rs

error

error_impl.rs mod.rs

as_fail.rs box_std.rs compat.rs context.rs error_message.rs lib.rs macros.rs result_ext.rs sync_failure.rs

failure_derive

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

futures

future

sink

buffer.rs fanout.rs flush.rs from_err.rs map_err.rs mod.rs send.rs send_all.rs wait.rs with.rs with_flat_map.rs

stream

sync

mpsc

mod.rs queue.rs

bilock.rs mod.rs oneshot.rs

task_impl

std

data.rs mod.rs task_rc.rs unpark_mutex.rs

atomic_task.rs core.rs mod.rs

unsync

mod.rs mpsc.rs oneshot.rs

executor.rs lib.rs lock.rs poll.rs resultstream.rs task.rs

futures_cpupool

goauth

auth.rs credentials.rs error.rs lib.rs scopes.rs

h2

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

httparse

simd

avx2.rs mod.rs sse42.rs

iter.rs lib.rs macros.rs

hyper

body

body.rs chunk.rs mod.rs payload.rs

client

connect

dns.rs http.rs mod.rs

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

common

io

mod.rs rewind.rs

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

proto

h1

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

h2

client.rs mod.rs server.rs

server

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

service

make_service.rs mod.rs new_service.rs service.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

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

iovec

sys

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

libz_sys

lock_api

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

log

lib.rs macros.rs

matches

maybe_uninit

memoffset

lib.rs offset_of.rs span_of.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_cpus

num_traits

openssl

openssl_probe

openssl_sys

parking_lot

condvar.rs deadlock.rs elision.rs lib.rs mutex.rs once.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

proc_macro2

fallback.rs lib.rs strnom.rs wrapper.rs

protobuf

protobuf_json

publicsuffix

errors.rs lib.rs

quote

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

rand

rand_chacha

chacha.rs lib.rs

rand_core

rand_hc

hc128.rs lib.rs

rand_isaac

isaac.rs isaac64.rs isaac_array.rs lib.rs

rand_jitter

dummy_log.rs error.rs lib.rs platform.rs

rand_os

dummy_log.rs lib.rs linux_android.rs random_device.rs

rand_pcg

lib.rs pcg128.rs pcg64.rs

rand_xorshift

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_syntax

ast

mod.rs parse.rs print.rs visitor.rs

hir

literal

interval.rs mod.rs print.rs translate.rs visitor.rs

unicode_tables

either.rs error.rs lib.rs parser.rs unicode.rs utf8.rs

reqwest

rustc_demangle

legacy.rs lib.rs v0.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 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

impls.rs impossible.rs mod.rs

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

serde_codegen_internals

ast.rs attr.rs case.rs ctxt.rs lib.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

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

slab

smallvec

smpl_jwt

error.rs lib.rs

socket2

sys

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

string

syn

synom

helper.rs lib.rs space.rs

synstructure

lib.rs macros.rs

time

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

tokio

executor

current_thread

reactor

mod.rs poll_evented.rs

runtime

current_thread

builder.rs mod.rs runtime.rs

threadpool

builder.rs mod.rs shutdown.rs task_executor.rs

util

enumerate.rs future.rs mod.rs stream.rs

clock.rs io.rs lib.rs net.rs prelude.rs timer.rs

tokio_buf

util

chain.rs collect.rs from.rs iter.rs limit.rs mod.rs stream.rs

lib.rs never.rs size_hint.rs str.rs u8.rs

tokio_current_thread

lib.rs scheduler.rs

tokio_executor

enter.rs error.rs executor.rs global.rs lib.rs park.rs typed.rs

tokio_io

tokio_reactor

background.rs lib.rs poll_evented.rs registration.rs sharded_rwlock.rs

tokio_sync

mpsc

block.rs bounded.rs chan.rs list.rs mod.rs unbounded.rs

task

atomic_task.rs mod.rs

lib.rs lock.rs loom.rs oneshot.rs semaphore.rs watch.rs

tokio_tcp

incoming.rs lib.rs listener.rs stream.rs

tokio_threadpool

tokio_timer

try_from

char.rs int.rs lib.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 normalize.rs perfect_hash.rs quick_check.rs recompose.rs stream_safe.rs tables.rs

unicode_xid

lib.rs tables.rs

url

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

uuid

adapter

core_support

parser

core_support.rs mod.rs std_support.rs

builder.rs core_support.rs lib.rs prelude.rs std_support.rs v4.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
    }
}