README- UAhoCorasick
- UArcCache
- UArenaTree
- UBiMap
- UBitSet
- UBitVec
- UBloomFilter
- UBloomOptions
- UBoyerMoore
- UCacheStats
- UChainMap
- UCombinations
- UCombinationsWithReplacement
- UCountMinSketch
- UCounter
- UCuckooFilter
- UCuckooOptions
- UDaryHeap
- UDefaultMap
- UDenseSlotMap
- UDisjointSet
- UDisjointSetMap
- UExpiringCache
- UFenwick
- UFibonacciHeap
- UFlatMap
- UFlatMultiMap
- UFlatMultiSet
- UFlatSet
- UGapBuffer
- UGrayCode
- UGrowth
- UHeapKey
- UHyperLogLog
- UIndexHeap
- UIndexMap
- UIndexSet
- UIntervalKey
- UIntervalTree
- UJoinEntry
- UKmp
- ULazySegmentTree
- ULfuCache
- ULinkedList
- ULruCache
- UMatch
- UMinMaxHeap
- UMultiMap
- UMultiSet
- UOpcode
- UOrder
- UOrderStatisticTree
- UOverflow
- UOverlap
- UPairingHeap
- UPermutations
- UPhfBuild
- UPhfBuilder
- UPhfLayout
- UPhfMap
- UPhfOptions
- UPhfOrderedMap
- UPhfOrderedSet
- UPhfSet
- UPosition
- UPowerset
- UProduct
- URadixHeap
- URadixTree
- URangeMap
- URangeSet
- URefused
- URingBuffer
- URope
- URopeBuilder
- URopeView
- USecondaryMap
- USegmentTree
- USequenceMatcher
- USequenceMatcherOptions
- USkipList
- USkipListOptions
- USlab
- USlotKey
- USlotMap
- USortedMultiMap
- USortedMultiSet
- USparseSet
- USuffixArray
- USuffixAutomaton
- UTDigest
- UThetaSketch
- UTreap
- UTreeId
- UTrie
moonbitstack/moonstl/cache does not have a README file
ArcCache
A cache that keeps the recency and the frequency of what it sees in balance,
in the manner of ARC: a hit on a re-requested key raises the share of the
cache given to frequent entries (recent_target moves up), a key that
falls back into the ghost lists takes that share down. lists reports the
four list sizes, which is how the adaptation is observed.
test {
let cache : @cache.ArcCache[String, Int32] = @cache.ArcCache::new(capacity=2)
let _ = cache.set("a", 1)
let _ = cache.set("b", 2)
let _ = cache.get("a")
let _ = cache.set("c", 3)
let (t1, t2, b1, b2) = cache.lists()
@test.assert_eq(t1 + t2, 2)
@test.assert_eq(b1 + b2 <= 2, true)
}ArcCache::contains
true when the key is resident. A key that is only remembered in a ghost
list is not contained.
ArcCache::equal
ArcCache::lists
The sizes of the four lists: the two resident ones and the two ghost ones.
ArcCache::new
ArcCache::not_equal
ArcCache::output
ArcCache::set
Stores value under key and returns the resident the insert displaced,
if any. A key that returns from a ghost list is admitted straight into the
frequent list and the share given to frequent entries moves in its favour.
ArcCache::to_string
ArcNode
pub struct ArcNode[K, V] {
key : K
value : V?
list : Int
prev : Int
next : Int
}A node of any of the four lists. A ghost carries None as its value: the
key is remembered so that a returning key can be recognised, the value is
gone.
CacheStats
Counters every cache keeps. hits and misses count lookups, evictions
counts the entries a policy dropped to make room — a remove is not an
eviction, and neither is a replacement.
impl Show for CacheStatsCacheStats::hit_rate
The hit rate, or 0 when nothing has been looked up.
test {
let stats : @cache.CacheStats = { hits: 3, misses: 1, evictions: 0, }
@test.assert_eq(stats.hit_rate(), 0.75)
}ExpNode
pub struct ExpNode[K, V] {
key : K
value : V
expire_at : Int64
stamp : Int
prev : Int
next : Int
}A node of the recency list, with the moment it stops being valid.
ExpiringCache
A cache whose entries expire: an entry is dropped when it is read after its
deadline, when a purge finds it, and by the least-recently-used rule when
the capacity is full. Expiry is lazy, so a purge is the only thing that
walks the expired entries in bulk.
The cache never reads a clock of its own — now is the caller's, which is
what lets a test move time without waiting. ttl and every deadline are in
the units of that clock.
test {
let mut clock : Int64 = 0L
let cache : @cache.ExpiringCache[String, Int32] = @cache.ExpiringCache::new(
ttl=10L,
capacity=2,
now=() => clock,
)
let _ = cache.set("a", 1)
@test.assert_eq(cache.get("a"), Some(1))
clock = 11L
@test.assert_eq(cache.get("a"), None)
}impl Show for ExpiringCache[K, V]ExpiringCache::contains
ExpiringCache::expire_at
The deadline of an entry, or None when it is not in the cache.
ExpiringCache::get
The value stored under key. An entry read after its deadline is dropped
and reads as absent.
ExpiringCache::is_empty
ExpiringCache::iter
The entries from least to most recently used, expired ones already dropped.
ExpiringCache::keys
ExpiringCache::length
The number of live entries. Expired entries are dropped first, so the count
is the count of what a get would find.
ExpiringCache::new
fn[K, V] ExpiringCache::new(ttl~ : Int64, capacity~ : Int, now~ : () -> Int64, hash_seed? : Int) -> ExpiringCache[K, V] raise RefusedExpiringCache::output
fn[K : Hash + Eq + Show, V : Show] ExpiringCache::output(self : ExpiringCache[K, V], logger : &Logger) -> UnitExpiringCache::purge
Drops every entry whose deadline has passed and reports how many went.
ExpiringCache::remove
ExpiringCache::set
fn[K : Hash + Eq, V] ExpiringCache::set(self : ExpiringCache[K, V], key : K, value : V, ttl? : Int64) -> (K, V)?Stores value under key and gives it a deadline: ttl after the clock
now, or the deadline given. Returns the entry the insert displaced.
ExpiringCache::set_expire
fn[K : Hash + Eq, V] ExpiringCache::set_expire(self : ExpiringCache[K, V], key : K, at : Int64) -> BoolMoves the deadline of an entry. false when the key is not in the cache.
ExpiringCache::to_string
ExpiringCache::values
LfuBucket
pub struct LfuBucket {
head : Int
tail : Int
}One frequency list. Buckets are indexed by frequency and grown on demand.
LfuCache
A least-frequently-used cache: an insert past the capacity drops the entry
with the smallest access count, and among equals the one that has gone
untouched the longest. A hit moves the entry into the list of the next
frequency, which is what keeps both operations O(1).
test {
let cache : @cache.LfuCache[String, Int32] = @cache.LfuCache::new(capacity=2)
let _ = cache.set("a", 1)
let _ = cache.set("b", 2)
let _ = cache.get("a")
let _ = cache.set("c", 3)
@test.assert_eq(cache.get("b"), None)
@test.assert_eq(cache.frequency("a"), Some(2))
}LfuCache::contains
LfuCache::equal
LfuCache::frequency
The access count of key, which is one more than the number of get calls
that have hit it since it was inserted.
LfuCache::new
LfuCache::not_equal
LfuCache::output
LfuCache::peek
The value stored under key without counting the access.
LfuCache::resize_capacity
LfuCache::set
LfuCache::take
Removes the entry and returns it, which is how a cache is drained one entry
at a time.
LfuCache::to_string
LfuNode
pub struct LfuNode[K, V] {
key : K
value : V
freq : Int
prev : Int
next : Int
}A node of the frequency lists. Every live entry sits in the list of its own
frequency, most recently used first, so the entry to drop is the head of the
lowest non-empty list.
LruCache
A least-recently-used cache with a fixed capacity: get marks an entry as
the most recent, and an insert past the capacity drops the entry that has
gone untouched the longest.
test {
let cache : @cache.LruCache[String, Int32] = @cache.LruCache::new(capacity=2)
let _ = cache.set("a", 1)
let _ = cache.set("b", 2)
let _ = cache.get("a")
let _ = cache.set("c", 3)
@test.assert_eq(cache.get("b"), None)
@test.assert_eq(cache.get("a"), Some(1))
}LruCache::contains
LruCache::equal
LruCache::get
The value stored under key, marking the entry as the most recently used.
test {
let cache : @cache.LruCache[Int32, String] = @cache.LruCache::new(capacity=1)
let _ = cache.set(1, "one")
@test.assert_eq(cache.get(1), Some("one"))
@test.assert_eq(cache.get(2), None)
@test.assert_eq(cache.stats().misses, 1L)
}LruCache::iter
The entries from least to most recently used.
LruCache::new
LruCache::not_equal
LruCache::output
LruCache::peek
The value stored under key, without changing the order. A cache that peeks
keeps whatever it looked at alive, which is how a scan warms entries without
keeping them.
LruCache::remove
Removes the entry under key. A removal is not an eviction: on_evict is
not called and the counter does not move.
LruCache::resize_capacity
Changes the capacity, dropping the least recently used entries when the new
capacity is smaller than the number of entries held.
LruCache::set
Stores value under key and returns the entry the insert displaced: the
pair it replaced when the key was already present, the pair the policy
dropped otherwise, None when there was room. Compare the key of the
result to tell the two apart.
test {
let cache : @cache.LruCache[String, Int32] = @cache.LruCache::new(capacity=1)
@test.assert_eq(cache.set("a", 1), None)
@test.assert_eq(cache.set("b", 2), Some(("a", 1)))
@test.assert_eq(cache.set("b", 3), Some(("b", 2)))
}LruCache::to_string
LruNode
pub struct LruNode[K, V] {
key : K
value : V
prev : Int
next : Int
}A node of one of the order lists. The slot array is indexed by a slab-style
handle; a free slot holds None, so a stale handle cannot be mistaken for a
live one.
memoize
Wraps f so that each argument is computed once and remembered, the way
functools.lru_cache does it: the returned function keeps the last
capacity results and recomputes anything that fell out.
test {
let mut calls = 0
let square : (Int32) -> Int32 = @cache.memoize(
key => {
calls += 1
key * key
},
capacity=8,
)
@test.assert_eq(square(4), 16)
@test.assert_eq(square(4), 16)
@test.assert_eq(calls, 1)
}Install
Download zipData structures and algorithms the MoonBit core library leaves out.
data-structuresalgorithmscollectionscontainersstlmoonbitindex-mapindex-setmultimapbimapcounterflat-mapsorted-maprange-maptrieradix-treelru-cachelfu-cachearc-cacheexpiring-cachememoizesortingselectionbisectbinary-searchpermutationscombinationspowersetpartitionmergering-bufferslotmapgap-bufferbit-vectorbit-setlinked-listbinary-heapfibonacci-heappairing-heapmin-max-heapradix-heapdisjoint-setunion-findsegment-treefenwick-treeinterval-treeskip-listtreapbloom-filtercuckoo-filtercount-min-sketchhyperloglogtheta-sketcht-digeststring-searchsuffix-arraysuffix-automatondiffropeperfect-hash
Apache-2.0
Updated 9 hours ago
102 downloads