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.
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)) '())
lru-cache-size[procedure] (lru-cache-size cache)
Returns the number of items currently in the cache.
lru-cache-capacity[procedure] (lru-cache-capacity cache)
Returns the capacity of the cache in items.
(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)
- 0.5 (2009-03-23): Initial release
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.