~/bend-docscommunity

src/containers/hash_table.bend checks

raw source on the hub · import 0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.bend as Hash_table

2 imports
import Base
import ../math/hash.bend as HS

Types

type HashMap source · line 31 · raw

@-a:Quant -> @-V:Kind(a) -> Type

type Found source · line 110 · raw

Type

type Step source · line 114 · raw

Type

Long keys: a matching word is confirmed against the slot's stored String.

type QStep source · line 183 · raw

Type

One-character keys: the bucket words alone decide.

type QFound source · line 213 · raw

Type

type RStep source · line 264 · raw

Type

type Mv source · line 298 · raw

Type

type Sh source · line 334 · raw

Type

type Arena source · line 404 · raw

@-a:Quant -> @-V:Kind(a) -> Type

type Walk source · line 536 · raw

Type

Definitions

def size source · line 34 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> Pair(HashMap<a, V>, U32)

def tag source · line 40 · raw

U32

def bnext source · line 43 · raw

@+i:U32 -> @+mask:U32 -> U32

def slot source · line 49 · raw

@+l:U32 -> U32

def short_word source · line 52 · raw

@+c:U32 -> U32

def long_word source · line 55 · raw

@+h:U32 -> U32

def is_short source · line 58 · raw

@+w:U32 -> Bool

def rev_onto source · line 61 · raw

@s:String -> @acc:String -> String

def hash_acc source · line 68 · raw

@s:String -> @+h:U32 -> @acc:String -> Pair(String, U32)

def eq_acc source · line 75 · raw

@a:String -> @b:String -> @ra:String -> @rb:String -> @+e:Bool -> Pair(Pair(String, String), Bool)

def eq source · line 87 · raw

@a:String -> @b:String -> Pair(Pair(String, String), Bool)

String equality, handing both strings back.

def copy_acc source · line 90 · raw

@s:String -> @ra:String -> @rb:String -> Pair(String, String)

def str_copy source · line 98 · raw

@s:String -> Pair(String, String)

A deep copy (sharing a String with + would refcount every String).

def lw_fin source · line 101 · raw

@r:Pair(String, U32) -> Pair(String, U32)

def key_long source · line 105 · raw

@key:String -> Pair(String, U32)

def sk_pick source · line 119 · raw

@tab:Array<U32> -> @+l:U32 -> @ks:Array<String> -> @key:String -> @e:Bool -> Step

def sk_fin source · line 126 · raw

@tab:Array<U32> -> @+l:U32 -> @ks:Array<String> -> @r:Pair(Pair(String, String), Bool) -> Step

def sk_cmp source · line 130 · raw

@tab:Array<U32> -> @+l:U32 -> @key:String -> @r:Pair(Array<String>, String) -> Step

def sk_same source · line 134 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+l:U32 -> @key:String -> @same:Bool -> Step

def sk_l source · line 141 · raw

@ks:Array<String> -> @key:String -> @+x:U32 -> @+w:U32 -> @r:Pair(Array<U32>, U32) -> Step

def sk_empty source · line 145 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+i:U32 -> @key:String -> @+w:U32 -> @+x:U32 -> @e:Bool -> Step

def sk_w source · line 152 · raw

@ks:Array<String> -> @+i:U32 -> @key:String -> @+w:U32 -> @r:Pair(Array<U32>, U32) -> Step

def step source · line 156 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+i:U32 -> @key:String -> @+w:U32 -> Step

def find source · line 159 · raw

@fuel:Nat -> @s:Step -> @+mask:U32 -> @+w:U32 -> @+i:U32 -> Found

def probe_lw source · line 175 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+mask:U32 -> @r:Pair(String, U32) -> Pair(Found, U32)

def probe_long source · line 179 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+mask:U32 -> @key:String -> Pair(Found, U32)

def qs_l source · line 188 · raw

@r:Pair(Array<U32>, U32) -> QStep

def qs_same source · line 192 · raw

@tab:Array<U32> -> @+i:U32 -> @same:Bool -> QStep

def qs_if source · line 199 · raw

@tab:Array<U32> -> @+i:U32 -> @+w:U32 -> @+x:U32 -> @e:Bool -> QStep

def qs_w source · line 206 · raw

@+i:U32 -> @+w:U32 -> @r:Pair(Array<U32>, U32) -> QStep

def qstep source · line 210 · raw

@tab:Array<U32> -> @+i:U32 -> @+w:U32 -> QStep

def qfind source · line 216 · raw

@fuel:Nat -> @s:QStep -> @+mask:U32 -> @+w:U32 -> @+i:U32 -> QFound

def q_fin source · line 232 · raw

@ks:Array<String> -> @+w:U32 -> @r:QFound -> Pair(Found, U32)

def probe_short source · line 236 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+mask:U32 -> @+c:U32 -> @ok:Bool -> Pair(Found, U32)

def probe_c source · line 243 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+mask:U32 -> @+c:U32 -> @t:String -> Pair(Found, U32)

def probe source · line 252 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+mask:U32 -> @key:String -> Pair(Found, U32)

The bucket holding key (link != 0) or the empty bucket ending its probe, the key as it would be stored (SNil for a one-character key), and its word.

def put_bucket source · line 261 · raw

@tab:Array<U32> -> @+i:U32 -> @+w:U32 -> @+l:U32 -> Array<U32>

def rs_if source · line 268 · raw

@tab:Array<U32> -> @e:Bool -> RStep

def rs_w source · line 275 · raw

@r:Pair(Array<U32>, U32) -> RStep

def rstep source · line 279 · raw

@tab:Array<U32> -> @+i:U32 -> RStep

def ins_go source · line 282 · raw

@fuel:Nat -> @s:RStep -> @+mask:U32 -> @+i:U32 -> @+w:U32 -> @+l:U32 -> Array<U32>

def ins_raw source · line 295 · raw

@tab:Array<U32> -> @+mask:U32 -> @+w:U32 -> @+l:U32 -> Array<U32>

Put (w, l) in the first empty bucket of w's probe.

def mv_l source · line 301 · raw

@+w:U32 -> @nt:Array<U32> -> @+nmask:U32 -> @r:Pair(Array<U32>, U32) -> Mv

def mv_if source · line 305 · raw

@+k:U32 -> @old:Array<U32> -> @nt:Array<U32> -> @+nmask:U32 -> @+w:U32 -> @e:Bool -> Mv

def mv_w source · line 312 · raw

@+k:U32 -> @nt:Array<U32> -> @+nmask:U32 -> @r:Pair(Array<U32>, U32) -> Mv

def mv_step source · line 316 · raw

@+k:U32 -> @+nmask:U32 -> @m:Mv -> Mv

def mv_go source · line 320 · raw

@fuel:Nat -> @+k:U32 -> @+nmask:U32 -> @m:Mv -> Mv

def mv_fin source · line 327 · raw

@m:Mv -> Array<U32>

def clear_bucket source · line 331 · raw

@tab:Array<U32> -> @+i:U32 -> Array<U32>

def sh_mv source · line 339 · raw

@tab:Array<U32> -> @+w:U32 -> @+l:U32 -> @mv:Bool -> Sh

def sh_l source · line 346 · raw

@+w:U32 -> @+mask:U32 -> @+i:U32 -> @+k:U32 -> @r:Pair(Array<U32>, U32) -> Sh

def sh_if source · line 350 · raw

@tab:Array<U32> -> @+mask:U32 -> @+i:U32 -> @+k:U32 -> @+w:U32 -> @e:Bool -> Sh

def sh_w source · line 357 · raw

@+mask:U32 -> @+i:U32 -> @+k:U32 -> @r:Pair(Array<U32>, U32) -> Sh

def sh_step source · line 361 · raw

@tab:Array<U32> -> @+mask:U32 -> @+i:U32 -> @+k:U32 -> Sh

def shift source · line 364 · raw

@fuel:Nat -> @s:Sh -> @+mask:U32 -> @+i:U32 -> @+k:U32 -> Array<U32>

def del_at source · line 382 · raw

@tab:Array<U32> -> @+mask:U32 -> @+i:U32 -> Array<U32>

Empty bucket i, closing the gap behind it.

def vac source · line 388 · raw

@-a:Quant -> @-V:Kind(a) -> @d:Nat -> Array<Maybe<a, V>>

A value array of 2^d vacant cells (Array.new needs Data values).

def new source · line 395 · raw

@-a:Quant -> @-V:Kind(a) -> HashMap<a, V>

def grow_tab source · line 401 · raw

@+mask:U32 -> @+td:U32 -> @tab:Array<U32> -> Array<U32>

Twice the buckets, every (word, link) pair re-placed.

def store source · line 407 · raw

@-a:Quant -> @-V:Kind(a) -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @+s:U32 -> @key:String -> @x:V -> Arena<a, V>

def ins_fin source · line 410 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @nx:Array<U32> -> @r:Arena<a, V> -> HashMap<a, V>

def ins_slot source · line 415 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @+s:U32 -> @+at:U32 -> @+w:U32 -> @key:String -> @x:V -> @over:Bool -> HashMap<a, V>

The new entry's slot s is chosen; its bucket is at (or, after growth, found anew).

def ins_free source · line 422 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @+s:U32 -> @+at:U32 -> @+w:U32 -> @key:String -> @x:V -> @r:Pair(Array<U32>, U32) -> HashMap<a, V>

def ins_fresh source · line 426 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @+at:U32 -> @+w:U32 -> @key:String -> @x:V -> @room:Bool -> HashMap<a, V>

def ins_new source · line 433 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @+at:U32 -> @+w:U32 -> @key:String -> @x:V -> @none:Bool -> HashMap<a, V>

def set_hit source · line 440 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @+at:U32 -> @+l:U32 -> @+w:U32 -> @key:String -> @x:V -> @absent:Bool -> HashMap<a, V>

def set_f source · line 447 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @x:V -> @r:Pair(Found, U32) -> HashMap<a, V>

def set source · line 453 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> @key:String -> @x:V -> HashMap<a, V>

Insert key -> x, replacing any value already stored under key.

def get_v source · line 459 · raw

@-V:Data -> @dflt:V -> @r:Pair(Array<Maybe<&2, V>>, Maybe<&2, V>) -> Pair(Array<Maybe<&2, V>>, V)

def get_fin source · line 467 · raw

@-V:Data -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @nx:Array<U32> -> @r:Pair(Array<Maybe<&2, V>>, V) -> Pair(HashMap<&2, V>, V)

def get_hit source · line 471 · raw

@-V:Data -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<&2, V>> -> @nx:Array<U32> -> @dflt:V -> @+l:U32 -> @absent:Bool -> Pair(HashMap<&2, V>, V)

def get_f source · line 478 · raw

@-V:Data -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @vs:Array<Maybe<&2, V>> -> @nx:Array<U32> -> @dflt:V -> @r:Pair(Found, U32) -> Pair(HashMap<&2, V>, V)

def get source · line 484 · raw

@-V:Data -> @dflt:V -> @m:HashMap<&2, V> -> @key:String -> Pair(HashMap<&2, V>, V)

The value stored under key, or dflt (values are copied out, so V: Data).

def has_f source · line 488 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @r:Pair(Found, U32) -> Pair(HashMap<a, V>, Bool)

def has source · line 493 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> @key:String -> Pair(HashMap<a, V>, Bool)

def drop_key source · line 499 · raw

@ks:Array<String> -> @+s:U32 -> @short:Bool -> Array<String>

def pop_v source · line 506 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @nx:Array<U32> -> @+at:U32 -> @+s:U32 -> @+w:U32 -> @r:Pair(Array<Maybe<a, V>>, Maybe<a, V>) -> Pair(HashMap<a, V>, Maybe<a, V>)

def pop_hit source · line 510 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @+at:U32 -> @+l:U32 -> @+w:U32 -> @absent:Bool -> Pair(HashMap<a, V>, Maybe<a, V>)

def pop_f source · line 517 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @r:Pair(Found, U32) -> Pair(HashMap<a, V>, Maybe<a, V>)

def pop source · line 523 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> @key:String -> Pair(HashMap<a, V>, Maybe<a, V>)

Remove key, answering its value.

def del_drop source · line 527 · raw

@-a:Quant -> @-V:Kind(a) -> @r:Pair(HashMap<a, V>, Maybe<a, V>) -> HashMap<a, V>

def del source · line 531 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> @key:String -> HashMap<a, V>

def wk_long source · line 539 · raw

@tab:Array<U32> -> @+s:U32 -> @acc:List<&2, String> -> @ks:Array<String> -> @kk:Pair(String, String) -> Walk

def wk_copy source · line 543 · raw

@tab:Array<U32> -> @+s:U32 -> @acc:List<&2, String> -> @r:Pair(Array<String>, String) -> Walk

def wk_ll source · line 547 · raw

@ks:Array<String> -> @acc:List<&2, String> -> @r:Pair(Array<U32>, U32) -> Walk

def wk_kind source · line 551 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+k:U32 -> @acc:List<&2, String> -> @+w:U32 -> @short:Bool -> Walk

def wk_if source · line 558 · raw

@tab:Array<U32> -> @ks:Array<String> -> @+k:U32 -> @acc:List<&2, String> -> @+w:U32 -> @e:Bool -> Walk

def wk_w source · line 565 · raw

@ks:Array<String> -> @+k:U32 -> @acc:List<&2, String> -> @r:Pair(Array<U32>, U32) -> Walk

def wk_step source · line 569 · raw

@+k:U32 -> @w:Walk -> Walk

def wk_go source · line 573 · raw

@fuel:Nat -> @+k:U32 -> @w:Walk -> Walk

def keys_fin source · line 580 · raw

@-a:Quant -> @-V:Kind(a) -> @+n:U32 -> @+mask:U32 -> @+td:U32 -> @+fresh:U32 -> @+sz:U32 -> @+sd:U32 -> @+free:U32 -> @vs:Array<Maybe<a, V>> -> @nx:Array<U32> -> @w:Walk -> Pair(HashMap<a, V>, List<&2, String>)

def keys source · line 585 · raw

@-a:Quant -> @-V:Kind(a) -> @m:HashMap<a, V> -> Pair(HashMap<a, V>, List<&2, String>)

Every key, in bucket order.