sparse.rs.html -- source

Files

adler32

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

alga

general

complex.rs identity.rs lattice.rs mod.rs module.rs one_operator.rs operator.rs real.rs specialized.rs subset.rs two_operators.rs wrapper.rs

linear

id.rs matrix.rs mod.rs transformation.rs vector.rs

lib.rs macros.rs

approx

abs_diff_eq.rs lib.rs macros.rs relative_eq.rs ulps_eq.rs

ascii

ascii_char.rs ascii_str.rs ascii_string.rs free_functions.rs lib.rs

atty

backtrace

backtrace

libunwind.rs mod.rs

symbolize

dladdr.rs libbacktrace.rs mod.rs

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

backtrace_sys

base64

lib.rs line_wrap.rs tables.rs

bitflags

blas_src

block_buffer

block_padding

brotli2

bufread.rs lib.rs raw.rs read.rs write.rs

brotli_sys

buf_redux

buffer

mod.rs std_buf.rs

lib.rs policy.rs

byte_tools

byteorder

cauchy

cblas_sys

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

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

chunked_transfer

decoder.rs encoder.rs lib.rs

colored

color.rs control.rs lib.rs style.rs

crc32fast

specialized

mod.rs pclmulqdq.rs

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

crossbeam

crossbeam_channel

flavors

after.rs array.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_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

ctrlc

platform

unix

error.rs lib.rs signal.rs

deflate

digest

digest.rs dyn_digest.rs errors.rs lib.rs

dirs

lib.rs lin.rs unix.rs

error_chain

error_chain.rs example_generated.rs lib.rs quick_error.rs quick_main.rs

filetime

unix

linux.rs mod.rs utimes.rs

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

generic_array

arr.rs functional.rs hex.rs impls.rs iter.rs lib.rs sequence.rs

getrandom

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

gzip_header

crc_reader.rs lib.rs

hex

error.rs lib.rs

httparse

simd

avx2.rs mod.rs sse42.rs

iter.rs lib.rs macros.rs

hyper

client

mod.rs pool.rs proxy.rs request.rs response.rs

header

common

accept.rs accept_charset.rs accept_encoding.rs accept_language.rs accept_ranges.rs access_control_allow_credentials.rs access_control_allow_headers.rs access_control_allow_methods.rs access_control_allow_origin.rs access_control_expose_headers.rs access_control_max_age.rs access_control_request_headers.rs access_control_request_method.rs allow.rs authorization.rs cache_control.rs connection.rs content_disposition.rs content_encoding.rs content_language.rs content_length.rs content_range.rs content_type.rs cookie.rs date.rs etag.rs expect.rs expires.rs from.rs host.rs if_match.rs if_modified_since.rs if_none_match.rs if_range.rs if_unmodified_since.rs last_modified.rs link.rs location.rs mod.rs origin.rs pragma.rs prefer.rs preference_applied.rs range.rs referer.rs referrer_policy.rs server.rs set_cookie.rs strict_transport_security.rs transfer_encoding.rs upgrade.rs user_agent.rs vary.rs

internals

cell.rs item.rs mod.rs vec_map.rs

shared

charset.rs encoding.rs entity.rs httpdate.rs mod.rs quality_item.rs

mod.rs parsing.rs

http

h1.rs message.rs mod.rs

server

listener.rs mod.rs request.rs response.rs

buffer.rs error.rs lib.rs method.rs net.rs status.rs uri.rs version.rs

idna

lib.rs punycode.rs uts46.rs

itoa

language_tags

lapack_src

lapacke

lapacke_sys

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

libm

math

acos.rs acosf.rs acosh.rs acoshf.rs asin.rs asinf.rs asinh.rs asinhf.rs atan.rs atan2.rs atan2f.rs atanf.rs atanh.rs atanhf.rs cbrt.rs cbrtf.rs ceil.rs ceilf.rs copysign.rs copysignf.rs cos.rs cosf.rs cosh.rs coshf.rs erf.rs erff.rs exp.rs exp10.rs exp10f.rs exp2.rs exp2f.rs expf.rs expm1.rs expm1f.rs expo2.rs fabs.rs fabsf.rs fdim.rs fdimf.rs fenv.rs floor.rs floorf.rs fma.rs fmaf.rs fmax.rs fmaxf.rs fmin.rs fminf.rs fmod.rs fmodf.rs frexp.rs frexpf.rs hypot.rs hypotf.rs ilogb.rs ilogbf.rs j0.rs j0f.rs j1.rs j1f.rs jn.rs jnf.rs k_cos.rs k_cosf.rs k_expo2.rs k_expo2f.rs k_sin.rs k_sinf.rs k_tan.rs k_tanf.rs ldexp.rs ldexpf.rs lgamma.rs lgamma_r.rs lgammaf.rs lgammaf_r.rs log.rs log10.rs log10f.rs log1p.rs log1pf.rs log2.rs log2f.rs logf.rs mod.rs modf.rs modff.rs nextafter.rs nextafterf.rs pow.rs powf.rs rem_pio2.rs rem_pio2_large.rs rem_pio2f.rs remainder.rs remainderf.rs remquo.rs remquof.rs round.rs roundf.rs scalbn.rs scalbnf.rs sin.rs sincos.rs sincosf.rs sinf.rs sinh.rs sinhf.rs sqrt.rs sqrtf.rs tan.rs tanf.rs tanh.rs tanhf.rs tgamma.rs tgammaf.rs trunc.rs truncf.rs

linked_hash_map

log

lib.rs macros.rs

matches

matrixmultiply

x86

macros.rs mod.rs

aligned_alloc.rs archparam.rs debugmacros.rs dgemm_kernel.rs gemm.rs kernel.rs lib.rs loopmacros.rs sgemm_kernel.rs util.rs

maybe_uninit

md5

consts.rs lib.rs utils.rs

memchr

x86

avx.rs mod.rs sse2.rs

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

memoffset

lib.rs offset_of.rs span_of.rs

mime

mime_guess

multipart

server

boundary.rs field.rs mod.rs save.rs

nalgebra

base

geometry

isometry.rs isometry_alga.rs isometry_alias.rs isometry_construction.rs isometry_conversion.rs isometry_ops.rs mod.rs op_macros.rs orthographic.rs perspective.rs point.rs point_alga.rs point_alias.rs point_construction.rs point_conversion.rs point_coordinates.rs point_ops.rs quaternion.rs quaternion_alga.rs quaternion_construction.rs quaternion_conversion.rs quaternion_coordinates.rs quaternion_ops.rs reflection.rs rotation.rs rotation_alga.rs rotation_alias.rs rotation_construction.rs rotation_conversion.rs rotation_ops.rs rotation_specialization.rs similarity.rs similarity_alga.rs similarity_alias.rs similarity_construction.rs similarity_conversion.rs similarity_ops.rs swizzle.rs transform.rs transform_alga.rs transform_alias.rs transform_construction.rs transform_conversion.rs transform_ops.rs translation.rs translation_alga.rs translation_alias.rs translation_construction.rs translation_conversion.rs translation_coordinates.rs translation_ops.rs unit_complex.rs unit_complex_alga.rs unit_complex_construction.rs unit_complex_conversion.rs unit_complex_ops.rs

linalg

balancing.rs bidiagonal.rs cholesky.rs convolution.rs determinant.rs full_piv_lu.rs givens.rs hessenberg.rs householder.rs inverse.rs lu.rs mod.rs permutation_sequence.rs qr.rs schur.rs solve.rs svd.rs symmetric_eigen.rs symmetric_tridiagonal.rs

ndarray

ndarray_linalg

net2

sys

unix

impls.rs mod.rs

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

netlib_src

nix

num_complex

cast.rs crand.rs lib.rs pow.rs

num_cpus

lib.rs linux.rs

num_integer

lib.rs roots.rs

num_rational

num_traits

ops

checked.rs inv.rs mod.rs mul_add.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

opaque_debug

percent_encoding

phf

lib.rs map.rs ordered_map.rs ordered_set.rs set.rs

phf_shared

ppv_lite86

x86_64

lib.rs soft.rs types.rs

proc_macro2

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

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

rand_distr

binomial.rs cauchy.rs dirichlet.rs exponential.rs gamma.rs lib.rs normal.rs pareto.rs pert.rs poisson.rs triangular.rs unit_ball.rs unit_circle.rs unit_disc.rs unit_sphere.rs utils.rs weibull.rs ziggurat_tables.rs

rawpointer

regex

regex_syntax

remove_dir_all

rosrust

rosrust_codegen

error.rs genmsg.rs helpers.rs lib.rs message_path.rs msg.rs output_layout.rs rosmsg_include.rs

rosrust_msg

rouille

rustc_demangle

legacy.rs lib.rs v0.rs

rustros_tf

lib.rs msg.rs transforms.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

safemem

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_bytes

lib.rs value.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_xml_rs

error.rs lib.rs map.rs seq.rs serialize.rs var.rs

sha1

siphasher

lib.rs sip.rs sip128.rs

smallvec

syn

tempdir

term

terminfo

parser

compiled.rs names.rs

mod.rs parm.rs searcher.rs

thread_local

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

threadpool

time

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

tiny_http

util

custom_stream.rs equal_reader.rs messages_queue.rs mod.rs refined_tcp_stream.rs sequential.rs task_pool.rs

client.rs common.rs lib.rs request.rs response.rs

traitobject

impls.rs lib.rs

twoway

bmh.rs lib.rs util.rs

typeable

typenum

array.rs bit.rs int.rs lib.rs marker_traits.rs operator_aliases.rs private.rs type_operators.rs uint.rs

ucd_util

unicode_tables

jamo_short_name.rs mod.rs

hangul.rs ideograph.rs lib.rs name.rs property.rs

unicase

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

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

utf8_ranges

char_utf8.rs lib.rs

void

xml

xml_rpc

xmlfmt

de.rs error.rs mod.rs parse.rs ser.rs value.rs

client.rs error.rs lib.rs server.rs

yaml_rust

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

use std::fmt;
use std::ops::Deref;
use std::slice;

/// A sparse set used for representing ordered NFA states.
///
/// This supports constant time addition and membership testing. Clearing an
/// entire set can also be done in constant time. Iteration yields elements
/// in the order in which they were inserted.
///
/// The data structure is based on: http://research.swtch.com/sparse
/// Note though that we don't actually use uninitialized memory. We generally
/// reuse allocations, so the initial allocation cost is bareable. However,
/// its other properties listed above are extremely useful.
#[derive(Clone)]
pub struct SparseSet {
    /// Dense contains the instruction pointers in the order in which they
    /// were inserted.
    dense: Vec<usize>,
    /// Sparse maps instruction pointers to their location in dense.
    ///
    /// An instruction pointer is in the set if and only if
    /// sparse[ip] < dense.len() && ip == dense[sparse[ip]].
    sparse: Box<[usize]>,
}

impl SparseSet {
    pub fn new(size: usize) -> SparseSet {
        SparseSet {
            dense: Vec::with_capacity(size),
            sparse: vec![0; size].into_boxed_slice(),
        }
    }

    pub fn len(&self) -> usize {
        self.dense.len()
    }

    pub fn is_empty(&self) -> bool {
        self.dense.is_empty()
    }

    pub fn capacity(&self) -> usize {
        self.dense.capacity()
    }

    pub fn insert(&mut self, value: usize) {
        let i = self.len();
        assert!(i < self.capacity());
        self.dense.push(value);
        self.sparse[value] = i;
    }

    pub fn contains(&self, value: usize) -> bool {
        let i = self.sparse[value];
        self.dense.get(i) == Some(&value)
    }

    pub fn clear(&mut self) {
        self.dense.clear();
    }
}

impl fmt::Debug for SparseSet {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "SparseSet({:?})", self.dense)
    }
}

impl Deref for SparseSet {
    type Target = [usize];

    fn deref(&self) -> &Self::Target {
        &self.dense
    }
}

impl<'a> IntoIterator for &'a SparseSet {
    type Item = &'a usize;
    type IntoIter = slice::Iter<'a, usize>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

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