Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

lru-cache implements an LRU cache of N elements. It uses a hash table for fast lookup and a doubly-linked list to maintain LRU ordering. As the hash table associates keys with list nodes, items may be reordered without traversing the list.

Outdated egg!
lru-cache

Interface

make-lru-cache

[procedure] (make-lru-cache capacity equal? [deleter])

Create an LRU cache capable of holding capacity items. equal? is the item equality procedure and is passed directly to the hash table, as in (make-hash-table equal?). deleter is an optional procedure of two arguments (key value) which will be invoked whenever an item is deleted, flushed or simply falls off the cache.

If capacity is zero, the cache is disabled. Attempts to read items will return #f, and writing them will silently fail.

lru-cache-ref

[procedure] (lru-cache-ref cache key)

Looks up the item matching key and returns the associated value, or #f if no such item exists.

If the item is not the most-recently used, it is marked as MRU (in other words, moved to the head of the list).

If the item is the most-recently used, the LRU list structure is not modified, and consequently the item is returned a bit faster.

lru-cache-set!

[procedure] (lru-cache-set! cache key val)

Add an item into the cache which associates key with val, or if an item matching key already exists, updates the item to the new val. If the key did not exist, the item is marked as the most-recently used. If the key did exist, the LRU ordering behavior is undefined; currently -- and don't take this for granted -- the LRU order is not updated.

If adding this item causes the cache to exceed its capacity, the least-recently used item is deleted, and consequently the deleter (if provided) is invoked. If the deleter throws an exception, the item remains in the cache, and the new item is not added.

lru-cache-delete!

[procedure] (lru-cache-delete! cache key)

Deletes the item matching key from cache. If no corresponding item exists, the procedure silently fails. The deleter, if provided, will be invoked for this item.

Note: if the deleter throws an exception, the item is not deleted from the cache.

lru-cache-flush!

[procedure] (lru-cache-flush! cache)

Delete all items in cache. The deleter procedure (if provided to make-lru-cache) is invoked for each item as the item list is traversed from head to tail. If an error occurs in the deleter, the offending item will be left at the head of the cache.

lru-cache-walk

[procedure] (lru-cache-walk cache proc)

Call (proc key value) for each item in the cache, returning an unspecified value. Items are traversed from MRU to LRU.

lru-cache-fold

[procedure] (lru-cache-fold cache kons knil)

Iterate over the items in the cache in order from MRU to LRU. kons is called with three arguments: k, the item's key; v, the item's value; and s, the current state. The initial state is set to knil, and the return value from the call to kons is passed as the next state value to kons.

For example, to build a list of (key . value) pairs in cache from LRU to MRU, execute:

(lru-cache-fold cache (lambda (k v s) (cons (cons k v) s)) '())

(use lru-cache)
(define C (make-lru-cache 4 string=?
                          (lambda (k v) (printf "deleting (~S ~S)\n" k v))))
(lru-cache-set! C "a" 1) ; a
(lru-cache-set! C "b" 2) ; b a
(lru-cache-set! C "c" 3) ; c b a
(lru-cache-set! C "d" 4) ; d c b a
(lru-cache-walk C print)
;; d4
;; c3
;; b2
;; a1
(lru-cache-set! C "e" 5) ; e d c b
;; deleting (a 1)
(lru-cache-ref C "b")    ; 2, b e d c
(lru-cache-ref C "d")    ; 4, d b e c
(lru-cache-walk C print)
;; d4
;; b2
;; e5
;; c3
(lru-cache-delete! C "e") ; d b c
;; deleting ("e" 5)
(lru-cache-set! C "a" 6) ; a d b c
(lru-cache-flush! C)
;; deleting ("a" 6)
;; deleting ("d" 4)
;; deleting ("b" 2)
;; deleting ("c" 3)
(lru-cache-walk C print)

Author

Jim Ursetto

Version history

0.5 (2009-03-23): Initial release

License

Copyright (c) 2009 Jim Ursetto.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

 Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer.
 Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
 Neither the name of the author nor the names of its contributors 
  may be used to endorse or promote products derived from this software 
  without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.