Racket

LRU Cache (Least Recently Used) for Racket🔗ℹ

An in-memory LRU cache with optional item expiration. The cache keeps items in recency order and evicts the least recently used item when the maximum capacity is reached. Optionally, items can expire after a given number of seconds.

1 Overview🔗ℹ

This module provides:

make-lru to construct a cache with a max-count, an optional equality/compare function for items, and optional expiration (seconds).
Mutation operations: lru-add!, lru-clear, set-lru-max-count!, set-lru-expire!.
Query operations: lru-has?, lru-count, lru->list, lru-expires?, lru-expire, lru-max-count, lru?.

The cache stores items (values) and uses a comparison function to decide whether an item is already present. Each item is associated with a last-access timestamp that drives recency; on insert or hit, the item is bubbled to the front.

Thread-safety: The implementation is thread-safe, but not reentrant.

2 Data Types🔗ℹ

struct
(struct lru* (cache compare max-count expire-in-seconds))
  cache : box?
  compare : procedure?
  max-count : (and/c integer? (>/c 0))
  expire-in-seconds : (or/c #f (and/c integer? (>/c 0)))

Internal representation of the LRU cache. Use lru? to test for this type; do not rely on fields directly. Create instances with make-lru.

procedure
(lru? v) → boolean?
v : any/c

Predicate that returns #t when v is an LRU instance.

3 Construction🔗ℹ

procedure
(make-lru max-count
[ #:cmp compare
#:expire expire-in-seconds]) → lru?
  max-count : (and/c integer? (>/c 0))
  compare : (-> any/c any/c boolean?) = equal?
  expire-in-seconds : (or/c #f (and/c integer? (>/c 0))) = #f

Create a new LRU cache.

max-count — Maximum number of items kept in the cache. When the limit is exceeded, the least recently used item is evicted.
#:cmp compare — Binary comparison function that returns #t when two items are considered equal (default: equal?).
#:expire expire-in-seconds — If a positive integer: items expire automatically after that many seconds of inactivity. #f disables expiration (default).

Returns A new empty LRU cache with the given parameters.

4 Core Operations🔗ℹ

procedure
(lru-add! l item) → lru?
l : lru?
item : any/c

Insert item. If it already exists (per compare), it is considered a hit: moved to the front and its access time is refreshed. If capacity is reached, the least recently used item is removed. Returns l.

procedure
(lru-has? l item) → boolean?
l : lru?
item : any/c

Returns #t if item is currently present (and not expired), otherwise #f. This call also performs lazy cleanup of expired items.

procedure
(lru-clear l) → lru?
l : lru?

Clear all items from the cache. Returns l.

procedure
(lru-count l) → (and/c integer? (>=/c 0))
l : lru?

Return the number of non-expired items currently in the cache.

procedure
(lru-empty? l) → boolean?
l : lru?

Return #t if the number of non-expired items currently in the cache equals 0.

procedure
(lru->list l [#:with-expire with-expire?]) → list?
l : lru?
with-expire? : boolean? = #f

Return the cache contents in recency order (most recent first). When with-expire? is #f (default), returns just the list of items. When with-expire? is #t, returns (list item age-in-seconds) pairs, where age-in-seconds is the elapsed time since last access/insert.

5 Parameters and Configuration🔗ℹ

procedure
(lru-max-count l) → (and/c integer? (>/c 0))
l : lru?

Read the maximum capacity.

procedure
(set-lru-max-count! l n) → lru?
l : lru?
n : (and/c integer? (>/c 0))

Set the maximum capacity. If the current size exceeds n, trimming will occur on subsequent mutations or cleanups, depending on usage. Returns l.

procedure
(lru-expire l) → (or/c #f (and/c integer? (>/c 0)))
l : lru?

Read the expiration period in seconds, or #f if expiration is disabled.

procedure
(set-lru-expire! l expire) → lru?
l : lru?
expire : (or/c #f (and/c integer? (>/c 0)))

Set the expiration period (seconds) or disable it with #f. Returns l.

procedure
(lru-expires? l) → boolean?
l : lru?

Return #t when expiration is enabled (i.e., (lru-expire l) is a positive integer), otherwise #f.

6 Examples🔗ℹ

(require racket/base)

(require lru-cache)

(define L (make-lru 3))        ; max 3 items, no expiration
(lru-add! L 'a)
(lru-add! L 'b)
(lru-add! L 'c)
(lru->list L)                  ; '(c b a)

(lru-add! L 'b)                ; hit: bubble to front
(lru->list L)                  ; '(b c a)

(lru-add! L 'd)                ; capacity 3 -> evicts LRU ('a)
(lru->list L)                  ; '(d b c)
(lru-count L)                  ; 3

(lru-has? L 'c)                ; #t
(lru-has? L 'a)                ; #f

(set-lru-expire! L 1)          ; items expire after 1 second
(sleep 2)
(lru-has? L 'b)                ; #f (expired)
(lru->list L)                  ; '()

(lru-add! L 'x)
(lru->list L #:with-expire #t) ; '((x 0)) – age ~ 0 sec

(set-lru-max-count! L 1)
(lru-add! L 'y)
(lru->list L)                  ; '(y)
(lru-clear L)
(lru->list L)                  ; '()

7 Behavior Details🔗ℹ

7.1 Recency and Hits🔗ℹ

Any insertion or hit refreshes the access time and moves the item to the front. When capacity is reached, the least recently used item is evicted.

7.2 Expiration🔗ℹ

If lru-expire is a positive integer, items become expired when their last access is older than that threshold. Cleanup is performed lazily on calls such as lru-has?, lru-count, and lru->list.

7.3 Comparison Function🔗ℹ

The #:cmp function decides item equality (e.g., equal?, = for numbers, or a custom predicate). For predictable behavior, it should be symmetric and transitive.

8 Errors and Contracts🔗ℹ

Contracts enforce:

max-count, lru-max-count, and set-lru-max-count! use positive integers.
#:expire and set-lru-expire! accept #f or positive integers.
#:cmp is a two-argument function returning a boolean?.

Invalid inputs raise contract violations with descriptive error messages.

9 Notes🔗ℹ

The implementation is thread-safe but not reentrant.
Expiration cleanup is lazy. If you need stricter guarantees, trigger periodic queries (e.g., lru-count) or add an explicit cleanup function.

1	Overview
2	Data Types
3	Construction
4	Core Operations
5	Parameters and Configuration
6	Examples
7	Behavior Details
8	Errors and Contracts
9	Notes