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

approx

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

arrayvec

array.rs array_string.rs char.rs errors.rs lib.rs maybe_uninit_stable.rs range.rs

ascii

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

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

bitflags

brotli2

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

brotli_sys

bstr

buf_redux

buffer

mod.rs std_buf.rs

lib.rs policy.rs

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

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

color_quant

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

sync

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

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

csv

byte_record.rs cookbook.rs deserializer.rs error.rs lib.rs reader.rs serializer.rs string_record.rs tutorial.rs writer.rs

csv_core

lib.rs reader.rs writer.rs

csv_user_import

csv_user_import.rs

deflate

diesel

associations

belongs_to.rs mod.rs

connection

mod.rs statement_cache.rs transaction_manager.rs

expression

expression_methods

bool_expression_methods.rs eq_all.rs escape_expression_methods.rs global_expression_methods.rs mod.rs text_expression_methods.rs

macros

internal.rs mod.rs ops.rs query_id.rs static_cond.rs tuples.rs

migration

errors.rs mod.rs

mysql

connection

stmt

iterator.rs metadata.rs mod.rs

bind.rs mod.rs raw.rs url.rs

query_builder

mod.rs query_fragment_impls.rs

types

date_and_time.rs mod.rs numeric.rs

backend.rs bind_collector.rs mod.rs

query_builder

delete_statement

insert_statement

column_list.rs insert_from_select.rs mod.rs

nodes

select_statement

boxed.rs dsl_impls.rs mod.rs

update_statement

changeset.rs mod.rs target.rs

ast_pass.rs bind_collector.rs clause_macro.rs debug_query.rs distinct_clause.rs functions.rs group_by_clause.rs limit_clause.rs locking_clause.rs mod.rs offset_clause.rs order_clause.rs query_id.rs returning_clause.rs select_clause.rs sql_query.rs where_clause.rs

query_dsl

belonging_to_dsl.rs boxed_dsl.rs distinct_dsl.rs filter_dsl.rs group_by_dsl.rs join_dsl.rs limit_dsl.rs load_dsl.rs locking_dsl.rs mod.rs nullable_select_dsl.rs offset_dsl.rs order_dsl.rs save_changes_dsl.rs select_dsl.rs single_value_dsl.rs

query_source

joins.rs mod.rs peano_numbers.rs

sql_types

fold.rs mod.rs ops.rs ord.rs

type_impls

date_and_time.rs decimal.rs floats.rs integers.rs mod.rs option.rs primitives.rs tuples.rs

types

backend.rs data_types.rs deserialize.rs insertable.rs lib.rs r2d2.rs result.rs row.rs serialize.rs util.rs

diesel_derives

as_changeset.rs as_expression.rs associations.rs diagnostic_shim.rs diesel_numeric_ops.rs field.rs from_sql_row.rs identifiable.rs insertable.rs lib.rs meta.rs model.rs query_id.rs queryable.rs queryable_by_name.rs resolved_at_shim.rs sql_type.rs util.rs

diesel_migrations

dirs

lib.rs lin.rs unix.rs

dotenv

errors.rs find.rs iter.rs lib.rs parse.rs

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 example_generated.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

filetime

unix

linux.rs mod.rs utimes.rs

flate2

deflate

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

gz

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

zlib

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

bufreader.rs crc.rs ffi.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

gif

reader

decoder.rs mod.rs

common.rs encoder.rs lib.rs traits.rs util.rs

google_signin

client.rs error.rs lib.rs token.rs

gzip_header

crc_reader.rs lib.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_rustls

hyper_tls

client.rs lib.rs stream.rs

idna

lib.rs punycode.rs uts46.rs

image

indexmap

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

inflate

checksum.rs lib.rs reader.rs utils.rs writer.rs

iovec

sys

itoa

jpeg_decoder

worker

immediate.rs mod.rs threaded.rs

decoder.rs error.rs huffman.rs idct.rs lib.rs marker.rs parser.rs upsampler.rs

language_tags

lazy_static

inline_lazy.rs lib.rs

libc

unix

linux_like

linux

gnu

b64

x86_64

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

lock_api

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

log

lib.rs macros.rs

lzw

bitstream.rs lib.rs lzw.rs

matches

memchr

x86

avx.rs mod.rs sse2.rs

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

memoffset

lib.rs offset_of.rs span_of.rs

migrations_internals

connection.rs lib.rs migration.rs schema.rs

migrations_macros

embed_migrations.rs lib.rs migrations.rs util.rs

mime

mime_guess

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

multipart

server

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

mysqlclient_sys

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

nodrop

num_cpus

num_derive

num_integer

lib.rs roots.rs

num_iter

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

openssl

openssl_probe

openssl_sys

ordered_float

owning_ref

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

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

percent_encoding

phf

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

phf_shared

png

decoder

mod.rs stream.rs

chunk.rs common.rs encoder.rs filter.rs lib.rs traits.rs utils.rs

proc_macro2

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

publicsuffix

errors.rs lib.rs

quick_error

quote

ext.rs lib.rs runtime.rs to_tokens.rs

r2d2

config.rs event.rs lib.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

rayon

delegate.rs lib.rs math.rs option.rs par_either.rs prelude.rs private.rs range.rs range_inclusive.rs result.rs split_producer.rs str.rs vec.rs

rayon_core

compile_fail

mod.rs quicksort_race1.rs quicksort_race2.rs quicksort_race3.rs rc_return.rs rc_upvar.rs scope_join_bad.rs

join

scope

sleep

spawn

thread_pool

job.rs latch.rs lib.rs log.rs private.rs registry.rs unwind.rs util.rs

regex

regex_automata

classes.rs dense.rs dfa.rs lib.rs regex.rs sparse.rs state_id.rs

regex_syntax

remove_dir_all

reqwest

ring

rouille

rustc_demangle

legacy.rs lib.rs v0.rs

rustls

rusttype

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

scheduled_thread_pool

lib.rs thunk.rs

scoped_threadpool

scopeguard

sct

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

sha1

simplelog

loggers

comblog.rs logging.rs mod.rs simplelog.rs termlog.rs writelog.rs

config.rs lib.rs

siphasher

lib.rs sip.rs sip128.rs

slab

smallvec

stable_deref_trait

stb_truetype

string

syn

synom

helper.rs lib.rs space.rs

synstructure

lib.rs macros.rs

tempdir

term

terminfo

parser

compiled.rs names.rs

mod.rs parm.rs searcher.rs

thread_local

lib.rs thread_id.rs unreachable.rs

threadpool

tiff

decoder

ifd.rs mod.rs stream.rs

encoder

colortype.rs mod.rs writer.rs

error.rs lib.rs

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

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

traitobject

impls.rs lib.rs

try_from

char.rs int.rs lib.rs

try_lock

twoway

bmh.rs lib.rs util.rs

typeable

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

decompose.rs lib.rs normalize.rs quick_check.rs recompose.rs stream_safe.rs tables.rs

unicode_xid

lib.rs tables.rs

untrusted

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

webdev_lib

chemicals

models.rs requests.rs schema.rs

permissions

models.rs requests.rs schema.rs

tests

question_categories

models.rs requests.rs schema.rs

questions

models.rs requests.rs schema.rs

test_sessions

models.rs requests.rs schema.rs

tests

models.rs requests.rs schema.rs

question_categories.rs questions.rs test_sessions.rs tests.rs

users

models.rs requests.rs schema.rs

chemicals.rs errors.rs lib.rs permissions.rs search.rs tests.rs users.rs

webpki

calendar.rs cert.rs der.rs name.rs signed_data.rs time.rs trust_anchor_util.rs verify_cert.rs webpki.rs

webpki_roots

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, Debug)]
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 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()
    }
}