UXCache

UXCache is keyed storage that cannot grow without bound. Set a capacity, and when a write would exceed it the least-recently-used entry is evicted.

#use <UXKit>            // or #import "UXCache.xc"

Overview

UXCache* c = new UXCache();
c.setCapacity(3);

c.set((u8*)"a", (Object*)thumbA);
c.set((u8*)"b", (Object*)thumbB);
c.set((u8*)"c", (Object*)thumbC);

c.get((u8*)"a");                  // hit — and now "a" is the most recent
c.set((u8*)"d", (Object*)thumbD); // over capacity: "b" is evicted

Thumbnail, decoded-image and parsed-resource caches use it to stay bounded. It is a pure data structure with no platform code, so it is testable.

The default capacity is 16.

What counts as a use

Every get and every set marks its entry most-recently-used by stamping it with a monotonic counter. The victim is always the entry with the oldest stamp.

c.get((u8*)"a");      // "a" is now newest; something else becomes the victim

contains does not mark recency:

Keys

Keys are strings, compared by content, so a key built at run time matches a literal. You need this when the key is a filename or a URL.

Setting an existing key updates in place: the value is replaced and the entry is re-stamped, and no second entry appears. Repeated writes to one key do not consume capacity.

A miss is null

Object* v = c.get((u8*)"gone");     // 0

As a result there is no way to cache a null value: storing 0 is indistinguishable from not having the key. To remember that a lookup found nothing, cache a marker object instead of null. UXNull exists for this.

Cost, and what it is sized for

Lookup is a linear scan, and each eviction is another scan to find the oldest entry. There is no hash and no linked list.

For a capacity in the tens, typical of a thumbnail cache, this is faster than the alternatives and much simpler. It is the wrong shape for thousands of entries: the scan dominates, and a hash plus an intrusive LRU list would suit better.

setCapacity clamps to a minimum of 1, so a cache cannot discard everything. Shrinking the capacity evicts immediately.

Topics

setCapacity · set · get · contains · remove · removeAll · count · find · evictToFit

setCapacity

void setCapacity(i32 n)

The maximum number of entries. Clamped to at least 1, and evicts down to fit immediately.

set

void set(u8* key, Object* value)

Store, replacing an existing key in place. Marks most-recently-used, then evicts if over capacity. See the caution about the key pointer.

get

Object* get(u8* key)

Fetch, or 0. Marks most-recently-used on a hit.

contains

bool contains(u8* key)

Presence only. Does not mark recency. See above.

remove

void remove(u8* key)

Drop one entry. A no-op if it is not there.

removeAll

void removeAll(void)

Empty the cache. The cache holds values strongly, so this releases them.

count

i32 count(void)

Entries currently held. Never more than the capacity.

find

UXCacheEntry* find(u8* key)

The UXCacheEntry, or null, without marking recency. The other methods are built on this lookup.

evictToFit

void evictToFit(void)

Evict least-recently-used entries until within capacity. set and setCapacity call it for you.

Example

cache count=3 a=1 b=0 c=1 d=1
after peek+set: c=0 e=1
miss=0
re-set same key: 3 -> 3 value=E2
after setCapacity(1): count=1

Capacity 3, keys a b c inserted in order. Getting a made it newest, so adding d evicted b. a was oldest by insertion but not by use. Then contains("c") did not save c, and e pushed it out. Re-setting e changed its value without changing the count.

The program is website/site/examples/uxkit/collections.xc. The doc-examples gate compiles it, and the listing above is its output.

Conforms to

A plain class (not an Object subclass)