~/bend-docscommunity

src/containers/lru.bend checks

raw source on the hub · import 0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/lru.bend as Lru

4 imports
import Base
import ../math/u64.bend as W
import ../math/hash.bend as HS
import ./hash_table.bend as H

Types

type Ent source · line 45 · raw

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

An entry about to be stored: its value, whether it is timed, its deadline.

type LRU source · line 56 · raw

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

type Made source · line 65 · raw

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

type DStep source · line 241 · raw

Type

type Rz source · line 733 · raw

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

type Kx source · line 781 · raw

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

type Walk source · line 828 · raw

Type

Definitions

def pick source · line 29 · raw

@b:Bool -> @+x:U32 -> @+y:U32 -> U32

def pidx source · line 36 · raw

@+s:U32 -> U32

def nidx source · line 39 · raw

@+s:U32 -> U32

def vac source · line 49 · raw

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

An entry array of depth vacant cells (Array.new needs Data values).

def bump_hi_go source · line 61 · raw

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

def meta0 source · line 69 · raw

Array<U32>

def init source · line 72 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> LRU<a, V>

def capacity source · line 75 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Pair(LRU<a, V>, U32)

def new_checked source · line 79 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @zero:Bool -> @reserved:Bool -> Made<a, V>

def new source · line 88 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> Made<a, V>

def grow_tab_b source · line 93 · raw

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

def grow_tab source · line 99 · raw

@m:Array<U32> -> @tab:Array<U32> -> @+mask:U32 -> @over:Bool -> Pair(Array<U32>, Array<U32>)

def room_fin source · line 106 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @r:Pair(Array<U32>, Array<U32>) -> LRU<a, V>

def room_m source · line 110 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def room source · line 115 · raw

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

Keep the table load <= 1/2 for one more entry.

def ent_dl source · line 119 · raw

@-a:Quant -> @-V:Kind(a) -> @v:V -> @d:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Ent<a, V>

def life_hi source · line 123 · raw

@-a:Quant -> @-V:Kind(a) -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+lo:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Ent<a, V>)

def life_lo source · line 127 · raw

@-a:Quant -> @-V:Kind(a) -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Ent<a, V>)

def ent_if source · line 131 · raw

@-a:Quant -> @-V:Kind(a) -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @m:Array<U32> -> @on:Bool -> Pair(Array<U32>, Ent<a, V>)

def ent_ttl source · line 138 · raw

@-a:Quant -> @-V:Kind(a) -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Ent<a, V>)

def entry_of source · line 143 · raw

@-a:Quant -> @-V:Kind(a) -> @m:Array<U32> -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(Array<U32>, Ent<a, V>)

The entry to store: immortal without a lifetime, else due at now + lifetime.

def set_if source · line 146 · raw

@a:Array<U32> -> @+i:U32 -> @+x:U32 -> @skip:Bool -> Array<U32>

def ul_fin source · line 155 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @+p:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def ul_p source · line 160 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @+s:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def touch_go source · line 175 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @newest:Bool -> LRU<a, V>

def touch source · line 182 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> LRU<a, V>

def bump_hi source · line 186 · raw

@k:Array<U32> -> @+c:U32 -> @zero:Bool -> Array<U32>

def bump_lo source · line 193 · raw

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

def bump source · line 198 · raw

@+c:U32 -> @k:Array<U32> -> Array<U32>

def tidx source · line 201 · raw

@+s:U32 -> U32

def dlo_idx source · line 204 · raw

@+s:U32 -> U32

def dhi_idx source · line 207 · raw

@+s:U32 -> U32

def put_ent source · line 211 · raw

@-a:Quant -> @-V:Kind(a) -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+s:U32 -> @e:Ent<a, V> -> Pair(Array<Maybe<a, V>>, Array<U32>)

Present key: new entry in place, touched, counted as an insertion.

def repl_fin source · line 215 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @+s:U32 -> @r:Pair(Array<Maybe<a, V>>, Array<U32>) -> LRU<a, V>

def replace source · line 220 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @e:Ent<a, V> -> LRU<a, V>

Present key: new entry in place, touched, counted as an insertion.

def drop_e source · line 228 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @lk:Array<U32> -> @+s:U32 -> @+c:U32 -> @r:Pair(Array<Maybe<a, V>>, Maybe<a, V>) -> Pair(LRU<a, V>, Maybe<a, V>)

def drop_core source · line 234 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+c:U32 -> Pair(LRU<a, V>, Maybe<a, V>)

Unlink live slot s, free it and count it (c = 1 eviction, 2 removal); the table is updated by the caller.

def drop_slot source · line 238 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+c:U32 -> Pair(LRU<a, V>, Maybe<a, V>)

def ds_if source · line 245 · raw

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

def ds_l source · line 252 · raw

@+l:U32 -> @r:Pair(Array<U32>, U32) -> DStep

def dstep source · line 256 · raw

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

def dfind source · line 259 · raw

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

def dl_h source · line 275 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @+s:U32 -> @+c:U32 -> @+mask:U32 -> @m:Array<U32> -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def hidx source · line 279 · raw

@+s:U32 -> U32

def dl_m source · line 282 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+s:U32 -> @+c:U32 -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def remove_slot source · line 287 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+c:U32 -> Pair(LRU<a, V>, Maybe<a, V>)

Drop slot s and its bucket (found by its stored hash and link).

def drop_v source · line 291 · raw

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

def evict_oldest source · line 295 · raw

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

def ps_fin source · line 299 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @+s:U32 -> @+h:U32 -> @r:Pair(Array<Maybe<a, V>>, Array<U32>) -> LRU<a, V>

def put_slot source · line 303 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+s:U32 -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> LRU<a, V>

def grow_sz source · line 306 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @+fresh:U32 -> @+size:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def fresh_room source · line 314 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @+fresh:U32 -> @+size:U32 -> @room:Bool -> LRU<a, V>

def fresh_sz source · line 321 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @+fresh:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def fresh_f source · line 325 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def free_next source · line 329 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+s:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def alloc_pick source · line 333 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> @none:Bool -> LRU<a, V>

def insert_slot source · line 341 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> LRU<a, V>

Store a new key (its bucket already written) in a free or fresh slot.

def next_slot_m source · line 346 · raw

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

The slot insert_slot will take: the free-list head, else the next fresh one.

def set_bucket_m source · line 350 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+at:U32 -> @+h:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def ins_m source · line 355 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+h:U32 -> @+mask:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def ins_mask source · line 359 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+h:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def miss_full source · line 365 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+h:U32 -> @e:Ent<a, V> -> LRU<a, V>

Full: evict the oldest first (which may shift buckets), then re-probe for an empty bucket; the key is known absent.

def mr_size source · line 370 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> @+fresh:U32 -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

Not full: the probe's empty bucket takes the key.

def mr_fresh source · line 374 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> @r:Pair(Array<U32>, U32) -> LRU<a, V>

def mr_pick source · line 378 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> @none:Bool -> LRU<a, V>

def miss_room source · line 386 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> LRU<a, V>

Not full: the probe's empty bucket takes the key; the slot is chosen once.

def add_miss source · line 390 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> @full:Bool -> Pair(LRU<a, V>, Bool)

def add_full source · line 397 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+at:U32 -> @+h:U32 -> @e:Ent<a, V> -> Pair(LRU<a, V>, Bool)

def add_pick source · line 401 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @+at:U32 -> @+h:U32 -> @+l:U32 -> @e:Ent<a, V> -> @absent:Bool -> Pair(LRU<a, V>, Bool)

def add_e source · line 408 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @+at:U32 -> @+h:U32 -> @+l:U32 -> @r:Pair(Array<U32>, Ent<a, V>) -> Pair(LRU<a, V>, Bool)

def add_fd source · line 412 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+h:U32 -> @fd:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found -> Pair(LRU<a, V>, Bool)

def add_found source · line 416 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found, U32) -> Pair(LRU<a, V>, Bool)

def add_m source · line 420 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Bool)

def add_go source · line 424 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

def add_long source · line 428 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

def add source · line 432 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @v:V -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

Insert or replace key; the Bool reports whether an entry was evicted.

def fbump source · line 435 · raw

@-a:Quant -> @-V:Kind(a) -> @+c:U32 -> @f:LRU<a, V> -> LRU<a, V>

def expired_choose source · line 439 · raw

@deadline:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @immortal:Bool -> Bool

def expired source · line 447 · raw

@+deadline:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Bool

A deadline of zero never expires; otherwise deadline <= now (signed).

def gone_hi source · line 451 · raw

@+lo:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Bool)

Whether slot s holds an expired entry (from its timing words in lk).

def gone_lo source · line 455 · raw

@+s:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Bool)

def gone_t source · line 459 · raw

@+s:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @lk:Array<U32> -> @timed:Bool -> Pair(Array<U32>, Bool)

def gone_r source · line 466 · raw

@+s:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Bool)

def gone source · line 470 · raw

@lk:Array<U32> -> @+s:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(Array<U32>, Bool)

def miss_if source · line 475 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+tracked:Bool -> LRU<a, V>

def rd_live source · line 482 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+tracked:Bool -> @v:V -> Pair(LRU<a, V>, Maybe<a, V>)

def rd_gone source · line 489 · raw

@-a:Quant -> @-V:Kind(a) -> @+tracked:Bool -> @r:Pair(LRU<a, V>, Maybe<a, V>) -> Pair(LRU<a, V>, Maybe<a, V>)

def rd_exp_m source · line 493 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+s:U32 -> @+at:U32 -> @+tracked:Bool -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def rd_expire source · line 498 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+at:U32 -> @+tracked:Bool -> Pair(LRU<a, V>, Maybe<a, V>)

The expired entry found at bucket at: dropped as a removal, read as a miss.

def rd_val source · line 504 · raw

@-V:Data -> @f:LRU<&2, V> -> @+s:U32 -> @+tracked:Bool -> @m:Maybe<&2, V> -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_v source · line 511 · raw

@-V:Data -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @lk:Array<U32> -> @+s:U32 -> @+tracked:Bool -> @r:Pair(Array<Maybe<&2, V>>, Maybe<&2, V>) -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_live_f source · line 515 · raw

@-V:Data -> @f:LRU<&2, V> -> @+s:U32 -> @+tracked:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_gone_pick source · line 519 · raw

@-V:Data -> @f:LRU<&2, V> -> @+s:U32 -> @+at:U32 -> @+tracked:Bool -> @g:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_g source · line 526 · raw

@-V:Data -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<&2, V>> -> @+s:U32 -> @+at:U32 -> @+tracked:Bool -> @r:Pair(Array<U32>, Bool) -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_hit source · line 530 · raw

@-V:Data -> @f:LRU<&2, V> -> @+s:U32 -> @+at:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_pick source · line 534 · raw

@-V:Data -> @f:LRU<&2, V> -> @+at:U32 -> @+l:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> @absent:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_fd source · line 541 · raw

@-V:Data -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<&2, V>> -> @lk:Array<U32> -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> @fd:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_found source · line 545 · raw

@-V:Data -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<&2, V>> -> @lk:Array<U32> -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> @r:Pair(0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found, U32) -> Pair(LRU<&2, V>, Maybe<&2, V>)

def rd_m source · line 549 · raw

@-V:Data -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<&2, V>> -> @lk:Array<U32> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> @r:Pair(Array<U32>, U32) -> Pair(LRU<&2, V>, Maybe<&2, V>)

def read_long source · line 553 · raw

@-V:Data -> @f:LRU<&2, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def read source · line 557 · raw

@-V:Data -> @f:LRU<&2, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+tracked:Bool -> Pair(LRU<&2, V>, Maybe<&2, V>)

def get source · line 560 · raw

@-V:Data -> @f:LRU<&2, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<&2, V>, Maybe<&2, V>)

def len source · line 563 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Pair(LRU<a, V>, U32)

def cnt_fin source · line 568 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @r:Pair(Array<U32>, Array<U32>) -> Pair(LRU<a, V>, Array<U32>)

A copy of the meta words: counter c is at 16 + 2c (low) and 17 + 2c (high).

def counters source · line 572 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Pair(LRU<a, V>, Array<U32>)

def set_life source · line 576 · raw

@m:Array<U32> -> @s:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @+on:U32 -> Array<U32>

def set_lifetime_packed source · line 582 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+ns:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> LRU<a, V>

Lifetime in nanoseconds; zero means entries never expire. It is kept in milliseconds, so a deadline is one limb addition.

def peek source · line 586 · raw

@-V:Data -> @f:LRU<&2, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<&2, V>, Maybe<&2, V>)

def ct_expire source · line 591 · raw

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

def ct_pick source · line 595 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+at:U32 -> @g:Bool -> Pair(LRU<a, V>, Bool)

def ct_g source · line 602 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @+s:U32 -> @+at:U32 -> @r:Pair(Array<U32>, Bool) -> Pair(LRU<a, V>, Bool)

def ct_hit source · line 606 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+s:U32 -> @+at:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

def ct_found_pick source · line 610 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+at:U32 -> @+l:U32 -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @absent:Bool -> Pair(LRU<a, V>, Bool)

def ct_fd source · line 617 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @fd:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found -> Pair(LRU<a, V>, Bool)

def ct_found source · line 621 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found, U32) -> Pair(LRU<a, V>, Bool)

def ct_m source · line 625 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Bool)

def ct_long source · line 629 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

def contains source · line 633 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @key:String -> @now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, Bool)

def rm_hit source · line 636 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+at:U32 -> @+l:U32 -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_go source · line 640 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+at:U32 -> @+l:U32 -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_pick source · line 644 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+at:U32 -> @+l:U32 -> @absent:Bool -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_pick2 source · line 651 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+at:U32 -> @+l:U32 -> @absent:Bool -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_fd source · line 654 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @fd:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_found source · line 658 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @r:Pair(0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.Found, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_m source · line 662 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @key:String -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def qrm source · line 668 · raw

@-a:Quant -> @-V:Kind(a) -> @fuel:Nat -> @s:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/containers/hash_table.QStep -> @+mask:U32 -> @+w:U32 -> @+i:U32 -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> Pair(LRU<a, V>, Maybe<a, V>)

Fused one-character remove: the probe loop finishes the operation itself, so no continuation is pushed around it.

def rm_q2 source · line 684 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @+w:U32 -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_q source · line 688 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+w:U32 -> Pair(LRU<a, V>, Maybe<a, V>)

def remove_long source · line 692 · raw

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

def rm_short source · line 696 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+c:U32 -> @ok:Bool -> Pair(LRU<a, V>, Maybe<a, V>)

def rm_c source · line 703 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+c:U32 -> @t:String -> Pair(LRU<a, V>, Maybe<a, V>)

def remove source · line 710 · raw

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

def zero_ctrs source · line 719 · raw

@m:Array<U32> -> Array<U32>

def purge_b source · line 724 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @lk:Array<U32> -> @r:Pair(Array<U32>, U32) -> Pair(LRU<a, V>, U32)

def purge source · line 729 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Pair(LRU<a, V>, U32)

Every entry and the metrics are cleared; the table keeps its size.

def rz_pick source · line 737 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @over:Bool -> Rz<a, V>

def rz_check source · line 744 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Rz<a, V>

def rz_go source · line 748 · raw

@-a:Quant -> @-V:Kind(a) -> @fuel:Nat -> @s:Rz<a, V> -> @+ev:U32 -> Pair(LRU<a, V>, Result<&2, &2, String, U32>)

def set_cap source · line 759 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+cap:U32 -> LRU<a, V>

def rz_start source · line 763 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> Pair(LRU<a, V>, Result<&2, &2, String, U32>)

def resize_go source · line 767 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+cap:U32 -> @zero:Bool -> Pair(LRU<a, V>, Result<&2, &2, String, U32>)

def resize source · line 776 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+cap:U32 -> Pair(LRU<a, V>, Result<&2, &2, String, U32>)

Set a positive capacity, evicting the oldest entries until the cache fits; reports how many were evicted. Capacity 0 fails and changes nothing.

def kx_pick source · line 785 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @gone:Bool -> Kx<a, V>

def kx_g source · line 794 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ks:Array<String> -> @ents:Array<Maybe<a, V>> -> @r:Pair(Array<U32>, Bool) -> Kx<a, V>

def kx_head source · line 798 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Kx<a, V>

def kx_if source · line 802 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @empty:Bool -> Kx<a, V>

def kx_check source · line 809 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Kx<a, V>

def drop_head source · line 813 · raw

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

def kx_go source · line 817 · raw

@-a:Quant -> @-V:Kind(a) -> @fuel:Nat -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @s:Kx<a, V> -> LRU<a, V>

def wk_p source · line 831 · raw

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

def wk_c source · line 835 · raw

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

def wk_k source · line 839 · raw

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

def wk_word source · line 843 · raw

@ks:Array<String> -> @acc:List<&2, String> -> @+at:U32 -> @+kw:U32 -> @lk:Array<U32> -> @short:Bool -> Walk

def wk_w source · line 850 · raw

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

def wk_step source · line 855 · raw

@w:Walk -> Walk

A one-character key is stored only as its tagged word.

def wk_loop source · line 859 · raw

@fuel:Nat -> @w:Walk -> Walk

def keys_fin source · line 866 · raw

@-a:Quant -> @-V:Kind(a) -> @+cap:U32 -> @+n:U32 -> @+head:U32 -> @+tail:U32 -> @+free:U32 -> @m:Array<U32> -> @tab:Array<U32> -> @ents:Array<Maybe<a, V>> -> @w:Walk -> Pair(LRU<a, V>, List<&2, String>)

def keys_list source · line 870 · raw

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

def keys_n source · line 874 · raw

@-a:Quant -> @-V:Kind(a) -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> @f:LRU<a, V> -> LRU<a, V>

def keys source · line 880 · raw

@-a:Quant -> @-V:Kind(a) -> @f:LRU<a, V> -> @+now:0x9ee2e9a299991dcc089fe22c7f3ceb5f/src/math/u64.U64 -> Pair(LRU<a, V>, List<&2, String>)

The keys oldest first, after the oldest EXPIRED prefix is removed (each a removal), stopping at the first immortal or live oldest entry.