The lru-cache Reference Manual

This is the lru-cache Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Sep 15 05:58:20 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 lru-cache

A least-recently-used cache structure

Maintainer

Yukari Hafner <>

Author

Yukari Hafner <>

Home Page

https://shinmera.github.io/lru-cache/

Source Control

(GIT https://github.com/shinmera/lru-cache.git)

Bug Tracker

https://github.com/shinmera/lru-cache/issues

License

zlib

Version

1.0.0

Dependency

documentation-utils (system).

Source

lru-cache.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 lru-cache/lru-cache.asd

Source

lru-cache.asd.

Parent Component

lru-cache (system).

ASDF Systems

lru-cache.


3.1.2 lru-cache/lru-cache.lisp

Source

lru-cache.asd.

Parent Component

lru-cache (system).

Packages

org.shirakumo.lru-cache.

Public Interface
Internals

3.1.3 lru-cache/documentation.lisp

Dependency

lru-cache.lisp (file).

Source

lru-cache.asd.

Parent Component

lru-cache (system).


4 Packages

Packages are listed by definition order.


4.1 org.shirakumo.lru-cache

Source

lru-cache.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Macros

Macro: do-lru-cache ((element id cache &optional result) &body body)

Convenience macro to iterate over the cached elements in order from most recent to least recent.

An implicit NIL block is bound around BODY.
If BODY does not explicitly return, RESULT is evaluated and returned instead.

See LRU-CACHE
See MAP-LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.


5.1.2 Ordinary functions

Function: lru-cache-clear (cache)

Evicts all elements in the cache and clears it.

This operation is O(n).

See LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-count (cache)

Counts the number of elements currently in the cache.

This operation is O(n).

See LRU-CACHE
See LRU-CACHE-SIZE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-evict (cache)

Evicts the least recently used element from the cache.

Returns the element and the ID of the evicted node, if any.

This operation is O(n).

See LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-id (value cache)

Returns the ID of the node the element is in.

If the element is not in the cache, NIL is returned.

This operation is O(1).

See LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-list (cache)

Returns a list of the elements in the cache in order of most recent to least recent.

See LRU-CACHE
See MAP-LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-pop (value cache)

Pops an element out of the cache.

If the element exists in the cache, the ID of the node is returned. If the element did not exist in the cache, NIL is returned.

This operation is O(1).

See LRU-CACHE
See LRU-CACHE-PUSH

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-push (value cache)

Pushes an element to the cache.

The element is put into the cache as the most recently used. If the element did not exist before and the cache is already full, the least recently used element is evicted.

Returns the ID of the node the element was put into, if it was not already in the cache. If the element was already in the cache, NIL is returned.

This operation is O(1).

See LRU-CACHE
See LRU-CACHE-POP

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: lru-cache-resize (cache size)

Change the size of the cache.

When decreasing the cache size, elements are *not* evicted according to LRU order, and instead elements with the largest assigned ID are evicted in order. This is required to ensure that the IDs remain consecutive and consistent across multiple shrinkages and growths.

If preserving LRU order is more important than preserving node IDs when shrinking, you should first coerce the cache to a sequence, then resize and reinsert in reverse order.

This operation is O(n) for increasing the size and O(n^2) for decreasing the size.

See LRU-CACHE
See LRU-CACHE-SIZE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Reader: lru-cache-size (instance)

Returns the size of the cache.

This operation is O(1).

See LRU-CACHE
See LRU-CACHE-RESIZE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

size.

Writer: (setf lru-cache-size) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

size.

Function: make-lru-cache (size &optional test)

Create a new LRU-CACHE instance that can hold SIZE elements.

The TEST may be one of the arguments acceptable as the TEST of a hash-table.

See CL:HASH-TABLE-TEST
See LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: map-lru-cache (function cache)

Iterates over the cached elements in order from most recent to least recent.

Calls FUNCTION with two values: the element and the ID of the node the element occupies. Note that the ID does *not* necessarily correspond
to the index of the node in the cache sequence.

Returns the CACHE instance.

See LRU-CACHE
See DO-LRU-CACHE

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.


5.1.3 Standalone methods

Method: describe-object ((cache lru-cache) stream)
Source

lru-cache.lisp.

Method: print-object ((cache lru-cache) stream)
Source

lru-cache.lisp.

Method: print-object ((node lru-cache-node) stream)
Source

lru-cache.lisp.


5.1.4 Structures

Structure: lru-cache

A least-recently-used cache datastructure.

See MAKE-LRU-CACHE
See LRU-CACHE-RESIZE
See LRU-CACHE-SIZE
See LRU-CACHE-PUSH
See LRU-CACHE-POP
See LRU-CACHE-ID
See LRU-CACHE-EVICT
See LRU-CACHE-CLEAR
See LRU-CACHE-COUNT
See MAP-LRU-CACHE
See DO-LRU-CACHE
See LRU-CACHE-LIST

Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: head
Type

org.shirakumo.lru-cache::lru-cache-node

Readers

lru-cache-head.

Writers

(setf lru-cache-head).

Slot: table
Type

hash-table

Readers

lru-cache-table.

Writers

(setf lru-cache-table).

Slot: size
Type

(unsigned-byte 32)

Initform

0

Readers

lru-cache-size.

Writers

(setf lru-cache-size).


5.2 Internals


5.2.1 Ordinary functions

Function: %make-lru-cache (head table size)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Function: check-lru-cache (cache &optional op)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Reader: lru-cache-head (instance)
Writer: (setf lru-cache-head) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

head.

Reader: lru-cache-node-id (instance)
Writer: (setf lru-cache-node-id) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

id.

Reader: lru-cache-node-left (instance)
Writer: (setf lru-cache-node-left) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

left.

Reader: lru-cache-node-right (instance)
Writer: (setf lru-cache-node-right) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

right.

Reader: lru-cache-node-value (instance)
Writer: (setf lru-cache-node-value) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

value.

Reader: lru-cache-table (instance)
Writer: (setf lru-cache-table) (instance)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Target Slot

table.

Function: make-lru-cache-node (left right id)
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.


5.2.2 Structures

Structure: lru-cache-node
Package

org.shirakumo.lru-cache.

Source

lru-cache.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: left
Readers

lru-cache-node-left.

Writers

(setf lru-cache-node-left).

Slot: right
Readers

lru-cache-node-right.

Writers

(setf lru-cache-node-right).

Slot: value
Readers

lru-cache-node-value.

Writers

(setf lru-cache-node-value).

Slot: id
Type

(unsigned-byte 32)

Initform

0

Readers

lru-cache-node-id.

Writers

(setf lru-cache-node-id).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   D   F   L   M   P  
Index Entry  Section

%
%make-lru-cache: Private ordinary functions

(
(setf lru-cache-head): Private ordinary functions
(setf lru-cache-node-id): Private ordinary functions
(setf lru-cache-node-left): Private ordinary functions
(setf lru-cache-node-right): Private ordinary functions
(setf lru-cache-node-value): Private ordinary functions
(setf lru-cache-size): Public ordinary functions
(setf lru-cache-table): Private ordinary functions

C
check-lru-cache: Private ordinary functions

D
describe-object: Public standalone methods
do-lru-cache: Public macros

F
Function, %make-lru-cache: Private ordinary functions
Function, (setf lru-cache-head): Private ordinary functions
Function, (setf lru-cache-node-id): Private ordinary functions
Function, (setf lru-cache-node-left): Private ordinary functions
Function, (setf lru-cache-node-right): Private ordinary functions
Function, (setf lru-cache-node-value): Private ordinary functions
Function, (setf lru-cache-size): Public ordinary functions
Function, (setf lru-cache-table): Private ordinary functions
Function, check-lru-cache: Private ordinary functions
Function, lru-cache-clear: Public ordinary functions
Function, lru-cache-count: Public ordinary functions
Function, lru-cache-evict: Public ordinary functions
Function, lru-cache-head: Private ordinary functions
Function, lru-cache-id: Public ordinary functions
Function, lru-cache-list: Public ordinary functions
Function, lru-cache-node-id: Private ordinary functions
Function, lru-cache-node-left: Private ordinary functions
Function, lru-cache-node-right: Private ordinary functions
Function, lru-cache-node-value: Private ordinary functions
Function, lru-cache-pop: Public ordinary functions
Function, lru-cache-push: Public ordinary functions
Function, lru-cache-resize: Public ordinary functions
Function, lru-cache-size: Public ordinary functions
Function, lru-cache-table: Private ordinary functions
Function, make-lru-cache: Public ordinary functions
Function, make-lru-cache-node: Private ordinary functions
Function, map-lru-cache: Public ordinary functions

L
lru-cache-clear: Public ordinary functions
lru-cache-count: Public ordinary functions
lru-cache-evict: Public ordinary functions
lru-cache-head: Private ordinary functions
lru-cache-id: Public ordinary functions
lru-cache-list: Public ordinary functions
lru-cache-node-id: Private ordinary functions
lru-cache-node-left: Private ordinary functions
lru-cache-node-right: Private ordinary functions
lru-cache-node-value: Private ordinary functions
lru-cache-pop: Public ordinary functions
lru-cache-push: Public ordinary functions
lru-cache-resize: Public ordinary functions
lru-cache-size: Public ordinary functions
lru-cache-table: Private ordinary functions

M
Macro, do-lru-cache: Public macros
make-lru-cache: Public ordinary functions
make-lru-cache-node: Private ordinary functions
map-lru-cache: Public ordinary functions
Method, describe-object: Public standalone methods
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods

P
print-object: Public standalone methods
print-object: Public standalone methods